View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0003336 | SAS.Планета | Рефакторинг / Refactoring | public | 22-05-2018 18:53 | 23-05-2018 12:23 |
| Reporter | zed | Assigned To | zed | ||
| Priority | normal | Severity | minor | Reproducibility | have not tried |
| Status | resolved | Resolution | fixed | ||
| Product Version | 160707 | ||||
| Target Version | 181221 | Fixed in Version | 181221 | ||
| Summary | 0003336: Заменить реализацию CRC32 на более быструю | ||||
| Description | Как-то случайно решил сравнить текущую реализацию алгоритма расчёта CRC32 с zlib и оказалось, что текущий вариант проигрывает в скорости в 2-3 раза. Далее решил поискать что-нибудь по-быстрее zlib и оказалось что есть реализация, которая в 2-3 раза быстрее. Провёл свои собственные тесты и цифры впечатляют (миллисекунды, чем меньше - тем лучше): Предлагаю перейти на эту библиотеку от Cyrus. | ||||
| Tags | No tags attached. | ||||
| Attached Files | t.txt (7,869 bytes)
Data size = 7441 bytes
pascal 0x0F0E3FCD 42246
assembler 0x0F0E3FCD 26254
crc32cfast 0x326B9A44 5600
libcrc32.dll 0x0F0E3FCD 5524
zlib1.dll 0x0F0E3FCD 11915
libzlib1.dll 0x0F0E3FCD 10355
CityHash32 0xBFE00453 4425
CityHash64 0x021EF35B 5655
-----------------------------------------------
Data size = 8421 bytes
pascal 0xE61C8E17 48165
assembler 0xE61C8E17 29219
crc32cfast 0x15A1F9D4 5434
libcrc32.dll 0xE61C8E17 6337
zlib1.dll 0xE61C8E17 13013
libzlib1.dll 0xE61C8E17 11918
CityHash32 0x45480CE1 5070
CityHash64 0x85A5805D 6546
-----------------------------------------------
Data size = 9007 bytes
pascal 0xE0935531 52813
assembler 0xE0935531 31264
crc32cfast 0xEDC9ECD0 5799
libcrc32.dll 0xE0935531 10391
zlib1.dll 0xE0935531 13602
libzlib1.dll 0xE0935531 12886
CityHash32 0xE6989AD3 5439
CityHash64 0x6F9004FF 6830
-----------------------------------------------
Data size = 10149 bytes
pascal 0x030EDCAD 56869
assembler 0x030EDCAD 34724
crc32cfast 0xCCBBD993 6695
libcrc32.dll 0x030EDCAD 7612
zlib1.dll 0x030EDCAD 15501
libzlib1.dll 0x030EDCAD 14306
CityHash32 0xB734AF5C 6106
CityHash64 0xB67F71BC 7702
-----------------------------------------------
Data size = 5933 bytes
pascal 0x91FCFE3E 33460
assembler 0x91FCFE3E 20707
crc32cfast 0x0B72E3B1 3885
libcrc32.dll 0x91FCFE3E 4558
zlib1.dll 0x91FCFE3E 9248
libzlib1.dll 0x91FCFE3E 8339
CityHash32 0x193D9D41 3564
CityHash64 0xBECC9B2F 4592
-----------------------------------------------
Data size = 4593 bytes
pascal 0xF772408D 25733
assembler 0xF772408D 15871
crc32cfast 0xB5F1B26A 3013
libcrc32.dll 0xF772408D 3789
zlib1.dll 0xF772408D 6987
libzlib1.dll 0xF772408D 6509
CityHash32 0xBBBD9A2F 2770
CityHash64 0x978A1927 3653
-----------------------------------------------
Data size = 5571 bytes
pascal 0x0E0BA859 31926
assembler 0x0E0BA859 19546
crc32cfast 0xD16EF4B6 3671
libcrc32.dll 0x0E0BA859 4108
zlib1.dll 0x0E0BA859 8759
libzlib1.dll 0x0E0BA859 7896
CityHash32 0x1A034F5F 3434
CityHash64 0xFC3EBD3B 4280
-----------------------------------------------
Data size = 6049 bytes
pascal 0xAF02BE7C 34068
assembler 0xAF02BE7C 21283
crc32cfast 0x323E8CC0 3900
libcrc32.dll 0xAF02BE7C 5026
zlib1.dll 0xAF02BE7C 9656
libzlib1.dll 0xAF02BE7C 8550
CityHash32 0xD2B5F4CD 4550
CityHash64 0x8A46D463 4561
-----------------------------------------------
Data size = 76 bytes
pascal 0xE038A199 451
assembler 0xE038A199 311
crc32cfast 0xCC368465 101
libcrc32.dll 0xE038A199 137
zlib1.dll 0xE038A199 155
libzlib1.dll 0xE038A199 300
CityHash32 0x02747080 94
CityHash64 0x24339DDB 189
-----------------------------------------------
Data size = 9694 bytes
pascal 0xA818367F 54822
assembler 0xA818367F 33997
crc32cfast 0xF672F6CB 6347
libcrc32.dll 0xA818367F 7490
zlib1.dll 0xA818367F 16051
libzlib1.dll 0xA818367F 14118
CityHash32 0x0B09FE7C 5947
CityHash64 0xF474F0AB 7275
-----------------------------------------------
Data size = 51251 bytes
pascal 0x79AE80DA 292125
assembler 0x79AE80DA 174124
crc32cfast 0x1E7C3EBB 34754
libcrc32.dll 0x79AE80DA 39217
zlib1.dll 0x79AE80DA 77642
libzlib1.dll 0x79AE80DA 74982
CityHash32 0x62D3DF46 33659
CityHash64 0x3D96AB88 38364
-----------------------------------------------
Data size = 99966 bytes
pascal 0x8E1E081E 561053
assembler 0x8E1E081E 339324
crc32cfast 0xB85ABE35 69432
libcrc32.dll 0x8E1E081E 75392
zlib1.dll 0x8E1E081E 152395
libzlib1.dll 0x8E1E081E 139714
CityHash32 0x5BB68DC6 60957
CityHash64 0xE809D1B6 74866
-----------------------------------------------
Data size = 20111 bytes
pascal 0xD5924F7B 111615
assembler 0xD5924F7B 68488
crc32cfast 0x03E8B9A2 13611
libcrc32.dll 0xD5924F7B 14999
zlib1.dll 0xD5924F7B 30511
libzlib1.dll 0xD5924F7B 28100
CityHash32 0xCD926548 11918
CityHash64 0xF994A755 15220
-----------------------------------------------
Data size = 69691 bytes
pascal 0x76B5C2AB 390149
assembler 0x76B5C2AB 234727
crc32cfast 0x2EEE2D81 47547
libcrc32.dll 0x76B5C2AB 53102
zlib1.dll 0x76B5C2AB 106407
libzlib1.dll 0x76B5C2AB 98832
CityHash32 0x618CCBF9 41724
CityHash64 0xE746CB50 54598
-----------------------------------------------
Data size = 15211 bytes
pascal 0x02C29871 87401
assembler 0x02C29871 52130
crc32cfast 0x86DB6AA4 9907
libcrc32.dll 0x02C29871 11497
zlib1.dll 0x02C29871 23627
libzlib1.dll 0x02C29871 21355
CityHash32 0x81CC25B0 9048
CityHash64 0x563F1785 11354
-----------------------------------------------
Data size = 63940 bytes
pascal 0x85F7669A 356920
assembler 0x85F7669A 217174
crc32cfast 0x40D6A0A7 43666
libcrc32.dll 0x85F7669A 48286
zlib1.dll 0x85F7669A 96680
libzlib1.dll 0x85F7669A 90050
CityHash32 0x895743BC 38385
CityHash64 0x0C3CE0D2 47338
-----------------------------------------------
Data size = 44750 bytes
pascal 0x6BD79B14 249357
assembler 0x6BD79B14 155824
crc32cfast 0x45F11521 30349
libcrc32.dll 0x6BD79B14 33921
zlib1.dll 0x6BD79B14 67909
libzlib1.dll 0x6BD79B14 62113
CityHash32 0x3CFB5779 26861
CityHash64 0xA90576FE 33472
-----------------------------------------------
Data size = 69839 bytes
pascal 0x439D40EC 393468
assembler 0x439D40EC 236638
crc32cfast 0x737393E8 47541
libcrc32.dll 0x439D40EC 52717
zlib1.dll 0x439D40EC 107806
libzlib1.dll 0x439D40EC 98320
CityHash32 0x45CC0289 41855
CityHash64 0x9AB44BAF 51953
-----------------------------------------------
Data size = 15018 bytes
pascal 0x69F26081 86096
assembler 0x69F26081 51552
crc32cfast 0x7B00A011 9973
libcrc32.dll 0x69F26081 11346
zlib1.dll 0x69F26081 22874
libzlib1.dll 0x69F26081 21098
CityHash32 0xDB3D8108 8928
CityHash64 0xD11187BC 11299
-----------------------------------------------
Data size = 57801 bytes
pascal 0x8552ABFF 324576
assembler 0x8552ABFF 198272
crc32cfast 0x9B468FB8 39320
libcrc32.dll 0x8552ABFF 43892
zlib1.dll 0x8552ABFF 89148
libzlib1.dll 0x8552ABFF 81521
CityHash32 0x7721CDF3 34486
CityHash64 0xAA67D77D 42976
-----------------------------------------------
| ||||
|
|
А можешь еще для сравнения на скорость CityHash64 наш проверить. Интересно соотношение производительности. |
|
|
Приаттачил. pascal - обычная реализация assembler - то что сейчас используется libzlib1.dll - zlib собранная в Mingw-w64 (считает немного быстрее) crc32cfast - реализация из mORMot (чексумма не совпадает с CRC32), используется у них в качестве алгоритма хэширования. Оптимизировано под SSE4.2. CityHash64 получается примерно одинаково быстрый по сравнению с быстрым CRC, а вот CityHash32 выигрывает. |
|
|
Спасибо за инфу. > CityHash64 получается примерно одинаково быстрый по сравнению с быстрым CRC, а вот CityHash32 выигрывает. Ну, я подозревал, что что-то такое будет. Зря ты на CRC32 в тайлохранилищах завязался - CityHash64 был бы гораздо лучше (размер больше всего на 4 байта, скорость такая же, а вероятность коллизии на порядки меньше), но теперь уже ничего не сделаешь. Поддерживать уже существующие тайлохранилища придется, так что просто добавить использование libcrc32.dll и ладно. Но для новых форматов тайлохранилищ и для случая новых версий существующих (без обратной совместимости), нужно иметь в виду, что лучше использовать CityHash64. |
|
|
Сделал репо с сорцами и бенчмарком (в секции Downloads можно скачать скомпилированную версию). Для порядку, форкни репо с сорцами в SAS.Dlls, а то я не знаю как это из своего аккаунта сделать. |
| 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 | |
| 08-08-2025 13:25 | zed | Category | Рефакторинг => Рефакторинг / Refactoring |