记忆化：连接参数或执行 md5 哈希？

Question

我正在为几个函数添加记忆。这些函数采用 2-3 个字符串参数（对象名称）、一个可选的 int 参数（记录 ID）和一个布尔参数（包括已删除的记录）。每个参数组合都保证运行产生唯一的结果（因此值得缓存）。

我想知道连接给定参数（$param1 . $param2 . $param3 等）并将其用作数组键是否会更快，或者采用相同的连接字符串并使用 md5 哈希作为键。在 99% 的情况下（平均约为 27），串联参数字符串的长度在 20-32 个字符之间，而 md5 哈希始终为 32 个字符。
编辑：md5 哈希只有 16 个字节，而不是 32 个字节。谢谢 Mjh。

我倾向于第一个选项，因为它：

为我节省了执行 md5 散列的成本
它通常会节省几个字节的内存（平均 27 对 32 散列）（Mjh 指出这不是真的：md5 只有 16 字节），并且
由于 md5 哈希只是另一个字符串，因此比较较短的字符串通常会更快

我怀疑这一点的唯一原因是绝大多数记忆函数似乎使用 (md5) 哈希，所以我想知道我是否遗漏了什么。

提前致谢。

P.S. 我忘了说：我用 # 字符分隔各个参数，它永远不会自然出现在任何参数中.

P.P.S. 到目前为止，ankhzet 的评论似乎是最好的解决方案，因为我的字符串实际上是独一无二的：crc32($paramString)。内存占用小，校验和计算速度非常快。

测试 crc32() 性能

下面是一个测试脚本，它填充了 4 个数组，每个数组有 100 万 key => value 对。所有 4 个数组的 values 是相同的。 keys 也是相同的，除了对于前 2 个数组，连接的字符串键首先在它们上面有 crc32() 运行。

$test1Array = [];
$start1 = microtime(true);
for ($i = 0; $i < 1000000; $i++)
{
    $test1Array[crc32("pagemanagement" . "#" . "staticblocktype" . "#" . $i . "#" . 1)] = "test " . $i;
}
$end1 = microtime(true);

$test2Array = [];
$start2 = microtime(true);
for ($j = 0; $j < 1000000; $j++)
{
    $test2Array[crc32("pagemanagement" . "#" . "staticblocktype" . "#" . $i . "#" . 1)] = "test " . $j;
}
$end2 = microtime(true);

$test3Array = [];
$start3 = microtime(true);
for ($x = 0; $x < 1000000; $x++)
{
    $test3Array["pagemanagement" . "#" . "staticblocktype" . "#" . $i . "#" . 1] = "test " . $x;
}
$end3 = microtime(true);

$test4Array = [];
$start4 = microtime(true);
for ($y = 0; $y < 1000000; $y++)
{
    $test4Array["pagemanagement" . "#" . "staticblocktype" . "#" . $i . "#" . 1] = "test " . $y;
}
$end4 = microtime(true);

3 次测试的结果运行s:
测试 1：3.9902291297913
测试 2：3.6312079429626
测试 3：0.91605305671692
测试 4：0.91405177116394

测试 1：3.9842278957367
测试 2：3.6172070503235
测试 3：0.91405200958252
测试 4：0.918053150177

测试 1：3.9842278957367
测试 2：3.6282079219818
测试 3：0.91205215454102
测试 4：0.91605186462402

如果我取所有 "Test 2" 和 "Test 4" 值的平均值（因为 "Test 1" 似乎有初始化开销），我剩下 3.6255409717560 用于 "Test 2" 和"Test 4" 的 0.9160522619883。这是 2.7094887097677 的差异，并且 (2.7094887097677 / 1000000) = 0.0000027094887 或每个函数调用 2.72 微秒。

不幸的是，我目前无法轻松计算内存使用量，但存储 4 字节 crc32() 值是 gua运行teed 比平均 27 个字符长度的字符串占用更少的内存.假设最好的情况是 1 字节字符，即每个缓存结果相差 23 字节。

为了完整性，我运行也对 md5() 进行了快速测试：
测试 1：4.2855787277221
测试 2：3.8108838399251
md5() 和 crc32() 之间的性能差异如此之小，这让我感到非常惊讶。当然crc32()还是有优势的，只用了4个字节到md5()的16.

结论：由于我的函数的主要开销是重复的数据库调用，并且由于这些函数在每个请求中被调用大约 50-200 次，所以我个人认为增加的 ~135-540 微秒的计算时间值得节省 ~1150-4600 字节的内存。

如果有人不同意我的测试 and/or 结论，我很想知道。

Answer 1

将其存储在数组中时：

$cache[$paramString] = $value;  // or
$cache[crc32($paramString)] = $value;

PHP 将从存储为无符号长整数的密钥创建哈希。它还将存储实际的 $paramString 以及所需的其他数据。所以，我没有看到你真的从执行 crc32() 或 md5() 中获得任何好处，特别是因为 $paramString 通常不会那么大。

这个页面有很多细节：https://nikic.github.io/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

Answer 2

仅当对象的 toString 方法不隐藏任何影响函数行为的特征，并且该函数不实例化依赖于任何隐藏特征的任何东西时，连接值才有效。但是由于我们讨论的是面向对象，我们不能确定连接字符串的大小是否可以预测。

因此，仅出于这个原因，您就应该使用散列。

您可以考虑使用 sha1()，尽管它比 md5() 更复杂，但实际上运行速度更快（至少我上次检查时是这样）。

但这对我来说像是过早的优化。

Answer 3

这是我在 AMD 2x2.3 GHz 机器上使用 PHP7:

对 md5-crc32-sha1-native 散列的简单性能测试

function probe($label, $times, $callback) {
    $mem = memory_get_usage();
    $start = microtime(true);
    $array = $callback($times);
    $time = microtime(true) - $start;
    $mem = sprintf('%.3f', (memory_get_usage() - $mem) / 1024 / 1024);
    return "$label:  $time s, $mem MB";
}

$times = 1000000;

$run1 = probe('String key', $times, function ($times) {
    $a = [];
    while ($times-- > 0) {
        $a["pagemanagement" . "#" . "staticblocktype" . "#" . $times . "#" . 1] = "test " . $times;
    }
    return $a;
});

$run2 = probe('CRC32 key', $times, function ($times) {
    $a = [];
    while ($times-- > 0) {
        $a[crc32("pagemanagement" . "#" . "staticblocktype" . "#" . $times . "#" . 1)] = "test " . $times;
    }
    return $a;
});

$run3 = probe('MD5 key', $times, function ($times) {
    $a = [];
    while ($times-- > 0) {
        $a[md5("pagemanagement" . "#" . "staticblocktype" . "#" . $times . "#" . 1)] = "test " . $times;
    }
    return $a;
});

$run4 = probe('SHA1 key', $times, function ($times) {
    $a = [];
    while ($times-- > 0) {
        $a[sha1("pagemanagement" . "#" . "staticblocktype" . "#" . $times . "#" . 1)] = "test " . $times;
    }
    return $a;
});

echo join("<br/>\n", [
    $run1,
    $run2,
    $run3,
    $run4,
    ]);

String key: 1.2421879768372 s, 111.923 MB
CRC32 key: 1.3447260856628 s, 58.517 MB
MD5 key: 2.1748039722443 s, 111.923 MB
SHA1 key: 2.2480459213257 s, 119.552 MB

看起来 MD5 比 crc32 稍微有点 slover，而 crc32 显然有更少的内存开销。

Here 您可以找到 PHP5.5+-PHP7 和 hhvm 版本的相同测试（但迭代次数减少了 10 次，因为测试过程的服务器内存限制为 64MB）。

编辑：添加了粗略的内存分配测试（演示 link 也已更新）。看起来 crc32 在提议的测试集上占用的内存大约减少了 1.5-2 倍。

编辑：添加了 sha1 测试。看起来比 md5 更慢更 havier。

注意：洗牌测试顺序不会改变任何内容，因此，没有 warm-up/memory 分配会严重影响结果。

记忆化：连接参数或执行 md5 哈希？

Memoization: concatenating params or performing md5 hash?

php

memoization

测试 crc32() 性能