Skip to content

Add CRC32IEEE()/CRC64() support#7480

Merged
akuzm merged 3 commits intoClickHouse:masterfrom
azat:crc-v3
Oct 28, 2019
Merged

Add CRC32IEEE()/CRC64() support#7480
akuzm merged 3 commits intoClickHouse:masterfrom
azat:crc-v3

Conversation

@azat
Copy link
Copy Markdown
Member

@azat azat commented Oct 24, 2019

Category (leave one):

  • New Feature

Short description (up to few sentences):
Add CRC32IEEE()/CRC64() support

Detailed description (optional):
zlib's implementation uses CRC-32-IEEE 802.3 polynomial (0xedb88320) but
with starting value 0xffffffff, so introduce another crc32
implementation - CRC32IEEE that has starting value - 0

Also add CRC64 with ECMA polynomial.

@azat
Copy link
Copy Markdown
Member Author

azat commented Oct 25, 2019

2019-10-25 09:48:42 /usr/bin/ld.gold: error: contrib/zlib-ng/libz.a(crc32.c.o): multiple definition of 'get_crc_table'
2019-10-25 09:48:42 /usr/bin/ld.gold: contrib/mariadb-connector-c/libmariadb/libmariadbclient.a(crc32.c.o): previous definition here

Don't see how the patch can introduce this, maybe I need to rebase, will take a look

azat added 3 commits October 25, 2019 15:52
@azat
Add CRC32IEEE()/CRC64() support
2d2e738 
zlib's implementation uses CRC-32-IEEE 802.3 polynomial (0xedb88320) but
with starting value 0xffffffff, so introduce another crc32
implementation - CRC32IEEE that has starting value - 0

Also add CRC64 with ECMA polynomial.

v2: s/crc*_data./crc*_data./ to avoid conflicts with other crc32.h in contrib
v3: join with existing CRC32()
@azat
Use crc32_z() over crc32(), since it size_t for length
04f1e6b
@azat
Avoid conflicts of static zlib and mariadb-connector-c zlib
fe98e90 
After crc32() had been replaced with crc32_z() the following error will
happen with two different zlib:
  2019-10-25 09:48:42 /usr/bin/ld.gold: error: contrib/zlib-ng/libz.a(crc32.c.o): multiple definition of 'get_crc_table'
  2019-10-25 09:48:42 /usr/bin/ld.gold: contrib/mariadb-connector-c/libmariadb/libmariadbclient.a(crc32.c.o): previous definition here

Fix this by using zlibstatic compiled for and by CH in
mariadb-connector-c, and wrap into function reduce variable scopes.
@akuzm akuzm merged commit 6e2af3d into ClickHouse:master Oct 28, 2019
@azat azat deleted the crc-v3 branch October 28, 2019 13:19
@alexey-milovidov
Copy link
Copy Markdown
Member

alexey-milovidov commented Oct 28, 2019

@akuzm The code has some flaws, it transforms to technical debt.

@akuzm akuzm self-assigned this Oct 28, 2019
@azat
Copy link
Copy Markdown
Member Author

azat commented Oct 28, 2019

The code has some flaws

@alexey-milovidov can you write them down?

@alexey-milovidov
Copy link
Copy Markdown
Member

alexey-milovidov commented Oct 28, 2019 •
edited
Loading

Copy-paste from private TG channel. @akuzm will address all the concerns.

Alexey Milovidov, [28.10.19 16:37]
@akuzm

with starting value 0xffffffff, so introduce another crc32
implementation - CRC32IEEE that has starting value - 0

А чем мотивировано, что функция должна так называться? Какое отношение отсутствие инициализации единичными битами имеет к IEEE? Есть какой-то стандарт, где такое прописано?

#7480 (comment)

Alexey Milovidov, [28.10.19 16:39]
https://github.com/ClickHouse/ClickHouse/pull/7480/files

Каждая функция должна быть в отдельном файле. Не хватает теста производительности, потому что добавленные функции не используют PCLMUL.

Alexey Milovidov, [28.10.19 16:39]
https://github.com/ClickHouse/ClickHouse/pull/7480/files#diff-65c3b090497906bec97e302b49ef282eR36

Здесь код не соответствует стилю. Придётся переделывать.

Alexey Milovidov, [28.10.19 16:41]
https://github.com/ClickHouse/ClickHouse/pull/7480/files#diff-65c3b090497906bec97e302b49ef282eR91

А здесь atomic операции на каждое значение - вообще треш.

Alexey Milovidov, [28.10.19 16:41]
(из-за static переменной)

@azat
Copy link
Copy Markdown
Member Author

azat commented Oct 28, 2019

Какое отношение отсутствие инициализации единичными битами имеет к IEEE? Есть какой-то стандарт, где такое прописано?

I couldn't think of anything better then this, and since IEEE is the name for the polynomial, crc32ieee() had been chosen.

(I though of accepting the polynomial as an parameter, but right now parameters exists only for aggregation functions AFAICS)

А здесь atomic операции на каждое значение - вообще треш.

(sigh)

Не хватает теста производительности, потому что добавленные функции не используют PCLMUL

Just in case, I did some testing, and got the following with PCLMUL, and results indeed looks promising (but it depends from the data length as expected):

2019-10-29 02:25:49
Running bin/bench-crc32
Run on (8 X 4000 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
------------------------------------------------------------------
Benchmark                           Time           CPU Iterations
------------------------------------------------------------------
crc32_bench/1                       2 ns          2 ns  464069133     582.1MB/s
crc32_bench/8                       7 ns          7 ns   93804251   1026.01MB/s
crc32_bench/64                    107 ns        107 ns    6568787   571.792MB/s
crc32_bench/512                  1019 ns       1017 ns     684314   480.084MB/s
crc32_bench/4096                 8432 ns       8424 ns      84392    463.69MB/s
crc32_bench/32768               66413 ns      66381 ns      10370   470.764MB/s
crc32_bench/262144             532647 ns     532307 ns       1316   469.654MB/s
crc32_bench/1048576           2128611 ns    2127213 ns        329   470.099MB/s
crc32c_bench/1                      6 ns          6 ns  113461899   154.198MB/s
crc32c_bench/8                      6 ns          6 ns  117318526   1.24951GB/s
crc32c_bench/64                     9 ns          9 ns   77680928    6.7137GB/s
crc32c_bench/512                   50 ns         50 ns   13177256   9.48935GB/s
crc32c_bench/4096                 132 ns        132 ns    5263151   28.9321GB/s
crc32c_bench/32768               1080 ns       1079 ns     646811   28.2734GB/s
crc32c_bench/262144              8808 ns       8803 ns      78766   27.7354GB/s
crc32c_bench/1048576            35746 ns      35709 ns      19734    27.348GB/s
crc32_folly_bench/1                14 ns         14 ns   52871351   69.9288MB/s
crc32_folly_bench/8                20 ns         20 ns   32726538   379.776MB/s
crc32_folly_bench/64               29 ns         28 ns   24482689   2.10203GB/s
crc32_folly_bench/512              50 ns         50 ns   13979856   9.51807GB/s
crc32_folly_bench/4096            218 ns        218 ns    3240779   17.5171GB/s
crc32_folly_bench/32768          1538 ns       1537 ns     457364   19.8528GB/s
crc32_folly_bench/262144        12903 ns      12878 ns      56088   18.9585GB/s
crc32_folly_bench/1048576       50733 ns      50666 ns      13111   19.2744GB/s
crc32c_folly_bench/1                5 ns          5 ns  137556658   190.554MB/s
crc32c_folly_bench/8                5 ns          5 ns  131341279    1.3888GB/s
crc32c_folly_bench/64               6 ns          6 ns  111139192   9.45814GB/s
crc32c_folly_bench/512             25 ns         25 ns   27550327   19.0324GB/s
crc32c_folly_bench/4096           155 ns        154 ns    4759466   24.7271GB/s
crc32c_folly_bench/32768         1160 ns       1159 ns     602707   26.3203GB/s
crc32c_folly_bench/262144        9586 ns       9572 ns      74196   25.5061GB/s
crc32c_folly_bench/1048576      39610 ns      39517 ns      17928   24.7125GB/s

Where:

(And this does not have that static var of course)

@akuzm akuzm added the pr-feature Pull request with new product feature label Oct 29, 2019
@nikitamikhaylov nikitamikhaylov mentioned this pull request Aug 28, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer

@akuzm akuzm akuzm approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

@akuzm akuzm

Labels

pr-feature Pull request with new product feature

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@azat @alexey-milovidov @akuzm