Одинаковое ли время занимают обработка массива с начала до конца
и от конца к началу?
Предполагается, что
1) элементы массива выравнены на границу машинного слова, страницы
2) что массив занимает целое количество страниц
Если бы это был файл, то можно было бы сослаться на алгоритм упреждающего чтения,
а так же на что диск вращается в определенную сторону (с ssd это уже не так).
Т.е. в случае чтения файла, лучше читать от начала к концу.
А вот если массив только в памяти,
то будет ли по аналогии заполнение tlb-кеша (кешей первого-второго уровня и какие там еще кеши бывают)
приводить к более быстрой обработке массива от начала к концу по сравнению с обратным порядком?
Приветствуются варианты практической проверки (устраняющие влияние специфики алгоритмов разделения времени используемой ОС)
Здравствуйте, aragorb, Вы писали:
A>Одинаковое ли время занимают обработка массива с начала до конца A>и от конца к началу?
В современных процессорах присутствуют алгоритмы hardware prefetching. При этом в кэщ подтаскиваются (предсказываются) не только инструкции (это уже давно), но и данные. Думаю, что такие алгоритмы предпочитают правильный проход по памяти, т.е. с от начала массива к концу.
Поэтому, ответ — НЕТ, не одинаковое, и зависит от процессора.
Учти еще вот что. Страницы массива могут оказаться в своп-файле. Windows использует подкачку с кластеризацией, то есть когда нужна очередная страница, подкачивается не одна одна, а несколько последовательных страниц. Вперед, естественно. Поэтому просмотр от начала может быть быстрее.
PD> Windows использует подкачку с кластеризацией, то есть когда нужна очередная страница, подкачивается не одна одна, а несколько последовательных страниц.
Другими словами — при необходимости обратиться к данным из кластера, кластер считывается целиком.
Дополним условие задачи условием — размер массива кратен кластеру.
(ну и чтобы два раза не вставать, если swap находится на raid, то размер массива кратен размеру страйпа рейда)
Будет ли в таком случае зависимость от направления? Я не вижу, почему.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, aragorb, Вы писали:
A>>Одинаковое ли время занимают обработка массива с начала до конца A>>и от конца к началу?
Б>В современных процессорах присутствуют алгоритмы hardware prefetching. При этом в кэщ подтаскиваются (предсказываются) не только инструкции (это уже давно), но и данные. Думаю, что такие алгоритмы предпочитают правильный проход по памяти, т.е. с от начала массива к концу. Б>Поэтому, ответ — НЕТ, не одинаковое, и зависит от процессора.
Конечно это зависит от процессора.
Но, скажем, в x86 предсказание вперёд работает с той же эффективностью как и назад. Так что направление прохода по кэшу никак не отразится на скорости. Смотри, например, официальную документацию на процессоры: Intel® 64 and IA-32 Architectures Optimization Reference Manual, глава HARDWARE PREFETCHING OF DATA.
Другое дело, когда ты обрабатываешь несколько массивов одновременно. В этом случае производительность программы "обрабатываю 8 независимых массивов в прямом направлении и 4 независимых массива в обратном с использованием общего счетчика одновременно" может измениться если просматривать все массивы наоборот (8 назад и 4 вперёд, соответственно). Об этом тоже рассказано в документации.
Здравствуйте, aragorb, Вы писали:
Б>> Думаю, что такие алгоритмы предпочитают правильный проход по памяти, т.е. с от начала массива к концу.
A>ок. Знать о наличии такой фичи важно, и я о ней не знал.
A>Но, для конкретно этой задачи A>http://www.futurechips.org/chip-design-for-all/prefetching.html A>разве не одинаково предсказывается как направление вперед, так и назад?
Здравствуйте, aragorb, Вы писали:
A>Приветствуются варианты практической проверки (устраняющие влияние специфики алгоритмов разделения времени используемой ОС)
Что вы понимаете под обработкой? От этого может зависеть очень многое.
Для проверки я бы ,для начала, выполнил N раз требуемые операции, как в прямом так и обратном порядке, и посмотрел на результат.
Здравствуйте, solianic, Вы писали:
S>Здравствуйте, aragorb, Вы писали:
A>>Одинаковое ли время занимают обработка массива с начала до конца A>>и от конца к началу?
S>Если с конца, то на каждой итерации на одну инструкцию меньше
Можно просто заменить цикл [0..n) на цикл [-n..0). Это позволит, не меняя направление просмотра массива, использовать упрощённое сравнение с нулём как признак завершения цикла. Собственно, компиляторы так тоже делают.
BE>Что вы понимаете под обработкой? От этого может зависеть очень многое.
что-нибудь простое, например подсчёт суммы значений элементов массива
BE>Для проверки я бы ,для начала, выполнил N раз требуемые операции, как в прямом так и обратном порядке, и посмотрел на результат.
где, в обычной операционке с вытесняющей многозадачностью? это же бесполезно.
предлагают варианты:
— написать модуль к linux, в котором на время теста запретить прерывания
— найти исходники memtest
выполненная с подачи Intel'овских инженеров оптимизация memcpy в glibc, которая теперь иногда стала выполняться "от конца", обеспечивая на некоторых процессорах выигрыш в скорости в полтора-два раза.
Здравствуйте, aragorb, Вы писали:
PD>> Windows использует подкачку с кластеризацией, то есть когда нужна очередная страница, подкачивается не одна одна, а несколько последовательных страниц.
A>Другими словами — при необходимости обратиться к данным из кластера, кластер считывается целиком.
Если ты обращаешься к странице, а ее не в ОП, то считывается она и еще несколько следующих по возрастанию виртуальных адресов. Речь идет не о фиксированном размере кластера, а просто о чтениии с упреждением.
A>Дополним условие задачи условием — размер массива кратен кластеру. A>(ну и чтобы два раза не вставать, если swap находится на raid, то размер массива кратен размеру страйпа рейда)
raid тут вообще ни при чем. Речь идет о страницах виртуального АП.
A>Будет ли в таком случае зависимость от направления? Я не вижу, почему.
Вот смотри. Пусть массив из int, то есть 1024 элемента на страницу. Обращаешься, скажем, к элементу 0, то есть к началу 0-й страницы этого массива. А ее нет в ОП. Она читается из свопа , но этим же запросом читается не она одна, а скажем, 4 страницы (не помню точно, сколько там). Теперь проходишь без страничных ошибок элементы этих 4 страниц (с 0-го по 4095), а на 4096-м опять ошибка страницы, опять читается 4 и т.д.
А если от конца, то, допустим, обращаешься ты к 4095 элементу. читается эта 3-я страница, к ней еще 3, но вперед , а они и так в памяти (ты же их раньше прошел). А 2-я не читается, поэтому как дойдешь до 3071-го, так опять страничная ошибка и т.д.
Здравствуйте, aragorb, Вы писали:
A>Одинаковое ли время занимают обработка массива с начала до конца A>и от конца к началу?
Поставь страницы 2Mb (или 1Gb на AMD), и я думаю, что про TLB можно будет забыть
Re[3]: Обработка массива в памяти
От:
Аноним
Дата:
26.01.13 07:32
Оценка:
Здравствуйте, watch-maker, Вы писали:
WM>Можно просто заменить цикл [0..n) на цикл [-n..0). Это позволит, не меняя направление просмотра массива, использовать упрощённое сравнение с нулём как признак завершения цикла. Собственно, компиляторы так тоже делают.
А это не усложнит индексацию по переменной цикла?
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, watch-maker, Вы писали:
WM>>Можно просто заменить цикл [0..n) на цикл [-n..0). Это позволит, не меняя направление просмотра массива, использовать упрощённое сравнение с нулём как признак завершения цикла. Собственно, компиляторы так тоже делают. А>А это не усложнит индексацию по переменной цикла?
Просто базой будет служить не начало массива, а его конец. То есть код вида
T* base = array + 0;
for (int i = 0; i < n; ++i)
action(base[i]);
будет заменён на
T* base = array + n;
for (int i = -n; i < 0; ++i)
action(base[i]);
Как видно, тело цикла никак не изменилось. Изменилось лишь условие продолжения цикла (стало проще) и код инициализации цикла (стал сложнее). Так как обычно цикл делает более одной итерации, то условие проверяется чаще и на нём имеет смысл сэкономить.
Но разумеется, не стоит бросаться переписывать все циклы во вторую форму, ибо у них хуже читаемость, проверка условия в таких циклах редко является тормозом (а на суперскалярных процессорах отличий между двумя вариантами может вообще не быть), да и компилятор обычно сам способен сделать такую замену.
Ну и интересно ещё то, что компилятор часто использует два регистра для прохода по массиву: счётчик и указатель. Счётчик всегда движется к нулю, а указатель непосредственно индексирует обрабатываемый элемент. В таком случае различий между двумя вариантами не будет вообще.
. Кеш, ИМХО, будет работать одинаково в обоих случаях.
