Здравствуйте, Vladimir, Вы писали:
V>Есть матрица (массив) 10000х10000. V>Заполнение всех элементов матрицы (m[i,j] = value) на моей машине выполняется 0.5 сек. V>(Половина времени уходит на цикл for, половина на присвоение). V>Можно ли как-то теоретически уменьшить скорость обработки?
1.
А можно увеличить число столбцов, так чтобы строка матрицы укладывалась точно в целое число страниц ?
10000 — это 40000 байт (если int, конечно). А надо сделать 4096*10 == 40960 байт. То есть столбцов должно быть 10240. Лишние столбцы можно не использовать.
Выделение памяти идет страницами. Не надо думать, что описав массив явно, ты выделяешь всю память сразу целиком. В языке формально — да, а ОС выделяет ее по мере надобности. При обращении к какому-то элементу, если его страницы еще нет в памяти, возникает исключение и страница подгружается.
Обмен с диском (если свопинг возникнет) идет страницами.
2. При заполнении какие команды используются ? Сейчас есть команды (SSEi AVXi), которые за одну команду пересылают 128/256/512 бит, то есть сразу 4/8/16 int. Компилятор C/C++ умеет их генерировать, если включена оптимизация. Что именно за код он сделал — можно посмотреть, указав режим генерации ассемблерного листинга
Здравствуйте, Кодт, Вы писали:
К>Важно. Кеширование.
... К>Забег поперёк такого массива — это сперва очень медленно, а потом быстро. Забег вдоль массива — это быстро с кратковременными тормозами.
Здравствуйте, Maniacal, Вы писали:
M>У Мыщьха в какой-то книге или статье есть огромная глава про это (про переключение страниц памяти). Тут главное последовательно матрицу в памяти заполнять. А то на запись ячейки памяти уходит условно два такта процессора, а на переключение 4KB страницы, вроде, что-то около 20000+
40-50 наносекунд. На такты можете пересчитать сами.
И наличие OoO позволяет смягчить эффекты.
M>Вот фрагмент из его книги "Техника оптимизации программ. Эффективное использование памяти",
Отработанной на P4 процессорах. Уже Core заметно отличались. Примерно после Haswell она уже неактуальна.
Здравствуйте, fk0, Вы писали:
fk0> 2.1. развернуть цикл (на 8-16-32-64 итерации); fk0> 2.2. избавиться от индексной адресации в пользу указателей; fk0> 2.3. избавиться от счётчика цикла в пользу сравнения с адресом конца;
Было:
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++)
m[i*w+j] = i * w + j;
}
Стало:
for (int i = 0; i < h; i++) {
DWORD *first = &m[i*w];
DWORD *last = &m[(i+1)*w-1];
while (first <= last)
*first++ = i;
}
Какие-то проблемы с компилятором, похоже. У меня этот код работает за 36 мс. Это где-то 10 ГБ/с, если ничего не путаю. Вроде нормально. Попробуй включить режим компиляции с оптимизацией.
Скрытый текст
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define w 10000
#define h 10000
int main(void) {
uint32_t *m = malloc(sizeof(uint32_t) * w * h);
clock_t start = clock();
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) m[i * w + j] = i * w + j;
}
clock_t stop = clock();
printf("%lu ms\n", (stop - start) * 1000 / CLOCKS_PER_SEC);
uint32_t sum = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) sum += m[i * w + j];
}
return (int) sum;
}
Здравствуйте, Vladimir, Вы писали:
V>Здравствуйте, fk0, Вы писали:
fk0>> 2.1. развернуть цикл (на 8-16-32-64 итерации); fk0>> 2.2. избавиться от индексной адресации в пользу указателей; fk0>> 2.3. избавиться от счётчика цикла в пользу сравнения с адресом конца;
V>Было: V>
for (int i = 0; i < h; i++) {
V> for (int j = 0; j < w; j++)
V> m[i*w+j] = i * w + j;
V>}
V>Стало: V>
for (int i = 0; i < h; i++) {
V> DWORD *first = &m[i*w];
V> DWORD *last = &m[(i+1)*w-1];
V> while (first <= last)
V> *first++ = i;
V>}
V>+30% !!!
Что бы было еще веселее попробуйте так:
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Выделение памяти идет страницами. Не надо думать, что описав массив явно, ты выделяешь всю память сразу целиком. В языке формально — да, а ОС выделяет ее по мере надобности.
ну, нужно mem_commit / mem_reserve задавть правильно и будет сильно быстрее потом
Здравствуйте, mike_rs, Вы писали:
PD>>Выделение памяти идет страницами. Не надо думать, что описав массив явно, ты выделяешь всю память сразу целиком. В языке формально — да, а ОС выделяет ее по мере надобности.
_>ну, нужно mem_commit / mem_reserve задавть правильно и будет сильно быстрее потом
И даже mem_commit не приведет к тому, что вся память будет выделена. Она выделяется по мере обращения в ней. По крайней мере в Windows это так.
Здравствуйте, kov_serg, Вы писали:
_>Только при таких объёмах оно упирается не в кэш, а организацию памяти
Мне чем дальше, тем больше кажется, что все древние наработки компьютерщиков по работе с медленными носителями типа магнитных лент и дисков времён IBM-360, становятся актуальными на новой элементной базе!
Только раньше воевали за килобайты и минуты, а сейчас за гигабайты и микросекунды.