[Python-Dev] decorate-sort-undecorate

[Tim Peters]

[Raymond Hettinger]
> ...
> * The key function triggers a DSU step with a wrapper object that
> holds the full record but returns only the key for a comparison.
> This is fast, memory efficient, and doesn't change the underlying
> stability characteristics of the sort. (I think this was Neil's idea
> -- and it works like a charm.)

I see the wrapper object participates in cyclic GC.  This adds 12 (32-bit
Linux) to 16 (32-bit Windows) gc overhead bytes per wrapper object, more
than the # of bytes needed to hold the 2 useful pointers.  Since the wrapper
objects only live for the life of the sort, I don't think it's important
that they participate in cyclic gc.  In particular, since the key and value
objects being wrapped stay alive for the life of the sort too, no cyclic
trash they appear in can become collectible during the sort, and so tracing
cycles involving these things can't do any good (it can fritter away time
moving the wrapper objects into older generations, but that's not usually
"good" <wink>).