LarsKrimi
3 days ago
> The switch in sparse_8 could be simplified by dividing x by eight before the jump. Interestingly, gcc doesn't find this simplification.
It could not because that would ensure that 7 values for each case would be handled by function calls instead of the default case - 0/8 is 0, but 3/8 is also 0
rep_lodsb
3 days ago
All the values are divisible by 8, so it could do it like this:
cmp eax,40
ja <return 0>
test eax,7
jnz <return 0>
jmp JumpTable[rax]LarsKrimi
3 days ago
Okay. Good point, that is quite a bit shorter than I first thought of
A rough benchmark of a version of that against the original shows it to be close to twice as fast for unpredictable input with GCC (4.5 ns vs 2.72 ns) on my old machine. With predictable input where x values often are the same the original version is quicker
int sparse_8_jump(int x, int val) {
unsigned int idx = (unsigned int)x >> 3;
if (idx > 5)
return 0;
if (x & 7)
return 0;
switch (idx) {
case 0:
return f0(val);
case 1:
return f1(val);
case 2:
return f2(val);
case 3:
return f3(val);
case 5:
return f4(val);
default:
return 0;
}
}ack_complete
3 days ago
Think it could also be done with rotate, but unsure if it'd be faster:
mov ecx, eax
ror eax, 3
cmp eax, 5
ja <return 0>
jmp JumpTable[rcx]Findecanor
3 days ago
Reducing the range would have been useful to reduce the size of a jump table, but when you have a decision tree then it does not matter.
... unless the size of immediate parameters would have affected code size. In the example code however, all constants fit in an `imm8` parameter to `cmp`.