Кэширование массива Python против C кеширования массива

Question

Довольно неопытен в Python, и я понимаю, что это ужасно просто, но насколько хорошо блоки Python кешируются по сравнению с C? Например, в C:

gridWidth = 100000
gridHeight = 100000

for (i=0; i<gridHeight; i++){

    for (j=0; j<gridWidth; j++){

       massiveNum += arr[i*gridWidth + j]
    }
}

намного быстрее, чем

  massiveNum += arr[i + j*gridWidth]

потому что данные эффективно кэшируются в первом.

Если я еду на той же скорости в Python, могу ли я сделать что-то простое, как

for i in range(0,gridHeight):

    for j in range(0,gridWidth):

       massiveNum += arr[i*gridWidth + j]

или я должен сделать что-то особенное?

Answer 1

Ваш вопрос спорный. Когда у вас есть весь интерпретатор, типы чисел в штучной упаковке, распределение кучи указанных типов и т. Д. Между вашим кодом и машиной, эффективность кеша - это наименьшее из ваших беспокойств. Поскольку встроенные типы последовательности Python используют (динамический и избыточный) массивы C под капотом, должны применяться те же правила, но есть два основных предостережения:

• Существует много «скрытого» доступа к памяти для всех операций Python (например, для проверки типов, поиска переменных и членов, создания объектов «связанных методов» перед вызовом методов, приведения чисел) между ними, которые могут уменьшить преимущество.
• Во многих случаях (т. Е. Если не указано иное), во всех контейнерах хранятся ссылки на объекты в штучной упаковке, поэтому при итерации list из int объектов кэш-память ЦП может помочь только в извлечении этих указателей быстрее, а не в обработке объекты за ними.

Я был бы удивлен, если бы вы могли измерить любую разницу как все. Если вы хотите оптимизировать, есть много вещей, которые в тысячу раз более эффективны и гораздо более очевидны. Используйте встроенные модули, NumPy, напишите немного C, используйте Cython или просто оптимизируйте свой код Python.

Answer 2

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

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

Answer 3

Я настоятельно рекомендую вам рассмотреть возможность использования numpy для работы с многомерными массивами в Python.

NumPy написан с чистым бэкэндом C, так что вы не будете подвергаться огромным штрафам за распаковку и коробкуинтерпретированный кодТогда, может быть , вы, по крайней мере, сможете измерить производительность кэша и использовать такие вещи, как мажорный ряд или порядковый номер столбца, шаг и т. Д.

Answer 4

Если вы говорите о Python массивах , то я бы предположил, что они расположены линейно в памяти, поэтому да, последовательный доступ был бы наиболее дружественным к кешу способом доступа к ним.

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

Кроме того, общие накладные расходы Python могут привести кЭффект кэширования незначителен.

Вы также можете оптимизировать цикл:

n = gridHeight * gridWidth
i = 0
while i < n:
    massiveNum += arr[i]
    i += 1