The Boston Diaries

The ongoing saga of a programmer who doesn't live in Boston, nor does he even like Boston, but yet named his weblog/journal “The Boston Diaries.”

Go figure.

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]

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:

Timings to generate a map file
VersionTimings
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]

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:

Updated timings to generate a map file
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.

Obligatory Picture

[It's the most wonderful time of the year!]

Obligatory Links

Obligatory Miscellaneous

You have my permission to link freely to any entry here. Go ahead, I won't bite. I promise.

The dates are the permanent links to that day's entries (or entry, if there is only one entry). The titles are the permanent links to that entry only. The format for the links are simple: Start with the base link for this site: http://boston.conman.org/, then add the date you are interested in, say 2000/08/01, so that would make the final URL:

http://boston.conman.org/2000/08/01

You can also specify the entire month by leaving off the day portion. You can even select an arbitrary portion of time.

You may also note subtle shading of the links and that's intentional: the “closer” the link is (relative to the page) the “brighter” it appears. It's an experiment in using color shading to denote the distance a link is from here. If you don't notice it, don't worry; it's not all that important.

It is assumed that every brand name, slogan, corporate name, symbol, design element, et cetera mentioned in these pages is a protected and/or trademarked entity, the sole property of its owner(s), and acknowledgement of this status is implied.

Copyright © 1999-2019 by Sean Conner. All Rights Reserved.