Вычисление CRC32 строк в compile-time

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

Локализация здесь осуществляется довольно нехитро. Все строки, требующие перевода, оборачиваются в макрос _TR():
wprintf(L"%s\n", _TR("Some translating string"));

Макрос возвращает нужную версию текста в зависимости от текущего используемого языка. Определён он следующим образом:
#define _TR(x) g_Translator.Translate(x)

Здесь происходит обращение к глобальному объекту g_Translator, который в функции Translate() считает в рантайме crc32 от указанной строки, ищет в своей xml-базе перевод с совпадающей контрольной суммой и возвращает его.

Не буду судить насколько такое решение оправдано, но оно проверено временем и показало себя достаточно надёжным. И всё бы ничего, но такое решение не лишено недостатков: по сути, функция делает лишнюю работу — контрольные суммы можно было бы подсчитать один раз на этапе компиляции, и использовать в дальнейшем уже готовые числовые значения. Это также избавило бы от необходимости хранить в исполняемом образе дублирующиеся строки, ведь они уже есть во внешнем xml-файле с переводами.

Немного погуглив по запросу «compile-time crc32» я быстро понял, что задача это не самая тривиальная, а готовых решений мне найти так и не удалось.

Использовать шаблонное метапрограммирование в чистом виде здесь, к сожалению, не получится. Любое обращение к символам строки, используемой в качестве параметра шаблона, не даёт компилятору свернуть рекурсивные вызовы шаблонной функции. Напрмер, в этой статье рассматривается создание только таблицы для расчётов crc32. А из полностью standard-compliant решений нашлось только одно — Boost.MPL. Здесь предлагается использовать следующую форму записи:
meta::hash_cstring< mpl::string<'bunn','ies'> >::value;

Вместо использования строковых литералов предлагается разбивать строку на кусочки и отдавать отдельными параметрами шаблона. Но помимо причудливости используемой записи, чтобы преобразовать все 2450 строк проекта к такому виду, пришлось бы писать внешний кодогенератор и учить всю команду проекта новой форме записи.
Проскакивали на форумах также сообщения, что в новом C++11 эта идея реализуема с использованием классического шаблонного метапрограммирования и ключевого слова constexpr, но, к сожалению, так просто перевести проект с длинной родословной на новый стандарт не представляется возможным.

Была и другая идея с использованием кодогенератора. Можно было бы сделать pre-build event, на котором приводить переводимые строки к такому виду:
_TR(0x12345678/*"Some hashing string"*/);

Но опять же, хотелось чего-то универсального… Хотелось такой волшебный _TR(), который просто оставит после себя чистый crc32 без лишних телодвижений. И тогда я начал изобретать свой велосипед.

Попытка №1. Чистые макросы


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

Я создал новый проект в Visual Studio, выставив настройки оптимизации на максимальный inline и максимальную скорость. Анализировать успешность/неуспешность свёртывания строк до хеша я решил в известном user-mode отладчике OllyDbg, поэтому хотелось бы видеть в результирующем ехе только по одной маленькой секции на код и данные без лишнего мусора. Для этого я отключил С-runtime, что вкупе с несколькими другими приёмчиками позволило на выходе получить пустой ехе размером всего 2 Кб.

После нескольких экспериментов я выдал простейшую реализацию расчёта crc32 для строк не более 3 символов:
static const unsigned int Crc32Table[256] = {
	0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
	0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
	0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
	/* ... ,*/
	0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
};

template <typename T, int N>
char (&array_length(T (&)[N]))[N];
// используется для нахождения длины строкового литерала
#define lengthof(x) (sizeof(array_length(x)))

// стандартная итерация расчёта crc32
#define TR_CRC(crc,i,s) (crc >> 8)^Crc32Table[(crc^s[i])&0xFF]

// расчитываем очередной символ только если еще не был достигнут конец строки
#define TR_CRC_COND(crc,i,s) (i<lengthof(s)-1 ? TR_CRC(crc,i,s):crc)

// окончательный расчёт CRC с помощью вложенных макросов (максимально 3 символа)
#define _TR(s) TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)^0xFFFFFFFF

int main(int argc, char *argv[])
{
	// Первая пришедшая в голову функция, принимающая один параметр - DWORD,
	// чтобы результат не проглотил оптимизатор и его можно было легко найти в Olly
	Sleep(_TR("123"));
}

В реализации макросами основная проблема заключается в том, что мы не можем развернуть цикл расчёта crc на нужное количество итераций по длине строки, как в шаблонном метапрограммировании. Макрос всегда будет пересчитывать столько итераций, сколько в него заложить изначально. Например, в примере выше строка «1» всё равно бы просчитывалась в 4 итерации (максимальные 3 символа + '\0'), несмотря на то, что длина у неё всего один символ. Обходится это условной операцией, которая подсовывает значение crc с предыдущей итерации, в случае если строка уже просчитана до последнего символа.

Запустив полученный ехе в отладчике, я увидел заветное PUSH 884863D2, правильность расчёта которого легко подтверждается первым попавшимся онлайн-калькулятором crc32.



Пришло время посмотреть насколько сильно упадёт скорость компиляции, если растиражировать макрос на длину строки, позволявшей покрыть требования проекта. Самая длинная строка в базе переводов была чуть короче 350 символов, так что хотелось заложиться хотя бы на предел в 500 символов.

Таким образом, я сгенерировал тело макроса, в сокращённой форме выглядившее примерно так:
#define _TR(s) TR_CRC_COND(TR_CRC_COND(/*...*/TR_CRC_COND(TR_CRC_COND(0xFFFFFFFF,0,s),1,s),2,s),3,s)/*...*/,448,s),449,s)^0xFFFFFFFF

Но тут меня ждало разочарование, когда компилятор выдал своё холодное: «fatal error C1009: compiler limit: macros nested too deeply». Опытным путём тогда удалось выяснить, что предел вложенности находится где-то в районе 300.

Попытка №2. Функция __forceinline


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

После всех мучений я практически был готов отказаться от этой идеи, но всё же решил попробовать написать одну большую __forceinline функцию с кучей последовательных расчётов и проверками длины строки (я почему-то был уверен, что такое компилятор никогда в жизни не свернёт в константу):
// Выполняем итерацию, если еще не достигли конца строки
#define CRC_STUB_(i) if (i<N-1) { crc = (crc>>8) ^ Crc32Table[(crc^s[i])&0xFF] }

template <int N>
static __forceinline DWORD CRC_ARR_CALC_(const char (&s)[N])
{
	static const unsigned int Crc32Table[256] = {
		0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
		0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3,
		0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
		/* ... ,*/
		0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D
	};
	DWORD crc = 0;
	CRC_STUB_(0);CRC_STUB_(1);CRC_STUB_(2);CRC_STUB_(3);CRC_STUB_(4);CRC_STUB_(5);CRC_STUB_(6);CRC_STUB_(7);CRC_STUB_(8);CRC_STUB_(9);CRC_STUB_(10);CRC_STUB_(11);CRC_STUB_(12);CRC_STUB_(13);CRC_STUB_(14);CRC_STUB_(15);CRC_STUB_(16);CRC_STUB_(17); /* ... */ CRC_STUB_(498);CRC_STUB_(499);
	return crc;
}

И это сработало! Компилятор довольно шустро сворачивал весь код в одно число, не оставляя в результирующем бинарнике ни самих строк, ни даже таблицу Crc32Table. Для правильной компиляции такой реализации достаточно только ключа /O2. Оставалось только дописать перегруженную версию метода g_Translator.Translate() с crc32 в качестве параметра, и дело в шляпе.

После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб, и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольше :)

Полный исходник к тестовому проекту можно взять здесь: 7z, tar.gz
Поделиться публикацией
Похожие публикации
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама
Комментарии 35
  • 0
    Интересный подход! Но ведь в реальных проектах оптимизация часто не превышает O2, а также используется C-runtime. В таких условиях можно получить crc32 от строк на этапе компиляции?
    • +1
      Рантайм был отключен только для теста, чтобы выходной ехе получился без мусора. В реальном проекте использовался O2, и само собой с рантаймом)
    • 0
      Не понимаю, почему бинарник «похудел» на 200 Кб. Прокомментируйте, пожалуйста.

      и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольше
      Как проводились измерения, и насколько выраженной получилась экономия энергии?
      • +1
        Бинарник похудел за счет того, что компилятор больше не засовывает в него строки, а хранит контрольные суммы.
        • 0
          А что не понятно? Вместо длинных строк теперь везде обычный int32, видимо много строк у него было в бинарнике, вот и «похудел».
          • +1
            Ну разве что действительно очень много строк.
            На 30000 строках шанс коллизии crc32 — 10%.
            • 0
              На данный момент в проекте около 2500 строк. Если вдруг начнут учащаться коллизии не исключено, что придется увеличивать длину хеша.
          • 0
            Про экономию энергии я написал больше в шутку :) Естественно, что на фоне общей работы приложения затраты на расчёт контрольной суммы будут практически незаметны.
            • 0
              В таком случае, декларируемые преимущества не слишком значительны. А значительное раздувание кода в дебаге кажется мне заметным недостатком.
              • 0
                В таком случае, декларируемые преимущества не слишком значительны.
                А руководство такой задачи мне и не ставило) решить её мне захотелось, потому что в своё время я уже сталкивался с такой проблемой, и тогда приходилось пользоваться внешним кодогенератором.
                А значительное раздувание кода в дебаге кажется мне заметным недостатком.
                В дебаге используется ifdef, по которому включается старая реализация.
          • +1
            Проверяли в других компиляторах (gcc, clang), как там с этим дела обстоят?
            • 0
              К сожалению, конкретно эта реализация на других компиляторах работать не будет, поскольку использует microsoft-specific ключевое слово __forceinline. Без него компилятор увидит, что реализация слишком большая для инлайна и откажется от попыток её дальнейшей оптимизации.
              • 0
                Я бы проверил на gcc и llvm, но ставить ради этого 7z мне лень.
              • 0
                Что любопытно, ключевое слово inline компилятор успешно игнорирует, считая что он умнее)
                • +5
                  Для gcc можно попробовать __attribute__((always_inline))
                  • +3
                    gcc и clang поддерживают constexpr'ы. По этому большой необходимости в трюках с __forceinline и их аналогами нет.
                • +4
                  А вот в языке D можно задавать функции, которые будут вычисляться в compile-time. Например, рассчитывать хеши строк-индексов для ассоциативного массива в момент компиляции, разве это не чудесно? Насколько далеко этот язык впереди порядком устревшего Си.

                  И странно, что вы озаботились оптимизацией вычисления crc32 (что делается быстро), но не оптимизацией парсинга XML с переводами. Вам не кажется, что логичнее было бы в момент компиляции превращать тяжелый, трудноразбираемый XML-файл в компактную бинарную хеш-таблицу с временем поиска O(1)? Мне кажется, выгоды и в объеме, и в скорости работы программы было бы больше.

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

                  Ну или использовать бибилиотеку gettext(), если лень писать свою реализацию.
                  • –1
                    Вы правы, xml грузится на стадии запуска приложения как раз-таки в компактную хеш-таблицу) Решил не забивать подробностями повествование.
                    И «понабрали в мейл ру» достаточно толковых людей. Не нужно забывать что Агент — это проект с большой историей, и многие архитектурные решения были продиктованы историческими соображениями.
                    • 0
                      >А вот в языке D можно задавать функции, которые будут вычисляться в compile-time. Например, рассчитывать хеши строк-индексов для ассоциативного массива в момент компиляции, разве это не чудесно? Насколько далеко этот язык впереди порядком устревшего Си.

                      привет constexpr! Хотя его в принципе с D и спионерили честно)
                    • +1
                      Сделал попытку №3.

                      Реализация через класс с шаблонным методом вычисления хеша (длина строки в качестве параметра шаблона).
                      Проверял в MSVC 2010 ЕЕ — на выходе так же одно число.
                      К сожалению, время сборки тестового приложения с одной строкой из 500 символов занимает умопомрачительные 63425 мс на четырехъядерном i5-2400.

                      Ну и эпикфейл — всё волшебство прекращается, как только пытаешься вычислить хеш второй строки: все скатывается к обычным call'ам соответствующих методов.

                      Впрочем, стоит, наверное, еще поковыряться.
                      • –1
                        Тихий ужас. Что будет, если CRC у двух разных исходных строк совпадёт? Только не говорите мне, что это маловероятно.
                        • +3
                          А чем вам не понравился стандартный подход уникальный ID -> строка, зачем нужны все эти crc, которые к тому же имеют свойство впадать в коллизии? Как вы отлавливаете коллизии, и что будете делать, если они возникнут?
                          • +4
                            Товарищи, статья вовсе не об оправданности выбора архитектурного решения. Оно внедрено в проект уже много лет назад, когда количество строк в проекте исчислялось десятками, а я частенько прогуливал школу в ближайшем компьютерном клубе…
                            Я взял конкретную прикладную задачу, решение которой до этого момента не было освещено в интернете, и описал свои исследования по этой теме.

                            Отвечая на ваш вопрос, скорее всего проблемы коллизий будут решаться банальной заменой crc32 на crc64. Но на данный момент такая проблема попросту неактуальна.
                            • +1
                              А если в х64 тоже коллизии будут (с расчетом на худшее)? :)

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

                              Что же касается compile time crc, то его действительно лучше сделать на constexpr (которых, к сожалению, пока нету в студии).

                              Ну а в их отсутствие можно сделать хотя бы так:
                              include "StdAfx.h"
                               
                              template< int >
                              inline __int32 crc32( const char *)
                              {
                                  static __int32 crc = 42; // insert crc calculation here
                                  return crc;
                              }
                               
                              #define CRC32( STRING ) crc32< __COUNTER__ >( STRING )
                               
                              void main ()
                              {
                                  std::cout << CRC32( "a" ) << std::endl;
                                  std::cout << CRC32( "b" ) << std::endl;
                              }

                              В каждой точке хеш будет вычисляться только один раз. Для производительности этого вполне достаточно.
                              • 0
                                Схему с использованием предопределённого макроса __COUNTER__ я рассматривал, но проблема возникает, когда модулей в программе больше, чем один. Порядок компиляции модулей непостоянен, и хеши собьются при малейших перестановках.
                                • 0
                                  А пардон… Тут имеется в виду что вычисление будет в рантайме, но только при первом обращении…
                                  Да, такое будет работать, но строки всё равно будут присутствовать в ехе. Ну и хотелось бы, чтобы расчёт происходил всё же полностью во время компиляции.
                                  • 0
                                    Вам жалко 200 Кб под строки, которые к тому же замечательно пожмутся инсталлом или тактов процессора на расчет хеша при первом обращении?

                                    Ни то ни другое существенного влияния на производительность не оказывает.
                                    • 0
                                      Я перфекционист, и не люблю компромиссы, когда есть возможность сделать лучше :)
                                      И да, вы правы, в данном случае это никому ненужная борьба за такты. Но если бы это был серверный highload проект, где приходилось бы считать нечто подобное несколько десятков тысяч раз в секунду, то это бы имело значение.
                                      • 0
                                        Как у перфекциониста у вас должно быть жгучее желание убрать вообще нафиг все эти crc
                                        • 0
                                          Убрать все crc — задача явно не для кофе-брейка)
                                          Главный принцип больших проектов с плохим покрытием тестами: работает — не трогай. У меня была возможность с минимальным количеством изменений улучшить работу программы, и я это сделал. Любые более серьёзные изменения потребовали бы обширное ручное тестирование, цена которого бы превысила получаемые преимущества.
                                  • 0
                                    А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?
                                    это легко проверить, ровно один раз — в момент добавления строк в языковой пакет.
                              • +6
                                Собственно, на constexpr'ах это волшебство будет выглядеть так:
                                constexpr uint32_t CalcCRC32Impl(uint32_t prevCrc, const char* str)
                                {
                                    return !(*str) ? prevCrc : CalcCRC32Impl((prevCrc >> 8) ^ Crc32Table[(prevCrc ^ *str) & 0xff], str + 1);
                                }
                                
                                constexpr unsigned int CalcCRC32(const char* str)
                                {
                                    return CalcCRC32Impl(0xffffffff, str) ^ 0xffffffff;
                                }
                                

                                Проверка:
                                
                                template<int crc>
                                void PrintCrc()
                                {
                                    std::cout << crc << std::endl;
                                }
                                
                                PrintCrc<CalcCRC32("123")>();
                                


                                Печатает ожидаемое 884863d2.

                                Проверял на gcc 4.7. Таблица Crc32Table такая же, как в статье.
                              • 0
                                После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб


                                Стал легче на 200Кб за счет чего? Английские строки где-то дублировались или программа поставляется локализованной строго на один язык и если ставитсярусская версия, то английских строк в ней в принципе нет?

                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.