View Issue Details Jump to Notes ] Issue History ] Print ]
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.
TagsNo tags attached.
Attached Filestxt file icon t.txt [^] (7,869 bytes) 23-05-2018 09:08 [Show Content]

- Relationships

-  Notes
(0018291)
vdemidov (manager)
23-05-2018 07:18

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

Приаттачил.

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

CityHash64 получается примерно одинаково быстрый по сравнению с быстрым CRC, а вот CityHash32 выигрывает.
(0018293)
vdemidov (manager)
23-05-2018 09:31

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

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

Сделал репо с сорцами и бенчмарком (в секции Downloads можно скачать скомпилированную версию).

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

- Users who viewed this issue
User List Anonymous (1022x), bk99 (1x), rass (2x), ygorigor (1x), vdemidov (14x), zed (10x)
Total Views 1050
Last View 09-08-2020 03:03

- Issue History
Date Modified Username Field Change
22-05-2018 18:53 zed New Issue
22-05-2018 18:53 zed Status new => assigned
22-05-2018 18:53 zed Assigned To => zed
23-05-2018 07:18 vdemidov Note Added: 0018291
23-05-2018 09:08 zed File Added: t.txt
23-05-2018 09:13 zed Note Added: 0018292
23-05-2018 09:31 vdemidov Note Added: 0018293
23-05-2018 10:33 zed Status assigned => resolved
23-05-2018 10:33 zed Fixed in Version => 181221
23-05-2018 10:33 zed Resolution open => fixed
23-05-2018 12:23 zed Note Added: 0018294



Copyright © 2007 - 2020 SAS.Planet Team