I imagine that you are not allowed to allocate a constant array that would contain a mapping between ASCII values of integers and the actual ints :)? The're just 255 of them needed. Or woukd it be slower?
For most CPUs you can do multiple lookups at once and have multiple in flight. This would allow you to use 256 bytes which should be able to stay in lower level cache once you start doing any meaningful number of conversions.
So not necessarily enormous and dog slow... but the real test is put it with the rest of your real code and see what happens. If you come to a certain answer it may not stay the same for another real bit of code.
Yeah you're right, I didn't consider that. However even if you allocate a 16 mln array you'll only need to access ~26 different cache lines, so it might still be ok? That's assuming that my calculation is correct that numbers will be grouped in tens, e.g. 240-249 would be on the same cache line as their numeric values are different by just 10
Also, the 8-bit lookup table only saves you a couple subtractions and conditional moves from the naive solution? That seems like one of the worst tradeoffs to make.
That's kinda neat. Actually, if you're doing that, you may as well reduce it to a single shift+or:
a = ((a >> 12) | a) & 0xfff
You could also skip the xor with 0x303030 by adjusting the lookup table accordingly.
Unfortunately, you'd still need to factor in the length argument somehow. That is, if given "23" with length=1, it should parse to 2, not 23. You could address this with a variable shift, but at that point, I can't see it being any better than a multiply+shift, even assuming the lookup table is fully cached.
The other major issue is validation, which the lookup table doesn't help much with.
It's unclear what is in the highest byte, so I assume not 0x000x0y0z, but 0xab0x0y0z where ab is unknown (in the past comment I used XX for this). If highest byte is known, then sure, even better.
I think you're right. Even better. Did you have time to bench it, etc.?
I see what you mean by length. I just skimmed over the text originally as I don't have time for rather lame problems like this. I'd just add 3 bits of length to be part of the index, job done. 12KB lookup table instead of 4KB, assuming 0 is not a valid value (negate to avoid needing 0b11).
Adding the length means another shift+or operation at minimum. I already think this is slower than the technique presented in the article, and this would make it worse.
It's an interesting idea, but I don't see it being practical, even if the size of the table wasn't an issue.
Instruction level parallelism will make extra shift free. Other than this it needs to be benched and might depend on cpu/arch. I don't care enough to bench and optimize further.
It's most definitely not free. It'd consume fetch bandwidth, decode/rename/scheduler slots, an execution port etc.
The comparison here is:
((v ^ 0x303030) * 0x640a0100) >> (len << 3)
against:
table[(((v >> 12) | v) & 0xfff) | (len << 12)]
The former is 4 ops, the latter is 6 ops, so throughput wise, the former wins. Latency wise, it also wins, considering that L1 cache lookups are generally 3-5 cycles, whilst integer multiply is typically 3-4.
A compiler could do that - involves inserting bswap on the way to/from memory, might also be a worthwhile flag for big endian machines that want to execute code that assumes little endian load/stores. I don't know of an implementation of such though.
This (from the op, not from Kaz) reads as nonsense. Half the union is unused so that should be a uint32_t. Looks like a failed attempt to bypass aliasing limitations. The out of bounds read is bad, would segv if you aimed shortly before a page you don't have permission to read. Maybe the subsequent shuffling does something useful but it's dubious to be returning a single uint8_t and a boolean (upcast to an int, weirdly) per four bytes of input.
Took another look at it and can't work out the interface. Reading ascii in base 10, but 'len' claims to be the length of the string and not how many digits to read, and the behaviour is roughly return 0 on non-ascii-numeric-char.
Maybe it's quicker than the unrolled loop, though I suspect if you mark the pointer aligned 4 (which would make the reading past the end segv-safe) the compiler would produce a single load for you from the byte at a time code.
uint32_t y = ((UINT64_C(0x640a0100) * digits.as_int)>>32)&0xff;
This makes assumptions about how a 64-bit int is laid out in memory. Not near a big endian system right now (I know, right?) but I'm pretty sure this is the problem.
I tried this out but it parsed the string "123\n" as 32.
Also it parses "400" as 144, when the reference implementation considers it not-a-uint8, but I don't mind so much about that.
EDIT: Ah, I think it assumes the string contains only a uint8, rather than trying to parse a uint8 from the start of a string. So you need to zero out the "\n" separately, and then it works.
Like the article says, it uses SWAR and requires a buffer of at least four bytes, with the trailing bytes zeroed. Your strings were both four bytes which saved you; had you tried with "42" or something, that would've been undefined behavior!
Edit: No, wait, the `len` parameter is there to ensure that trailing bytes don't matter. But note that it must be the length of the number-containing prefix part, not the whole input string!
> Also it parses "400" as 144
Did you check the return value? If false (as it is in case of overflow), the result is meaningless.
But the parsed value was 144. It's less than 256! It fits!
Indeed, all 3 conditions for returning true were satisfied. Just goes to show the value of accurate documentation: (Always safest to trust the docs. The code could easily be wrong!)
dlemire, you note that the read ”overflows”. Why can’t you copy just `len` bytes? Does it slow too much because of the branch/more load/store operations?
Yep ":>" does parse as 114. ";;" parses as 121. "<>" as 134. "999" parses as 231. Lots of work to do and nowhere close to being a magically clever and correct solution.
Note: \0 is implicit and redundant in C string literals. There is a fudge factor in some string handling semantics and it sort-of works without it with some UB risks that are platform specific. (It worked on GCC-13 on Linux on AMD EPYC.)
The literal ":>\0" gives us a 4 byte char array with the last two bytes being 0. I did this since the algorithm always does a 4 byte read from the passed pointer.
Oh yeah, wheee, I'm not carefully reading. Maybe it's vestigial leftovers from a port from c to c++ (major impls handle it in C++ like in C but the standard insists it's UB).
Is that still the case these days? I thought we lost that ability sometime around C99 (it's now UB to read from the inactive member), and you're now supposed to memcpy all over the place and hope the compiler elides it.
If you're not familiar with C, you might be unaware that there needs to be some way for code to know where the end of the string is. Supplying the length is a common way to achieve this (this other being a sentinel value (i.e. a null terminator)).
so there is a program processing a bunch of text containing 8 bit numbers and the way they process it is to have a single call to func() over and over for every small string length 1 to 3?
66 comments
[ 3.1 ms ] story [ 127 ms ] threadThe naive approach where you just index with the ASCII values you have would have to contain 16 million elements since it needs to look at 3 bytes.
Anything more space efficient than that would probably be slower than TFA.
So not necessarily enormous and dog slow... but the real test is put it with the rest of your real code and see what happens. If you come to a certain answer it may not stay the same for another real bit of code.
Also, the 8-bit lookup table only saves you a couple subtractions and conditional moves from the naive solution? That seems like one of the worst tradeoffs to make.
a = v ^ 0x30303030lu // normalize to digits 0xXX0a0b0c
b = (a << 12) | a // combine into XXXXXbacb0c
idx = (b >> 12) & 0xfff // get bac
res = lookup[idx]
a = ((a >> 12) | a) & 0xfff
You could also skip the xor with 0x303030 by adjusting the lookup table accordingly.
Unfortunately, you'd still need to factor in the length argument somehow. That is, if given "23" with length=1, it should parse to 2, not 23. You could address this with a variable shift, but at that point, I can't see it being any better than a multiply+shift, even assuming the lookup table is fully cached.
The other major issue is validation, which the lookup table doesn't help much with.
The lookup table can detect some, but not all errors, so yeah, it relies on valid input.
Your code doesn't handle the 'length' parameter, so the problem isn't the highest byte, it's bytes beyond 'length'.
I see what you mean by length. I just skimmed over the text originally as I don't have time for rather lame problems like this. I'd just add 3 bits of length to be part of the index, job done. 12KB lookup table instead of 4KB, assuming 0 is not a valid value (negate to avoid needing 0b11).
It's an interesting idea, but I don't see it being practical, even if the size of the table wasn't an issue.
The comparison here is:
((v ^ 0x303030) * 0x640a0100) >> (len << 3)
against:
table[(((v >> 12) | v) & 0xfff) | (len << 12)]
The former is 4 ops, the latter is 6 ops, so throughput wise, the former wins. Latency wise, it also wins, considering that L1 cache lookups are generally 3-5 cycles, whilst integer multiply is typically 3-4.
Note that the attribute is applied on `struct`s (and `union`s), taking effect for scalars within them, but does not recurse into further aggregates.
Took another look at it and can't work out the interface. Reading ascii in base 10, but 'len' claims to be the length of the string and not how many digits to read, and the behaviour is roughly return 0 on non-ascii-numeric-char.
Maybe it's quicker than the unrolled loop, though I suspect if you mark the pointer aligned 4 (which would make the reading past the end segv-safe) the compiler would produce a single load for you from the byte at a time code.
Also it parses "400" as 144, when the reference implementation considers it not-a-uint8, but I don't mind so much about that.
EDIT: Ah, I think it assumes the string contains only a uint8, rather than trying to parse a uint8 from the start of a string. So you need to zero out the "\n" separately, and then it works.
Edit: No, wait, the `len` parameter is there to ensure that trailing bytes don't matter. But note that it must be the length of the number-containing prefix part, not the whole input string!
> Also it parses "400" as 144
Did you check the return value? If false (as it is in case of overflow), the result is meaningless.
It returns 1 even though 400 is too large.
Indeed, all 3 conditions for returning true were satisfied. Just goes to show the value of accurate documentation: (Always safest to trust the docs. The code could easily be wrong!)
- string is 3 chars or less
- string contains no non-digit chars
- parsed value is less than 256
https://hn.algolia.com/?q=lemire+parsing
https://godbolt.org/z/5xa33qbar
Note: \0 is implicit and redundant in C string literals. There is a fudge factor in some string handling semantics and it sort-of works without it with some UB risks that are platform specific. (It worked on GCC-13 on Linux on AMD EPYC.)
(also removes the 64-bit multiply, which might be slow on 32-bit machines)
Sounds like the CPU should be designed in a smarter way, not the code.
"you are given a string and it's length".. i dont understand.
is the string like "1,1,22,2,189,3,12,2,120,3" ???
If you're not familiar with C, you might be unaware that there needs to be some way for code to know where the end of the string is. Supplying the length is a common way to achieve this (this other being a sentinel value (i.e. a null terminator)).
Maybe it's exactly like that, or maybe there's some variation to it, but the problem here has been simplified to make it more approachable.