Optimization is fun

[vshnayder]

Ignore unless you're a CS nerd :)

A friend of mine has a program that computes a funky number theoretical function. Unfortunately, it was taking 5 days to run. I volunteered to take a look at it, and managed to reduce the runtime to about 5 minutes by adding 14 characters to the code. Huzzah for optimization! As part of my investigations, I got yet another reminder that trying to guess where the slow bits are is pretty much useless. The actual culpit turned out to be that the math package she was using decided for some reason to use really really slow symbolic computations of floor() and ceil() instead of just using the built in versions. A couple of casts, and voila--a couple of orders of magnitude of improvement. But I would never have suspected that just by staring at the code.

Comments

[chuckro.livejournal.com]

But I would never have suspected that just by staring at the code.

I think I'm missing something here. What did you do to find the problem besides stare at the code?

[shnayder.livejournal.com]

Measure it--use a profiling program to see how long each function call took. It still required a bit of investigation to figure out where the actual problem was in this case, but it helped.

[cubby-t-bear.livejournal.com]

Amateurs optimize by inspection. Nerds and professionals optimize by profiling. Ludicrous mathematicians optimize by proving how long each step should take :)

[shnayder.livejournal.com]

Right. So you prove that floor(float) should take 100ns, and then get very surprised when the program goes off and fires up a whole separate process and chats with it via sockets for a while. Silly programs.

[dushai.livejournal.com]

This thing SPAWNED A SEPARATE PROCESS to implement floor() ?! There's a perfectly reasonable floor() in math.h!

That's just sick.

[shnayder.livejournal.com]

Well, it makes a bit more sense in context: it's was using part of SAGE, which is an open source math library for doing lots of crazy things, including symbolic computation. The floor and ceil methods behaved differently based on the type of their argument. If it was a regular number, they used the standard math.h implementation. If it wasn't, they sent it off to a symbolic algebra module that was in a separate process. I didn't investigate far enough to figure out why the type at call-time wasn't already float--I just added explicit casts and it solved the problem.

[(Anonymous)]

Okay, that's no longer in the "just sick" category. It's merely "enough rope to hang oneself", or "fully supporting shoot-self-in-foot methodology".