Comment by daeken | Hacker News Reader

Comment by daeken | Hacker News Reader

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.)

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.

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.

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.

Reply on news.ycombinator.com