Почему линейная запись с перемешиванием с чтением не быстрее, чем с линейной записью с перемешиванием?

Ответ 1

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

1. Современные процессоры очень эффективно скрывают задержку чтения

2. в то время как запись в память дороже, чем чтение в память

3. особенно в многоядерной среде

Причина № 1 Современные процессоры эффективно скрывают задержку чтения.

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

Чтобы объяснить это, давайте рассмотрим простой код, который копирует массив в другой.

for i in a:
    c[i] = b[i]

Один скомпилированный код, исполняемый процессором, будет как-то так

#1. (iteration 1) c[0] = b[0]
1a. read memory at b[0] and store result in register c0
1b. write register c0 at memory address c[0]
#2. (iteration 2) c[1] = b[1]
2a. read memory at b[1] and store result in register c1
2b. write register c1 at memory address c[1]
#1. (iteration 2) c[2] = b[2]
3a. read memory at b[2] and store result in register c2
3b. write register c2 at memory address c[2]
# etc

(это сильно упрощено, и реальный код более сложен и должен иметь дело с управлением циклами, вычислением адресов и т.д., но в настоящее время этой упрощенной модели достаточно).

Как сказано в вопросе, для чтения процессор должен ждать фактических данных. Действительно, 1b нужны данные, извлеченные 1a, и они не могут выполняться, пока 1a не завершена. Такое ограничение называется зависимостью, и мы можем сказать, что 1b зависит от 1a. Зависимости является основным понятием в современных процессорах. Зависимости выражают алгоритм (например, я пишу от b до c) и должны обязательно соблюдаться. Но, если между инструкциями нет зависимости, процессоры попытаются выполнить другие ожидающие инструкции, чтобы всегда поддерживать активный конвейер. Это может привести к неупорядоченному выполнению при условии соблюдения зависимостей (аналогично правилу "как будто").

Для рассматриваемого кода нет никакой зависимости между инструкциями высокого уровня 2. и 1. (или между инструкциями asm 2a и 2b и предыдущими инструкциями). На самом деле, конечный результат даже будет идентичен: 2. выполняется перед 1., и процессор попытается выполнить 2a и 2b, до завершения 1a и 1b. Между 2a и 2b все еще существует зависимость, но обе могут быть выданы. И аналогично для 3а. и 3б. и тд. Это мощное средство скрытия задержки памяти. Если по какой-либо причине 2., 3. и 4. могут прекратить работу до того, как 1. загрузит свои данные, вы можете даже не заметить никакого замедления.

Этот параллелизм на уровне команд управляется набором "очередей" в процессоре.

• Очередь ожидающих инструкций в станциях резервирования RS (введите 128 µinstructions в последние пятидесятые годы). Как только ресурсы, требуемые инструкцией, становятся доступными (например, значение регистра c1 для инструкции 1b), инструкция может выполняться.

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

• очередь для обеспечения последовательности при обратной записи приводит к регистрам (буфер переупорядочения или ROB из 168 записей) по аналогичным причинам.

• и некоторые другие очереди при получении инструкций для генерации мопов, буферов записи и пропуска в кэше и т.д.

В какой-то момент выполнения предыдущей программы будет много ожидающих хранения инструкций в RS, несколько загрузок в MOB и инструкций, ожидающих выхода в ROB.

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

Это объясняет разницу между линейным и случайным доступом к памяти.
В линейном доступе 1/число пропусков будет меньше из-за лучшей пространственной локализации и потому что кеши могут предварительно выбирать доступы с регулярным шаблоном, чтобы еще больше его уменьшить, и 2/всякий раз, когда чтение завершается, это будет касаться полной строки кеша и может освободить несколько ожидающих загрузки инструкций, ограничивающих заполнение очередей инструкций. Таким образом, процессор постоянно занят, а задержка памяти скрыта.
Для произвольного доступа число пропусков будет выше, и при поступлении данных может обслуживаться только одна загрузка. Следовательно, очереди инструкций будут быстро насыщаться, зависание процессора и задержка памяти больше не будут скрыты при выполнении других инструкций.

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

... за исключением случаев, когда у вас длинные цепочки зависимостей.

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

Например, рассмотрим код for я in range(1,100000): s += a[i]. Все чтения из памяти независимы, но есть цепочка зависимостей для накопления в s. Никакое дополнение не может произойти, пока предыдущий не закончился. Эти зависимости позволят быстро заполнить станции резервирования и создать киоски в трубопроводе.

Но чтения редко участвуют в цепочках зависимостей. По-прежнему возможно представить патологический код, в котором все чтения зависят от предыдущего (например, for я in range(1,100000): s = a[s]), но в реальном коде они редки. И проблема возникает из цепочки зависимостей, а не из-за того, что это чтение; ситуация была бы аналогичной (и даже, вероятно, еще хуже) с зависимым от вычислений кодом, подобным for я in range(1,100000): x = 1.0/x+1.0.

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

Причина № 2: записи в память (особенно случайные) стоят дороже, чем чтение в память

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

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

Когда процессор записывает данные в память, кеш также проверяет наличие строки. Если строка отсутствует, кэш не может отправить свои данные в память (поскольку все передачи основаны на строке) и выполняет следующие шаги:

1. кеш извлекает строку из памяти и записывает ее в строку кеша.
2. данные записываются в кеш и полная строка помечается как измененная (грязная)
3. когда строка подавляется из кэша, она проверяет наличие измененного флага, а если строка была изменена, она записывает ее обратно в память (обратная запись в кэш)

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

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

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

В любом случае запись всегда дороже, чем чтение. И многоядерные увеличивают этот аспект.

Причина № 3: Случайные записи создают ошибки кэша в многоядерных

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

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

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

Что касается проблемы случайной записи, строки кэша занимают 64 байта и могут содержать 8 int64, и если компьютер имеет 8 ядер, каждое ядро будет обрабатывать в среднем 2 значения. Следовательно, существует важный ложный обмен, который замедляет запись.

Мы сделали некоторые оценки производительности. Это было выполнено в C для того, чтобы включить оценку влияния распараллеливания. Мы сравнили 5 функций, которые обрабатывают массивы int64 размера N.

1. Просто копия b в c (c[i] = b[i]) (реализуется компилятором с помощью memcpy())

2. Копирование с линейным индексом c[i] = b[d[i]] где d[i]==i (read_linear)

3. Скопируйте со случайным индексом c[i] = b[a[i]] где a - случайная перестановка 0..N-1 (read_random эквивалентен fwd в исходном вопросе)

4. Напишите линейное c[d[i]] = b[i] где d[i]==i (write_linear)

5. Написать случайный c[a[i]] = b[i] с a случайной перестановки 0..n-1 (write_random эквивалентно inv в вопросе)

Код был скомпилирован с помощью gcc -O3 -funroll-loops -march=native -malign-double на процессоре Skylake. Производительность измеряется с помощью _rdtsc() и задается в циклах на итерацию. Функция выполняется несколько раз (1000-20000 в зависимости от размера массива), выполняется 10 экспериментов и сохраняется наименьшее время.

Размеры массивов варьируются от 4000 до 1200000. Весь код был измерен в последовательной и параллельной версиях с openmp.

Вот график результатов. Функции бывают разных цветов, с последовательной версией в толстых линиях и параллельной с тонкими.

Прямое копирование (очевидно) является самым быстрым и реализуется gcc с высокооптимизированной memcpy(). Это способ получить оценку пропускной способности данных с помощью памяти. Он варьируется от 0,8 цикла на итерацию (ИПЦ) для маленьких матриц до 2,0 ИПЦ для больших.

Линейные чтения выполняются примерно в два раза дольше, чем memcpy, но есть 2 чтения и запись, против 1 чтение и запись для прямой копии. Более индекс добавляет некоторую зависимость. Минимальное значение составляет 1,56 ИПЦ, а максимальное значение 3,8 ИПЦ. Запись линейная немного длиннее (5-10%).

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

size    4000    6000    9000    13496   20240   30360   45536   68304   102456  153680  230520  345776  518664  777992  1166984
rd-rand 1.86821 2.52813 2.90533 3.50055 4.69627 5.10521 5.07396 5.57629 6.13607 7.02747 7.80836 10.9471 15.2258 18.5524 21.3811
wr-rand 7.07295 7.21101 7.92307 7.40394 8.92114 9.55323 9.14714 8.94196 8.94335 9.37448 9.60265 11.7665 15.8043 19.1617 22.6785

• малые значения (<10 КБ): кэш-память L1 имеет размер 32 КБ и может содержать массив из 4 КБ uint64. Обратите внимание, что из-за случайности индекса после ~ 1/8 итераций кэш L1 будет полностью заполнен значениями массива случайных индексов (поскольку строки кэша имеют размер 64 байта и могут содержать 8 элементов массива). При доступе к другим линейным массивам мы быстро сгенерируем много пропусков L1, и нам придется использовать кэш L2. Доступ к кэш-памяти L1 составляет 5 циклов, но он конвейерный и может обслуживать пару значений за цикл. Доступ L2 длиннее и требует 12 циклов. Количество пропусков одинаково для случайных операций чтения и записи, но мы видим, что мы полностью оплачиваем двойной доступ, необходимый для записи при небольшом размере массива.

• средние значения (10k-100k): кэш-память L2 имеет размер 256 КБ и может содержать массив размером 32 КБ int64. После этого нам нужно перейти в кэш L3 (12Mo). По мере увеличения размера увеличивается число пропусков в L1 и L2 и соответственно увеличивается время вычисления. Оба алгоритма имеют одинаковое количество пропусков, в основном из-за случайного чтения или записи (другие обращения являются линейными и могут быть очень эффективно предварительно извлечены кэшем). Мы извлекаем фактор два между случайным чтением и записью, уже отмеченными в ответе BM. Это может быть частично объяснено двойной стоимостью записей.

• большие значения (> 100 КБ): разница между методами постепенно уменьшается. Для этих размеров большая часть информации хранится в кеше L3. Размер L3 достаточен для хранения всего массива 1,5 М, и линии с меньшей вероятностью будут извлечены. Следовательно, для записей, после начального чтения, большее количество записей может быть выполнено без извлечения строки, и относительная стоимость операций записи по сравнению с чтением снижается. Для этих больших размеров есть также много других факторов, которые необходимо учитывать. Например, кэши могут обслуживать только ограниченное количество пропусков (тип 16), а когда количество пропусков велико, это может быть ограничивающим фактором.

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

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

Ответ 2

• Сначала опровержение вашей интуиции: fwd побеждает inv даже без грубого меанизма.

Это случай для этой версии Numba:

import numba

@numba.njit
def fwd_numba(a,b,c):
    for i in range(N):
        c[a[i]]=b[i]

@numba.njit
def inv_numba(a,b,c):
    for i in range(N):
        c[i]=b[a[i]]

Сроки для N = 10 000:

%timeit fwd()
%timeit inv()
%timeit fwd_numba(a,b,c)
%timeit inv_numba(a,b,c)
62.6 µs ± 3.84 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
144 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
16.6 µs ± 1.52 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
34.9 µs ± 1.57 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

• Во-вторых, Numpy имеет дело с грозными проблемами выравнивания и (cache-) локальности.

По сути, это обертка на низкоуровневых процедурах от BLAS/ATLAS/MKL. Необычное индексирование - хороший инструмент высокого уровня, но еретический для этих проблем; нет прямой передачи этой концепции на низком уровне.

• В-третьих, NumPy Dev Docs: подробные индексации. Особенно:

Если при получении элемента не существует только одного индексного массива, валидность индексов проверяется заранее. В противном случае он обрабатывается во внутреннем цикле для оптимизации.

Мы в этом случае здесь. Я думаю, что это может объяснить разницу, и почему набор медленнее, чем получить.

Это также объясняет, почему сделанная вручную numba часто быстрее: она ничего не проверяет и вылетает при несовместимом индексе.

Ответ 3

Ваши два фрагмента NumPy b[a] и c[a] = b кажутся разумными эвристиками для измерения перемешанных/линейных скоростей чтения/записи, о чем я расскажу, рассмотрев базовый код NumPy в первом разделе ниже.

Что касается вопроса о том, что должно быть быстрее, то представляется вероятным, что shuffled-read-linear-write обычно может победить (как показывают тесты), но на разницу в скорости может повлиять то, как "тасуется" перемешанный индекс. и один или несколько из:

• Политики чтения/обновления кэша ЦП (обратная запись или сквозная запись и т.д.).
• Как процессор выбирает (пере) упорядочивает инструкции, которые ему необходимо выполнить (конвейерная обработка).
• ЦП распознает шаблоны доступа к памяти и предварительно выбирает данные.
• Кэш-логика выселения.

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

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

"Тривиальная" модная индексация

Цель этого раздела - просмотреть исходный код NumPy, чтобы определить, есть ли какие-либо очевидные объяснения времени, а также получить как можно более четкое представление о том, что происходит при выполнении A[B] или A[B] = C,

Процедура итерации, лежащая в основе причудливого индексирования для операций getitem и setitem в этом вопросе, " тривиальна ":

• B - одноиндексный массив с одним шагом
• A и B имеют одинаковый порядок памяти (оба C-смежных или оба Fortran-смежных)

Кроме того, в нашем случае и A и B выровнены по Uint:

Код прокрученной копии: здесь вместо этого используется "выравнивание uint". Если размер элемента [N] массива равен 1, 2, 4, 8 или 16 байтов и массив выровнен по uint, то вместо [использования буферизации] numpy сделает *(uintN*)dst) = *(uintN*)src) для соответствующих N. В противном случае, NUMPY копии, выполнив memcpy(dst, src, N).

Дело в том, что использование внутреннего буфера для обеспечения выравнивания исключается. Базовое копирование, реализованное с помощью *(uintN*)dst) = *(uintN*)src), так же просто, как "поместить байты X из смещения src в байты X со смещением dst".

Компиляторы, скорее всего, очень просто mov инструкции mov (например, на x86) или аналогичные.

Основной низкоуровневый код, который выполняет получение и настройку элементов, находится в функциях mapiter_trivial_get и mapiter_trivial_set. Эти функции создаются в lowlevel_strided_loops.c.src, где шаблоны и макросы затрудняют чтение (повод быть благодарным за языки более высокого уровня).

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

    while (itersize--) {
        char * self_ptr;
        npy_intp indval = *((npy_intp*)ind_ptr);

#if @[email protected]
        if (check_and_adjust_index(&indval, fancy_dim, 0, _save) < 0 ) {
            return -1;
        }
#else
        if (indval < 0) {
            indval += fancy_dim;
        }
#endif

        self_ptr = base_ptr + indval * self_stride; /* offset into array being indexed */

#if @[email protected]
        *(npy_uint64 *)result_ptr = *(npy_uint64 *)self_ptr;
#else
        *(npy_uint64 *)self_ptr = *(npy_uint64 *)result_ptr;
#endif

        ind_ptr += ind_stride;         /* move to next item of index array */
        result_ptr += result_stride;   /* move to next item of result array */

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

Дополнительные проверки индекса для setitem

Стоит отметить, что для setitem действительность индексов (независимо от того, являются ли они все входящими для целевого массива) проверяется перед началом копирования (через check_and_adjust_index), что также заменяет отрицательные индексы соответствующими положительными индексами.

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

Эта дополнительная предварительная проверка, вероятно, может оказать небольшое, но отрицательное влияние на скорость установки (A[B] = C).

Кеш пропускает

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

Процессор кэширует небольшие блоки памяти (строки кэша), к которым недавно обращались, в ожидании, что ему, вероятно, скоро понадобится снова обратиться к этой области памяти.

Для контекста строки кэша обычно имеют размер 64 байта. Кэш данных L1 (самый быстрый) на старом ЦП моего ноутбука составляет 32 КБ (этого достаточно для хранения около 500 значений int64 из массива, но имейте в виду, что ЦП будет выполнять другие задачи, требующие другой памяти, пока выполняется фрагмент NumPy):

$ cat /sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size
64
$ cat /sys/devices/system/cpu/cpu0/cache/index0/size
32K

Как вы, наверное, уже знаете, для чтения/записи памяти последовательное кэширование работает хорошо, потому что блоки 64-байтовой памяти выбираются по мере необходимости и хранятся ближе к процессору. Повторный доступ к этому блоку памяти происходит быстрее, чем выборка из ОЗУ (или более медленный кэш более высокого уровня). Фактически, CPU может даже превентивно извлечь следующую строку кэша, прежде чем она будет запрошена программой.

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

Итак, что быстрее обрабатывать ЦП: частые пропуски при чтении или записи?

Предположим, что политика записи ЦП является обратной записью, что означает, что измененная память записывается обратно в кэш. Кэш помечен как измененный (или "грязный"), и изменение будет записано обратно в основную память только после того, как строка будет удалена из кэша (ЦП все еще может читать из грязной строки кэша).

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

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

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

Ответ 4

Ваша функция fwd не касается глобальной переменной c. Вы не указали ему global c (только в setup), поэтому он имеет свою локальную переменную и использует STORE_FAST в cpython:

>>> import dis
>>> def fwd():
...     c = b[a]
...
>>> dis.dis(fwd)
  2           0 LOAD_GLOBAL              0 (b)
              3 LOAD_GLOBAL              1 (a)
              6 BINARY_SUBSCR
              7 STORE_FAST               0 (c)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

Теперь, давайте попробуем это с глобальным:

>>> def fwd2():
...     global c
...     c = b[a]
...
>>> dis.dis(fwd2)
  3           0 LOAD_GLOBAL              0 (b)
              3 LOAD_GLOBAL              1 (a)
              6 BINARY_SUBSCR
              7 STORE_GLOBAL             2 (c)
             10 LOAD_CONST               0 (None)
             13 RETURN_VALUE

Несмотря на это, он может отличаться во времени по сравнению с функцией inv которая вызывает setitem для global.

В любом случае, если вы хотите записать его в c, вам нужно что-то вроде c[:] = b[a] или c.fill(b[a]). Присвоение заменяет переменную (name) на объект с правой стороны, поэтому старый c может быть освобожден вместо нового b[a], и такого рода перестановка памяти может быть дорогостоящей.

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

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

Ответ 5

Следующий эксперимент подтверждает, что случайные записи выполняются быстрее, чем случайные. Для небольших размеров данных (когда они полностью помещаются в кеши) случайный код записи медленнее, чем код случайного чтения (вероятно, из-за определенных особенностей реализации в numpy), но по мере увеличения размера данных начальная разница в исполнении в 1,7 раза увеличивается время почти полностью устранено (однако в случае с numba в numba происходит странное изменение этой тенденции).

$ cat test.py 
import numpy as np
from timeit import timeit
import numba

def fwd(a,b,c):
    c = b[a]

def inv(a,b,c):
    c[a] = b

@numba.njit
def fwd_numba(a,b,c):
    for i,j in enumerate(a):
        c[i] = b[j]

@numba.njit
def inv_numba(a,b,c):
    for i,j in enumerate(a):
        c[j] = b[i]


for p in range(4, 8):
    N = 10**p
    n = 10**(9-p)
    a = np.random.permutation(N)
    b = np.random.random(N)
    c = np.empty_like(b)
    print('---- N = %d ----' % N)
    for f in 'fwd', 'fwd_numba', 'inv', 'inv_numba':
        print(f, timeit(f+'(a,b,c)', number=n, globals=globals()))

$ python test.py 
---- N = 10000 ----
fwd 1.1199337750003906
fwd_numba 0.9052993479999714
inv 1.929507338001713
inv_numba 1.5510062070025015
---- N = 100000 ----
fwd 1.8672701190007501
fwd_numba 1.5000483989970235
inv 2.509873716000584
inv_numba 2.0653326050014584
---- N = 1000000 ----
fwd 7.639554155000951
fwd_numba 5.673054756000056
inv 7.685382894000213
inv_numba 5.439735023999674
---- N = 10000000 ----
fwd 15.065879136000149
fwd_numba 12.68919651500255
inv 15.433822674000112
inv_numba 14.862108078999881