5 ms·

Questions about Superoptimization

79 points by nkurz 10y ago

awirth 10y ago
The nop and xchg in the GCC output are padding to make the next function aligned. You can ignore everything after the ret. The execution of movzx should be negligible. The big difference between the code generated by GCC and the code generated by clang is that the clang code does everything using 8-bit registers, and zero-extends at the end, whereas the GCC code does everything with full 32-bit registers. I actually had never seen the dil register before this (it's the low 8-bits of the [er]?di register). It's pretty cool that clang uses this when it knows the value in the first argument is byte-sized. I think it's also neat seeing how the compilers use the commutativity of binary-and differently, and end up anding in a different order. Overall I like the clang code better, as it seems closer to the asm someone might write by hand.
- chubot 10y ago
  OK thanks, do you know why it's 16-byte aligned? The Clang code is exactly 16 bytes but the GCC code is 20 bytes and it pads it out to 32. For i-cache maybe? (I asked this on reddit too)
  - awirth 10y ago
    It's definitely an optimization thing, but I'm not actually sure off the top of my head why. According to https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Opt... -falign-functions is enabled at -O2 and higher, unless you use -Os. Presumably something about aligned instruction fetch/decoding can be faster.
- dumael 10y ago
  > It's pretty cool that clang uses this when it knows the value in the first argument is byte-sized. Clang is using the 8 bit subregister due to how it legalizes types. When LLVM-IR is compiled for a target, it undergoes a process called "legalization" where invalid operations for the target are Expanded (replace the invalid operation with a semantically equivalent but legal series of operations), or Promoted (e.g. promote operations on boolean types to character types), Libcall (call out to the likes of libgcc.a) or Legal where the target directly supports the operation. Since X86(_64) supports 8, 16, 32 (and 64) bit register accesses and operations, operations on variables of those sizes will be matched to the corresponding operation and register sizes. If you were to compile that code for the likes of MIPS, ARM or PowerPC you'd see fully 32 bit code.
nightcracker 10y ago
My comments here are not to the posted article, but the one referenced at the top: http://www.oilshell.org/blog/2016/12/23.html http://www.oilshell.org/blog/2016/12/23.html def LookupKind(id): return KIND_TABLE[id] def LookupKind(id): return 175 & id & ((id ^ 173) + 11) > The second implementation is faster because it doesn't require any memory accesses. This is not necessarily true. If this function is in a hot loop, and the entire lookup table fits in L1 cache you can treat KIND_TABLE[id] as only taking ~1-2 cycles. > Jeff Dean also posed this question in his talk: How long it does it take to quicksort 1 billion 4-byte integers? It surprised me that he estimated it by simply counting the number of branch mispredictions, which is described in this post. This is no longer true. In state of the art implementations quicksort is implemented in a branchless fashion. See https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort for details (I'm the author of pdqsort, old username on HN). The trick is to first replace directly swapping misplaced elements in a loop by first finding a buffer of elements on the left that should be on the right, and a buffer of elements that are on the right but should be on the left. This can be done in a branchless manner: buffer_num = 0; buffer_max_size = 64; for (int i = 0; i < buffer_max_size; ++i) { // With branch: if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; } // Without: buffer[buffer_num] = i; buffer_num += (elements[i] < pivot); } These buffers can then also be swapped branchlessly.
- chubot 10y ago
  Thanks for the link on sorting -- that looks really interesting! I think it's fair to say that the expression is no slower than the lookup table. Even if missing the cache is rare, the penalty is large, so the average case will be significantly worse. I freely admit the problem is contrived, but I think most people would agree it is actually an optimization! If you really want to nitpick, you might want to count the "opportunity cost" of some other 221 bytes not being in L1 cache.
  - nightcracker 10y ago
    I haven't read about the rest of your problem much, but I usually think in terms of _cache pressure_. A lookup table can be very fast, but adds to the cache pressure. A large implementation with many special smart cases can also be very fast, but also adds to the cache pressure (instructions also need to be loaded from memory). Another thing I don't believe you mention is that not every n-instruction solution is equal (even if we only use single cycle instructions as possibilities). This is because of instruction-level parallelism. (a _ b) _ (c _ d) only takes two cycles to evaluate on a modern CPU. a _ (b _ (c _ d)) takes three.
powera 10y ago
If you're considering doing this, it's important to consider what you will do when you inevitably add additional values to the enum. If you have persistence or partial rollouts (and networked services always have partial rollouts) this is likely to break horribly. If the app never changes or it's used entirely in memory on a single process, you're fine.

79 points by nkurz 10y ago

The nop and xchg in the GCC output are padding to make the next function aligned. You can ignore everything after the ret. The execution of movzx should be negligible. The big difference between the code generated by GCC and the code generated by clang is that the clang code does everything using 8-bit registers, and zero-extends at the end, whereas the GCC code does everything with full 32-bit registers. I actually had never seen the dil register before this (it's the low 8-bits of the [er]?di register). It's pretty cool that clang uses this when it knows the value in the first argument is byte-sized. I think it's also neat seeing how the compilers use the commutativity of binary-and differently, and end up anding in a different order. Overall I like the clang code better, as it seems closer to the asm someone might write by hand.

chubot 10y ago
OK thanks, do you know why it's 16-byte aligned? The Clang code is exactly 16 bytes but the GCC code is 20 bytes and it pads it out to 32. For i-cache maybe? (I asked this on reddit too)
- awirth 10y ago
  It's definitely an optimization thing, but I'm not actually sure off the top of my head why. According to https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Optimize-Options https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#Opt... -falign-functions is enabled at -O2 and higher, unless you use -Os. Presumably something about aligned instruction fetch/decoding can be faster.
dumael 10y ago
> It's pretty cool that clang uses this when it knows the value in the first argument is byte-sized. Clang is using the 8 bit subregister due to how it legalizes types. When LLVM-IR is compiled for a target, it undergoes a process called "legalization" where invalid operations for the target are Expanded (replace the invalid operation with a semantically equivalent but legal series of operations), or Promoted (e.g. promote operations on boolean types to character types), Libcall (call out to the likes of libgcc.a) or Legal where the target directly supports the operation. Since X86(_64) supports 8, 16, 32 (and 64) bit register accesses and operations, operations on variables of those sizes will be matched to the corresponding operation and register sizes. If you were to compile that code for the likes of MIPS, ARM or PowerPC you'd see fully 32 bit code.

nightcracker 10y ago

My comments here are not to the posted article, but the one referenced at the top: http://www.oilshell.org/blog/2016/12/23.html http://www.oilshell.org/blog/2016/12/23.html def LookupKind(id): return KIND_TABLE[id] def LookupKind(id): return 175 & id & ((id ^ 173) + 11) > The second implementation is faster because it doesn't require any memory accesses. This is not necessarily true. If this function is in a hot loop, and the entire lookup table fits in L1 cache you can treat KIND_TABLE[id] as only taking ~1-2 cycles. > Jeff Dean also posed this question in his talk: How long it does it take to quicksort 1 billion 4-byte integers? It surprised me that he estimated it by simply counting the number of branch mispredictions, which is described in this post. This is no longer true. In state of the art implementations quicksort is implemented in a branchless fashion. See https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort for details (I'm the author of pdqsort, old username on HN). The trick is to first replace directly swapping misplaced elements in a loop by first finding a buffer of elements on the left that should be on the right, and a buffer of elements that are on the right but should be on the left. This can be done in a branchless manner: buffer_num = 0; buffer_max_size = 64; for (int i = 0; i < buffer_max_size; ++i) { // With branch: if (elements[i] < pivot) { buffer[buffer_num] = i; buffer_num++; } // Without: buffer[buffer_num] = i; buffer_num += (elements[i] < pivot); } These buffers can then also be swapped branchlessly.

chubot 10y ago
Thanks for the link on sorting -- that looks really interesting! I think it's fair to say that the expression is no slower than the lookup table. Even if missing the cache is rare, the penalty is large, so the average case will be significantly worse. I freely admit the problem is contrived, but I think most people would agree it is actually an optimization! If you really want to nitpick, you might want to count the "opportunity cost" of some other 221 bytes not being in L1 cache.
- nightcracker 10y ago
  I haven't read about the rest of your problem much, but I usually think in terms of _cache pressure_. A lookup table can be very fast, but adds to the cache pressure. A large implementation with many special smart cases can also be very fast, but also adds to the cache pressure (instructions also need to be loaded from memory). Another thing I don't believe you mention is that not every n-instruction solution is equal (even if we only use single cycle instructions as possibilities). This is because of instruction-level parallelism. (a _ b) _ (c _ d) only takes two cycles to evaluate on a modern CPU. a _ (b _ (c _ d)) takes three.

powera 10y ago

If you're considering doing this, it's important to consider what you will do when you inevitably add additional values to the enum. If you have persistence or partial rollouts (and networked services always have partial rollouts) this is likely to break horribly. If the app never changes or it's used entirely in memory on a single process, you're fine.