4 ms·

As for size = -size I think he was inverting the bits then adding 1 in one step (or something similar). Just a guess.

by _nalply 10y ago

efaref 10y ago
This is a good example of a pointless "optimization" making the code harder to read. If he had indeed meant that, he should have written x = ~x + 1; GCC, even with optimisation turned off, will turn that into a negl instruction.
- joosters 10y ago
  He mentions Visual Studio often in the page, and the code is several years old. Perhaps your alternative doesn't optimise well across the compilers he used, back several years ago when the author was developing the code. In any case, there are unknowns here. Perhaps you should be less hasty in declaring people's work 'pointless' and telling others what they 'should' have done?
kstrauser 10y ago
That paragraph lost my interest in the project. He's writing a function that has to work perfectly, every time, in all situations, and gets used A LOT. And yet, he never bothered to document his reasoning and no longer knows why it works? No thanks.
nkurz 10y ago
I didn't look at the code, but I often use something similar in assembly when hyper-optimizing loops. The fastest memcpy-like loop structure I've found on x64 involves using a negative offset from the end of the region, which is then incremented until it hits zero. The advantage of this construct is that you can use the flags set by the increment to test for loop termination, rather than needing an additional comparison. The problem in C is that the compiler tends to "unoptimize" it for you after seemingly innocuous changes. Anyway, the loop ends up looking something like this: char *end = start + size; size_t neg = -size; do { register = *(end + neg); process(register); neg += advance; } while (neg); For certain loops this construct shaves off 1 cycle per iteration, at the cost of ~1 cycle of initial setup cost. I'm wagering that he was doing something similar, but just kept the name "size" after the negation, rather than switching to "neg" as I did here.
- DblPlusUngood 10y ago
  > The advantage of this construct is that you can use the flags set by the increment to test for loop termination, rather than needing an additional comparison. I don't understand your optimization. ZF is also set for dec, so why not just use dec and not negate the size?
  - nkurz 10y ago
    Sticking with a positive value and using dec or sub works if you just have a loop counter or if it's acceptable to process the data in your buffer backwards, but switching to negative lets you go through the buffer in standard ascending order. Sometimes data dependencies require this, and sometimes ascending works better for prefetching.
- _nalply 10y ago
  Your theory sounds way better than mine.

As for size = -size I think he was inverting the bits then adding 1 in one step (or something similar). Just a guess.

by _nalply 10y ago

As for size = -size I think he was inverting the bits then adding 1 in one step (or something similar). Just a guess.

This is a good example of a pointless "optimization" making the code harder to read. If he had indeed meant that, he should have written x = ~x + 1; GCC, even with optimisation turned off, will turn that into a negl instruction.

joosters 10y ago
He mentions Visual Studio often in the page, and the code is several years old. Perhaps your alternative doesn't optimise well across the compilers he used, back several years ago when the author was developing the code. In any case, there are unknowns here. Perhaps you should be less hasty in declaring people's work 'pointless' and telling others what they 'should' have done?

kstrauser 10y ago

That paragraph lost my interest in the project. He's writing a function that has to work perfectly, every time, in all situations, and gets used A LOT. And yet, he never bothered to document his reasoning and no longer knows why it works? No thanks.

nkurz 10y ago

I didn't look at the code, but I often use something similar in assembly when hyper-optimizing loops. The fastest memcpy-like loop structure I've found on x64 involves using a negative offset from the end of the region, which is then incremented until it hits zero. The advantage of this construct is that you can use the flags set by the increment to test for loop termination, rather than needing an additional comparison. The problem in C is that the compiler tends to "unoptimize" it for you after seemingly innocuous changes. Anyway, the loop ends up looking something like this: char *end = start + size; size_t neg = -size; do { register = *(end + neg); process(register); neg += advance; } while (neg); For certain loops this construct shaves off 1 cycle per iteration, at the cost of ~1 cycle of initial setup cost. I'm wagering that he was doing something similar, but just kept the name "size" after the negation, rather than switching to "neg" as I did here.

DblPlusUngood 10y ago
> The advantage of this construct is that you can use the flags set by the increment to test for loop termination, rather than needing an additional comparison. I don't understand your optimization. ZF is also set for dec, so why not just use dec and not negate the size?
- nkurz 10y ago
  Sticking with a positive value and using dec or sub works if you just have a loop counter or if it's acceptable to process the data in your buffer backwards, but switching to negative lets you go through the buffer in standard ascending order. Sometimes data dependencies require this, and sometimes ascending works better for prefetching.
_nalply 10y ago
Your theory sounds way better than mine.