Hacker News Reader

Comment by JensRantil | Hacker News Reader

Second article I'm reading on implementing this in Go. Since the temperatures are in the range [-99.9, 99.9] with a tenth of precision (~2k values), I am surprised why no one has implemented a parsing of the numbers using a prepopulated lookup table. Should probably speed things up.

I submitted a github issue on this for the other implementation I looked at here[1].

[1] https://github.com/shraddhaag/1brc/issues/2

View on HN

He already uses custom parsing.

How do you search in the lookup table? If you are thinking of a hash map it will be slower than the few operations of his custom parser.

If you're clever about how you initially take apart the input you can just do a single memory load at a computed offset.

I don't see how you can make computing the offset faster than just parsing the number.

You could have a much simpler parsing than ordinary parsing if you know/assume that you definitely have a valid number from -99.99 to 99.99.

For example, you could find whether it starts with a '-' and where the delimiter is to know the length of the number string representation (that's the "simpler parsing" part), and then don't do any work at all to decode the number, simply use these 1-5 bytes of that string (without sign and separator) directly as an index into a very large very sparse memory region in which all the valid values are pre-populated with the proper result.

You'd need to allocate 4 or 8 terabytes of virtual memory address space for that lookup table, but you'll touch only a tiny fraction of the memory pages, so it doesn't require an unacceptable amount of physical memory.

If that is faster would seem to depend on if you can get most lookups from the L2 cache. Otherwise you're waiting for main memory, which is a few hundred cycles. Even with multiple loads in parallel, it would be hard to beat arithmetic.

https://specbranch.com/posts/lookup-tables/

You don't need to cover all bits of the values, just 10 numeric values that can pass a a bounds check. That reduces the space to only 10K elements. With some bit shifting (and pre-validation) that should easily reduce the search space.

Creating a LUT index with bit-shifting is essentially the same as parsing into an integer. Even if the LUT fits in L1 cache, I doubt it would be faster. If it doesn't fit, it's certainly slower.

Take the bytes of the number, «-9.7», and interpret as an integer? That’s a 4-byte int -> array index. (Haven’t tried but…)

I'd start here: The ASCII for '9' is 0b00111001, a UInt8 9 is 0b00001001 (this was of course deliberate). So (A & 0b11110000) << 4 + (B & 0b11110000) to get the low byte, the high byte is an exercise for the reader, 16 bit jump table to the value, if there's a '-' you invert it.

I did it with custom parsing[0] and treated the numbers as 16 bit integers, the representation in the file is not a constant number of bytes which complicates the table approach. If you end up computing a hash I think it might be slower than just doing the equivalent parsing I do and a four byte constant table will be very large and mostly empty. Maybe a a trie would be good.

0: https://github.com/k0nserv/brc/blob/main/src/main.rs#L279

Wouldn't you need a fixed length of the temps?

  00.1
 -10.3

  0.1 (with an ending space)

so you can look up 5 bytes in the map? (+/i, two digits, dot, one digit)

you can create a perfect hash based on the presence of at least 4 characters. perfect hash is pre calculated based on possible inputs (-99.9 to 99.0 in bytes). the hash is usual byte*seed+hash. "seed" is chosen so that there is no clash (you can find a static seed in a single brute force from 1 to 1m in < 1 min)

I thought the lookup would just be a byte tree not a hash. Wouldn't a hash with it's calculation beat the purpose of being faster than parsing a number?

The idea would be, you have a tree of all values of 0.0 to 99.9 and then just use the bytes to iterate the tree (e.g. in an array) to come up with the int value of e.g. 45.5

parsing a number contains an (addition + multiplication) *(number of digits) for each row. if you do precalculated perfect hash then multiplication for each row can be avoided. ( you anyways need to read each byte)

Reply on news.ycombinator.com