cPickle asymptotic performance?

[Hrvoje Niksic]

Eric Jonas <jonas at MIT.EDU> writes:

>> Try gc.disable() before loading the pickle, and gc.enable() after.
>> 
>> > Is cPickle's behavior known to be O(n^2)?
>> 
>> No, but the garbage collector's sometimes is.
>
> Wow, that totally fixed it -- we went from 1200 seconds to 60
> seconds.

60 seconds is still a long time.  How many objects are you
deserializing?  Is the time now approximately O(n)?

> I'm somewhat shocked -- is the occasionally-abysmal behavior of the
> GC documented anywhere?

I don't think so.  It's somewhat of an FAQ on the list, though.  The
question tends to arise when someone tries to construct a large list
of non-trivial objects, which takes quadratic time because object
allocation regularly triggers GC, which traverses the growing list.