Hacker News Reader

Comment by nasretdinov | Hacker News Reader

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?

View on HN

That is likely to be extremely slow. https://news.ycombinator.com/item?id=37823805

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.

How would you actually implement that?

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

Here is a table-driven idea.

  #include <stdio.h>

  int bcd2dec[] = {
    [0x000] = 0, [0x001] = 1, [0x002] = 2, [0x003] = 3, [0x004] = 4,
    [0x005] = 5, [0x006] = 6, [0x007] = 7, [0x008] = 8, [0x009] = 9,
    [0x010] = 10, [0x011] = 11, [0x012] = 12, [0x013] = 13, [0x014] = 14,
    [0x015] = 15, [0x016] = 16, [0x017] = 17, [0x018] = 18, [0x019] = 19,
    [0x020] = 20, [0x021] = 21, [0x022] = 22, [0x023] = 23, [0x024] = 24,
    [0x025] = 25, [0x026] = 26, [0x027] = 27, [0x028] = 28, [0x029] = 29,
    [0x030] = 30, [0x031] = 31, [0x032] = 32, [0x033] = 33, [0x034] = 34,
    [0x035] = 35, [0x036] = 36, [0x037] = 37, [0x038] = 38, [0x039] = 39,
    [0x040] = 40, [0x041] = 41, [0x042] = 42, [0x043] = 43, [0x044] = 44,
    [0x045] = 45, [0x046] = 46, [0x047] = 47, [0x048] = 48, [0x049] = 49,
    [0x050] = 50, [0x051] = 51, [0x052] = 52, [0x053] = 53, [0x054] = 54,
    [0x055] = 55, [0x056] = 56, [0x057] = 57, [0x058] = 58, [0x059] = 59,
    [0x060] = 60, [0x061] = 61, [0x062] = 62, [0x063] = 63, [0x064] = 64,
    [0x065] = 65, [0x066] = 66, [0x067] = 67, [0x068] = 68, [0x069] = 69,
    [0x070] = 70, [0x071] = 71, [0x072] = 72, [0x073] = 73, [0x074] = 74,
    [0x075] = 75, [0x076] = 76, [0x077] = 77, [0x078] = 78, [0x079] = 79,
    [0x080] = 80, [0x081] = 81, [0x082] = 82, [0x083] = 83, [0x084] = 84,
    [0x085] = 85, [0x086] = 86, [0x087] = 87, [0x088] = 88, [0x089] = 89,
    [0x090] = 90, [0x091] = 91, [0x092] = 92, [0x093] = 93, [0x094] = 94,
    [0x095] = 95, [0x096] = 96, [0x097] = 97, [0x098] = 98, [0x099] = 99,
    [0x100] = 100, [0x101] = 101, [0x102] = 102, [0x103] = 103, [0x104] = 104,
    [0x105] = 105, [0x106] = 106, [0x107] = 107, [0x108] = 108, [0x109] = 109,
    [0x110] = 110, [0x111] = 111, [0x112] = 112, [0x113] = 113, [0x114] = 114,
    [0x115] = 115, [0x116] = 116, [0x117] = 117, [0x118] = 118, [0x119] = 119,
    [0x120] = 120, [0x121] = 121, [0x122] = 122, [0x123] = 123, [0x124] = 124,
    [0x125] = 125, [0x126] = 126, [0x127] = 127, [0x128] = 128, [0x129] = 129,
    [0x130] = 130, [0x131] = 131, [0x132] = 132, [0x133] = 133, [0x134] = 134,
    [0x135] = 135, [0x136] = 136, [0x137] = 137, [0x138] = 138, [0x139] = 139,
    [0x140] = 140, [0x141] = 141, [0x142] = 142, [0x143] = 143, [0x144] = 144,
    [0x145] = 145, [0x146] = 146, [0x147] = 147, [0x148] = 148, [0x149] = 149,
    [0x150] = 150, [0x151] = 151, [0x152] = 152, [0x153] = 153, [0x154] = 154,
    [0x155] = 155, [0x156] = 156, [0x157] = 157, [0x158] = 158, [0x159] = 159,
    [0x160] = 160, [0x161] = 161, [0x162] = 162, [0x163] = 163, [0x164] = 164,
    [0x165] = 165, [0x166] = 166, [0x167] = 167, [0x168] = 168, [0x169] = 169,
    [0x170] = 170, [0x171] = 171, [0x172] = 172, [0x173] = 173, [0x174] = 174,
    [0x175] = 175, [0x176] = 176, [0x177] = 177, [0x178] = 178, [0x179] = 179,
    [0x180] = 180, [0x181] = 181, [0x182] = 182, [0x183] = 183, [0x184] = 184,
    [0x185] = 185, [0x186] = 186, [0x187] = 187, [0x188] = 188, [0x189] = 189,
    [0x190] = 190, [0x191] = 191, [0x192] = 192, [0x193] = 193, [0x194] = 194,
    [0x195] = 195, [0x196] = 196, [0x197] = 197, [0x198] = 198, [0x199] = 199,
    [0x200] = 200, [0x201] = 201, [0x202] = 202, [0x203] = 203, [0x204] = 204,
    [0x205] = 205, [0x206] = 206, [0x207] = 207, [0x208] = 208, [0x209] = 209,
    [0x210] = 210, [0x211] = 211, [0x212] = 212, [0x213] = 213, [0x214] = 214,
    [0x215] = 215, [0x216] = 216, [0x217] = 217, [0x218] = 218, [0x219] = 219,
    [0x220] = 220, [0x221] = 221, [0x222] = 222, [0x223] = 223, [0x224] = 224,
    [0x225] = 225, [0x226] = 226, [0x227] = 227, [0x228] = 228, [0x229] = 229,
    [0x230] = 230, [0x231] = 231, [0x232] = 232, [0x233] = 233, [0x234] = 234,
    [0x235] = 235, [0x236] = 236, [0x237] = 237, [0x238] = 238, [0x239] = 239,
    [0x240] = 240, [0x241] = 241, [0x242] = 242, [0x243] = 243, [0x244] = 244,
    [0x245] = 245, [0x246] = 246, [0x247] = 247, [0x248] = 248, [0x249] = 249,
    [0x250] = 250, [0x251] = 251, [0x252] = 252, [0x253] = 253, [0x254] = 254,
    [0x255] = 255,
  };

  /*
   * If the input is an empty string or a string of length four or more,
   * we return -1. Other than that, we assume we have digits.
   */
  int parse_uint8_bcd(const char *str)
  {
    if (!str[0])
      return -1;
    if (!str[1])
      return str[0] & 0xF;
    if (!str[2])
      return bcd2dec[(str[0] & 0xF) << 4 | (str[1] & 0xF)];
    if (!str[3])
      return bcd2dec[(str[0] & 0xF) << 8 | (str[1] & 0xF) << 4 | (str[2] & 0xF)];
    return -1;
  }

  int main(int argc, char **argv)
  {
    if (argv[1])
      printf("value of %s is %d\n", argv[1], parse_uint8_bcd(argv[1]));

    return 0;
  }

Table element should be unsigned char, otherwise it's wastefully large. Oversight.

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

Would use XOR 0x30303030lu, then OR with a value shifted left 12 bits, take bits 24..12 and lookup in 4k pre-computed lookup array.

How are you packing the number into 12 bits? Multiple shift+and+or operations? If so, I'd expect that to generally be slower than a multiply+shift.

it's one XOR, SHL, OR, SHR, AND, on some archs the shifts might come free with the other instruction. I'd expect it to be faster.

a = v ^ 0x30303030lu // normalize to digits 0xXX0a0b0c

b = (a << 12) | a // combine into XXXXXbacb0c

idx = (b >> 12) & 0xfff // get bac

res = lookup[idx]

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.

Might be wrong but this shortcut corrupts the lower bits with garbage from the higher byte.

The lookup table can detect some, but not all errors, so yeah, it relies on valid input.

I can't see how it's any different. If you have 0x0y0z, a shift+or gives 0x0yxz, so the result is same as what you have, just with fewer operations.

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.

The '& 0xfff' eliminates the highest byte, so it doesn't matter what it is.

Your code doesn't handle the 'length' parameter, so the problem isn't the highest byte, it's bytes beyond 'length'.

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.

You'd need a very sparse array of 2^(3*8) =~ 16 million entries, not 256, since you're going in the other direction. A hashtable might work.

Reply on news.ycombinator.com