3 ms·
When I worked on a semi-similar problem (a realtime-ish feed with lots of numbers), we found that it was better to just eat the extra RAM costs. Once you have
by Rebelgecko 6y ago
When I worked on a semi-similar problem (a realtime-ish feed with lots of numbers), we found that it was better to just eat the extra RAM costs.
Once you have variable width values, it gets much more expensive to answer questions like "Here's a file with every stock price, we know that Berkshire is the 1,000th one in the list, what is their current price?" Instead of being able to jump straight to the relevant bytes, you end up needing to parse (potentially) the entire file. Even with better CPU support for variable integer sizes, you're still essentially turning an O(1) operation into one that is O(N)
- bombcar 6y agoI wonder if a CPU could do something like have 9-bit bytes internally that would allow you to quickly jump over a list like that (use the 9th bit to indicate the first of a multi-byte sequence or something). You'd need dedicated hardware to make it as fast as 1000xRecordsize, though.
- firethief 6y agoThat's the typical approach to varints except optimized for hardware with 9-bit bytes. It's not the kind of thing that dedicated instructions can make faster, or we'd be using them all the time.