SASGIS - SAS.Планета
View Issue Details
IDProjectCategoryView StatusDate SubmittedLast Update
0003336SAS.ПланетаРефакторингpublic22-05-2018 18:5323-05-2018 12:23
Reporterzed 
Assigned Tozed 
PrioritynormalSeverityminorReproducibilityhave not tried
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version160707 
Target Version181221Fixed in Version181221 
Summary0003336: Заменить реализацию CRC32 на более быструю
DescriptionКак-то случайно решил сравнить текущую реализацию алгоритма расчёта CRC32 с zlib и оказалось, что текущий вариант проигрывает в скорости в 2-3 раза. Далее решил поискать что-нибудь по-быстрее zlib и оказалось что есть реализация, которая в 2-3 раза быстрее.

Провёл свои собственные тесты и цифры впечатляют (миллисекунды, чем меньше - тем лучше):


      assembler:  127657

   libcrc32.dll:  27706

      zlib1.dll:  54800



(Data size = 35840 bytes)


Предлагаю перейти на эту библиотеку от Cyrus.
Steps To Reproduce
Additional Information
TagsNo tags attached.
Relationships
Attached Filestxt t.txt (7,869) 23-05-2018 09:08
https://bugtracker.sasgis.org/file_download.php?file_id=2214&type=bug
Issue History
Date ModifiedUsernameFieldChange
22-05-2018 18:53zedNew Issue
22-05-2018 18:53zedStatusnew => assigned
22-05-2018 18:53zedAssigned To => zed
23-05-2018 07:18vdemidovNote Added: 0018291
23-05-2018 09:08zedFile Added: t.txt
23-05-2018 09:13zedNote Added: 0018292
23-05-2018 09:31vdemidovNote Added: 0018293
23-05-2018 10:33zedStatusassigned => resolved
23-05-2018 10:33zedFixed in Version => 181221
23-05-2018 10:33zedResolutionopen => fixed
23-05-2018 12:23zedNote Added: 0018294

Notes
(0018291)
vdemidov   
23-05-2018 07:18   
А можешь еще для сравнения на скорость CityHash64 наш проверить. Интересно соотношение производительности.
(0018292)
zed   
23-05-2018 09:13   
Приаттачил.

pascal - обычная реализация
assembler - то что сейчас используется
libzlib1.dll - zlib собранная в Mingw-w64 (считает немного быстрее)
crc32cfast - реализация из mORMot (чексумма не совпадает с CRC32), используется у них в качестве алгоритма хэширования. Оптимизировано под SSE4.2.

CityHash64 получается примерно одинаково быстрый по сравнению с быстрым CRC, а вот CityHash32 выигрывает.
(0018293)
vdemidov   
23-05-2018 09:31   
Спасибо за инфу.
> CityHash64 получается примерно одинаково быстрый по сравнению с быстрым CRC, а вот CityHash32 выигрывает.
Ну, я подозревал, что что-то такое будет. Зря ты на CRC32 в тайлохранилищах завязался - CityHash64 был бы гораздо лучше (размер больше всего на 4 байта, скорость такая же, а вероятность коллизии на порядки меньше), но теперь уже ничего не сделаешь.

Поддерживать уже существующие тайлохранилища придется, так что просто добавить использование libcrc32.dll и ладно. Но для новых форматов тайлохранилищ и для случая новых версий существующих (без обратной совместимости), нужно иметь в виду, что лучше использовать CityHash64.
(0018294)
zed   
23-05-2018 12:23   
Сделал репо с сорцами и бенчмарком (в секции Downloads можно скачать скомпилированную версию).

Для порядку, форкни репо с сорцами в SAS.Dlls, а то я не знаю как это из своего аккаунта сделать.