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

и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольше
Как проводились измерения, и насколько выраженной получилась экономия энергии?
Бинарник похудел за счет того, что компилятор больше не засовывает в него строки, а хранит контрольные суммы.
А что не понятно? Вместо длинных строк теперь везде обычный int32, видимо много строк у него было в бинарнике, вот и «похудел».
На данный момент в проекте около 2500 строк. Если вдруг начнут учащаться коллизии не исключено, что придется увеличивать длину хеша.
Про экономию энергии я написал больше в шутку :) Естественно, что на фоне общей работы приложения затраты на расчёт контрольной суммы будут практически незаметны.
В таком случае, декларируемые преимущества не слишком значительны. А значительное раздувание кода в дебаге кажется мне заметным недостатком.
В таком случае, декларируемые преимущества не слишком значительны.
А руководство такой задачи мне и не ставило) решить её мне захотелось, потому что в своё время я уже сталкивался с такой проблемой, и тогда приходилось пользоваться внешним кодогенератором.
А значительное раздувание кода в дебаге кажется мне заметным недостатком.
В дебаге используется ifdef, по которому включается старая реализация.
Проверяли в других компиляторах (gcc, clang), как там с этим дела обстоят?
К сожалению, конкретно эта реализация на других компиляторах работать не будет, поскольку использует microsoft-specific ключевое слово __forceinline. Без него компилятор увидит, что реализация слишком большая для инлайна и откажется от попыток её дальнейшей оптимизации.
Что любопытно, ключевое слово inline компилятор успешно игнорирует, считая что он умнее)
gcc и clang поддерживают constexpr'ы. По этому большой необходимости в трюках с __forceinline и их аналогами нет.
А вот в языке D можно задавать функции, которые будут вычисляться в compile-time. Например, рассчитывать хеши строк-индексов для ассоциативного массива в момент компиляции, разве это не чудесно? Насколько далеко этот язык впереди порядком устревшего Си.

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

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

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

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

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

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

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

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

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

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

Ну а в их отсутствие можно сделать хотя бы так:
include "StdAfx.h"

template< int >
inline __int32 crc32( const char *s )
{
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;
}

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

Ни то ни другое существенного влияния на производительность не оказывает.
Я перфекционист, и не люблю компромиссы, когда есть возможность сделать лучше :)
И да, вы правы, в данном случае это никому ненужная борьба за такты. Но если бы это был серверный highload проект, где приходилось бы считать нечто подобное несколько десятков тысяч раз в секунду, то это бы имело значение.
Как у перфекциониста у вас должно быть жгучее желание убрать вообще нафиг все эти crc
Убрать все crc — задача явно не для кофе-брейка)
Главный принцип больших проектов с плохим покрытием тестами: работает — не трогай. У меня была возможность с минимальным количеством изменений улучшить работу программы, и я это сделал. Любые более серьёзные изменения потребовали бы обширное ручное тестирование, цена которого бы превысила получаемые преимущества.
А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?
это легко проверить, ровно один раз — в момент добавления строк в языковой пакет.
Собственно, на 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 такая же, как в статье.
После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб


Стал легче на 200Кб за счет чего? Английские строки где-то дублировались или программа поставляется локализованной строго на один язык и если ставитсярусская версия, то английских строк в ней в принципе нет?
Only those users with full accounts are able to leave comments. Log in, please.