Мемоизация: объединение параметров или выполнение хэша md5?

Я добавляю запоминание к нескольким функциям. Эти функции принимают 2-3 строковых параметра (имена объектов), необязательный параметр int (идентификатор записи) и логический параметр (включая удаленные записи). Каждая комбинация параметров гарантированно дает уникальный результат (поэтому стоит кэшировать).

Мне интересно, будет ли быстрее объединить заданные параметры ($param1 . $param2 . $param3 и т. д.) и использовать их в качестве ключа массива или взять ту же объединенную строку и использовать хэш md5 в качестве ключа. Длина объединенной строки параметра составляет от 20 до 32 символов в 99% случаев (в среднем около 27), тогда как хэш md5 всегда составляет 32 символа.
Изменить: md5 хэш всего 16 байт, а не 32. Спасибо, Mjh.

Я склоняюсь к первому варианту, так как он:

  • экономит мне стоимость выполнения хэша md5
  • обычно это экономит несколько байтов памяти (27 в среднем против 32 хешированных) (Mjh указал, что это неправда: md5 занимает всего 16 байт), и
  • поскольку хэш md5 — это просто еще одна строка, обычно быстрее сравнивать более короткую строку.

Единственная причина, по которой я сомневаюсь в этом, заключается в том, что подавляющее большинство функций запоминания, похоже, используют хэши (md5), поэтому мне интересно, не упустил ли я что-то.

Заранее спасибо.

P.S. Забыл упомянуть: я разделяю отдельные параметры символом #, который естественным образом не встречается ни в одном из параметров.

P.P.S. На данный момент комментарий ankhzet кажется лучшим решением, учитывая, что мои строки изначально практически уникальны: crc32($paramString). Небольшой объем памяти и очень быстрая функция вычисления контрольной суммы.


Тестирование производительности crc32()

Ниже приведен тестовый скрипт, который заполняет 4 массива по 1 миллиону key => value пар в каждом. values всех 4 массивов идентичны. keys также идентичны, за исключением того, что для первых двух массивов конкатенированные строковые ключи сначала обрабатываются 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 тестов:
Тест 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

Если я возьму среднее значение всех значений «Тест 2» и «Тест 4» (поскольку «Тест 1», похоже, имеет накладные расходы на инициализацию), у меня останется 3,6255409717560 для «Теста 2» и 0,9160522619883 для «Теста 4». Это разница в 2,7094887097677 и (2,7094887097677/1000000) = 0,0000027094887 или 2,72 микросекунды на вызов функции.

К сожалению, в данный момент я не могу легко рассчитать использование памяти, но сохранение 4-байтового значения crc32() гарантированно займет значительно меньше памяти, чем средняя длина строки в 27 символов. Предполагая, что в лучшем случае 1 байт символов, это разница в 23 байта на кешированный результат.


Для полноты картины я также провел быстрый тест с md5():
Тест 1: 4.2855787277221
Тест 2: 3.8108838399251
Я действительно удивлен тем, насколько мала разница в производительности между md5() и crc32(). Конечно, crc32() по-прежнему имеет то преимущество, что использует всего 4 байта вместо 16 у md5().


Вывод: поскольку основные накладные расходы моих функций связаны с повторными вызовами базы данных, и поскольку эти функции вызываются порядка 50-200 раз за запрос, я лично считаю, что ~135-540 микросекунд дополнительного вычислительного времени стоит сэкономить ~1150-4600 байт памяти.

Если кто-то не согласен с моими тестами и/или выводами, я хотел бы знать.


person Byson    schedule 17.03.2016    source источник
comment
Гарантированно ли при любом подходе избежать коллизий?   -  person summea    schedule 17.03.2016
comment
@summea Ну, вероятность столкновения хэшей md5 с самого начала очень мала. С моей конкатенированной строкой параметров коллизии практически невозможны, поскольку каждая комбинация параметров относится либо к определенному типу объекта в моей системе, либо к определенной записи этого типа объекта.   -  person Byson    schedule 17.03.2016
comment
Подразумевается, что столкновение практически гарантированно будет кэшированным результатом, который я ищу для начала.   -  person Byson    schedule 17.03.2016
comment
md5 занимает 16 байт, а не 32. Он занимает 32, когда мы представляем хеш в виде строки, но в двоичном формате это меньше. Использование чего-то вроде $memoized_index = md5(json_encode(func_get_args()), true); не должно быть ни медленным, ни требовательным к памяти. По крайней мере, я бы так поступил.   -  person Mjh    schedule 17.03.2016
comment
Если вы беспокоитесь о производительности, почему бы не использовать простой встроенный crc? Это намного быстрее, чем md5, с уникальными и короткими исходными строками коллизии имеют тот же шанс, что и md5 (но это можно легко проверить), и требует только 32/64-битного целого числа в качестве ключа... В противном случае я бы также предпочел простой конкатенация...   -  person ankhzet    schedule 17.03.2016
comment
@ankhzet Хммм, crc32() действительно кажется хорошим и быстрым решением, торгующим крошечным приростом скорости (путем вычисления контрольной суммы) для значительно меньшего использования памяти (путем замены строки из 25-30 символов на 4-байтовый целое число).   -  person Byson    schedule 17.03.2016
comment
@Mjh Лично я бы никогда не использовал здесь json_encode(), а вручную объединил бы свои параметры (моя функция все равно не работает с переменным числом аргументов). json_encode() на мой вкус добавляет слишком много накладных расходов (стек вызовов функций, возвращающий гораздо больше строковых данных, чем требуется).   -  person Byson    schedule 17.03.2016
comment
Да, используемый в алгоритме расчета diff для больших текстов (100k+ строк), пару лет назад на php 5.+, был довольно эффективен. Просто не забудьте протестировать коллизии на данных производственного масштаба.   -  person ankhzet    schedule 17.03.2016
comment
@ankhzet Я добавил тесты и заключение к своему первоначальному вопросу. Возможно, вам это интересно. РЕДАКТИРОВАТЬ: также, если вы добавите свое первоначальное предложение в качестве ответа, я приму его, поскольку это решение, которое я действительно буду использовать.   -  person Byson    schedule 18.03.2016
comment
Ммм, протестировано с php 7 (2x2,3 ГГц, 1 ГБ свободной памяти), получил 1.3896489143372, 1.1757810115814, 0.99707007408142, 0.98535180091858. Похоже, что прямое использование хэша имеет ту же производительность, но вычисление crc32 примерно в 2-4 раза быстрее... Я попробую также с массивами целочисленных ключей через пару минут.   -  person ankhzet    schedule 18.03.2016
comment
@ankhzet Я использую PHP 5.5.8 на своей локальной машине 4x3,4 ГГц с чуть менее 2 ГБ свободной оперативной памяти. Я также только что добавил небольшой тест md5(). EDIT: когда я меняю приоритет процесса на высокий, я могу выжать из него ~ 3-4% дополнительной производительности.   -  person Byson    schedule 18.03.2016
comment
@Bison, так что, если вы принимаете массив в качестве параметра, как вы объединяете его для целей запоминания?   -  person Mjh    schedule 22.03.2016
comment
@Mjh Мне нужно подумать об этом. В настоящее время все функции, которые я реализую для кэширования, принимают некоторые простые строковые/целые/логические параметры, извлекают данные из базы данных и выполняют над ними некоторую логику. Особенно вызовы БД дороги и их можно избежать. Если бы функция принимала массив аргументов, я бы, вероятно, объединил их с помощью цикла (или обхода массива, в зависимости от того, что вы предпочитаете). С многомерным массивом снова будет другая история. В любом случае, я всегда проверяю, действительно ли кэширование на самом деле ускорило процесс. Я никогда не предполагаю, что это так.   -  person Byson    schedule 24.03.2016
comment
@Mjh И даже тогда вам придется сбалансировать время обработки и используемую память. Если данные, влияющие на результаты вызовов, меняются нечасто (или если вы можете аннулировать кеш всякий раз, когда это происходит), вы можете перейти от кеширования по запросу к кешированию сеанса или даже к совместно используемому кешу между пользователями ( подумайте о кэше памяти). Очевидно, что межпользовательский кеш будет работать только в том случае, если функция будет возвращать одни и те же результаты с одинаковыми параметрами, даже если они вызываются разными пользователями/сеансами.   -  person Byson    schedule 24.03.2016
comment
@Mjh Я только что понял, что вы имеете в виду мой комментарий о том, что вы не используете json_encode() ранее. И да, в этом сценарии может быть полезно использовать json_encode(), var_export() или любую другую функцию в этом роде.   -  person Byson    schedule 24.03.2016
comment
Вы сказали, что вызовы db дороги и их можно избежать. Как вы это сделали? Это неправда, как раз наоборот, особенно если вы обслуживаете php через php-fpm. Вы уверены, что не будете повторять работу базы данных дважды? Базы данных чрезвычайно эффективны с их кешем, я был свидетелем сотен сайтов, где разработчики пытались быть умными в отношении производительности и делали свои сайты медленнее.   -  person Mjh    schedule 24.03.2016
comment
@Mjh Сам процесс составления запроса, замены параметров и запроса к базе данных требует времени. Конечно, базы данных очень эффективны в том, что они делают, но простое взаимодействие с другой такой системой будет медленнее, чем получение желаемого результата прямо из (ОЗУ) памяти. Очевидно, что процесс создания кеша требует времени, поэтому функции, которые могут вызываться всего несколько раз с одними и теми же параметрами, скорее всего, не стоит кэшировать. По этой причине крайне важно всегда проверять фактическую выгоду/убыток реализации кэширования.   -  person Byson    schedule 24.03.2016
comment
К сожалению, я должен быть плохим парнем и снова заявить, что это неправда. Использование подготовленных операторов решает проблему лексических запросов. php-fpm сохраняет соединения с базой данных открытыми, а не открывает и закрывает их при каждом запросе. Для последующих запросов вообще не требуется рукопожатие. Чего вы добьетесь, так это удвоения использования оперативной памяти для сомнительного прироста производительности. Извлечение записи из базы данных не настолько медленное, чтобы вам нужно было запоминать и создавать всю систему кэширования, которая сама по себе влечет за собой накладные расходы, которые НАМНОГО больше, чем накладные расходы на лексирование базы данных.   -  person Mjh    schedule 24.03.2016
comment
Кроме того, вызов базы данных обычно не единственное, что делает моя функция. Например, в функции проверки разрешений она затем сравнивает полученные результаты с некоторыми другими данными, чтобы в конечном итоге прийти к логическому заключению true/false. Сохранение этого заключения позволяет пропустить 1-2 обращения к базе данных, а также всю логику между ними и оператором return. Добавление кэширования к некоторым функциям сделало их в 20-70 раз быстрее (профилировано с помощью XDebug).   -  person Byson    schedule 24.03.2016
comment
В конце концов, это ваша система и ваш код, я не буду навязывать вам свое мнение. Я не знаю вашего кода, и если вы говорите, что он увеличивает вашу производительность в 70 раз, то это здорово. Я сделал предложение, как создать оболочку для мемоизации (я бы передал объект/метод с параметрами в мемоайзер, который либо извлечет из кеша, либо выполнит данный метод с параметрами, следовательно, json_encode с func_get_args()).   -  person Mjh    schedule 24.03.2016
comment
Подготовленные запросы работают, только если вы выполняете один и тот же запрос много раз подряд. В моей ситуации одна и та же функция может быть вызвана с одними и теми же параметрами 50 раз в запросе, но всего 200 раз и в разных перепутанных порядках. Как я уже упоминал ранее, я никогда не предполагал просто ускорение. Я измерял, среди прочего, с помощью XDebug и заметил не только профилированные улучшения, но и реальное время загрузки страниц, которое сократилось с 5-7 секунд до 1-1,5 секунд.   -  person Byson    schedule 24.03.2016
comment
О, не беспокойтесь об этом. Мне нравится хорошая дискуссия, в которой оспариваются мои взгляды. Я буду защищать их и, может быть, буду придерживаться их, а может быть, пойму, что ошибался. В этом случае я кое-чему научился, что всегда является моей целью на Stackoverflow. Так что, пожалуйста, не стесняйтесь ругать меня за ошибки. :)   -  person Byson    schedule 24.03.2016
comment
У вас там сильно загружается страница, даже 1,5 секунды - это многовато. Думали ли вы об использовании фоновых исполнителей задач, которые создают эти страницы, а затем просто показывают предварительно обработанную/кешированную страницу? Если вы не возражаете, я спрошу, что делает PHP, что требует так много итераций и ресурсов?   -  person Mjh    schedule 25.03.2016
comment
@Mjh Да, я согласен, что это большая нагрузка, и ее нужно делать намного быстрее. К сожалению, я являюсь единственным программистом, ответственным за создание CMS, на которой работают этот и другие веб-сайты, и у меня есть очень время, которое я могу потратить на оптимизацию. Рассматриваемая страница предназначена для агентства недвижимости и загружает 50 свойств недвижимости, включая изображение и множество атрибутов и настраиваемых полей из разных таблиц. Есть одна важная оптимизация, которую я уже реализовал, но еще не разместил в реальном времени, а именно: в настоящее время извлекается больше полей, чем показано в списке (которое я исправил сейчас).   -  person Byson    schedule 25.03.2016
comment
@Mjh Кроме того, о бегунах фоновых задач: к сожалению (или, может быть, к счастью), я несу ответственность только за бэкэнд-системы. Другой коллега занимается внешним интерфейсом, и мой вклад/совет для этой стороны по большей части игнорируется. Поэтому я делаю все, что в моих силах, чтобы сделать свою часть как можно лучше и быстрее. ;)   -  person Byson    schedule 25.03.2016
comment
Хорошо, в таком случае - желаю вам удачи в борьбе с этим зверем, и я надеюсь, что эта оптимизация запоминания сделает свое дело :) хорошего дня!   -  person Mjh    schedule 25.03.2016
comment
@Mjh Спасибо, тебе тоже. И спасибо за хорошую дискуссию, мне понравилось. :)   -  person Byson    schedule 25.03.2016


Ответы (3)


Вот мой наивный тест производительности для md5-crc32-sha1-native хеширования на машине AMD 2x2,3 ГГц с PHP7:

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,
    ]);

Строковый ключ: 1,2421879768372 с, 111,923 МБ
Ключ CRC32: 1,3447260856628 с, 58,517 МБ
Ключ MD5: 2,1748039722443 с, 111,923 МБ
Ключ SHA1: 2,5 2480457921

Похоже, что MD5 немного хуже, чем crc32, в то время как crc32 явно требует меньше памяти.

Здесь вы можете найти тот же тест (но в 10 раз меньше итераций, так как ограничение памяти сервера для тестового процесса составляет 64 МБ) для PHP5. 5+-версии PHP7 и hhvm.


Изменить: добавлен примерный тест выделения памяти (демонстрационная ссылка также обновлена). Похоже, что crc32 занимает примерно в 1,5-2 раза меньше памяти на предлагаемом тестовом наборе.

Изменить: добавлен тест sha1. Выглядит еще медленнее и тяжелее, чем md5.

Примечание: порядок тестов в случайном порядке ничего не меняет, поэтому отсутствие прогрева/распределения памяти сильно влияет на результаты.

person ankhzet    schedule 18.03.2016
comment
Ваше последнее замечание интересно. Есть идеи, почему в моих тестах первый всегда занимал значительно больше времени, чем второй, даже если они были идентичными копипастами? (минус измененное имя переменной массива) И 3-я и 4-я, опять же идентичные копии, дали почти одинаковый результат. - person Byson; 18.03.2016
comment
Инициализация процесса и начальное выделение кучи требуют времени. В рабочей среде это будет обрабатываться кодом до заполнения кеша в памяти из-за обычного потока кода, поскольку большая часть циклов процессора в предлагаемом тесте занята генерацией/копированием/распределением ключей и процессом заполнения хэш-таблиц массива. С большей свободной кучей процессов, которая будет работать быстрее. - person ankhzet; 19.03.2016

Когда вы сохраняете это в массиве:

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

PHP собирается создать хэш из ключа, который он хранит как unsigned long. Он также будет хранить фактическую $paramString вместе с другими необходимыми данными. Итак, я не вижу, чтобы вы действительно что-то выиграли от выполнения crc32() или md5(), тем более что $paramString обычно не будет таким большим.

На этой странице много подробностей: https://nikic.github.io/2011/12/12/How-big-are-PHP-arrays-really-Hint-BIG.html

person Dave    schedule 17.03.2016
comment
Если вы используете целочисленные ключи crc, вы также можете использовать разреженный массив с целочисленными индексами (SplFixedArray) в качестве хранилища кеша в памяти, который требует меньше памяти/накладных расходов на ЦП и не использует хэши для сравнения строк, на самом деле... - person ankhzet; 17.03.2016
comment
SplFixedArray не является разреженным массивом из того, что я читал: основные различия между SplFixedArray и обычным массивом PHP заключаются в том, что SplFixedArray имеет фиксированную длину. - person Dave; 17.03.2016
comment
О, ошибся с sparse битом. Тем не менее, SplFixedArray является хэш-картой целочисленного ключа и, следовательно, является более производительным и эффективным с точки зрения использования памяти, чем простой array() для целей хранения в памяти (кэш) ключ-значение, когда используются crc-ed целочисленные ключи. И по-прежнему любой подход под вопросом без тестов производительности... - person ankhzet; 17.03.2016

Объединение значений будет работать только в том случае, если метод toString для объектов не скрывает никаких функций, влияющих на поведение функций, и функция не создает экземпляров, зависящих от каких-либо скрытых функций. Но поскольку мы говорим об объектной ориентации, мы не можем быть уверены, что размер объединенных строк будет предсказуемым.

Поэтому только по этой причине вы должны использовать хэш.

Вы можете подумать об использовании sha1(), который, несмотря на то, что он сложнее, чем md5(), на самом деле работает намного быстрее (по крайней мере, когда я последний раз проверял).

Но для меня это пахнет преждевременной оптимизацией.

person symcbean    schedule 17.03.2016
comment
OP означало объединение аргументов функции, а не параметров объекта результата ... В любом случае, если concatenation of parameters недостаточно для «уникальной» идентификации желаемого результата функции, то hash of concatenation of parameters также не будет. И хэш объекта результата не имеет ничего общего с кешированием, так как для сравнения хэшей для извлечения желаемого объекта вы будете вынуждены получить объект результата функции, чтобы получить его хеш, что противоречит цели использования кеша, не так ли?.. - person ankhzet; 17.03.2016
comment
Таким образом, он будет возвращать одно и то же значение/выполнять одно и то же действие независимо от переданных ему фактических значений? Это новый подход к программированию. - person symcbean; 18.03.2016
comment
он вернет то же значение - как именно вы пришли к такому выводу? Результатом функции является создание параметров функции, одни и те же параметры всегда генерируют один и тот же результат, такое поведение можно кэшировать. Если одни и те же параметры могут давать разные результаты (через недетерминированное внутреннее состояние объекта результата, как вы подразумеваете в своем ответе), то кеширование невозможно, независимо от того, хэширован ли ключ или нет. - person ankhzet; 18.03.2016
comment
@symcbean Вы неправильно поняли использование этих функций. Одним из примеров функции является получение object_id из таблицы базы данных objects. В этом случае функция принимает параметры $moduleName, $objectName и $enabledObjectsOnly. По самой архитектуре системы комбинация имени модуля и объекта уникальна. Таким образом, для одних и тех же параметров вывод всегда один и тот же. Википедия: A function can only be memoized if it is referentially transparent; that is, only if calling the function has exactly the same effect as replacing that function call with its return value - person Byson; 18.03.2016
comment
Кроме того, запоминание/кэширование результатов ДАЛЕКО от преждевременной оптимизации. Применив его к нескольким часто используемым функциям, мне удалось увеличить скорость загрузки страницы примерно на 50%. (Это система, управляемая базой данных, и вызовы базы данных относительно дороги.) - person Byson; 18.03.2016