Wow, Perl’s Memoize.pm is cool. Try this:
use Memoize;
sub fib {
my $n = shift;
print "called fib($n)\\n";
return $n if $n < 2;
fib($n-1) + fib($n-2);
}
print fib(5) . "\\n\\n";
memoize( 'fib' );
print fib(5) . "\\n\\n";
It does two different things:
- It wraps the function with a caching version.
- It replaces all calls to the function with calls to the memoized version. This includes the recursive calls inside the function itself.
It does all of this without requiring any source-level changes to the memoized function. This makes it easy to accelerate any referrentially-transparent function. Just don’t do something dumb like memoize print() or time().
With C++ I can mimic #1, but not #2. It’s a shame, because #2 is the cool part. With my C++ implementation, I only speed up identical repeated calls:
fib(5); // slow: makes 14, mostly-redundant, recursive calls
fib(5); // fast: purely a look up
fib(4); // slow
fib(6); // slow
Perl does much better:
fib(5); # fast: makes 5 recursive calls
fib(5); # fast: purely a look up
fib(4); # fast: purely a look up
fib(6); # fast: picks up where fib(5) left off
I’m somewhat bugged that I couldn’t duplicate this behavior with C++. Perl needn’t reach into it’s “dynamic language” bag of tricks to achieve this. It just provides access to the symbol table:
sub a() { print "a\\n"; }
sub b() { print "b\\n"; }
*a = \\&b;
a(); # prints b
I’ve been self-hosting Vista Beta 2 on my notebook for a week. The overall verdict is: I like it. Here are some details:
The good:
- No banged-out devices. Between the “in-box” stuff and Windows Update, I was good to go. I actually had more trouble with WinXP x64, a shipped product.
- I can finally suspend/resume sucessfully. I hope this is the norm. I see too many half-closed laptops being toted around building 41
- The boot menu has been redesigned and it now includes a memory tester. I can finally throw away my MemTest86+ floppy.
- The sound control panel is much improved. I get per-app volume sliders, and only for the apps that are actually running. Bless you, Larry Osterman.
- I don’t want to jinx myself, but the date popup is sufficiently changed as to suggest it might work reliably now. It has yet to fail me.
- The new fonts are quite well done, and look especially nice with ClearType (on by default). My favorites are Segoe (the default sans-serif UI font) and Consolas (fixed-width for programming and cmd.exe, available here).
The Bad:
- Windows needs my permission to continue. A lot. I worry that I’ll eventually approve something evil out of habit
- I am desperately seeking the windows equivalent of sudo. If anyone in the LUA/UAC team is reading, I implore you: please add this functionality to runas.
- I had hoped for an in-box MPEG2 decoder. No dice. DVD playback still requires additional software. Maybe this will change by RTM?
- Aero Glass: frivilous eye candy or productivity boon? I’d like to make this judgment, but I don’t have WDDM graphics.
- The sidebar and gadgets are a big letdown. Apple did it right, by placing the widets in a layer that spans the desktop and can be raised with a quick keypress. Why are the Vista gadgets confined to the side of my screen? I guess Microsoft’s corporate ego is too fragile to tolerate wholesale imitation of a good idea.
Microsoft’s Visual C compiler generates the following branch-free code to calculate the absolute value of an integer.
cdq
xor eax, edx
sub eax, edx
The cdq instruction sign-extends eax into the register pair edx:eax. The cute trick here is to abuse that behavior to get an all-ones register (edx) in the case of negative input. This can be used to compute the 1’s complement, and we can also subtract it to add one (for the 2’s complement). In the case of a positive input, edx is zero and thus the xor and sub are harmless.
This is faster than the naive version, which would likely contain an unpredictable branch.
I’m surely not clever enough to have written abs this way. It seems like something the Superoptimizer might have conjured up.
Latest Comments
RSS