Re:Avoiding instruction cache misses (2019)
by jorangreef on Friday January 08, 2021 @05:54AM
(#25683440)
Yes :)
By a hair of 1ms on the sprint data set (76ms vs 77ms), but by 2x on the long distance marathon data set, compared to the next runner up, who also used a switching hybrid to enter two types of "runner" in terms of algorithm, but with a single switch point instead of a curve so the sprint algorithm wasn't always used when it should have been, and a slower long distance algorithm that used a more theoretically optimal algorithm but with pointer chasing and more cache misses on real hardware.
This was also in JavaScript, on a literal V8 input data string instead of a Node.js buffer, and the thing that really helped was taking time upfront to first recode the string to a buffer. Sounds crazy and slow and unintuitive, but byte operations on a buffer are way faster than charCodeAt() function calls on a string and this more than made up for the upfront recoding. This came the closest to the "null cipher" imaginary competitor I had, close enough within a few percent, of all the prototypes I tried, so I submitted...
By a hair of 1ms on the sprint data set (76ms vs 77ms), but by 2x on the long distance marathon data set, compared to the next runner up, who also used a switching hybrid to enter two types of "runner" in terms of algorithm, but with a single switch point instead of a curve so the sprint algorithm wasn't always used when it should have been, and a slower long distance algorithm that used a more theoretically optimal algorithm but with pointer chasing and more cache misses on real hardware.
This was also in JavaScript, on a literal V8 input data string instead of a Node.js buffer, and the thing that really helped was taking time upfront to first recode the string to a buffer. Sounds crazy and slow and unintuitive, but byte operations on a buffer are way faster than charCodeAt() function calls on a string and this more than made up for the upfront recoding. This came the closest to the "null cipher" imaginary competitor I had, close enough within a few percent, of all the prototypes I tried, so I submitted...