Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 35
Интересный подход! Но ведь в реальных проектах оптимизация часто не превышает O2, а также используется C-runtime. В таких условиях можно получить crc32 от строк на этапе компиляции?
Не понимаю, почему бинарник «похудел» на 200 Кб. Прокомментируйте, пожалуйста.
и теперь он не заставляет заниматься процессоры пользователей ненужной работой, позволяя их ноутбукам работать от батареи чуточку дольшеКак проводились измерения, и насколько выраженной получилась экономия энергии?
Бинарник похудел за счет того, что компилятор больше не засовывает в него строки, а хранит контрольные суммы.
А что не понятно? Вместо длинных строк теперь везде обычный int32, видимо много строк у него было в бинарнике, вот и «похудел».
Ну разве что действительно очень много строк.
На 30000 строках шанс коллизии crc32 — 10%.
Про экономию энергии я написал больше в шутку :) Естественно, что на фоне общей работы приложения затраты на расчёт контрольной суммы будут практически незаметны.
В таком случае, декларируемые преимущества не слишком значительны. А значительное раздувание кода в дебаге кажется мне заметным недостатком.
В таком случае, декларируемые преимущества не слишком значительны.А руководство такой задачи мне и не ставило) решить её мне захотелось, потому что в своё время я уже сталкивался с такой проблемой, и тогда приходилось пользоваться внешним кодогенератором.
А значительное раздувание кода в дебаге кажется мне заметным недостатком.В дебаге используется ifdef, по которому включается старая реализация.
Проверяли в других компиляторах (gcc, clang), как там с этим дела обстоят?
К сожалению, конкретно эта реализация на других компиляторах работать не будет, поскольку использует microsoft-specific ключевое слово __forceinline. Без него компилятор увидит, что реализация слишком большая для инлайна и откажется от попыток её дальнейшей оптимизации.
Что любопытно, ключевое слово inline компилятор успешно игнорирует, считая что он умнее)
Для gcc можно попробовать __attribute__((always_inline))
А вот в языке D можно задавать функции, которые будут вычисляться в compile-time. Например, рассчитывать хеши строк-индексов для ассоциативного массива в момент компиляции, разве это не чудесно? Насколько далеко этот язык впереди порядком устревшего Си.
И странно, что вы озаботились оптимизацией вычисления crc32 (что делается быстро), но не оптимизацией парсинга XML с переводами. Вам не кажется, что логичнее было бы в момент компиляции превращать тяжелый, трудноразбираемый XML-файл в компактную бинарную хеш-таблицу с временем поиска O(1)? Мне кажется, выгоды и в объеме, и в скорости работы программы было бы больше.
Вообще, это странное решение разработчиков, зачем в рантайме тратить драгоценные такты процессора на то, что можно сделать в момент компиляции. Кого они там понабирали в мейл ру?
Ну или использовать бибилиотеку gettext(), если лень писать свою реализацию.
И странно, что вы озаботились оптимизацией вычисления crc32 (что делается быстро), но не оптимизацией парсинга XML с переводами. Вам не кажется, что логичнее было бы в момент компиляции превращать тяжелый, трудноразбираемый XML-файл в компактную бинарную хеш-таблицу с временем поиска O(1)? Мне кажется, выгоды и в объеме, и в скорости работы программы было бы больше.
Вообще, это странное решение разработчиков, зачем в рантайме тратить драгоценные такты процессора на то, что можно сделать в момент компиляции. Кого они там понабирали в мейл ру?
Ну или использовать бибилиотеку gettext(), если лень писать свою реализацию.
Вы правы, xml грузится на стадии запуска приложения как раз-таки в компактную хеш-таблицу) Решил не забивать подробностями повествование.
И «понабрали в мейл ру» достаточно толковых людей. Не нужно забывать что Агент — это проект с большой историей, и многие архитектурные решения были продиктованы историческими соображениями.
И «понабрали в мейл ру» достаточно толковых людей. Не нужно забывать что Агент — это проект с большой историей, и многие архитектурные решения были продиктованы историческими соображениями.
>А вот в языке D можно задавать функции, которые будут вычисляться в compile-time. Например, рассчитывать хеши строк-индексов для ассоциативного массива в момент компиляции, разве это не чудесно? Насколько далеко этот язык впереди порядком устревшего Си.
привет constexpr! Хотя его в принципе с D и спионерили честно)
привет constexpr! Хотя его в принципе с D и спионерили честно)
Сделал попытку №3.
Реализация через класс с шаблонным методом вычисления хеша (длина строки в качестве параметра шаблона).
Проверял в MSVC 2010 ЕЕ — на выходе так же одно число.
К сожалению, время сборки тестового приложения с одной строкой из 500 символов занимает умопомрачительные 63425 мс на четырехъядерном i5-2400.
Ну и эпикфейл — всё волшебство прекращается, как только пытаешься вычислить хеш второй строки: все скатывается к обычным call'ам соответствующих методов.
Впрочем, стоит, наверное, еще поковыряться.
Реализация через класс с шаблонным методом вычисления хеша (длина строки в качестве параметра шаблона).
Проверял в MSVC 2010 ЕЕ — на выходе так же одно число.
К сожалению, время сборки тестового приложения с одной строкой из 500 символов занимает умопомрачительные 63425 мс на четырехъядерном i5-2400.
Ну и эпикфейл — всё волшебство прекращается, как только пытаешься вычислить хеш второй строки: все скатывается к обычным call'ам соответствующих методов.
Впрочем, стоит, наверное, еще поковыряться.
Тихий ужас. Что будет, если CRC у двух разных исходных строк совпадёт? Только не говорите мне, что это маловероятно.
А чем вам не понравился стандартный подход уникальный ID -> строка, зачем нужны все эти crc, которые к тому же имеют свойство впадать в коллизии? Как вы отлавливаете коллизии, и что будете делать, если они возникнут?
Товарищи, статья вовсе не об оправданности выбора архитектурного решения. Оно внедрено в проект уже много лет назад, когда количество строк в проекте исчислялось десятками, а я частенько прогуливал школу в ближайшем компьютерном клубе…
Я взял конкретную прикладную задачу, решение которой до этого момента не было освещено в интернете, и описал свои исследования по этой теме.
Отвечая на ваш вопрос, скорее всего проблемы коллизий будут решаться банальной заменой crc32 на crc64. Но на данный момент такая проблема попросту неактуальна.
Я взял конкретную прикладную задачу, решение которой до этого момента не было освещено в интернете, и описал свои исследования по этой теме.
Отвечая на ваш вопрос, скорее всего проблемы коллизий будут решаться банальной заменой crc32 на crc64. Но на данный момент такая проблема попросту неактуальна.
А если в х64 тоже коллизии будут (с расчетом на худшее)? :)
А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?
Что же касается compile time crc, то его действительно лучше сделать на constexpr (которых, к сожалению, пока нету в студии).
Ну а в их отсутствие можно сделать хотя бы так:
В каждой точке хеш будет вычисляться только один раз. Для производительности этого вполне достаточно.
А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?
Что же касается 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 проект, где приходилось бы считать нечто подобное несколько десятков тысяч раз в секунду, то это бы имело значение.
И да, вы правы, в данном случае это никому ненужная борьба за такты. Но если бы это был серверный highload проект, где приходилось бы считать нечто подобное несколько десятков тысяч раз в секунду, то это бы имело значение.
Как у перфекциониста у вас должно быть жгучее желание убрать вообще нафиг все эти crc
Убрать все crc — задача явно не для кофе-брейка)
Главный принцип больших проектов с плохим покрытием тестами: работает — не трогай. У меня была возможность с минимальным количеством изменений улучшить работу программы, и я это сделал. Любые более серьёзные изменения потребовали бы обширное ручное тестирование, цена которого бы превысила получаемые преимущества.
Главный принцип больших проектов с плохим покрытием тестами: работает — не трогай. У меня была возможность с минимальным количеством изменений улучшить работу программы, и я это сделал. Любые более серьёзные изменения потребовали бы обширное ручное тестирование, цена которого бы превысила получаемые преимущества.
А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?это легко проверить, ровно один раз — в момент добавления строк в языковой пакет.
Собственно, на constexpr'ах это волшебство будет выглядеть так:
Проверка:
Печатает ожидаемое 884863d2.
Проверял на gcc 4.7. Таблица Crc32Table такая же, как в статье.
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 такая же, как в статье.
А вот clang, говорит что нельзя так: coliru.stacked-crooked.com/a/cae07634ff032ebf
Наверное это все таки не по стандарту… Из-за аргумента const char* str
Наверное это все таки не по стандарту… Из-за аргумента const char* str
Но с кастом (const int) вроде работает goo.gl/d6xZeB
После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб
Стал легче на 200Кб за счет чего? Английские строки где-то дублировались или программа поставляется локализованной строго на один язык и если ставитсярусская версия, то английских строк в ней в принципе нет?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисление CRC32 строк в compile-time