По своей программистской природе я очень не люблю неоптимальность и избыточность в коде. И вот, читая в очередной раз на работе исходный код Mail.Ru Агента, вновь наткнулся на одну раздражающую особенность в способе реализации перевода строк продукта на разные языки.
Локализация здесь выполняется довольно нехитро. Все строки, требующие перевода, оборачиваются в макрос _TR():
wprintf(L"%sn", _TR("Some hashing 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 и максимальную скорость. Также я отключил С-runtime, что вкупе с несколькими другими приёмчиками позволило на выходе получить пустой ехе размером всего 2 Кб. Анализировать успешность/неуспешность свёртывания строк до хеша я стал в известном user-mode отладчике OllyDbg, поэтому хотелось бы видеть в результирующем ехе только по одной маленькой секции на код и данные без лишнего мусора.
После нескольких экспериментов я выдал простейшую реализацию расчёта 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 символа + ''), несмотря на то, что длина у неё всего один символ. Обходится это условной операцией, которая подсовывает значение crc с предыдущей итерации, в случае если строка уже досчитана до последнего символа.
Запустив полученный ехе в отладчике, я увидел заветное PUSH 884863D2, правильность расчёта которого легко подтверждается первым попавшимся онлайн-калькулятором crc32.
В этот момент я отбросил в сторону мысли о том, что при каком-нибудь плохом раскладе программа теоретически может обратиться к памяти, находящейся за последним символом строки. Хотелось посмотреть насколько сильно упадёт скорость компиляции, если растиражировать макрос на длину строки, позволявшей покрыть требования проекта.
Самая длинная строка в базе переводов была чуть короче 350 символов, так что хотелось заложиться хотя бы на предел в 500 символов. И тут меня ждало огорчение, когда компилятор выдал своё холодное: «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. Оставалось только дописать перегруженную версию метода g_Translator.Translate() с crc32 в качестве параметра, и дело в шляпе.
После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб, и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольше :)
Полный исходник к тестовому проекту можно взять здесь (компилировать в конфигурации Release).
Автор: Glowfall
