Tuesday, August 06, 2013
Programs from the past, Part III: It's a numbers game
I'm still not done yet. When last we left off, the recreation of a project written twenty-some years ago wasn't as fast as I thought. But as I shall reveal, there's a bit more lurking here than I realized.
For a fair comparison, I actually have two versions of a program that generates those map files:
![[Yeah, this again]](/2013/08/05/map.png "Yeah, this again")
One version in C and one in Lua (previously, the recreated programs just spit out numbers that were then converted to an image with a second program). And here's how long it took to generate the results:
| Version | Timings |
|---|---|
| Original program | ~36,000s |
| Lua | 1,096s |
| C | 79s |
| LuaJIT | 69s |
(remember, the “Original program” was written twenty-some years ago and ran on a 32-bit 33MHz machine; the programs I just wrote are running on a 64-bit 2.8GHz machine)
My initial mistake in recreating this program was to toss out values that exceeded a range and from that, I got fantastic timings, but I was throwing out too much, as can be seen here:
![[Trimming things a bit too close]](/2013/08/04/map1.png "Trimming things a bit too close")
The “too-trimmed” version came about because I looked at some of the intermediate results and saw infinities (well, the IEEE 754's concept of infinity) and at that point, any operations done on “infinity” is “infinity.”
But my mistake was thinking that all values that fell out of range would end up being “infinite.” Not all did, and some even fell back into range.
But I was still troubled by the infinite results. So, why not explicitely check for “infinity?” In Lua/LuaJIT:
if xn == math.huge or xn == -math.huge then return MAX end if yn == math.huge or yn == -math.huge then return MAX end
And in C:
if (xn == HUGE_VAL) return MAX; if (xn == -HUGE_VAL) return MAX; if (yn == HUGE_VAL) return MAX; if (yn == -HUGE_VAL) return MAx;
(for those curious, HUGE_VAL is defined in
math.h.)
Adding those lines makes all the difference:
| Version | Timings |
|---|---|
| Original program | N/A |
| Lua | 16.25s |
| C | 2.60s |
| LuaJIT | 1.25s |
It's nice to see LuaJIT still beating the snot out of C, and yes, I was able to generate a full set of maps, just like I did twenty-some years ago, in under three minutes (remember, I'm running the code across four CPUs).
But now I'm upset, because checking for “infinity” was something I didn't do twenty-some years ago, and now I'm thinking, what if I had? Could that simple check, had I known about it, cut the run time of a year down to a month?
I can't blame the university for not offering a class on floating point arithmetic, because it did! And worse, I took the class! (when I entered FAU as a freshman, I knew that the first class for the Computer Science degree involved Fortran. I found the first class that had “Fortran” as part of the title and signed up for it, only to spend find the lectures spending more time on the horrors of floating point arithmetic and very little time on programming. It turned out I took the wrong class; what I signed up for was a Fortran class taught out of the Math Department (the very one I worked for when I wrote these programs twenty-some years ago) for mathematicians. When I discovered the mistake, I was able to get out of the class without issue, but only becuase I was actually doing quite well. In my defense, I was a freshman and didn't have my act together; but FAU didn't exactly have a Computer Science Department at the time, so it didn't have its act together either!). It never dawned on me to even check the intermediate results and bail early.
Sigh.
