8 ms·

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 custo

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.

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.