Как эффективно сохранить в память несколько элементов по различным адресам.

Что за нечитаемая дичь? Почему не

for(size_t i = 0; i < sizeInp; ++i) {
    out[bufOffsets[offset]] = inp[i];
    ++offset;
}

Нет, я так не считаю. Собственно какая разница как написано? Лишь бы до**аться. Это вообще почти выдержка из чужого кода, на деле в массиве buffoffsets еще и тип другой и внутри этого выражения в леовой части в скобках еще и касты есть. Я по быстрому привел в более короткий вид, сильно не заморачиваясь над разумным редактированием. Вопрос вообще не в этом.

Собственно какая разница как написано?

Человек не машина. Его «кэш» очень маленький. Поэтому забивая его адресной арифметикой ты снижаешь свою способность искать решения и ошибки в решениях.

Можно как-нибудь оптимизировать запись в память для такого алгоритма?

Может, стоит пересмотреть способ хранения данных? Сделать записи близкими друг к другу. Чем дальше адреса, тем меньше толку от кэша. Линии грузятся из памяти только для того, чтобы заменить в них несколько байт из 64.

Или перемешать вычисления и запись. Тогда пока одни команды будут ожидать запись в память, другие могут продолжать вычисления.

Возможно этот тот редкий случай когда многопоточность может себя оправдать.

Если копируемые обьекты большие то может стоить вообще ничего не копировать а тупо перемапить? Тоесть один обьект сразу по двум виртуальным адресам?

Всё - придумал. Если твое железо умеет mem2mem DMA вместе со scatter-gatter то просто подсунь DMA контроллеру свои буфера, а остально он сделает сам.

Это вообще почти выдержка из чужого кода

Тогда извиняюсь.

Собственно какая разница как написано?

Потому что непонятно что именно написано. Какой-нибудь джуниор читая это либо не поймет индексацию, либо пропустит инкремент. А простой вариант с квадратными скобками прочтет любой прогер.

А по делу: если адреса в третьем буфере гарантированно не пересекаются, то это можно распараллелить через треды или openmp вообще. Во втором для этого даже специальная прагма есть,

Избавиться от лишних квадратных скобок, где возможно. Примерно так

   size_t offset = calc_offset();
    
    bufOffsets1 = bufOffsets + offset;
    inp1 = inp;
    for(size_t i = 0; i < sizeInp; ++i) {
      *(out + *(bufOffsets1)) = *inp1;
      bufOffsets1++; inp1++;
    }

Проще обратиться *inp1, а потом инкрементировать inp1. чем в каждой итерации взять i, взять inp, вычислить адрес i-го элемента и обратиться к нему.

И листинги Вам в помощь. *inp1 и inp1++ будет выглядеть типа

mov eax,[ebp+12] ;// *inp1
...
add  [ebp+12], 18 ;// например sizeof(inp[0])

mov eax,[ebp+8] ;// достать i
mul  eax, 18
mov ebx, [ebp+12] ;// достать inp
mov eax, [ebx] ;// получить inp[i]
...
inc [ebp+8] ;// i++

Ну может компилятор на самом деле что-то лучше предложит.

Я думаю, компилятор в подавляющем большинстве случаев сообразит, что умножения можно избежать.

#include <stdlib.h>

size_t calc_offset(void);

typedef struct {
    char d[18];
} tuple;

void func1(tuple *out, size_t *bufOffsets, tuple *inp, size_t sizeInp) {
  size_t offset = calc_offset();

  for (size_t i = 0; i < sizeInp; ++i) {
    *(out + *(bufOffsets + offset++)) = inp[i];
  }
}

void func2(tuple *out, size_t *bufOffsets, tuple *inp, size_t sizeInp) {
  size_t offset = calc_offset();

  size_t *bufOffsets1 = bufOffsets + offset;
  tuple *inp1 = inp;
  for (size_t i = 0; i < sizeInp; ++i) {
    *(out + *(bufOffsets1)) = *inp1;
    bufOffsets1++;
    inp1++;
  }
}

0000000000000000 <func1>:
   0:	41 55                	push   %r13
   2:	41 54                	push   %r12
   4:	49 89 cc             	mov    %rcx,%r12
   7:	55                   	push   %rbp
   8:	53                   	push   %rbx
   9:	48 89 fd             	mov    %rdi,%rbp
   c:	49 89 f5             	mov    %rsi,%r13
   f:	48 89 d3             	mov    %rdx,%rbx
  12:	48 83 ec 08          	sub    $0x8,%rsp
  16:	e8 00 00 00 00       	callq  1b <func1+0x1b>
  1b:	4d 85 e4             	test   %r12,%r12
  1e:	74 39                	je     59 <func1+0x59>
  20:	4b 8d 0c e4          	lea    (%r12,%r12,8),%rcx
  24:	49 8d 44 c5 00       	lea    0x0(%r13,%rax,8),%rax
  29:	48 89 da             	mov    %rbx,%rdx
  2c:	48 8d 3c 4b          	lea    (%rbx,%rcx,2),%rdi
  30:	48 8b 08             	mov    (%rax),%rcx
  33:	48 83 c2 12          	add    $0x12,%rdx
  37:	48 83 c0 08          	add    $0x8,%rax
  3b:	f3 0f 6f 42 ee       	movdqu -0x12(%rdx),%xmm0
  40:	48 8d 0c c9          	lea    (%rcx,%rcx,8),%rcx
  44:	48 8d 4c 4d 00       	lea    0x0(%rbp,%rcx,2),%rcx
  49:	0f 11 01             	movups %xmm0,(%rcx)
  4c:	0f b7 72 fe          	movzwl -0x2(%rdx),%esi
  50:	48 39 fa             	cmp    %rdi,%rdx
  53:	66 89 71 10          	mov    %si,0x10(%rcx)
  57:	75 d7                	jne    30 <func1+0x30>
  59:	48 83 c4 08          	add    $0x8,%rsp
  5d:	5b                   	pop    %rbx
  5e:	5d                   	pop    %rbp
  5f:	41 5c                	pop    %r12
  61:	41 5d                	pop    %r13
  63:	c3                   	retq   
  64:	66 90                	xchg   %ax,%ax
  66:	66 2e 0f 1f 84 00 00 	nopw   %cs:0x0(%rax,%rax,1)
  6d:	00 00 00 

0000000000000070 <func2>:
  70:	41 55                	push   %r13
  72:	41 54                	push   %r12
  74:	49 89 f5             	mov    %rsi,%r13
  77:	55                   	push   %rbp
  78:	53                   	push   %rbx
  79:	48 89 cd             	mov    %rcx,%rbp
  7c:	49 89 fc             	mov    %rdi,%r12
  7f:	48 89 d3             	mov    %rdx,%rbx
  82:	48 83 ec 08          	sub    $0x8,%rsp
  86:	e8 00 00 00 00       	callq  8b <func2+0x1b>
  8b:	48 85 ed             	test   %rbp,%rbp
  8e:	49 8d 4c c5 00       	lea    0x0(%r13,%rax,8),%rcx
  93:	74 34                	je     c9 <func2+0x59>
  95:	31 c0                	xor    %eax,%eax
  97:	66 0f 1f 84 00 00 00 	nopw   0x0(%rax,%rax,1)
  9e:	00 00 
  a0:	48 8b 14 c1          	mov    (%rcx,%rax,8),%rdx
  a4:	48 83 c0 01          	add    $0x1,%rax
  a8:	48 83 c3 12          	add    $0x12,%rbx
  ac:	f3 0f 6f 43 ee       	movdqu -0x12(%rbx),%xmm0
  b1:	48 8d 14 d2          	lea    (%rdx,%rdx,8),%rdx
  b5:	49 8d 14 54          	lea    (%r12,%rdx,2),%rdx
  b9:	0f 11 02             	movups %xmm0,(%rdx)
  bc:	0f b7 73 fe          	movzwl -0x2(%rbx),%esi
  c0:	48 39 c5             	cmp    %rax,%rbp
  c3:	66 89 72 10          	mov    %si,0x10(%rdx)
  c7:	75 d7                	jne    a0 <func2+0x30>
  c9:	48 83 c4 08          	add    $0x8,%rsp
  cd:	5b                   	pop    %rbx
  ce:	5d                   	pop    %rbp
  cf:	41 5c                	pop    %r12
  d1:	41 5d                	pop    %r13
  d3:	c3                   	retq 

Если смотреть по джампам в конце цикла, то тело цикла получилось 0x27 в обоих случаях.

Компилятор скорее всего выровняет структуру и поля в ней на машинное слово. А если обнести это #pragma pack(push,1) ... #pragma pack(pop) ?

И вдобавок переменная i во втором случае не нужна. Можно сделать

tuple  *inp1, *inpe;
for(inp1=inp,inpe=inp+sizeInp; inp1<inpe; inp1++)
{
.....

У меня вообще что-то вроде такого выходит

    #pragma GCC ivdep
    for (uint32_t i=0; i<(iMax1-k0);++i)
    {

        *(output + (uint32_t)*(offsetPtr++)) = (int8_t) g_Temp2[i];
 69b:   8b 55 ac                mov    -0x54(%ebp),%edx
 69e:   8a 8c 36 00 00 00 00    mov    0x0(%esi,%esi,1),%cl
 6a5:   0f b7 04 72             movzwl (%edx,%esi,2),%eax
    }



    #pragma GCC ivdep
    for (uint32_t i=0; i<(iMax1-k0);++i)
 6a9:   46                      inc    %esi
    {

        *(output + (uint32_t)*(offsetPtr++)) = (int8_t) g_Temp2[i];
 6aa:   8b 55 e0                mov    -0x20(%ebp),%edx
 6ad:   88 0c 02                mov    %cl,(%edx,%eax,1)
    }



    #pragma GCC ivdep
    for (uint32_t i=0; i<(iMax1-k0);++i)
 6b0:   3b 75 dc                cmp    -0x24(%ebp),%esi
 6b3:   75 e6                   jne    69b <..........+0x115>

Это продакшн версия? А то я бы ожидал в ней увидеть разворачивание циклов. Если у GCC не получается, то вручную.

А не внесет ли многопоточность доп оверхэд из-за необходимости синхронизировать кэши на ядрах проца? Трэды тут точно не катят, а вот openmp из научного интереса можно и глянуть.

Я надеялся, что проглядел какую-нибудь инструкцию x86, которая позволить векторно записать вектор по набору адресов (а не по одному адресу __m256i*), но походу таки не проглядел...

Да, возможно так и придется сделать.

Трэды тут точно не катят, а вот openmp из научного интереса можно и глянуть.

Но openmp это же обёртка над потоками. Если данные можно разбить на независимые подмножества и данных много, то можно было бы и потоки использовать.

Там конечно компилятор староватый, gcc 4.7.

Мы скорее всего его будем обновлять до последних версий. Но что-то не думаю, что в данном конкретном случае это как-то поможет.

Там -funroll-loops надо добавлять (или прагму соответствующую). Оно само не включается, видимо. 4.7 нормально подобное разворачивает.

А какого порядка значение sizeInp (еденици, десятки, сотни ...) ?

Десятки тысяч.

Хм, ну да, чот туплю.

А почему бы просто не использовать memcpy() или std::copy() (который превратится в memcpy()).

Еще, возможно, будет полезно в исходном буфере сделать начала копируемых объектов выровненными (хотя бы на 4 байта). В выходном, скорее всего не получится.

Еще, возможно, будет полезно в исходном буфере сделать начала копируемых объектов выровненными (хотя бы на 4 байта).

Уже по 64 байта.

А почему бы просто не использовать memcpy() или std::copy() (который превратится в memcpy()).

Потому что мы заранее не знаем по каким адресам писать и память в которую надо писать в результирующем буфере располжена не в соседних буферах. Грубый пример 0 байт из входящего должен быть записан в 0 в исходщяем, а 1 в 3. Но не никакой гарантии, что при другом запуске и другом характере алгоритма не будет 0->1, 1->8. Можно конечно произвести глубокое переосмысление изначальной мат. модели этой функции и возможно переписвания всего с нуля. Но боюсь времени у меня на это нет.

Можно попробовать использовать clflush http://x86.renejeschke.de/html/file_module_x86_id_30.html для инвалидации в кеше данных из первого и второго буфера при переходе через 64 байта (размер строки кеша). Т.е. каждые 8 итераций инвалидировать bufOffsets[offset-8]; inp[i-8];. Это может добавить место в кеше (нужно тестировать, разумеется).

Также, можно попробовать делать запись в несколько проходов, сначала в один диапазон индексов out, затем в другой (и сделать, чтобы он помещался в кеш). А каков размер активно переписываемой области out?

Уже по 64 байта.

Я изначально не правильно понял что и куда копируется. Выравнивание тут скорее мешает - занимает больше кеша.

Реализуй обвязку поверх твоего цикла. Заполни все массивы и напиши рабочий пример, который так же является бенчмарком. Естественно с соблюдением всех объёмов данных.

А так - это такая себе идея с этим заморачиваться.

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

Так же пиши какой длинны сами элементы в массивах.

У вашего TLB кататония. Если уж совсем никак не переделать модель, чтобы код в случайные страницы не писал, то хотя бы память выделяйте через mmap с MAP_HUGETLB.

Изыски производительности лучше делайте с perf stat -ddd -p <PID>.

то хотя бы память выделяйте через mmap с MAP_HUGETLB.

У вас рассинхронизация с реальностью.

У вас рассинхронизация с реальностью.

В каком месте?

В том месте, что ядро давно уже не сидит на 4к страницах и их не нужно прикастыливать сбоку. Оно само наложит тебе больших страниц.

Напоминает S-BOX, если честно.

В том месте, что ядро давно уже не сидит на 4к страницах и их не нужно прикастыливать сбоку. Оно само наложит тебе больших страниц.

THP, что ли? Во-первых, не везде включено, во-вторых, дампни анонимные vma процесса и посмотри, есть там PSE или нет.

В целом близко, да.

Тогда по моему опыту оптимизации крипто-алгоритмов, эта штука (если она реализована именно через индексы) сильно не оптимизируется. Будет к примеру 2 чтения, одна запись. Плюс-минус пару арифметических инструкций. Это предел... Если говорить про использование AVX, то может помочь занесение таблицы замен в XMM/YMM регистры и использование перемешивания и маскирования через PSHUFB. Как-то так...

Во-первых, не везде включено

Везде, а где не включено, либо выключено - это мало кого волнует. Везде включено по умолчанию. debian, rhel. Дальше мне уже лень стало гуглить.

во-вторых, дампни анонимные vma процесса и посмотри, есть там PSE или нет.

Что из этого следует? Ты споришь с тем, что оно работает?

Трэды тут точно не катят, а вот openmp из научного интереса можно и глянуть.

openmp — это треды для неосиляторов.

По теме: scatter/gather операции есть только в avx512-чего-то-там, которые, в свою очередь, за пределами xeon phi, наверное, не встречаются.

Лучшее, что ты можешь сделать — переупорядочить индексы таким образом, чтобы избежать проблемных паттернов обращения к памяти. Как это сделать? Обмазаться здоровенными мануалами или искать выжимки от тех, кто обмазывался.

По теме: scatter/gather операции есть только в avx512-чего-то-там, которые, в свою очередь, за пределами xeon phi, наверное, не встречаются.

Есть в avx2, а avx512 уже есть в новых хеонах/десктопных не на бич платформах.

Лучшее, что ты можешь сделать — переупорядочить индексы таким образом, чтобы избежать проблемных паттернов обращения к памяти. Как это сделать? Обмазаться здоровенными мануалами или искать выжимки от тех, кто обмазывался.

Судя по рассказам у него там данные копеечной длинны( десятки тысяч байтов). Либо он ошибся, либо к памяти это имеет крайне опосредованное отношение.

Да и цикл это не верх реализации, как и долбление памяти в один поток.

Что из этого следует? Ты споришь с тем, что оно работает?

Я знаю, как оно работает. Поэтому THP отключили, а память выделили через mmap. И ТС советую то же самое сделать.

Есть в avx2

https://software.intel.com/sites/landingpage/IntrinsicsGuide/ — не вижу scatter/gather для avx2

https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=gather&amp... - это что такое?

Я знаю, как оно работает.

Это не ответ.

Поэтому THP отключили, а память выделили через mmap. И ТС советую то же самое сделать.

Т.е. всё это свелось к совету с аргументацией «потому что я так сказал». Осталось только понять - зачем и к чему появились изначальные «во-первых» и «во-вторых», которые превратились в пшик?

Т.е. всё это свелось к совету с аргументацией «потому что я так сказал». Осталось только понять - зачем и к чему появились изначальные «во-первых» и «во-вторых», которые превратились в пшик?

Если ты посмотришь, как THP реализован, то станет понятны две вещи:

1. На системах с большим количеством памяти от него толку мало.

2. На системах с хоть каким-то требованием к лейтенси или производительности от THP одни проблемы. В SLES11, например, у большой аппликухи производительность где-то на 30% падала из-за постоянных сканирований и локов.

Кроме того, если характер загрузки у системы статичен, т.е. крутится одна программа, THP там просто не нужен. Городить огород «запуститься, форсировать сканирование, подождать, отключить» не проще, чем mmap сделать.

Мои примеры все из реальной серверной жизни.

openmp — это треды для неосиляторов.

++

1. На системах с большим количеством памяти от него толку мало.

Почему?

2. На системах с хоть каким-то требованием к лейтенси или производительности от THP одни проблемы. В SLES11, например, у большой аппликухи производительность где-то на 30% падала из-за постоянных сканирований и локов.

Сканированием можно управлять.

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

Это неважно. Всегда можно найти кейсы в которых что-то не нужно, но из этого не следует ненужность чего-то.

У нас есть ситуация с автором, у которого thp включено и у него всё работает. И с прикруткой htlb руками у него вряд ли что-то поменяется.

На самом деле ты просто сменил тему. Ты изначально утверждал что?

У вашего TLB кататония

Я лишь сказал, что причиной этого утверждения стала рассинхронизация с реальностью, которая стала причиной вывода ошибочного следствия. Т.к. в реальной реальности из отсутствия MAP_HUGETLB не следует «кататония». Всё просто. Мы не обсуждали thp, либо какие-то проблемы каких-то кейсов. Я ничего не утверждал ни за, ни против thp.

Городить огород «запуститься, форсировать сканирование, подождать, отключить» не проще, чем mmap сделать.

Ничего там не надо городить. Включаешь и само всё работает.

Да и mmap просто не сделать. Для его работы так же надо крутить ручки.

У нас есть ситуация с автором, у которого thp включено и у него всё работает. И с прикруткой htlb руками у него вряд ли что-то поменяется.

Давай проще: на одной задаче perf stat -ddd с THP, без THP и с MAP_HUGETLB.

Ты типа решил заигнорить всё и играть в неадекват? Я не понимаю, что тебе нужно? Ты это с меня спрашиваешь, либо что?

Ты типа решил заигнорить всё и играть в неадекват? Я не понимаю, что тебе нужно? Ты это с меня спрашиваешь, либо что?

Что заигнорить? У тебя предположение, у меня предположение. perf stat покажет, что на самом деле происходит.