Perhaps pickle could grow an option to assume that a data structure is non-recursive ?
Then you'd probably want some means of detecting cycles, or you'd get infinite recursion when you got it wrong. That would mean keeping a stack of objects, I think -- probably less memory than keeping all of them at once.
cPickle has an obscure options for this. You create a pickler object and set the attribute "fast" to True, I believe. It detects cycles by using a nesting counter, I believe (read the source to learn more).
But I think the idea of keeping the object references in a list is well worth trying first. 4 bytes per object instead of 36 sounds like a good improvement to me!
So maybe we need to create an identitydict... --Guido van Rossum (home page: http://www.python.org/~guido/)