c struct order

[lastpriot]

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

[Bizdelnick]

На производительность не должен. Вот на размер её в памяти - влияет.

[eddy]

Если упаковать, то пофиг же!

[drBatty]

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

ну если структура упакована, и она такая:

Код: Выделить всё

struct
{
  uint8_t b;
  uint32_t d;
};

то конечно поле d будет тормозить. Мораль: не нужно упаковывать структуры, компилятор сам всё выровняет.

[eddy]

Гы, я чепуху ляпнул: конечно, упаковка уменьшает размер, но ухудшает производительность.
Поэтому если важна скорость и бинарные данные передаваться никуда не будут, то паковать не нужно; если же важен размер либо хочется обмениваться этими данными, следует паковать.
Я пару лет назад когда одну штуку писал, столкнулся с проблемой неупаковки данных, передаваемых по сети (слалась целиком структура без сериализации). Т.к. написано оно было под i586, а у меня был x86_64, то, понятное дело, возникла проблема несогласованности размеров и положений элементов в структурах. Пришлось патчить. Теперь с ужасом думаю о том, что нужно это еще и для тупоконечного ARM написать, т.е. придется еще больше извращаться! Вот она - проблема передачи бинарных данных без сериализации!!!

[lastpriot]

test.c

Spoiler

Код: Выделить всё

#include <stdio.h>

#define BLEN 100
struct s {
   int  b[BLEN];
   char a[1024];
   int  cnt;
};

void f1(struct s *st) {
    int i;

    for(i = 0; i < BLEN; i++)
        st->b[i]++;
}

int main() {
    struct s st = {0};
    int i;

    for(i = 0; i < 30000000; i++)
    f1(&st);

    return 0;
}

cc -O0 -o test test.c

вроде разобрался: часто используемые элементы лучше размещать на вершине структуры

[Bizdelnick]

test.c

Хм, действительно, если использовать gcc, вариант, когда массив в начале структуры, быстрее. Если использовать clang, разница пренебрежимо мала.

[drBatty]

часто используемые элементы лучше размещать на вершине структуры

В общем случае — как повезёт. В данном конкретном случае очевидно ускорение достигается за счёт того, что int b[BLEN]; оказался ближе к вершине стека. А вершина стека практически всегда в L1. Если задвинуть int b[BLEN]; подальше, то оно уже не будет в L1, а окажется в L2(потому что вершина стека по любому в L1, а этот L1 очень маленький, и второй массив туда уже не влезет)

Возможно также, что вам повезло с выравниванием: gcc не может очень хорошо выравнивать внутренности структуры, т.к. это приведёт к большим дырам. Но саму структуру он в принципе может попытаться выровнять.

[drBatty]

когда структура вначале

Код: Выделить всё

080483fd <f1>:
 80483fd:   55                      push   ebp
 80483fe:   89 e5                   mov    ebp,esp
 8048400:   83 ec 10                sub    esp,0x10
 8048403:   c7 45 fc 00 00 00 00    mov    DWORD PTR [ebp-0x4],0x0
 804840a:   eb 18                   jmp    8048424 <f1+0x27>
 804840c:   8b 45 08                mov    eax,DWORD PTR [ebp+0x8]
 804840f:   8b 55 fc                mov    edx,DWORD PTR [ebp-0x4]
 8048412:   8b 04 90                mov    eax,DWORD PTR [eax+edx*4]
 8048415:   8d 48 01                lea    ecx,[eax+0x1]
 8048418:   8b 45 08                mov    eax,DWORD PTR [ebp+0x8]
 804841b:   8b 55 fc                mov    edx,DWORD PTR [ebp-0x4]
 804841e:   89 0c 90                mov    DWORD PTR [eax+edx*4],ecx
 8048421:   ff 45 fc                inc    DWORD PTR [ebp-0x4]
 8048424:   83 7d fc 63             cmp    DWORD PTR [ebp-0x4],0x63
 8048428:   7e e2                   jle    804840c <f1+0xf>
 804842a:   c9                      leave
 804842b:   c3                      ret

когда в конце

Код: Выделить всё

080483fd <f1>:
 80483fd:   55                      push   ebp
 80483fe:   89 e5                   mov    ebp,esp
 8048400:   83 ec 10                sub    esp,0x10
 8048403:   c7 45 fc 00 00 00 00    mov    DWORD PTR [ebp-0x4],0x0
 804840a:   eb 24                   jmp    8048430 <f1+0x33>
 804840c:   8b 45 08                mov    eax,DWORD PTR [ebp+0x8]
 804840f:   8b 55 fc                mov    edx,DWORD PTR [ebp-0x4]
 8048412:   81 c2 00 01 00 00       add    edx,0x100
 8048418:   8b 04 90                mov    eax,DWORD PTR [eax+edx*4]
 804841b:   8d 48 01                lea    ecx,[eax+0x1]
 804841e:   8b 45 08                mov    eax,DWORD PTR [ebp+0x8]
 8048421:   8b 55 fc                mov    edx,DWORD PTR [ebp-0x4]
 8048424:   81 c2 00 01 00 00       add    edx,0x100
 804842a:   89 0c 90                mov    DWORD PTR [eax+edx*4],ecx
 804842d:   ff 45 fc                inc    DWORD PTR [ebp-0x4]
 8048430:   83 7d fc 63             cmp    DWORD PTR [ebp-0x4],0x63
 8048434:   7e d6                   jle    804840c <f1+0xf>
 8048436:   c9                      leave
 8048437:   c3                      ret

т.е. она к индексу добавляет 256 (это как раз 1024 char'а), причём делает это каждый раз в цикле. Т.е. приходится хранить в кеше И ячейки из стека (она какждый раз читает [ebp±]), И ячейки через 1024 байта после стека.

Если сделать -O2, то код будет одинаковым

Код: Выделить всё

 80482d5:   bb 80 c3 c9 01          mov    ebx,0x1c9c380
 80482da:   31 d2                   xor    edx,edx
 80482dc:   8d 8c 24 9c 05 00 00    lea    ecx,[esp+0x59c]
 80482e3:   8d b6 00 00 00 00       lea    esi,[esi+0x0]
 80482e9:   8d bc 27 00 00 00 00    lea    edi,[edi+eiz*1+0x0]
 80482f0:   8d 84 24 0c 04 00 00    lea    eax,[esp+0x40c]
 80482f7:   eb 09                   jmp    8048302 <main+0x42>
 80482f9:   8d b4 26 00 00 00 00    lea    esi,[esi+eiz*1+0x0]
 8048300:   8b 10                   mov    edx,DWORD PTR [eax]
 8048302:   42                      inc    edx
 8048303:   89 10                   mov    DWORD PTR [eax],edx
 8048305:   83 c0 04                add    eax,0x4
 8048308:   39 c8                   cmp    eax,ecx
 804830a:   75 f4                   jne    8048300 <main+0x40>
 804830c:   4b                      dec    ebx
 804830d:   74 09                   je     8048318 <main+0x58>
 804830f:   8b 94 24 0c 04 00 00    mov    edx,DWORD PTR [esp+0x40c]

как и время работы.

Вывод: проблема только в -O0 и разном коде (в одном случае нужно прибавлять смещение, в другом не нужно).