Saturday 31 March 2012

Shell Game

For the longest time, I thought there were only two (good) ways to exchange the value of two variables.

Use this form when 'a' and 'b' are likely to be in memory.

Use this form when 'a' and 'b' are likely to be in registers.

The first form uses the classic load-store architecture.  We load the variables from the cache, we do some work, we write the variables back into the cache. Great.

The second form is for when you are register starved.  We're in a tight loop, and trying to squeeze as much into the instruction cache.  Let's use the ALU to do all the work for us. Again, Great!

But it turns out that for all that time, I was completely wrong.  The right way to exchange variables is actually this :
Lets optimize for developer time.
Why? Because the compiler knows if the variables are in registers or in memory, and will automatically choose the best form of the function.  Almost as an added bonus, we get type checking and polymorphism for free.

(Are you still doing it the one of other ways, I'd love to hear from you in the comments!)

But can we do better even than std::swap?  Why yes, it turns out we can :

Wait, that's not C++ !
Over here in Python land, things are much more expressive.  We can actually assign a tuple to a tuple. You wouldn't want to do this in C++ because it would involve making temporaries and at least 4 copies. But in python, tuples are immutable, and by reference, so all this has to do is change 'a' to reference 'b', and vice versa, regardless of the size of 'a' and 'b'.

Great! So what else can we do?


We're perhaps bordering into stunt programming now, but consider, how would you rewrite these two python statements in C++?

Maybe it's time for us to reconsider what it is we're optimizing...


No comments:

Post a Comment