Xxhash: Hashing case-insensitive strings

[gsagula]

Hi, what's the best way for handling case-insensitivity with xxHash?

Thanks!

[Cyan4973]

Uppercase your input before sending it to xxHash

[pichi]

Well, it depends. Are we talking about ASCII then yes. If we are talking about Unicode then no. For example, this is the reason why there is fc function in Perl because neither uppercase nor lowercase is the right answer. So right answer is to normalize your string in a case-insensitive way which could be a quite easy task in ASCII or very complicated in other encodings and character stets.

[gsagula]

Thanks for replying. It's for ASCII. However, I can't modify or copy the content. I have only a string_view (pointer to the string and length) of the string. A simpler hash would look like this

static uint64_t djb2CaseInsensitiveHash(absl::string_view input) {
    uint64_t hash = 5381;
    for (unsigned char c : input) {
      hash += ((hash << 5) + hash) + absl::ascii_tolower(c);
    };
    return hash;
  }

[pichi]

@gsagula What prevents you from copying? If you choose some buffer of size smaller than L1 CPU cache size (like half or less) and take care that compiler knows source and buffer can't be aliased so vectorization is safe you would probably have faster solution than djb2CaseInsensitiveHash() above because there is barrier between processing each byte of input. I guess you are considering xxHash for performance reasons, right?

[gsagula]

There's a bit of concern in terms of allocations given the context of the project, but I guess that's ok. I'll fire a perf benchmark to see how it goes. Thanks @pichi for all the tips!

[ifduyue]

@gsagula Why not use stack memory? No allocations. Maybe your string_view is too large to be filled in the stack, you still can copy them chunk by chunk.
Also you can invoke xxh32/64_update char by char.

[gsagula]

@ifduyue Thanks for the info. Any way that I could call xxh64_update char by char without explicitly having to create a new container for each char?

[Bulat-Ziganshin]

updating xxHash char--by-char will be even less efficient. I suggest you to alloc in the stack fixed-size char array (in the range of 64..1024 chars) and then copy data to this array in chunks and call xxHash update function on these chunks

[gsagula]

Right, I just did a benchmark test on both. Alloc is the way to go. Thanks, everyone!

[xtemp09]

I do not know, if it is related, but xxhsum cannot open file with non-standard characters, for example, it will try to open "åä.mkv" as "aa.mkv".

[Cyan4973]

I believe it's not related.
I suspect this is more a question of unicode support.
Are you compiling xxhsum on Windows ?

[xtemp09]

Yes, Windows 7 64-bit, g++ (x86_64-posix-seh-rev0, Built by MinGW-W64 project) 7.1.0.
chcp does not affect it.

[Cyan4973]

xxhsum uses standard C libraries,
it gets the file name through standard main() interface,
and just forwards it unmodified, to fopen().
In theory, this should be agnostic of any kind of format the filename is expressed in.

Unfortunately, if the C runtime library applies some transformation when providing argument to the main() interface, and is then unable to understand the same transformation on fopen() one, the whole assumptions of standard C are broken.

None of the platforms I'm using currently is Windows, which makes debugging such issue more difficult. My understanding is that Windows breaks some of the above assumptions with the way it handles unicode format for file names.

If my memory serves me right, on Visual, there are some project options available which can force the program to behave "normally".
Unfortunately, I have no idea how to solve the same kind of issue on mingw...