Сказ про 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. В следующий раз мы продолжим ломать стереотипы и взрывать мозг. Удачного программинга ^_~
Отправить комментарий