6 ms·

Search the transcript for 'SWAR'. That's the secret sauce for quickly converting ASCII digits, even with a decimal point separator, and combining them into an i

by canucker2016 2y ago

Search the transcript for 'SWAR'. That's the secret sauce for quickly converting ASCII digits, even with a decimal point separator, and combining them into an integer value. While not the actual code used in the solutions, here's an example of SWAR to convert ASCII numbers into an integer value. see https://lemire.me/blog/2022/01/21/swar-explained-parsing-eight-digits/ https://lemire.me/blog/2022/01/21/swar-explained-parsing-eig... The mind-bending stuff is the multiplication with the mul1 and mul2 constants.

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 ago
  Thanks, 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.)

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 ago
Thanks, 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.)