illumium.org

Главная › Блоги › Блог kayo

Сказ про GCC и продвинутые вычисления во время компиляции

kayo — Чт, 17/12/2015 - 04:02

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

Постойте, речь же идёт не о продвинутых языках типа C++, D или Haskell, а всего-навсего о языке C! Да-да, нет никакой ошибки, в этот раз мы будем рушить стереотипы. Мы заставим известный компилятор языка C из коллекции GNU извиваться змеёю, и вычислять функции с циклами во время компиляции.

Задача

В процессе разработки встраиваемого HTTP-сервера Marten в целях экономии ресурсов и упрощения реализации было принято решение использовать хэши вместо строк для быстрой выборки полей из запросов. Это означало буквально следующее:

  • В процессе приёма вместо сохранения строки некоторого поля сервер считает хэш
  • Вместо сравнения строки поля со строками нужных полей обработчик сравнивает вычисленный хэш с имеющимися хэшами этих полей

К примеру, нас интересует заголовок Content-Length запроса. Сервер считает хэш поля заголовка, затем вызывается обработчик, у которого есть посчитанные хэши, используемых в приложении полей.

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

Решение

Первый блин

Изначально предполагалось использовать отдельный препроцессор типа M4, но с ним дело не пошло, слишком специфичная и архаичная штукенция. Затем я даже написал свой препроцессор на Lua. За основу была взята функция хэширования djb2, очень простая в вычислении и имеющая достаточно равномерное распределение с магическим множителем 33.

Второй блин

И всё было хорошо, но мне не давала покоя мысль, что такие вещи должен и обязан делать сам компилятор. Сначала я сделал несколько предположений, которые оказались ошибочными и не особенно помогли. Вот мой первый вариант реализации на языке C:

#include <stdint.h>

typedef uint32_t marten_hash_t;

static inline marten_hash_t marten_hash_cstr(const char *s) {
  marten_hash_t h = 5381;
  for (; *s != '\0'; s++)
    h = h * 33 + *s;
  return h;
}

/* тестируем */
#include <stdio.h>
 
int main() {
#define test(s) printf("The djb2 hash of " #s " is a %u\n", marten_hash_cstr(#s))
  
  test(POST);
  test(/path/to/file);
  test(Content-Length);
}

Компилируем:

$ gcc-4.9 -o hash_test -O2 hash_test.c

Запускаем и убеждаемся, что всё работает:

$ ./hash_test 
The djb2 hash of POST is a 2089437419
The djb2 hash of /path/to/file is a 1632746786
The djb2 hash of Content-Length is a 1662858543

Проверяем наличие строк в исполняемом файле:

$ strings hash_test | grep '^\(POST\|/path/to/file\|Content-Length\)'
POST
/path/to/file
Content-Length

Строки есть, а мы ведь хотели вычислить от них хэши в процессе компиляции.

Третий блин

Итак, давайте разбираться, что же здесь может быть не так. Во-первых, чтобы вычисляемые выражения были константными, всё, что участвует в вычислении должно быть константами. Во-вторых, не должно быть неоднозначных условий и не развёрнутых циклов.

В данном случае проблема очевидна, это условие продолжения итераций *s != '\0', которое не однозначно разрешимо в момент компиляции и не позволяет развернуть цикл. Что мы можем с этим сделать? Поскольку константные строки это ничто иное как массивы символов, то размеры этих массивов нам заведомо известны. Мы всего-лишь должны передавать в функцию эти размеры, чтобы все вычисления внутри неё были однозначно предопределены.

Вот, что у меня получилось:

#include <stdint.h>

typedef uint32_t marten_hash_t;

/* вспомогательный макрос */
#define marten_hash_cstr(s) _marten_hash_cstr(s, sizeof(s) - 1)
static inline marten_hash_t _marten_hash_cstr(const char *s, size_t l) {
  const char *e = s + l; /* конец строки */
  marten_hash_t h = 5381;
  for (; s < e; s++)
    h = h * 33 + *s;
  return h;
}

/* тестируем */
#include <stdio.h>
 
int main() {
#define test(s) printf("The djb2 hash of " #s " is a %u\n", marten_hash_cstr(#s))
  
  test(POST);
  test(/path/to/file);
  test(Content-Length);
}

Запускаем и убеждаемся, что всё по-прежнему работает:

$ ./hash_test 
The djb2 hash of POST is a 2089437419
The djb2 hash of /path/to/file is a 1632746786
The djb2 hash of Content-Length is a 1662858543

Проверяем наличие строк в исполняемом файле:

$ strings hash_test | grep '^\(POST\|/path/to/file\|Content-Length\)'
POST
/path/to/file
Content-Length

Не может быть, строки всё ещё присутствуют, а ведь на этот раз мы всё правильно сделали.

Теперь уже не комом

Как это часто бывает, решение лежало на поверхности. Попробуем собрать с -O3 вместо -O2 и снова проверим:

$ strings hash_test | grep '^\(POST\|/path/to/file\|Content-Length\)'

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

$ gcc-4.9 -S -o hash_test.s -O3 hash_test.c

Вот что у нас внутри, убедитесь, что значения хешей именно те, что мы ожидали:

        .file   "hash_test.c"
        .section        .rodata.str1.8,"aMS",@progbits,1
        .align 8
.LC0:
        .string "The djb2 hash of POST is a 0x%08x\n"
        .align 8
.LC1:
        .string "The djb2 hash of /path/to/file is a 0x%08x\n"
        .align 8
.LC2:
        .string "The djb2 hash of Content-Length is a 0x%08x\n"
        .section        .text.unlikely,"ax",@progbits
.LCOLDB3:
        .section        .text.startup,"ax",@progbits
.LHOTB3:
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB12:
        .cfi_startproc
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $2089437419, %esi
        movl    $.LC0, %edi
        xorl    %eax, %eax
        call    printf
        movl    $1632746786, %esi
        movl    $.LC1, %edi
        xorl    %eax, %eax
        call    printf
        movl    $1662858543, %esi
        movl    $.LC2, %edi
        xorl    %eax, %eax
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        jmp     printf
        .cfi_endproc
.LFE12:
        .size   main, .-main
        .section        .text.unlikely
.LCOLDE3:
        .section        .text.startup
.LHOTE3:
        .ident  "GCC: (Debian 4.9.2-10) 4.9.2"
        .section        .note.GNU-stack,"",@progbits

Заветные строчки (24, 28, 32) с вычисленными хэшами на своих местах! Сравните с листингом первоначального варианта, где строчки и код вычисления хэшей присутствуют:

        .file   "hash_test.c"
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "POST"
.LC1:
        .string "/path/to/file"
.LC2:
        .string "Content-Length"
        .section        .rodata.str1.8,"aMS",@progbits,1
        .align 8
.LC3:
        .string "The djb2 hash of Content-Length is a 0x%08x\n"
        .align 8
.LC4:
        .string "The djb2 hash of POST is a 0x%08x\n"
        .align 8
.LC5:
        .string "The djb2 hash of /path/to/file is a 0x%08x\n"
        .section        .text.unlikely,"ax",@progbits
.LCOLDB6:
        .section        .text.startup,"ax",@progbits
.LHOTB6:
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB12:
        .cfi_startproc
        movl    $.LC0, %edx
        movl    $80, %eax
        movl    $5381, %esi
        .p2align 4,,10
        .p2align 3
.L2:
        movl    %esi, %ecx
        addq    $1, %rdx
        sall    $5, %ecx
        addl    %ecx, %esi
        addl    %eax, %esi
        movsbl  (%rdx), %eax
        testb   %al, %al
        jne     .L2
        subq    $8, %rsp
        .cfi_def_cfa_offset 16
        movl    $.LC4, %edi
        xorl    %eax, %eax
        call    printf
        movl    $.LC1, %edx
        movl    $47, %eax
        movl    $5381, %esi
        .p2align 4,,10
        .p2align 3
.L4:
        movl    %esi, %ecx
        addq    $1, %rdx
        sall    $5, %ecx
        addl    %ecx, %esi
        addl    %eax, %esi
        movsbl  (%rdx), %eax
        testb   %al, %al
        jne     .L4
        movl    $.LC5, %edi
        xorl    %eax, %eax
        call    printf
        movl    $.LC2, %edx
        movl    $67, %eax
        movl    $5381, %esi
        .p2align 4,,10
        .p2align 3
.L6:
        movl    %esi, %ecx
        addq    $1, %rdx
        sall    $5, %ecx
        addl    %ecx, %esi
        addl    %eax, %esi
        movsbl  (%rdx), %eax
        testb   %al, %al
        jne     .L6
        movl    $.LC3, %edi
        addq    $8, %rsp
        .cfi_def_cfa_offset 8
        jmp     printf
        .cfi_endproc
.LFE12:
        .size   main, .-main
        .section        .text.unlikely
.LCOLDE6:
        .section        .text.startup
.LHOTE6:
        .ident  "GCC: (Debian 4.9.2-10) 4.9.2"
        .section        .note.GNU-stack,"",@progbits

Может показаться, что и первый вариант даст то, что нам нужно, если собрать с -O3, но это, к сожалению, не так. GCC не на столько хитёр, чтобы развернуть цикл с неоднозначным условием завершения. Вот вам домашнее задание это проверить. А сейчас проверим, как обстоит дело с компиляцией для архитектуры ARM:

$ arm-none-eabi-gcc-4.9 -S -o hash_test.s -O3 hash_test.c

Вот листинг, можете убедиться, что значения вычисленных хэшей совпадают со значениями из листинга для архитектуры x86:

        .cpu arm7tdmi
        .fpu softvfp
        .eabi_attribute 20, 1
        .eabi_attribute 21, 1
        .eabi_attribute 23, 3
        .eabi_attribute 24, 1
        .eabi_attribute 25, 1
        .eabi_attribute 26, 1
        .eabi_attribute 30, 2
        .eabi_attribute 34, 0
        .eabi_attribute 18, 4
        .file   "hash_test.c"
        .section        .text.startup,"ax",%progbits
        .align  2
        .global main
        .type   main, %function
main:
        @ Function supports interworking.
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        stmfd   sp!, {r3, lr}
        ldr     r1, .L3
        ldr     r0, .L3+4
        bl      printf
        ldr     r1, .L3+8
        ldr     r0, .L3+12
        bl      printf
        ldr     r0, .L3+16
        ldr     r1, .L3+20
        bl      printf
        ldmfd   sp!, {r3, lr}
        bx      lr
.L4:
        .align  2
.L3:
        .word   2089437419
        .word   .LC0
        .word   1632746786
        .word   .LC1
        .word   .LC2
        .word   1662858543
        .size   main, .-main
        .section        .rodata.str1.4,"aMS",%progbits,1
        .align  2
.LC0:
        .ascii  "The djb2 hash of POST is a 0x%08x\012\000"
        .space  1
.LC1:
        .ascii  "The djb2 hash of /path/to/file is a 0x%08x\012\000"
.LC2:
        .ascii  "The djb2 hash of Content-Length is a 0x%08x\012\000"
        .ident  "GCC: (4.9.2-10+14~bpo8+1) 4.9.2"

Сравним с изначальным вариантом, в котором хэши не вычислились:

        .cpu arm7tdmi
        .fpu softvfp
        .eabi_attribute 20, 1
        .eabi_attribute 21, 1
        .eabi_attribute 23, 3
        .eabi_attribute 24, 1
        .eabi_attribute 25, 1
        .eabi_attribute 26, 1
        .eabi_attribute 30, 2
        .eabi_attribute 34, 0
        .eabi_attribute 18, 4
        .file   "hash_test.c"
        .section        .text.startup,"ax",%progbits
        .align  2
        .global main
        .type   main, %function
main:
        @ Function supports interworking.
        @ args = 0, pretend = 0, frame = 0
        @ frame_needed = 0, uses_anonymous_args = 0
        stmfd   sp!, {r3, lr}
        mov     r3, #80
        ldr     r2, .L19
        ldr     r1, .L19+4
.L2:
        add     r1, r1, r1, asl #5
        add     r1, r3, r1
        ldrb    r3, [r2, #1]!   @ zero_extendqisi2
        cmp     r3, #0
        bne     .L2
        ldr     r0, .L19+8
        bl      printf
        mov     r3, #47
        ldr     r2, .L19+12
        ldr     r1, .L19+4
.L4:
        add     r1, r1, r1, asl #5
        add     r1, r3, r1
        ldrb    r3, [r2, #1]!   @ zero_extendqisi2
        cmp     r3, #0
        bne     .L4
        ldr     r0, .L19+16
        bl      printf
        mov     r3, #67
        ldr     r2, .L19+20
        ldr     r1, .L19+4
.L6:
        add     r1, r1, r1, asl #5
        add     r1, r3, r1
        ldrb    r3, [r2, #1]!   @ zero_extendqisi2
        cmp     r3, #0
        bne     .L6
        ldr     r0, .L19+24
        bl      printf
        mov     r0, #0
        ldmfd   sp!, {r3, lr}
        bx      lr
.L20:
        .align  2
.L19:
        .word   .LC0
        .word   5381
        .word   .LC4
        .word   .LC1
        .word   .LC5
        .word   .LC2
        .word   .LC3
        .size   main, .-main
        .section        .rodata.str1.4,"aMS",%progbits,1
        .align  2
.LC0:
        .ascii  "POST\000"
        .space  3
.LC1:
        .ascii  "/path/to/file\000"
        .space  2
.LC2:
        .ascii  "Content-Length\000"
        .space  1
.LC3:
        .ascii  "The djb2 hash of Content-Length is a 0x%08x\012\000"
        .space  3
.LC4:
        .ascii  "The djb2 hash of POST is a 0x%08x\012\000"
        .space  1
.LC5:
        .ascii  "The djb2 hash of /path/to/file is a 0x%08x\012\000"
        .ident  "GCC: (4.9.2-10+14~bpo8+1) 4.9.2"

Ещё лучше, ещё универсальнее

Справедливости ради стоит отметить, что весь этот фокус возможно провернуть только с GCC версии 4.9 и выше, на 4.8 и ниже у меня это не сработало. Но позднее было найдено неожиданное решение. Дело в том, что GCC не любит лезть глубоко в код при оптимизации, поэтому я заменил функцию на макрос с параметром. Это дело стало выглядеть както так:

#include <stddef.h>
#include <stdint.h>

typedef uint32_t marten_hash_t;

#define marten_hash_cstr(s) ({    \
      typeof(sizeof(s)) i = 0;    \
      marten_hash_t h = 5381;     \
      for (; i < sizeof(s) - 1; ) \
        h = h * 33 + s[i++];      \
      h;                          \
    })

/* тестируем */
#include <stdio.h>
 
int main() {
#define test(s) printf("The djb2 hash of " #s " is a %u\n", marten_hash_cstr(#s))
  
  test(POST);
  test(/path/to/file);
  test(Content-Length);
}

Этот подход позволяет использовать вычисления во время компиляции также и с GCC версии 4.8, на более ранних не пробовал, но вполне возможно, что тоже будет работать.

Что удивительно, хэш вычислялся даже с -Os, но почему-то только для строки POST. Чем эта строка отличается от других? Правильно! Она намного короче их. Чтобы проверить эту гипотезу, я решил написать ещё тестов со строками GET и DELETE, и действительно: для GET хэш был подсчитан, а для DELETE нет. Очевидно, что всё дело было в лимитах на развёртку цикла. Например, с -O2 все хэши благополучно вычислятся.

Чтобы заставить этот способ работать всегда, надо иметь возможность указать уровень оптимизации для конкретно этого фрагмента кода, но на сколько мне известно, ни один из способов, предлагаемый GCC в данный момент для этого не подходит.

Итог

Мы убедились, что модные штуки, вроде вычислений во время компиляции, не обошли стороной и нашу серебряную пулю, коей является язык C. В следующий раз мы продолжим ломать стереотипы и взрывать мозг. Удачного программинга ^_~

  • c
  • compile-time
  • gcc
  • компиляторы
  • оптимизация
  • хэши
  • Бортовой журнал Иллюмиума

Отправить комментарий

Содержимое этого поля является приватным и не будет отображаться публично.
  • Доступные HTML теги: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Syntax highlight code surrounded by the {syntaxhighlighter SPEC}...{/syntaxhighlighter} tags, where SPEC is a Syntaxhighlighter options string or "class="OPTIONS" title="the title".

Подробнее о форматировании

CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.
  ____           __   __  _____   _      ____  
| _ \ __ _ \ \ / / |___ | | | __ | __ )
| | | | / _` | \ V / / / | |/ / | _ \
| |_| | | (_| | | | / / | < | |_) |
|____/ \__,_| |_| /_/ |_|\_\ |____/
Введите код, изображенный в стиле ASCII-арт.
RSS-материал

Навигация

  • Подшивки
  • Фотоальбомы

«Иллюмиум» на якоре.

Работает на Drupal, система с открытым исходным кодом.

(L) 2010, Illumium.Org. All rights reversed ^_~