Parsing short hexadecimal strings efficiently

Re:Parsing short hexadecimal strings efficiently by daeken on Wednesday April 17, 2019 @03:51PM (#19685857)

I don't have the spare cycles to test this out for myself right now, but I'm curious if a 64kb table would be substantially faster. You'd cut it down from 8 indirections, 3 shifts, and 3 ORs to 4 indirections, 1 shift, and 1 OR.

    uint32_t hex_to_u32_lookup(const uint8_t *src) {
     uint16_t *wsrc = (uint16_t *) src;
     uint32_t v1 = digittoval[wsrc[0]];
     uint32_t v2 = digittoval[wsrc[1]];
     return v2 << 8 | v1;
    }

(Also, small note: The function is named `hex_to_u32_lookup` but it only gives a 16-bit result. Might want to clarify in the post.)

[ Parent | on HN ]

Re:Parsing short hexadecimal strings efficiently by 0815test on Wednesday April 17, 2019 @04:13PM (#19686076)

One comment in the article pointed out that you could create a 4GB lookup table, and convert 32 bits of input at once. This is actually less silly than might otherwise seem, because only 64KB of it would ever be read for correct input; the table itself would only exist as a reservation somewhere in the process' 64-bit (well, 48-bit actually, but still) virtual address space, so a lookup of invalid input could easily be made to error out and return some error condition.

For that matter, I'd want to run the author's "fancy math-based function" through a superoptimizer and check that there isn't something that can do the job in fewer cycles.

[ Parent | on HN ]

Re:Parsing short hexadecimal strings efficiently by BonesJustice on Wednesday April 17, 2019 @06:31PM (#19687017)

Wouldn’t the ‘valid’ values in such a table be relatively sparse, creating a high likelihood of cache misses? The guy’s agonizing over 4 cycles, but a cache miss is far more costly.

[ Parent | on HN ]

Re:Parsing short hexadecimal strings efficiently by hairtuq on Wednesday April 17, 2019 @06:22PM (#19686962)

I tried using https://github.com/falk-hueffner/sematrope. Best I can get is x - ((x >> 4) ^ 0x33), should be slightly faster. EDIT: unfortunately that works only for upper case letters.

[ Parent | on HN ]