How to become an author
Search
Write a publication
Pull to refresh

Comments 35

Интересный подход! Но ведь в реальных проектах оптимизация часто не превышает O2, а также используется C-runtime. В таких условиях можно получить crc32 от строк на этапе компиляции?
This comment wasn’t rated yet0
Рантайм был отключен только для теста, чтобы выходной ехе получился без мусора. В реальном проекте использовался O2, и само собой с рантаймом)
Total votes 1: ↑1 and ↓0+1
Не понимаю, почему бинарник «похудел» на 200 Кб. Прокомментируйте, пожалуйста.

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

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

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

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

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

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

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

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

Отвечая на ваш вопрос, скорее всего проблемы коллизий будут решаться банальной заменой crc32 на crc64. Но на данный момент такая проблема попросту неактуальна.
Total votes 4: ↑4 and ↓0+4
А если в х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;
}

В каждой точке хеш будет вычисляться только один раз. Для производительности этого вполне достаточно.
Total votes 1: ↑1 and ↓0+1
Схему с использованием предопределённого макроса __COUNTER__ я рассматривал, но проблема возникает, когда модулей в программе больше, чем один. Порядок компиляции модулей непостоянен, и хеши собьются при малейших перестановках.
This comment wasn’t rated yet0
А пардон… Тут имеется в виду что вычисление будет в рантайме, но только при первом обращении…
Да, такое будет работать, но строки всё равно будут присутствовать в ехе. Ну и хотелось бы, чтобы расчёт происходил всё же полностью во время компиляции.
This comment wasn’t rated yet0
Вам жалко 200 Кб под строки, которые к тому же замечательно пожмутся инсталлом или тактов процессора на расчет хеша при первом обращении?

Ни то ни другое существенного влияния на производительность не оказывает.
Total votes 2: ↑1 and ↓10
Я перфекционист, и не люблю компромиссы, когда есть возможность сделать лучше :)
И да, вы правы, в данном случае это никому ненужная борьба за такты. Но если бы это был серверный highload проект, где приходилось бы считать нечто подобное несколько десятков тысяч раз в секунду, то это бы имело значение.
Total votes 2: ↑1 and ↓10
Как у перфекциониста у вас должно быть жгучее желание убрать вообще нафиг все эти crc
Total votes 2: ↑1 and ↓10
Убрать все crc — задача явно не для кофе-брейка)
Главный принцип больших проектов с плохим покрытием тестами: работает — не трогай. У меня была возможность с минимальным количеством изменений улучшить работу программы, и я это сделал. Любые более серьёзные изменения потребовали бы обширное ручное тестирование, цена которого бы превысила получаемые преимущества.
This comment wasn’t rated yet0
А вы уверены, что уже сейчас у вас нету коллизий? может их просто не заметили, и где-то выдаются неправильные сообщения?
это легко проверить, ровно один раз — в момент добавления строк в языковой пакет.
This comment wasn’t rated yet0
Собственно, на 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 такая же, как в статье.
Total votes 6: ↑6 and ↓0+6
После внедрения кода в проект, компиляция релизной сборки стала дольше на 1-2 минуты, но зато бинарник стал легче на 200 Кб


Стал легче на 200Кб за счет чего? Английские строки где-то дублировались или программа поставляется локализованной строго на один язык и если ставитсярусская версия, то английских строк в ней в принципе нет?
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr