4 ms·
A latency improvement would be to have digitCountThresholds be indexed by the lzcnt, instead of the result of the other LUT. Increases the size of that lookup t
by dzaima 2y ago
A latency improvement would be to have digitCountThresholds be indexed by the lzcnt, instead of the result of the other LUT. Increases the size of that lookup table from 160B to 512B though. Funnily enough I've had this approach in a local copy of Ryu when I was working on cutting it down for my purposes. Unfortunately whatever ended up public had cut this out too.
edit: some chat messages of me at [0]. Some previous unrelated discussion found at [1].
[0]: https://app.element.io/#/room/#bqn:matrix.org/$KKIK86x0tygAfOodAx6z5ZD3lc8iSrKRXxMmYlE2Le8 https://app.element.io/#/room/#bqn:matrix.org/$KKIK86x0tygAf... (arbitrarily capped at 18 digits because Ryu didn't need more)
[1]: https://github.com/ulfjack/ryu/issues/34 https://github.com/ulfjack/ryu/issues/34
- adgjlsfhk1 2y agoyou can cut back the table size at the cost of 1 cycle latency by shifting the lzcnt right by 3. this works since 2^3<10
- dzaima 2y agoThat doesn't work - the numbers change every 3 or 4 entries, i.e. ~log2(10), not 10. (and the precise point of change is important too)
- adgjlsfhk1 2y agoGood point. The other option is to use (1233*(64-lzcnt(x)))>>12 to bypass the first lookup entirely (not sure if this is faster or not), which works since 1233/2^12 is close enough to log_2(10).
- dzaima 2y agoMultiplication typically takes 3 cycles, so a total of 1+3+1=5 cycles of latency. A load from L1 takes 4-5 cycles on non-ancient x86 and Apple M1. So roughly on-par, perhaps a bit faster, at the cost of eating some ILP in the odd case that there's not still plenty left (also better if not already in-cache, though only significantly so if using that instead of the lzcnt directly as the threshold table index).