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)
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.