4 ms·

The ASPLOS paper makes a bold assertion regarding the first example: > To the best of our knowledge, it is truly optimal: it is the fastest program for this fu

by pbsd 14y ago

The ASPLOS paper makes a bold assertion regarding the first example: > To the best of our knowledge, it is truly optimal: it is the fastest program for this function written in the 64-bit x86 (x86-64) instruction set. This is an unwise claim to make, since x86_64 speed is a moving target, and what is fast today will not be 6 months from now. For example, this sequence should be slightly superior on modern Intel CPUs: mov edx, edx shl rcx, 32 ; xor rcx, rdx ; mov rax, rcx lea rax, [rdx + rcx] mul rsi add rdi, r8 adc rdx, 0 add rax, rdi adc rdx, 0 mov r8, rdx mov rdi, rax

jacques_chester 14y ago
> This is an unwise claim to make, since x86_64 speed is a moving target, and what is fast today will not be 6 months from now. It's pointed out that the optimizations can be changed. Nature-inspired techniques are very good at updating solutions in dynamic search spaces.
- pbsd 14y ago
  I simply meant the specific example they give and discuss in Fig. 1. The technique itself looks sound (and pretty cool).
  - jacques_chester 14y ago
    Right, it's a moving target. Basically you'd adjust the cost function each time a new instruction comes along and rerun the optimiser to see what changes. Thinking about dealing with a changing search space makes me wonder what an ant colony optimiser JIT would look like. A graph of instructions, maybe? With escalating path lengths? edit: but then I need to update the graph based on the next legal instruction and voila, it looks a lot like markov chains with 0/1 probabilities :|
nkurz 14y ago
Wow, that's really embarrassing. I checked against IACA (http://software.intel.com/en-us/articles/intel-architecture-code-analyzer http://software.intel.com/en-us/articles/intel-architecture-...) in case I was missing something, and it agrees that your version is 2 cycles faster on Sandy Bridge. Worse, while both blocks are slower on Nehalem than Sandy Bridge, yours appears to be 2 cycles faster on the older architecture as well. Seeing as that came out in 2008, it's hard to be charitable to their boasting. Would you mind if I use your sample code to ask the authors?
- pbsd 14y ago
  Sure, you can use that however you wish.

by pbsd 14y ago

jacques_chester 14y ago

> This is an unwise claim to make, since x86_64 speed is a moving target, and what is fast today will not be 6 months from now. It's pointed out that the optimizations can be changed. Nature-inspired techniques are very good at updating solutions in dynamic search spaces.

pbsd 14y ago
I simply meant the specific example they give and discuss in Fig. 1. The technique itself looks sound (and pretty cool).
- jacques_chester 14y ago
  Right, it's a moving target. Basically you'd adjust the cost function each time a new instruction comes along and rerun the optimiser to see what changes. Thinking about dealing with a changing search space makes me wonder what an ant colony optimiser JIT would look like. A graph of instructions, maybe? With escalating path lengths? edit: but then I need to update the graph based on the next legal instruction and voila, it looks a lot like markov chains with 0/1 probabilities :|

nkurz 14y ago

Wow, that's really embarrassing. I checked against IACA (http://software.intel.com/en-us/articles/intel-architecture-code-analyzer http://software.intel.com/en-us/articles/intel-architecture-...) in case I was missing something, and it agrees that your version is 2 cycles faster on Sandy Bridge. Worse, while both blocks are slower on Nehalem than Sandy Bridge, yours appears to be 2 cycles faster on the older architecture as well. Seeing as that came out in 2008, it's hard to be charitable to their boasting. Would you mind if I use your sample code to ask the authors?

pbsd 14y ago
Sure, you can use that however you wish.