This is a really neat article. One thing: the author falls victim to a common, unfortunate mistake in calculating the percentage gains: ...120 cycles. That’s a 30-percent speed-up. and then ...98 cycles. Compared to the original code, that’s 60 percent faster.
The right way to calculate this figure is (t1 - t0)/t0, rather than the author's formula which seems to be (t1 - t0)/t1. For instance: (157 - 98)/98 = 60%, but the actual amount is (157 - 98)/157 = a 38% speed up. A heuristic: 60% of 157 will be much more than 60 (since 60% of 100 = 60), which means a 60% speed up would reduce the speed to below 97 cycles.
It gets even more misleading the more efficient it gets: Adding up the cycles, the total was just 1689. I had shaved almost 1200 cycles off of my friend’s code. That’s a 70 percent speed-up! The author has 1200/1689 = 71%, but the correct numbers yield 1200/(1689+1200) = 42%.
Not that I don't think these are significant gains, but it's just misleading to label them like this. If you've removed less than half the cycles, there's no way you've seen a 70% speed up.
By my calculations (which I'll machine-check now with Maxima), the 30% and 70% speed-up claims are sound. First, let's fire up Maxima:
$ maxima
Maxima 5.30.0 http://maxima.sourceforge.net
using Lisp SBCL 1.1.8-2.fc19
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
Now let's calculate how much faster we made the row-copy code by unrolling its loop:
Your only "mistake" was to switch to a different measure when giving the percentages. Your calculations are actually fine, because you explicitly label them "speedup".
However, this can confuse a non-thorough reader because your previous measures are not about "speed"; they are about "cost" (cycles). The parent just did not realize the switch, and thought that you were claiming to have reduced "cost" (cycles) by 30%/70%, which wouldn't be true.
Thanks for this insight! I never would have seen it had you not told me. (I'm an engineering guy and switching between time-per-unit and units-per-time is so automatic for me that I didn't realize it wasn't automatic for everybody.)
I've updated the story to explain the calculation the first time it happens.
I'm having trouble with your post. You said the right way to calculate it is (t1 - t0)/t0, but said later that the actual amount is (157 - 98)/157, which is (t1 - t0)/t1.
Also I believe the author is referring to speed improvements, whereas you are referring to time improvements. Let's say I take 200 operations to perform a task, then I optimize code to perform the same task in 100 operations. The program runs at 20 operations per second regardless of how many operations there are.
The task which took 10 seconds before will now take 5 seconds, or a 50% time reduction, which is how you calculate it. However, the program is now running twice as fast, because in 20 seconds, the program can run twice, which is how the author calculated it.
Both of you are correct, just depending on what your context is.
The right way to calculate this figure is (t1 - t0)/t0, rather than the author's formula which seems to be (t1 - t0)/t1. For instance: (157 - 98)/98 = 60%, but the actual amount is (157 - 98)/157 = a 38% speed up. A heuristic: 60% of 157 will be much more than 60 (since 60% of 100 = 60), which means a 60% speed up would reduce the speed to below 97 cycles.
It gets even more misleading the more efficient it gets: Adding up the cycles, the total was just 1689. I had shaved almost 1200 cycles off of my friend’s code. That’s a 70 percent speed-up! The author has 1200/1689 = 71%, but the correct numbers yield 1200/(1689+1200) = 42%.
Not that I don't think these are significant gains, but it's just misleading to label them like this. If you've removed less than half the cycles, there's no way you've seen a 70% speed up.