By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
455,538 Members | 1,428 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 455,538 IT Pros & Developers. It's quick & easy.

cPickle asymptotic performance?

P: n/a
Hello,

I've done some benchmarking while attempting to serialize my (large)
graph data structure with cPickle; I'm seeing superlinear performance
(plotting it seems to suggest n^2 where n is the number of nodes of my
graph), in the duration of the pickle.dump calls and I can't quite
figure out why. The connectivity of the graph is such that the number of
nodes is ~ number of edges, so I don't think this is a problem of edge
count secretly growing O(n). Is cPickle's behavior known to be O(n^2)?
Does anyone have any generic tips for speeding up cPickle?

Thanks,
...Eric
Jun 27 '08 #1
Share this Question
Share on Google+
3 Replies


P: n/a
Eric Jonas <jo***@MIT.EDUwrites:
I've done some benchmarking while attempting to serialize my (large)
graph data structure with cPickle; I'm seeing superlinear performance
(plotting it seems to suggest n^2 where n is the number of nodes of my
graph), in the duration of the pickle.dump calls and I can't quite
figure out why.
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.
Jun 27 '08 #2

P: n/a

On Thu, 2008-06-12 at 20:57 +0200, Hrvoje Niksic wrote:
Eric Jonas <jo***@MIT.EDUwrites:
I've done some benchmarking while attempting to serialize my (large)
graph data structure with cPickle; I'm seeing superlinear performance
(plotting it seems to suggest n^2 where n is the number of nodes of my
graph), in the duration of the pickle.dump calls and I can't quite
figure out why.

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.
I'm somewhat shocked -- is the occasionally-abysmal behavior of the GC
documented anywhere?
...Eric

Jun 27 '08 #3

P: n/a
Eric Jonas <jo***@MIT.EDUwrites:
>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.
Jun 27 '08 #4

This discussion thread is closed

Replies have been disabled for this discussion.