Где можно снизить производительность, а не оптимизировать ее?

Question

Пожалуйста, взгляните на следующий фрагмент кода

#define HF_ND_SZ sizeof(struct huffman_node)
#define TSIZE_MAX 256

struct huffman_node * build_decomp_huffman_tree(uint64_t *table, int size) {
    static struct huffman_node huffman_node_list2[TSIZE_MAX * 3];
    int i = 0, j = 0;
    int k = TSIZE_MAX * 2; // this is the case point 1
    //...//
    for (i = 0; i < size - 1; i++) {
        huffman_node_list2[k + i] = huffman_node_list2[i + 1]; // point 2
        huffman_node_list2[TSIZE_MAX + i].right = &huffman_node_list2[k+ i];
    // ... //
    }
    return &huffman_node_list2[size - 1];
}

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

Я хочу, чтобы, если мы определяем точку 1 как const int k = TSIZE_MAX * 2;, то происходит ли какая-либо оптимизация в точке 2 или 3 , где происходит присвоение смежным данным (массиву)) huffman_node_list2[k + i] = huffman_node_list2[i + 1];?

(Пожалуйста, имейте в виду и исправьте мое предположение, если оно неверно, я подумал, когда мы объявляем const в локальной или глобальной области видимости, оно создается как неизменяемое распределение памяти, если мы используем это постоянная память и выполненная математическая операция как в точка 2 или 3 ([k + i]) в структуре цикла, во время выполнения программа должна загрузить неизменяемая память на каждой итерации цикла и сохранение результата во временной ячейке памяти. Что если произойдет, если эта неизменная память имеет большой кусок, надеюсь, вы сможете понять мою идею, я прав?)

Answer 1

const вовсе не обязательно создает ячейку памяти, если вы не берете ее адрес.Они могут просто исчезнуть в потоке команд как константы непосредственного режима или быть добавлены в адреса во время компиляции или соединения.

Например, huffman_node_list2[k + i] = huffman_node_list2[i + 1] почти наверняка компилируется как huffman_node_list2[TSIZE_MAX * 2 + i] = huffman_node_list2[i + 1], где не толькоTSIZE_MAX * 2 оценивается во время компиляции, но huffman_node_list2+TSIZE_MAX*2 оценивается во время компоновки.

Answer 2

const может быть медленнее, если компилятор поместит его в раздел только для чтения .text достаточно далеко, что приведет к пропаданию кэша.

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

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

Есть хорошая статья о том, как разныеданные выкладываются здесь

Answer 3

Используя Visual C, я скомпилировал обе версии вашего кода: с const int k и без const.Флаг /FA создает код машины в файле .asm, читаемом (некоторым) человеком.Флаги оптимизации не использовались.

Результат: оптимизации нет, разницы нет.Полученный машинный код точно такой же:

; Listing generated by Microsoft (R) Optimizing Compiler Version 19.00.24231.0 

    TITLE   opt_const.c
    .686P
    .XMM
    include listing.inc
    .model  flat

INCLUDELIB LIBCMT
INCLUDELIB OLDNAMES

PUBLIC  _main
_BSS    SEGMENT
?huffman_node_list2@?1??main@@9@9 DB 01fd4H DUP (?) ; `main'::`2'::huffman_node_list2
_BSS    ENDS
; Function compile flags: /Odtp
; File c:\joël\tests\opt_const.c
_TEXT   SEGMENT
_j$ = -16                       ; size = 4
_size$ = -12                        ; size = 4
_k$ = -8                        ; size = 4
_i$ = -4                        ; size = 4
_argc$ = 8                      ; size = 4
_argv$ = 12                     ; size = 4
_main   PROC

; 10   : {

    push    ebp
    mov ebp, esp
    sub esp, 16                 ; 00000010H
    push    esi
    push    edi

; 11   :     static struct huffman_node huffman_node_list2[TSIZE_MAX * 3];
; 12   :     int i = 0, j = 0, size = 17;

    mov DWORD PTR _i$[ebp], 0
    mov DWORD PTR _j$[ebp], 0
    mov DWORD PTR _size$[ebp], 17       ; 00000011H

; 13   :     int k = TSIZE_MAX * 2; // this is the case point 1

    mov DWORD PTR _k$[ebp], 194         ; 000000c2H

; 14   :     //...//
; 15   :     for (i = 0; i < size - 1; i++) {

    mov DWORD PTR _i$[ebp], 0
    jmp SHORT $LN4@main
$LN2@main:
    mov eax, DWORD PTR _i$[ebp]
    add eax, 1
    mov DWORD PTR _i$[ebp], eax
$LN4@main:
    mov ecx, DWORD PTR _size$[ebp]
    sub ecx, 1
    cmp DWORD PTR _i$[ebp], ecx
    jge SHORT $LN3@main

; 16   :         huffman_node_list2[k + i] = huffman_node_list2[i + 1]; // point 2

    mov edx, DWORD PTR _i$[ebp]
    add edx, 1
    imul    esi, edx, 28
    add esi, OFFSET ?huffman_node_list2@?1??main@@9@9
    mov eax, DWORD PTR _k$[ebp]
    add eax, DWORD PTR _i$[ebp]
    imul    edi, eax, 28
    add edi, OFFSET ?huffman_node_list2@?1??main@@9@9
    mov ecx, 7
    rep movsd

; 17   :         huffman_node_list2[TSIZE_MAX + i].right = &huffman_node_list2[k+ i];

    mov ecx, DWORD PTR _k$[ebp]
    add ecx, DWORD PTR _i$[ebp]
    imul    edx, ecx, 28
    add edx, OFFSET ?huffman_node_list2@?1??main@@9@9
    mov eax, DWORD PTR _i$[ebp]
    add eax, 97                 ; 00000061H
    imul    ecx, eax, 28
    mov DWORD PTR ?huffman_node_list2@?1??main@@9@9[ecx], edx

; 18   :     // ... //
; 19   :     }

    jmp SHORT $LN2@main
$LN3@main:

; 20   :     return 0;

    xor eax, eax

; 21   : }

    pop edi
    pop esi
    mov esp, ebp
    pop ebp
    ret 0
_main   ENDP
_TEXT   ENDS
END

РЕДАКТИРОВАТЬ: я сделал тот же тест с флагами оптимизации gcc, -O3.И ... тот же результат: сгенерированный ассемблерный код снова строго одинаков с ключевым словом const и без него.

        .file       "opt_const.c"
        .section    .text.unlikely,"ax",@progbits
.LCOLDB0:
        .section    .text.startup,"ax",@progbits
.LHOTB0:
        .p2align 4,,15
        .globl      main
        .type       main, @function
main:
.LFB23:
        .cfi_startproc
        movl        $huffman_node_list2.2488+16384, %eax
        .p2align 4,,10
        .p2align 3
.L2:
        movq        -16352(%rax), %rdx
        movq        %rax, -8192(%rax)
        addq        $32, %rax
        movq        %rdx, -32(%rax)
        movq        -16376(%rax), %rdx
        movq        %rdx, -24(%rax)
        movq        -16368(%rax), %rdx
        movq        %rdx, -16(%rax)
        movq        -16360(%rax), %rdx
        movq        %rdx, -8(%rax)
        cmpq        $huffman_node_list2.2488+17088, %rax
        jne .L2
        xorl        %eax, %eax
        ret
        .cfi_endproc
.LFE23:
        .size       main, .-main
        .section    .text.unlikely
.LCOLDE0:
        .section    .text.startup
.LHOTE0:
        .local      huffman_node_list2.2488
        .comm       huffman_node_list2.2488,24576,32
        .ident      "GCC: (Ubuntu 5.4.0-6ubuntu1~16.04.9) 5.4.0 20160609"
        .section    .note.GNU-stack,"",@progbits