Уменьшает ли использование памяти больше производительности?

Question

В частности, запоминание несколько снижает производительность? Линейное увеличение производительности?

У меня есть функция, которая вызывает сложную математическую функцию 200 000 000 раз. Без запоминания (сохранения значений / кеширования) это занимает 1м. Если я сохраню значения - около 5 000 000 уникальных записей - это все равно займет 30 секунд. Значения являются двойными, я использую свою собственную хеш-функцию, а размер хеш-таблицы составляет около 20 000 000 (чтобы сделать вычисление хеш-значений немного проще).

Но сложная математическая функция все еще запускается только 5 000 000 раз (я даже проверял счетчик). Почему он не работает примерно на 2,5% от скорости 5 000 000/200 000 000?

Раньше я не использовал большие структуры данных, а сейчас я использую двойной массив размером 20 000 000 только для пояснения. Я не знаю, будет ли это иметь значение.

Answer 1

Ответ на все вопросы о производительности - «сравните и узнайте». Всегда. Таким образом, ваши реальные результаты выполнения являются вашим ответом - эмпирически, вот как он себя ведет. Вы можете узнать почему , используя что-то вроде инструментов callgrind / cachegrind от valgrind.

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

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

Итак, хотя «использование большего количества памяти» не напрямую связано с уменьшением производительности (я имею в виду, что акт его использования делает, но я предполагаю, что вы не говорите о том, как это стоит того, чтобы выделять объекты здесь), когда у вас более широкий объем ОЗУ, в котором могут лежать нужные вам вещи, шансы получить попадание в кеш ниже, что может значительно снизить скорость выполнения вашего кода.

Мемоизация - это только выигрыш, когда выполнение вашей функции занимает нетривиальное время. Обычно это так, но это компромисс, и даже в идеальных условиях запоминание десяти вызовов функций до пяти никогда не даст вам теоретического ускорения на 50%.

Это нелогичное поведение («но Бореалид, я делаю больше работы, как это может быть быстрее ?!») является ярким примером того, почему вы всегда должны перепроверять, чтобы увидеть, что « оптимизация ", которую вы поставили на место, на самом деле повышает производительность. Преждевременная оптимизация - корень всего зла.

Answer 2

Большее использование памяти часто значительно снижает производительность - основная проблема связана с тем, что большие структуры данных не помещаются в кэш вашего процессора и для доступа к ним потребуется много дольше.

На современных процессорах вы часто обнаруживаете, что на самом деле повторный математический расчет выполняется намного быстрее, чем получение результата из памяти.Доступ к памяти, в основном, является узким местом, а не процессором.

Также, если вы запоминаете значения, помните о потенциальных издержках хэширования и поиска.В частности, если вы неправильно внедрили свою хэш-функцию и у вас много коллизий хешей, вы можете столкнуться с очень дорогими поисками.