Незаметные для кэша структуры данных и динамические языки - эффективны?

Question

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

Большинство этих структур данных реализованы на языке низкого уровня, таком как C / C ++. Стоит ли пытаться портировать эти структуры данных на динамический язык, такой как Python, или накладные расходы при работе на виртуальной машине разрушают все преимущества производительности этих структур данных? Похоже на последнее, но я подумал, что хотел бы спросить, есть ли у кого-то какой-то опыт с этим.

Answer 1

В C (или C ++) вы имеете точный контроль над точным размером каждой структуры данных. У вас также есть возможность детального контроля за распределением памяти. В конце концов, вы можете расширить метод new, напрямую использовать malloc и иначе структурировать память для создания пространственной локализации.

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

В Python у вас может быть некоторая временная локализация, но у вас мало или нет пространственной локализации.

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

Я не думаю, что реализации C или C ++, не относящиеся к кешу, переводят на динамические языки, потому что я не думаю, что у вас достаточно контроля. Вместо этого просто используйте памятку для ускорения.

http://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

Answer 2

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

Кроме того, большинство распределителей памяти ВМ будет выделяться в конце пространства генерации, поэтому, если вы распределите все свои объекты одновременно, вы можете начать все в порядке. К сожалению, некоторые алгоритмы, не обращающие внимания на кэш, предполагают, что вы можете изменить структуру памяти, что обычно невозможно с виртуальной машиной.

Другая большая проблема заключается в том, что большинство реализаций на основе виртуальных машин используют ссылки на объекты. Таким образом, объект с тремя строками в действительности представляет собой 4 объекта (сам объект и 3 строковых объекта). Если эти четыре объекта не расположены рядом друг с другом, анализ алгоритма не работает.

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