The Walker classes pass the $output variable back and forth between their methods many many times, each time making the variable bigger and bigger. For walkable data with many items, this means the classes are copying very large variables many many times.
Converting the Walkers to pass $output by reference gives us a modest speed increase.
On a site with ~3200 categories (yes, that's a lot), the attached patch gave me ~35% decrease in the time it took Walker::walk() to output the $output created by Walker_Category_Checklist.
Note that any speed boost will only be significant in very large lists. Only then is $output copied many times and only then is $output very large.
Attached passes $output by reference in Walker and all core inheriting classes. Depending on how they are written, most Walker classes from plugins will work fine with these core modifications (but will not get the speed boost).
2.5.1?
