LINUX.ORG.RU

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

 , ,


3

7

Задача примерно такая. Есть некий буфер в котором есть некоторые значения. Есть второй буфер, в котором хранятся адреса для сохранения в выходной буфер. Есть третий буфер(выходной), в который сохраняются данный из первого по адресам из второго. Перед началом сохранения вычисляется офсет во втором буфере, начиная с которого берутся адреса

То есть примерно такое

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

Можно как-нибудь оптимизировать запись в память для такого алгоритма? На данный момент это является узким местом самой тяжелой функции в системе. Остальную часть функции уже удалось оптимизировать через avx2.

Значения в bufOffsets само собой могут отличаться от соседних значений больше чем на 1 (то есть куском через тот же avx не записать). Подойдут решения как общие(с++/c), так и под асм x86(x86_64).

Заранее спасибо.

★★★★★

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

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

mov eax,[ebp+12] ;// *inp1
...
add  [ebp+12], 18 ;// например sizeof(inp[0])
всего 2 инструкции в теле цикла. А inp\[i\] и i++ будет что-то типа
mov eax,[ebp+8] ;// достать i
mul  eax, 18
mov ebx, [ebp+12] ;// достать inp
mov eax, [ebx] ;// получить inp[i]
...
inc [ebp+8] ;// i++
Ну может компилятор на самом деле что-то лучше предложит.

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

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

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

#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 
i-rinat ★★★★★
()
Ответ на: комментарий от i-rinat

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

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

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

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

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

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

    #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>

Dudraug ★★★★★
() автор топика
Ответ на: комментарий от Dudraug

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

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

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

Dudraug ★★★★★
() автор топика
Ответ на: комментарий от xaizek

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

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

Dudraug ★★★★★
() автор топика
Ответ на: комментарий от Dudraug

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

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