Re: Очень быстрое заполнение матрицы (массива)
От: Pavel Dvorkin Россия  
Дата: 27.01.24 11:51
Оценка: +1
Здравствуйте, 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++ умеет их генерировать, если включена оптимизация. Что именно за код он сделал — можно посмотреть, указав режим генерации ассемблерного листинга
With best regards
Pavel Dvorkin
Re[4]: Очень быстрое заполнение матрицы (массива)
От: kov_serg Россия  
Дата: 27.01.24 14:15
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Важно. Кеширование.

...
К>Забег поперёк такого массива — это сперва очень медленно, а потом быстро. Забег вдоль массива — это быстро с кратковременными тормозами.

Только при таких объёмах оно упирается не в кэш, а организацию памяти
Re[4]: Очень быстрое заполнение матрицы (массива)
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 27.01.24 14:26
Оценка:
Здравствуйте, Maniacal, Вы писали:

M>У Мыщьха в какой-то книге или статье есть огромная глава про это (про переключение страниц памяти). Тут главное последовательно матрицу в памяти заполнять. А то на запись ячейки памяти уходит условно два такта процессора, а на переключение 4KB страницы, вроде, что-то около 20000+


40-50 наносекунд. На такты можете пересчитать сами.
И наличие OoO позволяет смягчить эффекты.

M>Вот фрагмент из его книги "Техника оптимизации программ. Эффективное использование памяти",


Отработанной на P4 процессорах. Уже Core заметно отличались. Примерно после Haswell она уже неактуальна.
The God is real, unless declared integer.
Re[2]: Очень быстрое заполнение матрицы (массива)
От: Vladimir Россия  
Дата: 28.01.24 09:03
Оценка:
Здравствуйте, 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;
}

+30% !!!
Re: Очень быстрое заполнение матрицы (массива)
От: vsb Казахстан  
Дата: 28.01.24 10:34
Оценка:
Какие-то проблемы с компилятором, похоже. У меня этот код работает за 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;
}
Отредактировано 28.01.2024 10:35 vsb . Предыдущая версия . Еще …
Отредактировано 28.01.2024 10:35 vsb . Предыдущая версия .
Re[3]: Очень быстрое заполнение матрицы (массива)
От: kov_serg Россия  
Дата: 28.01.24 12:41
Оценка:
Здравствуйте, 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% !!!
Что бы было еще веселее попробуйте так:
#include <chrono>
#include <iostream>

int main(int argc, char const *argv[]) {
    std::chrono::steady_clock::time_point begin, end;
    double dt, size, gb=1024*1024*1024;
    
    enum { N=16384 };
    enum { m=2048 };
    typedef unsigned T;
    T* x=new T[N*N]; if (!x) return 1;
    size=N*N*sizeof(*x);
    begin = std::chrono::steady_clock::now();
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j+=m) {
            for(int k=0;k<m;k++) x[i*N+j+k]=0; // -30%
            for(int k=0;k<m;k++) x[i*N+j+k]=i;
        }
    }
    end = std::chrono::steady_clock::now();
    dt=std::chrono::duration<double>(end-begin).count();
    std::cout << "cold dt = " << std::chrono::duration_cast<std::chrono::milliseconds>(end-begin).count() << "[ms]";
    std::cout << " speed=" << size/dt/gb << " Gb/s\n";
    begin = std::chrono::steady_clock::now();
    for(int i=0;i<N;i++) {
        for(int j=0;j<N;j+=m) {
            for(int k=0;k<m;k++) x[i*N+j+k]=0; // +90% :)
            for(int k=0;k<m;k++) x[i*N+j+k]=i;
        }
    }
    end = std::chrono::steady_clock::now();
    dt=std::chrono::duration<double>(end-begin).count();
    std::cout << "warm dt = " << std::chrono::duration_cast<std::chrono::milliseconds> (end - begin).count() << "[ms]";
    std::cout << " speed=" << size/dt/gb << " Gb/s\n";
    delete[] x;
    return 0;
}
Re: Очень быстрое заполнение матрицы (массива)
От: WiseAlex Беларусь  
Дата: 29.01.24 08:45
Оценка: +1
а какую скорость показывает memset?
Re[2]: Очень быстрое заполнение матрицы (массива)
От: mike_rs Россия  
Дата: 29.01.24 16:36
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Выделение памяти идет страницами. Не надо думать, что описав массив явно, ты выделяешь всю память сразу целиком. В языке формально — да, а ОС выделяет ее по мере надобности.


ну, нужно mem_commit / mem_reserve задавть правильно и будет сильно быстрее потом
Re: Очень быстрое заполнение матрицы (массива)
От: Serpuh фотомер.рф
Дата: 29.01.24 17:34
Оценка:
Распаралеллить, например через OpenMP.
Re[2]: Очень быстрое заполнение матрицы (массива)
От: CreatorCray  
Дата: 29.01.24 19:52
Оценка: +1
Здравствуйте, Serpuh, Вы писали:

S>Распаралеллить, например через OpenMP.

Если параллелить бездумно то можно и вовсе замедлить из-за cache coherency
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[3]: Очень быстрое заполнение матрицы (массива)
От: Pavel Dvorkin Россия  
Дата: 30.01.24 04:01
Оценка: +1
Здравствуйте, mike_rs, Вы писали:

PD>>Выделение памяти идет страницами. Не надо думать, что описав массив явно, ты выделяешь всю память сразу целиком. В языке формально — да, а ОС выделяет ее по мере надобности.


_>ну, нужно mem_commit / mem_reserve задавть правильно и будет сильно быстрее потом


И даже mem_commit не приведет к тому, что вся память будет выделена. Она выделяется по мере обращения в ней. По крайней мере в Windows это так.
With best regards
Pavel Dvorkin
Re[5]: Очень быстрое заполнение матрицы (массива)
От: Кодт Россия  
Дата: 30.01.24 14:37
Оценка: +1
Здравствуйте, kov_serg, Вы писали:

_>Только при таких объёмах оно упирается не в кэш, а организацию памяти


Мне чем дальше, тем больше кажется, что все древние наработки компьютерщиков по работе с медленными носителями типа магнитных лент и дисков времён IBM-360, становятся актуальными на новой элементной базе!
Только раньше воевали за килобайты и минуты, а сейчас за гигабайты и микросекунды.
Перекуём баги на фичи!
Re[3]: Очень быстрое заполнение матрицы (массива)
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 01.02.24 05:22
Оценка:
Здравствуйте, Vladimir, Вы писали:

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% !!!

За два гига размер не перешагивает?
Какая-то у тебя мелкая матрица
Маньяк Робокряк колесит по городу
Re[2]: Очень быстрое заполнение матрицы (массива)
От: Michael7 Россия  
Дата: 08.03.24 18:59
Оценка:
Здравствуйте, kov_serg, Вы писали:

_>Что у вас выводит такой код?


Хороший пример, что бенчмарки дело не такое простое.

$ g++ a.cpp -O3 && ./a.out
cold dt = 0[ms] speed=8.27842e+06 Gb/s
warm dt = 0[ms] speed=3.72529e+07 Gb/s

$ g++ a.cpp -O2 && ./a.out
cold dt = 0[ms] speed=7.45058e+06 Gb/s
warm dt = 0[ms] speed=3.72529e+07 Gb/s

$ g++ a.cpp -O1 && ./a.out
cold dt = 88[ms] speed=8.39206 Gb/s
warm dt = 62[ms] speed=11.9538 Gb/s

$ g++ a.cpp -O0 && ./a.out
cold dt = 296[ms] speed=2.50938 Gb/s
warm dt = 273[ms] speed=2.72459 Gb/s


DDR4 двухканал 3000 МГц, gcc — 12-й версии
Re: Очень быстрое заполнение матрицы (массива)
От: DiPaolo Россия  
Дата: 09.03.24 01:49
Оценка:
SIMD/векторизация/интринсики + распараллеливание.

Вот пример статьи, об чем речь — https://stackoverflow.blog/2020/07/08/improving-performance-with-simd-intrinsics-in-three-use-cases/

А вот тут можно посмотреть код для быстрой работы с массивами или даже заюзать библиотечку — https://github.com/kfjahnke/zimt
Патриот здравого смысла
Re: Очень быстрое заполнение матрицы (массива)
От: CreatorCray  
Дата: 09.03.24 04:08
Оценка: +1
Здравствуйте, Vladimir, Вы писали:

V>Можно ли как-то теоретически уменьшить скорость обработки?

Т.е. замедлить?
... << RSDN@Home 1.3.110 alpha 5 rev. 62>>
Забанили по IP, значит пора закрыть эту страницу.
Всем пока
Re[3]: Очень быстрое заполнение матрицы (массива)
От: ArtDenis Россия  
Дата: 09.03.24 05:24
Оценка:
Здравствуйте, Vladimir, Вы писали:

V>cold dt = 617[ms] speed=1.20683 Gb/s

V>warm dt = 308[ms] speed=2.41684 Gb/s

Что-то очень мало. Не x64 проц + медленная память?
[ 🎯 Дартс-лига Уфы | 🌙 Программа для сложения астрофото ]
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.