LINUX.ORG.RU

Двумерный массив из одномерного - ван секонд фастер вжуух.

 , , , ,


1

2

Уптимизирвал тут уптимизации, подумалось локальность данных улокалить, а чёб нет.

Пример, скорости мытья 400000000 тарелок

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main(int argc, char *argv[])
{
    uint32_t   len = 20000;
    
#ifdef Villabajo
    uint32_t ** mem_a = malloc(sizeof(uint32_t *) * len);
    for (int i = 0; i < len; ++i)
    {
        mem_a[i] = malloc(sizeof(uint32_t) * len);
        for (int j = 0; j < len; j++)
        {
            mem_a[i][j]=j;
        }
    }
#endif


#ifdef Villaribo
    uint32_t  * mem_b = malloc(sizeof(uint32_t)*(len*len));
    uint32_t ** mem_c = malloc(sizeof(uint32_t*)*len);

    for (int i = 0; i < len; ++i)
    {
        mem_c[i] = mem_b+len*i;

        for (int j = 0; j < len; j++)
        {
            mem_c[i][j]=j;
        }
    }

#endif

    return 0;
}
dron@gnu:~$ gcc gg.c -O0 -DVillabajo -o Villabajo && time ./Villabajo

real	0m3,499s
user	0m2,602s
sys	0m0,876s
dron@gnu:~$ gcc gg.c -O0 -DVillaribo -o Villaribo && time ./Villaribo

real	0m2,737s
user	0m2,160s
sys	0m0,561s
dron@gnu:~$ 

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

зачем два цикла?!

индексы берутся операторами / и %, хотя нет это наверно так сложно)

anonymous2
()
Ответ на: комментарий от agentgoblin

Два малока быстрее 20001 малока. Записал.

1. хочешь сказать, что 20к маллоков занимает аж полсекунды? ну-ну

2. точно не скажу, но емнип компилятор имеет право маллоки двигать и объединять

3. это мода сейчас такая среди молодежи бенчить с -O0 ? а то я знаете все по-старинке как-то, -O2 либо -O3, отстал наверно от современных тенденций?

a--
()
Последнее исправление: a-- (всего исправлений: 2)

Чувак, любой твой цикл должен быть 0.2 секунды или меньше. Скорость проезда по памяти как минимум 10 ГБ/с, а на приличном железе сейчас наверно уже все 100 ГБ/с (при условии что только одно ядро из нескольких едет по памяти)

a--
()
Последнее исправление: a-- (всего исправлений: 2)
Ответ на: комментарий от a--

Послушай, но это не ко мне претензии должны быть, а к ТСу. Не я это открытие сделал с -O0.

agentgoblin
()
Ответ на: комментарий от a--

любой твой цикл должен быть 0.2 секунды или меньше

Просто добавь printf или return c mem_X в конце каждого примера. Иначе с -O2 и -O3 компилятор выкидывает все эти циклы и выделения памяти в топку как неиспользуемые, после чего скорость исполнения вырастает аж до 0,002s. В ассемблерном листинге можешь убедиться в этом (gcc -S).

Вариант с return mem_a[len-1][len-1];:

$ gcc mallocs20k.c -O2 -DVillabajo -o Villabajo && time ./Villabajo

real    0m0,661s
user    0m0,144s
sys     0m0,515s

$ gcc mallocs20k.c -O3 -DVillabajo -o Villabajo && time ./Villabajo

real    0m0,559s
user    0m0,056s
sys     0m0,502s

В другой деревне с return mem_b[(len*len)-1];:

$ gcc mallocs20k.c -O2 -DVillaribo -o Villaribo && time ./Villaribo

real    0m0,574s
user    0m0,132s
sys     0m0,441s

$ gcc mallocs20k.c -O3 -DVillaribo -o Villaribo && time ./Villaribo

real    0m0,627s
user    0m0,096s
sys     0m0,530s

Ryzen 5 2600 + DDR4 2666 + Ubuntu 20.04.

agentgoblin
()
Последнее исправление: agentgoblin (всего исправлений: 2)

Не совсем понятно, что именно мы хотим померять. Скорость выделения памяти (многократно или за один раз)? Скорость прохождения по массиву?

Какое % соотношение этих двух величин в коде примера?

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

blex
()

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

Выдумки.

только вроде плюсы.

Да.

И у тебя нигде не было двумерного массива, у тебя был массив указателей на массивы. Двумерный это синтаксический сахар для твоего второго варианта.

firkax ☕☕☕☕☕
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от a--

точно не скажу, но емнип компилятор имеет право маллоки двигать и объединять

Да, т.к. дёрганье malloc это не наблюдаемое поведение.

utf8nowhere
()

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

static void BM_array_of_pointers(benchmark::State& state) {
  uint32_t   len = 20000;
  uint32_t ** mem_a = static_cast<uint32_t **>(malloc(sizeof(uint32_t *) * len));
  for (int i = 0; i < len; ++i)
  {
      mem_a[i] = static_cast<uint32_t*>(malloc(sizeof(uint32_t) * len));
  }

  for (auto _ : state)
  {
    for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j < len; j++)
        {
            mem_a[i][j]=j;
        }
    }
  }
}

static void BM_array_single(benchmark::State& state) {
  uint32_t   len = 20000;
    uint32_t  * mem_b = static_cast<uint32_t *>(malloc(sizeof(uint32_t)*(len*len)));
    uint32_t ** mem_c = static_cast<uint32_t **>(malloc(sizeof(uint32_t*)*len));
      for (int i = 0; i < len; ++i)
    {
        mem_c[i] = mem_b+len*i;
    }

  for (auto _ : state)
  {
      for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j < len; j++)
        {
            mem_c[i][j]=j;
        }
    }

  }
}

BENCHMARK(BM_array_single);
BENCHMARK(BM_array_of_pointers);

BENCHMARK_MAIN();

Результат (CPU 9 изолирован от планировщика):

$ taskset -c 9 ./mybenchmark 
2022-07-21T11:25:11+00:00
Running ./mybenchmark
Run on (144 X 3000 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x72)
  L1 Instruction 32 KiB (x72)
  L2 Unified 1024 KiB (x72)
  L3 Unified 25344 KiB (x4)
Load Average: 72.75, 72.25, 72.16
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
BM_array_of_pointers 1291111886 ns   1288062532 ns            1
BM_array_single      1296587307 ns   1293546084 ns            1

Поменял местами тесты и получил противоположный результат:

$ taskset -c 9 ./mybenchmark 
2022-07-21T11:26:44+00:00
Running ./mybenchmark
Run on (144 X 3000 MHz CPU s)
CPU Caches:
  L1 Data 32 KiB (x72)
  L1 Instruction 32 KiB (x72)
  L2 Unified 1024 KiB (x72)
  L3 Unified 25344 KiB (x4)
Load Average: 71.45, 71.83, 72.01
---------------------------------------------------------------
Benchmark                     Time             CPU   Iterations
---------------------------------------------------------------
BM_array_single      1338351062 ns   1335195693 ns            1
BM_array_of_pointers 1390381974 ns   1387119691 ns            1

Вывод: измеримых преимуществ нет.

Но вариант с одним выделением памяти идеологически верный.

blex
()
Ответ на: комментарий от utf8nowhere

Да каеш. Пока в другой единице трансляции free() на середину «объединённого» куска не вызовется. Не надо придумывать магию которую компиляторы не умеют и уметь не могут.

slovazap
()
Ответ на: комментарий от slovazap

Не надо придумывать магию которую компиляторы не умеют и уметь не могут.

Компиляторы не умеют и не могут уметь в анализ утечки указателей в другие TU?

utf8nowhere
()
Ответ на: комментарий от slovazap

Пока в другой единице трансляции free() на середину «объединённого» куска не вызовется.

Если память выделяется и освобождается в одном месте, то даже если указатель передаётся куда-то ХЗ куда, очевидно, это ХЗ куда не может на нём вызывать free().

utf8nowhere
()
Ответ на: комментарий от utf8nowhere

Если память выделяется и освобождается в одном месте, то даже если указатель передаётся куда-то ХЗ куда, очевидно, это ХЗ куда не может на нём вызывать free().

Конечно же может.

slovazap
()

Двухмерный массив из одномерного это new T[W*H] с доступом к элементу i,j как arr[i*W + j]. Кстати, многомерные фичамапы в диплернинге ровно по тому же принципу уложены (правда чуть хитрее). А вы как думали??

yoghurt
()
Ответ на: комментарий от yoghurt

Я знаю Про генерацию картинок... (комментарий). Просто у меня в другом коде ниже по тексту куча всего с доступом через arr[x][y] а для создания arr[][] я всегда почему то сначала выделял массив указателей, а потом в каждый пихал по массиву отдельному. Это я к тому что не трогая уже работающий код, выше него поменял кучу аллокаций на две и всё. Хотя хрен с ними с алокациями. Ну и данные лежат физически рядышком количество промахов кеша при переходе на следующую «строку» поделилось на ~4. Короче уже готовый код так можно заоптимизировать маненька вообще не влезая в кишки основные ^.^/

Короче мелочь, а приятно. Написал просто потому что наверняка не я один такой балбес.

LINUX-ORG-RU 😊😊😊😊😊
() автор топика
Ответ на: комментарий от slovazap

Ну вот кусок кода:

void f(void*); // определена где-то в другой TU

void* p1 = malloc(N);
void* p2 = malloc(M);
void* p3 = malloc(K);

// ...

f(p2);

// ...

free(p3);
free(p2);
free(p1);

Очевидно, f не может делать free на свой аргумент. Поэтому компилятору не о чем беспокоиться и он может объединить 3 выделения и освобождения памяти в одно.

utf8nowhere
()
Ответ на: комментарий от utf8nowhere

Во-первых, с чего это ты взял что компилятор может делать какие-то предположения о семантике маллока? Это вполне себе библиотечные функции, могут работать как им вздумается, заменяться чем угодно как на этапе линковки, так и в рантайме LD_PRELOAD’ом. Могут иметь особые требования по выравниванию, трассировке, локальности, группировке, намеренно оставлять дырки для контроля выхода за границы массовов и т.д.

Во-вторых, даже без учёта этого в твоём примере можно сделать free и exit, не касаясь даже аллокаторо-специфичных вещей типа jemalloc’овских xallocx (in-place реаллок) и sallocx (запрос информации о размере аллокации).

slovazap
()
Ответ на: комментарий от slovazap

Во-первых, с чего это ты взял что компилятор может делать какие-то предположения о семантике маллока?

Скажи ещё, компилятор не может printf("str\n") на puts("str") заменять (когда в результат printf не смотрят). Или цикл for копирования из одного массива в другой на memcpy (или наоборот).

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

malloc может работать только так, как описано в стандарте.

заменяться чем угодно как на этапе линковки, так и в рантайме LD_PRELOAD’ом.

Проблемы заменяющих. Никто не гарантирует, что если в программе написано malloc, оно будет вызвано. Или что если написано printf, то не вызовется puts вместо.

Во-вторых, даже без учёта этого в твоём примере можно сделать free и exit

Наконец реальная причина, а не маняфантазии. Чёт я это прошляпил.

utf8nowhere
()
Ответ на: комментарий от slovazap

Во-первых, с чего это ты взял что компилятор может делать какие-то предположения о семантике маллока?

Компилятор может, потому что в него заложили знание о семантике маллока.

Siborgium 👍
()
Последнее исправление: Siborgium (всего исправлений: 1)
Ответ на: комментарий от utf8nowhere

Скажи ещё, компилятор не может printf(«str\n») на puts(«str») заменять (когда в результат printf не смотрят).

Не может. Повторяю, перестань фантазировать.

Или цикл for копирования из одного массива в другой на memcpy (или наоборот).

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

Проблемы заменяющих. Никто не гарантирует, что если в программе написано malloc, оно будет вызвано

Конечно же гарантирует, глупенький.

slovazap
()
Ответ на: комментарий от slovazap

Скажи ещё, компилятор не может printf(«str\n») на puts(«str») заменять (когда в результат printf не смотрят).

Не может.

Жаль, что компиляторостроители об этом не знают.

utf8nowhere
()
Ответ на: комментарий от Siborgium

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

slovazap
()
Ответ на: комментарий от slovazap

В стандарте нет ни слова про то что на malloc накладываются требования позволяющие схлопывать аллокации

Главное, что нет требований которые это запрещают.

utf8nowhere
()
Ответ на: комментарий от slovazap

Во-первых, с чего это ты взял что компилятор может делать какие-то предположения о семантике маллока?

Он не только может, но и делает, причем знает про все функции стандартной библиотеки. LD_PRELOAD это проблемы индейцев. Пункт стандарта не скажу. В коде внизу остается только один malloc и один free при -O2.

#include <stdlib.h>

void f(int* ip);

int main(int argc, char** argv)
{
  int* p1 = malloc(sizeof(int)); *p1 = argc;
  int* p2 = malloc(sizeof(int)); *p2 = argc;
  int* p3 = malloc(sizeof(int)); *p3 = argc;

  f(p2);

  int result = *p1+*p2+*p3;

  free(p3);
  free(p2);
  free(p1);

  return result;
}

main:
        push    {r3, r4, r5, lr}
        mov     r5, r0
        movs    r0, #4
        bl      malloc
        mov     r4, r0
        str     r5, [r0]
        bl      f
        mov     r0, r4
        ldr     r3, [r4]
        add     r5, r3, r5, lsl #1
        bl      free
        mov     r0, r5
        pop     {r3, r4, r5, pc}

a--
()
Последнее исправление: a-- (всего исправлений: 1)
Ответ на: комментарий от utf8nowhere

Наконец реальная причина, а не маняфантазии. Чёт я это прошляпил.'

жаль что нет какого-нибудь атрибута [[no_exit]]

a--
()
Ответ на: комментарий от slovazap

https://en.cppreference.com/w/cpp/language/as_if

Because the compiler is (usually) unable to analyze the code of an external library to determine whether it does or does not perform I/O or volatile access, third-party library calls also aren’t affected by optimization. However, standard library calls may be replaced by other calls, eliminated, or added to the program during optimization. Statically-linked third-party library code may be subject to link-time optimization.

Siborgium 👍
()
Ответ на: комментарий от a--

Конечно же если указатель передать во внешнюю функцию никакого одного маллока уже не будет. В твоём примере компилятор имеет полное право вообще выкинуть все маллоки и оставить return argc + argc + argc;

slovazap
()
Ответ на: комментарий от slovazap

В твоём примере компилятор имеет полное право вообще выкинуть все маллоки и оставить return argc + argc + argc;

Не имеет (по двум причинам), поэтому оставляет только один маллок. Первую причину ты сам указал (exit), а вторая причина — f может поменять *p2. Кстати, можно попробовать поставить const и посмотреть.

a--
()
Ответ на: комментарий от a--

В коде внизу остается только один malloc и один free при -O2.

а причем тут семантика malloc? компилятор просто выкинул неиспользуемые переменные и тавтологии, и остался один malloc.

все что отметил компилятор - что есть вызов f(p2); - вот malloc для p2 и остался. остальные просто мусор. если заюзать p1 и p3 так, чтобы компилятор не мог это упростить, то там будет три malloc. например если приcваивать *p1 другие значения и вызывать f(p1).

alysnix ☕☕☕☕☕
()
Ответ на: комментарий от a--

Погоди, я не заметил у тебя вызов f(). Так твой пример как раз демонстрирует ровно то что я сказал.

slovazap
()
Ответ на: комментарий от alysnix

а причем тут семантика malloc?

при том, что твой hrenalloc компилятор не будет так вольно двигать/удалять/склеивать, как malloc

кстати, под похожие цели есть атрибут gnu::malloc, но я его не изучал — хотя сейчас (в результате дискуссии) понял, что это полезно бы сделать, так как там туча интересных нюансов

a--
()
Последнее исправление: a-- (всего исправлений: 1)
Ответ на: комментарий от a--

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

alysnix ☕☕☕☕☕
()
Ответ на: комментарий от alysnix

откуда компилятор знает, какой malloc дадут линкеру при сборке?

это исключительно *твои* проблемы

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

впрочем, скорее всего ты ничего из вольностей компилятора и не заметишь — за исключением случая, если придумаешь в своем маллоке какую-то чересчур вычурную функциональность

a--
()
Последнее исправление: a-- (всего исправлений: 3)
Ответ на: комментарий от a--

тут маллок не причем совсем. можешь попробовать его заменить некой функцией void* hren_alloc(int fsize) и вызвать ее. он должен тоже выкинуть два хреналока. и два free. потому что оптимизация тут в другом месте. проверяй.

alysnix ☕☕☕☕☕
()
Ответ на: комментарий от alysnix

че, правда что ли? а если вот так:

static int pavlik_morozov=0;

void f(int* ip)
{
  *ip+=pavlik_morozov;
}

void* hren_alloc(int fsize)
{
  pavlik_morozov += fsize;
  return malloc(fsize);
}

a--
()
Ответ на: комментарий от alysnix

выкидывание free, которое видимым для компилятора образом не соответствует маллоку, это отдельный вопрос, над которым опять стоит подумать

a--
()
Ответ на: комментарий от a--

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

alysnix ☕☕☕☕☕
()
Ответ на: комментарий от alysnix

тут опять думать надо, потому что случай, который мы тут рассматриваем — весьма частный

более общий случай — это когда p1 где-то далеко кладется в структуру данных, а сейчас только вынимается из нее и сразу free(p1)

а еще может быть что указатель p1 вообще читается с диска, или приходит по сети из БД (а до этого р1 был туда положен, само собой)

a--
()
Последнее исправление: a-- (всего исправлений: 2)
Ответ на: комментарий от alysnix

если он умный такой

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

а как сделать его одновременно и проверяющим этого программиста, и умным — требует обдумывания

a--
()
Последнее исправление: a-- (всего исправлений: 2)
Ответ на: комментарий от a--

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

void test_free(){
  void *lp =  (void*) 1;
  free (lp);
}
alysnix ☕☕☕☕☕
()
Ответ на: комментарий от alysnix

при оптимизациях компилятор считает программиста никогда не ошибающимся — почти это и написал выше

кстати, а откуда такое мнение, что 1 — это мусорный указатель?

a--
()
Ответ на: комментарий от alysnix

1. емнип на х86 указатели могут быть нечетными

2. любое другое число, кроме 0, тоже может быть указателем на какой-то архитектуре

a--
()
Последнее исправление: a-- (всего исправлений: 2)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.