4 ms·

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 surpri

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 https://github.com/shraddhaag/1brc/issues/2

pillusmany 3y ago
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.
- treyd 3y ago
  If you're clever about how you initially take apart the input you can just do a single memory load at a computed offset.
  - praptak 3y ago
    I don't see how you can make computing the offset faster than just parsing the number.
    - PeterisP 3y ago
      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.
      - akvadrako 3y ago
        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/ https://specbranch.com/posts/lookup-tables/
      - heavenlyblue 3y ago
        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.
        nwellnhof 3y ago
        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.
    - pletnes 3y ago
      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…)
    - samatman 3y ago
      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.
K0nserv 3y ago
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 https://github.com/k0nserv/brc/blob/main/src/main.rs#L279
KingOfCoders 3y ago
Wouldn't you need a fixed length of the temps? 00.1 -10.3 or 0.1 (with an ending space) so you can look up 5 bytes in the map? (+/i, two digits, dot, one digit)
- codegladiator 3y ago
  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)
  - KingOfCoders 3y ago
    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
    - codegladiator 3y ago
      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)
      - deleted 3y ago
        [deleted]

pillusmany 3y ago

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.

treyd 3y ago
If you're clever about how you initially take apart the input you can just do a single memory load at a computed offset.
- praptak 3y ago
  I don't see how you can make computing the offset faster than just parsing the number.
  - PeterisP 3y ago
    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.
    - akvadrako 3y ago
      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/ https://specbranch.com/posts/lookup-tables/
    - heavenlyblue 3y ago
      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.
      - nwellnhof 3y ago
        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.
  - pletnes 3y ago
    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…)
  - samatman 3y ago
    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.

K0nserv 3y ago

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 https://github.com/k0nserv/brc/blob/main/src/main.rs#L279

KingOfCoders 3y ago

Wouldn't you need a fixed length of the temps? 00.1 -10.3 or 0.1 (with an ending space) so you can look up 5 bytes in the map? (+/i, two digits, dot, one digit)

codegladiator 3y ago
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)
- KingOfCoders 3y ago
  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
  - codegladiator 3y ago
    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)
    - deleted 3y ago
      [deleted]