3 ms·
Nice write-up! (I read the transcript.) Maybe this is covered in the actual video, but one potential target for optimisation that I didn't see in the transcrip
by akoboldfrying 2y ago
Nice write-up! (I read the transcript.)
Maybe this is covered in the actual video, but one potential target for optimisation that I didn't see in the transcript was how the temperature values are converted to integers.
One suggestion is that, after deleting the period, if the numbers have at most 4 digits and 64-bit multiplication is available, the conversion to an integer can be done with a single such multiplication and a few shifts. Ensure each digit is in the low byte of a separate 16-bit word (that is, "space them out" with a zero byte in between each digit; this may require extra work, though there's often a SIMD "scatter"-type instruction that will accomplish it), subtract the ASCII value of the "0" digit from each 16-bit word's low byte (one instruction), then multiply by a constant which has 1000 in its lowest 16-bit word, 100 in the next-lowest, ..., 1 in the highest. The final answer will now be in the highest word, available with a 48-bit right shift.
If multiplication is slow, another trick to gain some speed is to not actually convert from decimal until you need to, possibly right at the end. That is, just subtract the ASCII value of the "0" digit from each 16-bit word's low byte, and then treat the resulting 64-bit value as a very wasteful BCD representation in which each decimal digit occupies 16 bits. These "integers" can be safely added to each other up to 65535/9=7281 times before there is a risk of overflow; you only need to convert to regular binary then. This representation also honours min and max operations.
- gunnarmorling 2y agoThanks for sharing! I don't think people did exactly that, but most indeed did leverage the fact that values only ranged from -99.9 to 99.9 with exactly one fractional digit and handled them as integers (avoiding FP maths) up until the very end when printing out the results.
- canucker2016 2y agoSearch 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 agoLooking 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.)