3 ms·
Looking at the fastest solution, the convertIntoNumber() function is where the magic happens. Specifically, line 318. The line above (long digits ... ) conver
by canucker2016 2y ago
Looking at the fastest solution, the convertIntoNumber() function is where the magic happens.
Specifically, line 318.
The line above (long digits ... ) converts from ASCII digits ('0'-'9') to actual numeric digits (range 0-9)
Line 318 does the shift into position and addition to combine the 1-3 digits via one multiplication, left-shift and mask operation.
see https://github.com/gunnarmorling/1brc/blob/main/src/main/java/dev/morling/onebrc/CalculateAverage_thomaswue.java#L318 https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...
- akoboldfrying 2y agoThanks, that looks like exactly the single-multiplication approach I was suggesting, but with one improvement: They don't "space out" the TT and HH digits as I thought would be necessary. I assumed that leaving these digits in adjacent bytes would cause the multiplication by 100 to corrupt the top 2 bits of the final answer (the bits corresponding to the "3" in the final mask with 0x3FF), but it turns out they actually don't, since 100 = 64+32+4 -- that is, 100 in binary leaves the low 2 bits off, thus so will any integer multiple of 100, so multiplying TT by 100 will not contaminate those 2 bits after all! This is a really lucky coincidence that would not work out for every base. (Lemire's calculation, in contrast, uses the add-adjacent-blocks trick, so takes a logarithmic number of multiplications -- 3 for his 8- digit calculation, which would become 2 for a 3- or 4- digit calculation.)