Warnings in xxh3.h on MSVC #249

New issue

Closed

opened 2019-09-03 14:34:54 -05:00 by pitrou · 9 comments

pitrou commented 2019-09-03 14:34:54 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

I get this on AppVeyor when building with 0.7.1 and XXH_INLINE_ALL:

c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1372): error C2220: warning treated as error - no 'object' file generated
c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1372): warning C4146: unary minus operator applied to unsigned type, result still unsigned
c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1379): warning C4146: unary minus operator applied to unsigned type, result still unsigned
c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1383): warning C4146: unary minus operator applied to unsigned type, result still unsigned

I get this on AppVeyor when building with 0.7.1 and XXH_INLINE_ALL: ``` c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1372): error C2220: warning treated as error - no 'object' file generated c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1372): warning C4146: unary minus operator applied to unsigned type, result still unsigned c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1379): warning C4146: unary minus operator applied to unsigned type, result still unsigned c:\projects\arrow\cpp\src\arrow\vendored\xxhash\xxh3.h(1383): warning C4146: unary minus operator applied to unsigned type, result still unsigned ```

👍 1

Cyan4973 commented 2019-09-03 14:42:51 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks for notification @pitrou ,
we probably need an additional test in AppveyorCI to catch this issue.

Thanks for notification @pitrou , we probably need an additional test in `AppveyorCI` to catch this issue.

Cyan4973 commented 2019-09-04 19:14:49 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Actually, the appveyorCI found the issues, as you mentioned :
https://ci.appveyor.com/project/YannCollet/xxhash/build/job/todic2778t438b7u#L59

but they were classified as silent warnings, instead of blocking errors.

So what we are lacking is an ability to make the test fail when it generates compilation warnings.

Actually, the `appveyorCI` found the issues, as you mentioned : https://ci.appveyor.com/project/YannCollet/xxhash/build/job/todic2778t438b7u#L59 but they were classified as silent warnings, instead of blocking errors. So what we are lacking is an ability to make the test fail when it generates compilation warnings.

wesm commented 2019-09-05 20:46:11 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Passing -DCMAKE_C_FLAGS="/WX" in the Visual Studio CMake build should do the trick

Passing `-DCMAKE_C_FLAGS="/WX"` in the Visual Studio CMake build should do the trick

👍 1

Cyan4973 commented 2019-09-06 18:08:45 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Thanks @wesm , this command works !

edit : well, it almost worked. If using -DCMAKE_C_FLAGS=#### after the project was already created and compiled properly, then it works. But if I start from an empty directory, then the script seems to be missing generation of xxhash.lib, which makes the linking stage fails afterwards ...

Thanks @wesm , this command works ! _edit_ : well, it _almost_ worked. If using `-DCMAKE_C_FLAGS=####` _after_ the project was already created and compiled properly, then it works. But if I start from an empty directory, then the script seems to be missing generation of `xxhash.lib`, which makes the linking stage fails afterwards ...

Cyan4973 commented 2019-09-15 11:38:01 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Hi @pitrou,

I was looking at ARROW repository recently, and noticed the following comment :

Use xxh3 instead of custom hashing code for non-tiny strings
(...)
Specialize for small hash strings (...) Even XXH3 isn't quite as fast.

The next lines develop a custom algorithm for inputs <= 16 byte, using the same read access method as XXH3, but with a different mixing algorithm. It suggests the custom method is considered faster for this use case.

There is of course nothing in doing so, I'm just curious.

XXH3 was developed with the hope that it could fix most hash / checksum situations, including hashing small inputs to generate random bits for indexing hash tables. The goal is to simplify hashing for user applications, by offering a one-stop shop for all needs. I see that it's apparently not the case for ARROW, and I'm wondering if there's something important that could be learned from it, eventually allowing XXH3 to improve and get closer to the intended goal.

edit : fixed project name : ARROW, within a final S

Hi @pitrou, I was looking at [ARROW](https://github.com/apache/arrow/commit/b829f534d32e3ceb3f9ca902b4f1172002df0802) repository recently, and noticed the following comment : > Use xxh3 instead of custom hashing code for non-tiny strings (...) > Specialize for small hash strings (...) Even XXH3 isn't quite as fast. The next lines develop a custom algorithm for inputs <= 16 byte, using the same read access method as `XXH3`, but with a different mixing algorithm. It suggests the custom method is considered faster for this use case. There is of course nothing in doing so, I'm just curious. `XXH3` was developed with the hope that it could fix most hash / checksum situations, including hashing small inputs to generate random bits for indexing hash tables. The goal is to simplify hashing for user applications, by offering a one-stop shop for all needs. I see that it's apparently not the case for ARROW, and I'm wondering if there's something important that could be learned from it, eventually allowing `XXH3` to improve and get closer to the intended goal. _edit_ : fixed project name : ARROW, within a final `S`

easyaspi314 commented 2019-09-15 13:39:08 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Well to be fair, XXH3's short hash is not as trivial as it seems, at least on A64.

Here is my best (read: not that good lol) handwritten asm version of XXH3_len_0to16_64b:

    .type XXH3_len_0to16_64b, @function
XXH3_len_0to16_64b:
    cmp    x1, #8
    b.gt   .LXXH3_len_9to16_64b    // TAIL CALL
    cmp    x1, #4
    b.ge   .LXXH3_len_4to8_64b     // TAIL CALL
    cbnz   x1, .LXXH3_len_1to3_64b // TAIL CALL
    mov    x0, xzr
    ret

.LXXH3_len_1to3_64b:
    ldrb   w4, [x0]
    lsr    x5, x1, #1
    ldrb   w5, [x0, x5]
    orr    w4, w4, w5, lsl #8
    sub    x5, x1, #1
    ldrb   w5, [x0, x5]
    orr    w4, w4, w5, lsl #16
    orr    w4, w4, w1, lsl #24
    ldr    w8, [x2]
    add    x3, x3, x8
    eor    x3, x3, x4
    movl   x8, PRIME64_1
    mul    x0, x3, x8
    // FALLTHROUGH

    .type XXH3_avalanche, @function
XXH3_avalanche:
    movl   x1, PRIME64_3
    eor    x0, x0, x0, lsr #37
    mul    x0, x0, x1
    eor    x0, x0, x0, lsr #32
    ret
.LXXH3_len_4to8_64b:
    ldr    w8, [x0]
    sub    x5, x1, #4
    movl   x6, PRIME64_2
    ldr    w5, [x0, x5]
    orr    x8, x8, x5, lsl #32
    ldr    x4, [x2]
    add    x4, x4, x3
    eor    x4, x4, x8
    eor    x4, x4, x4, lsr #51
    movl   w3, PRIME32_1
    madd   x0, x4, x3, x1
    eor    x0, x0, x0, lsr #47
    mul    x0, x0, x6
    b      XXH3_avalanche // TAIL CALL
.LXXH3_len_9to16_64b:
    ldr    x8, [x0]
    ldr    x4, [x2]
    add    x4, x4, x3
    eor    x8, x8, x4 // x8 = ll1
    sub    x6, x1, #8
    ldr    x6, [x0, x6]
    ldr    x2, [x2, #8]
    sub    x2, x2, x3
    eor    x3, x2, x6 // x3 = ll2
    mul    x4, x3, x8
    umulh  x5, x3, x8
    eor    x0, x5, x4
    add    x8, x8, x3
    add    x0, x0, x1
    add    x0, x0, x8
    b      XXH3_avalanche // TAIL CALL

(movl expands to mov/movk)

Granted, most of that is loading values which isn't changed.

Well to be fair, XXH3's short hash is not as trivial as it seems, at least on A64. Here is my best (read: not that good lol) handwritten asm version of XXH3_len_0to16_64b: ```asm .type XXH3_len_0to16_64b, @function XXH3_len_0to16_64b: cmp x1, #8 b.gt .LXXH3_len_9to16_64b // TAIL CALL cmp x1, #4 b.ge .LXXH3_len_4to8_64b // TAIL CALL cbnz x1, .LXXH3_len_1to3_64b // TAIL CALL mov x0, xzr ret .LXXH3_len_1to3_64b: ldrb w4, [x0] lsr x5, x1, #1 ldrb w5, [x0, x5] orr w4, w4, w5, lsl #8 sub x5, x1, #1 ldrb w5, [x0, x5] orr w4, w4, w5, lsl #16 orr w4, w4, w1, lsl #24 ldr w8, [x2] add x3, x3, x8 eor x3, x3, x4 movl x8, PRIME64_1 mul x0, x3, x8 // FALLTHROUGH .type XXH3_avalanche, @function XXH3_avalanche: movl x1, PRIME64_3 eor x0, x0, x0, lsr #37 mul x0, x0, x1 eor x0, x0, x0, lsr #32 ret .LXXH3_len_4to8_64b: ldr w8, [x0] sub x5, x1, #4 movl x6, PRIME64_2 ldr w5, [x0, x5] orr x8, x8, x5, lsl #32 ldr x4, [x2] add x4, x4, x3 eor x4, x4, x8 eor x4, x4, x4, lsr #51 movl w3, PRIME32_1 madd x0, x4, x3, x1 eor x0, x0, x0, lsr #47 mul x0, x0, x6 b XXH3_avalanche // TAIL CALL .LXXH3_len_9to16_64b: ldr x8, [x0] ldr x4, [x2] add x4, x4, x3 eor x8, x8, x4 // x8 = ll1 sub x6, x1, #8 ldr x6, [x0, x6] ldr x2, [x2, #8] sub x2, x2, x3 eor x3, x2, x6 // x3 = ll2 mul x4, x3, x8 umulh x5, x3, x8 eor x0, x5, x4 add x8, x8, x3 add x0, x0, x1 add x0, x0, x8 b XXH3_avalanche // TAIL CALL ``` (`movl` expands to `mov/movk`) Granted, most of that is loading values which isn't changed.

👍 1

pitrou commented 2019-09-15 13:54:48 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

@Cyan4973

(Nitpick: the project name is "Arrow", not "Arrows" :-))

The next lines develop a custom algorithm for inputs <= 16 byte, using the same read access method as XXH3, but with a different mixing algorithm.

Well, that's an interesting coincidence, because the "custom algorithm for inputs <= 16 byte" was developed before switching to xxh3. So I'm glad to learn the code I wrote makes sense :-)

We're using this benchmark for string hashing:
https://github.com/apache/arrow/blob/master/cpp/src/arrow/util/hashing_benchmark.cc#L80-L112

With the custom algorithm in place, I get the following results (gcc 7.4.0, Ryzen 7 1700, Ubuntu 18.04):

HashSmallStrings       59455 ns        59440 ns        47088 bytes_per_second=3.42346G/s items_per_second=336.475M/s
HashMediumStrings     171256 ns       171211 ns        16345 bytes_per_second=7.57206G/s items_per_second=116.815M/s
HashLargeStrings      131766 ns       131732 ns        21437 bytes_per_second=14.5461G/s items_per_second=15.1824M/s

If I disable the custom algorithm (thus always using xxh3 regardless of length), the results are as follow:

HashSmallStrings       77020 ns        76999 ns        36339 bytes_per_second=2.64276G/s items_per_second=259.743M/s
HashMediumStrings     165283 ns       165236 ns        16950 bytes_per_second=7.84587G/s items_per_second=121.039M/s
HashLargeStrings      131967 ns       131932 ns        21421 bytes_per_second=14.524G/s items_per_second=15.1593M/s

Similarly on less micro-benchmarks relying on a hash table. With custom algorithm:

BuildStringDictionaryArray          1446292457 ns   1445849113 ns            1 bytes_per_second=236.218M/s

UniqueString10bytes/4194304/1024     71590401 ns     71559956 ns           10 bytes_per_second=558.972M/s
UniqueString10bytes/4194304/10240   104562043 ns    104519279 ns            7 bytes_per_second=382.705M/s
UniqueString100bytes/4194304/1024   182032838 ns    181926192 ns            4 bytes_per_second=2.14716G/s
UniqueString100bytes/4194304/10240  250706644 ns    250534700 ns            3 bytes_per_second=1.55917G/s

Without custom algorithm:

BuildStringDictionaryArray          1555853820 ns   1555344106 ns            1 bytes_per_second=219.588M/s

UniqueString10bytes/4194304/1024     81888786 ns     81862158 ns            8 bytes_per_second=488.626M/s
UniqueString10bytes/4194304/10240   112586934 ns    112535413 ns            6 bytes_per_second=355.444M/s
UniqueString100bytes/4194304/1024   188276504 ns    188173700 ns            4 bytes_per_second=2.07587G/s
UniqueString100bytes/4194304/10240  254715046 ns    254569574 ns            3 bytes_per_second=1.53445G/s

So, there is a noticeable slowdown, though far from catastrophic. Perhaps it's just this particular compiler. If you want I can check tomorrow with clang?

Finally, to be honest, if we had used xxh3 from the start, I'm not sure I'd have bothered with a custom algorithm for tiny strings, because xxh3 is very fast already. But our pre-xxh3 hashing algorithm wasn't very good on tiny strings, so the custom algorithm was developed at the time.

@Cyan4973 (Nitpick: the project name is "Arrow", not "Arrows" :-)) > The next lines develop a custom algorithm for inputs <= 16 byte, using the same read access method as XXH3, but with a different mixing algorithm. Well, that's an interesting coincidence, because the "custom algorithm for inputs <= 16 byte" was developed before switching to xxh3. So I'm glad to learn the code I wrote makes sense :-) We're using this benchmark for string hashing: https://github.com/apache/arrow/blob/master/cpp/src/arrow/util/hashing_benchmark.cc#L80-L112 With the custom algorithm in place, I get the following results (gcc 7.4.0, Ryzen 7 1700, Ubuntu 18.04): ``` HashSmallStrings 59455 ns 59440 ns 47088 bytes_per_second=3.42346G/s items_per_second=336.475M/s HashMediumStrings 171256 ns 171211 ns 16345 bytes_per_second=7.57206G/s items_per_second=116.815M/s HashLargeStrings 131766 ns 131732 ns 21437 bytes_per_second=14.5461G/s items_per_second=15.1824M/s ``` If I disable the custom algorithm (thus always using xxh3 regardless of length), the results are as follow: ``` HashSmallStrings 77020 ns 76999 ns 36339 bytes_per_second=2.64276G/s items_per_second=259.743M/s HashMediumStrings 165283 ns 165236 ns 16950 bytes_per_second=7.84587G/s items_per_second=121.039M/s HashLargeStrings 131967 ns 131932 ns 21421 bytes_per_second=14.524G/s items_per_second=15.1593M/s ``` Similarly on less micro-benchmarks relying on a hash table. With custom algorithm: ``` BuildStringDictionaryArray 1446292457 ns 1445849113 ns 1 bytes_per_second=236.218M/s UniqueString10bytes/4194304/1024 71590401 ns 71559956 ns 10 bytes_per_second=558.972M/s UniqueString10bytes/4194304/10240 104562043 ns 104519279 ns 7 bytes_per_second=382.705M/s UniqueString100bytes/4194304/1024 182032838 ns 181926192 ns 4 bytes_per_second=2.14716G/s UniqueString100bytes/4194304/10240 250706644 ns 250534700 ns 3 bytes_per_second=1.55917G/s ``` Without custom algorithm: ``` BuildStringDictionaryArray 1555853820 ns 1555344106 ns 1 bytes_per_second=219.588M/s UniqueString10bytes/4194304/1024 81888786 ns 81862158 ns 8 bytes_per_second=488.626M/s UniqueString10bytes/4194304/10240 112586934 ns 112535413 ns 6 bytes_per_second=355.444M/s UniqueString100bytes/4194304/1024 188276504 ns 188173700 ns 4 bytes_per_second=2.07587G/s UniqueString100bytes/4194304/10240 254715046 ns 254569574 ns 3 bytes_per_second=1.53445G/s ``` So, there is a noticeable slowdown, though far from catastrophic. Perhaps it's just this particular compiler. If you want I can check tomorrow with clang? Finally, to be honest, if we had used xxh3 from the start, I'm not sure I'd have bothered with a custom algorithm for tiny strings, because xxh3 is very fast already. But our pre-xxh3 hashing algorithm wasn't very good on tiny strings, so the custom algorithm was developed at the time.

👍 1

Cyan4973 commented 2019-09-15 16:50:55 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Great ASM investigation @easyaspi314 !

Note that I would expect some of these operations to be folded, depending on the exact variant.

The "full" variant must load the key values from the provided custom secret, and add the seed.
The "seed" variant uses the default secret : in this case, I would expect the compiler to embed the secret values directly into instructions. This would save a corresponding load instruction.
The "default" variant does not even need to add the seed to the default secret, since it's 0, saving yet another operation.

Therefore, the default variant is supposed to be the fastest one, and seems the most appropriate for hash tables.

At least, that would be my expectation. Obviously, it's compiler driven, and different compilers, flags and even versions may result in different outcomes.

Note also that, providing both XXH3 with XXH_INLINE_ALL and a custom secret bundled together should allow the compiler to make the same kind of optimization when using the "full" variant, resulting in the same instructions as the "default" variant, just different constants.

Great ASM investigation @easyaspi314 ! Note that I would expect some of these operations to be folded, depending on the exact variant. The "full" variant must load the key values from the provided custom `secret`, and add the `seed`. The "seed" variant uses the default `secret` : in this case, I would expect the compiler to embed the `secret` values _directly into instructions_. This would save a corresponding `load` instruction. The "default" variant does not even need to add the `seed` to the default `secret`, since it's `0`, saving yet another operation. Therefore, the `default` variant is supposed to be the fastest one, and seems the most appropriate for hash tables. At least, that would be my expectation. Obviously, it's compiler driven, and different compilers, flags and even versions may result in different outcomes. Note also that, providing both `XXH3` with `XXH_INLINE_ALL` and a custom secret bundled together should allow the compiler to make the same kind of optimization when using the "full" variant, resulting in the same instructions as the "default" variant, just different constants.

pitrou commented 2019-09-16 06:46:52 -05:00 (Migrated from github.com)

• Copy link
• Copy Markdown

Ok, I've tried with clang 7.0. The absolute numbers are different, but the slowdown is similar (~30% slower on the tiny string hashing micro-benchmark, 5-10% slower on the hashtable benchmarks).

Ok, I've tried with clang 7.0. The absolute numbers are different, but the slowdown is similar (~30% slower on the tiny string hashing micro-benchmark, 5-10% slower on the hashtable benchmarks).

👍 1

Sign in to join this conversation.

No Branch/Tag specified

Branches Tags

dev

dependabot/github_actions/actions/upload-artifact-7.0.2

dependabot/github_actions/actions/download-artifact-8.0.2

dependabot/github_actions/actions/setup-node-7.1.0

archive/20261011T062114Z-rescue/fhgffy/fix/cmake-dispatch-off

dependabot/github_actions/msys2/setup-msys2-2.33.0

archive/20261011T062114Z-rescue/filtede98/fix-null-guards

ci/release-windows

fix/mingw-exe-symlink

gh-pages

release

ci/pin-actions

docs/refresh-readme

archive/20261011T062114Z-recovered/docs/refresh-readme

v0.8.4

v0.8.3

v0.8.2

v0.8.1

v0.8.0

v0.7.4

v0.7.3

v0.7.2

v0.7.1

v0.7.0

graphs

v0.6.5

v0.6.4

v0.6.3

v0.6.2

v0.6.1

v0.6.0

v0.5.1

v0.5.0

r42

r41

r40

r39

r38

r37

r36

r35

Labels

Clear labels   

announcement

  

bug

  

build

  

CI

Continuous Integration tests

  

dependencies

Pull requests that update a dependency file

  

documentation

  

duplicate

  

enhancement

  

experience feedback

  

feature request

  

github_actions

Pull requests that update GitHub Actions code

  

help wanted

  

install

  

invalid

  

Long-term

  

optimization

  

portability

  

question

  

target-specific

issue triggered in a specific environment (harware, compiler, OS)

  

test issue

  

wontfix

No labels

announcement

bug

build

CI

dependencies

documentation

duplicate

enhancement

experience feedback

feature request

github_actions

help wanted

install

invalid

Long-term

optimization

portability

question

target-specific

test issue

wontfix

Milestone

Clear milestone

No items

No milestone

Assignees

Clear assignees

No assignees

1 participant

Notifications

Subscribe

Due date

The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set

Reference

gh-Cyan4973/xxHash#249

No description provided.