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

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