5 ms·

Based on the title, I thought you were Daniel Lemire with another writeup for benchmarking character conversion of some sort - for examples see https://hn.algol

by canucker2016 6y ago

Based on the title, I thought you were Daniel Lemire with another writeup for benchmarking character conversion of some sort - for examples see https://hn.algolia.com/?q=lemire.me https://hn.algolia.com/?q=lemire.me. Great work on reducing the size of the character conversion tables, but I don't see any evidence for the title of the web page. "Compact character case conversion" is more appropriate currently based on the data given in the readme. Data can be greatly compressed at the cost of access speed or the compressed data could speed up data access - with x86 CPU complexity these days, I wouldn't bet on determining the speed based on a quick glance of the code. You state the case conversion is fast, yet I don't see any benchmarks backing up the assertion. I'd expect a few different types of input to be benchmarked - ASCII upper/lower case alphabet chars (typical A-Z,a-z & space/punctuation thrown in to make it look like typical written language text inputs), Unicode upper/lower case et al., and random characters. Not gonna leave people in the lurch though - Daniel Lemire has a recent post which can be used as a scaffold for benchmarking. Code: https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2021/02/09/toutf16.c https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/... Post: https://lemire.me/blog/2021/02/09/on-the-cost-of-converting-ascii-to-utf-16/ https://lemire.me/blog/2021/02/09/on-the-cost-of-converting-... If the code is to be timed on Windows, the code will need a Windows version of "clock_gettime(CLOCK_REALTIME, ...)" - see https://stackoverflow.com/questions/5404277/porting-clock-gettime-to-windows https://stackoverflow.com/questions/5404277/porting-clock-ge...

lifthrasiir 6y ago
Anything necessarily requiring lookup tables would be (comparably) slow. Unicode lookup tables are large, so it would be inherently slow for some inputs. For the performance you should assume the input distribution (e.g. ASCII is frequent even in Unicode texts, so we detect a run of ASCII and go SIMD). You can also combine adjacent operations: instead of working with Unicode scalar values, you can directly accept UTF-8 string and optimize tables for them (Oniguruma regexp engine of Ruby fame does this).
apankrat 6y ago
You want a benchmark that shows that one >>, one &, two [] and a + are going to be fast? The test loop that wraps the lookup code will likely take as much CPU as what's being benchmarked. Even if you are to use RDPMC and even if you are to use it very sparingly.
- yorwba 6y ago
  The naive solution uses just one [], so it's reasonable to ask whether the compressed solution is faster. (Especially for the higher compression levels with even more memory accesses.) And the relevant workload to benchmark wouldn't be just case-converting a single character, but a whole text, as would be done e.g. for constructing a case-insensitive search index. Because most texts contain only a limited range of characters, it's entirely possible that a large lookup table works just fine because only a tiny portion of it needs to fit into the cache.
  - Asooka 6y ago
    I'm fairly confident that since the lookup table fits comfortably in L1 cache, both algorithms will be about equally fast. You may see a difference if you have to case-fold the entire Library of Congress several times per user operation. The other case where there may be meaningful difference in performance would be embedded devices with small caches and slow memory.
    - vardump 6y ago
      Indirect memory lookups are slow, even if the data is in the L1 cache.
Someone 6y ago
I would guess the better cache locality of a much smaller lookup table could make the smaller table with more shifts and lookups beat the larger one in speed in real-world code (where other code also competes for cache lines) If you go down that rabbit hole, however, you might want to check whether foregoing using the shifts and lookups for 7-bit ASCII is even faster, if (as is often the case), you expect those characters to be the vast majority.
- vardump 6y ago
  You could test whether all of the characters in a SIMD (256 or 512 bits, so 32 or 64 UTF-8 chars) register are in 7-bit range and just use simple logical operations for lower or upper casing them in a few cycles. If not, then use a slow path with lookups.

lifthrasiir 6y ago

Anything necessarily requiring lookup tables would be (comparably) slow. Unicode lookup tables are large, so it would be inherently slow for some inputs. For the performance you should assume the input distribution (e.g. ASCII is frequent even in Unicode texts, so we detect a run of ASCII and go SIMD). You can also combine adjacent operations: instead of working with Unicode scalar values, you can directly accept UTF-8 string and optimize tables for them (Oniguruma regexp engine of Ruby fame does this).

apankrat 6y ago

You want a benchmark that shows that one >>, one &, two [] and a + are going to be fast? The test loop that wraps the lookup code will likely take as much CPU as what's being benchmarked. Even if you are to use RDPMC and even if you are to use it very sparingly.

yorwba 6y ago
The naive solution uses just one [], so it's reasonable to ask whether the compressed solution is faster. (Especially for the higher compression levels with even more memory accesses.) And the relevant workload to benchmark wouldn't be just case-converting a single character, but a whole text, as would be done e.g. for constructing a case-insensitive search index. Because most texts contain only a limited range of characters, it's entirely possible that a large lookup table works just fine because only a tiny portion of it needs to fit into the cache.
- Asooka 6y ago
  I'm fairly confident that since the lookup table fits comfortably in L1 cache, both algorithms will be about equally fast. You may see a difference if you have to case-fold the entire Library of Congress several times per user operation. The other case where there may be meaningful difference in performance would be embedded devices with small caches and slow memory.
  - vardump 6y ago
    Indirect memory lookups are slow, even if the data is in the L1 cache.

Someone 6y ago

I would guess the better cache locality of a much smaller lookup table could make the smaller table with more shifts and lookups beat the larger one in speed in real-world code (where other code also competes for cache lines) If you go down that rabbit hole, however, you might want to check whether foregoing using the shifts and lookups for 7-bit ASCII is even faster, if (as is often the case), you expect those characters to be the vast majority.

vardump 6y ago
You could test whether all of the characters in a SIMD (256 or 512 bits, so 32 or 64 UTF-8 chars) register are in 7-bit range and just use simple logical operations for lower or upper casing them in a few cycles. If not, then use a slow path with lookups.