classification
Title: eliminate recursion in pickling
Type: enhancement Stage:
Components: Library (Lib) Versions: Python 2.5
process
Status: closed Resolution: duplicate
Dependencies: Superseder: pickle.py is limited by python's call stack
View: 3119
Assigned To: Nosy List: alexandre.vassalotti, bkline, cyhawk, habnabit, jcea, schmir
Priority: normal Keywords:

Created on 2008-03-25 13:44 by cyhawk, last changed 2009-06-29 00:19 by alexandre.vassalotti. This issue is now closed.

Files
File name Uploaded Description Edit
bugdemo.py cyhawk, 2008-03-25 13:44 bug demo
nonrecursivepickler.py cyhawk, 2008-03-25 16:03 Alternative implementation of Pickler, that does not have this limitation
picklertest.py cyhawk, 2008-03-25 16:04 A small test I used to verify my modification
nonrecursivepickler-fixed.py cyhawk, 2008-03-25 16:15
Messages (9)
msg64481 - (view) Author: Daniel Darabos (cyhawk) Date: 2008-03-25 13:44
In the attached demo I create a graph of 250 nodes, all of which are
connected to every other node, and this is represented by a set
attribute of the Node objects.

When I try to pickle this graph, it fails in various ways. In regular
pickle it is always a "maximum recursion depth exceeded" error. In
cPickle it is either a KeyError or a silent termination of the process.
(As tested on Windows XP 32 bits.) It depends on the size of the graph.
For smaller graphs (say 100 nodes) it works fine.

If connections are described using a dictionary or even a list, I get
the same errors.
msg64492 - (view) Author: Daniel Darabos (cyhawk) Date: 2008-03-25 16:03
So now I've learned that this is a result of the way Pickler is
implemented. I think that it would make sense to create an
implementation that is not that recursive and that would handle such
structures better.

I have now written one such implementation that is a subclass of the
original pickler and handles recursive data structures. I presume that
it is inferior in a couple of ways (performance and memory efficiency
probably), but a complete rewrite could probably create an
implementation that handles recursive data structures and is not inferior.
msg64493 - (view) Author: Daniel Darabos (cyhawk) Date: 2008-03-25 16:15
Sidenote: If I click "edit" for nonrecursivepickler.py, I get told that
"File has been classified as spam." Strange. Should I not use Viagra as
a classname? :) (j/k I didn't do anything like that)

However I have now fixed a mistake in my code.
msg65799 - (view) Author: Bob Kline (bkline) * Date: 2008-04-25 17:33
I just ran into this behavior with an attempt to pickle a dom tree for
an XML document whose nesting level never got deeper than nine child
nodes, and indeed it crashed the interpreter.  Throwing an exception
would be preferable, of course, to silent blowing up Python, but even
the exception seems to fly in the face of the documentation for the
pickle module [1] which claims (summarizing) that serializing recursive
objects using marshal will fail but pickling recursive objects will not
fail.  I can provide a repro for the XML/DOM pickling case if you think
that would be helpful, but that seems redundant since essentially you've
already illustrated the problem with your own repro case.  Thanks for
your work on the solution.

[1] http://docs.python.org/lib/node314.html
msg65870 - (view) Author: Alexandre Vassalotti (alexandre.vassalotti) * (Python committer) Date: 2008-04-27 02:48
Bob Kline wrote:
> I just ran into this behavior with an attempt to pickle a dom tree
> for an XML document whose nesting level never got deeper than nine
> child nodes, and indeed it crashed the interpreter.

Pickling recursive data-structure should not crash the interpreter.
Please open a new issue and don't forget to provide an example case.

> the documentation for the pickle module [1] which claims (summarizing)
> that serializing recursive objects using marshal will fail but
> pickling recursive objects will not fail.

The section of documentation, you are referring to, uses the term
"recursive object" to means an object which contains a reference to
itself. Anyway, the documentation [1] states clearly:

  Trying to pickle a highly recursive data structure may exceed the
  maximum recursion depth, a RuntimeError will be raised in this
  case. You can carefully raise this limit with sys.setrecursionlimit().

[1]: http://docs.python.org/lib/node317.html
msg65877 - (view) Author: Daniel Darabos (cyhawk) Date: 2008-04-27 07:55
I have also described the crash, but it makes sense to handle it
separately. So I have created issue 2702, and changed the title of this
issue.
msg65927 - (view) Author: Bob Kline (bkline) * Date: 2008-04-28 19:08
> Please open a new issue and don't forget to provide an example case.

Looks like Daniel beat me to the punch.
msg68965 - (view) Author: Aaron Gallagher (habnabit) Date: 2008-06-29 20:12
I've provided an alternate implementation of this that works with very 
minimal modification to pickle.py. See issue 3119 for the patch.
msg89802 - (view) Author: Alexandre Vassalotti (alexandre.vassalotti) * (Python committer) Date: 2009-06-29 00:19
I am closing this issue in favour of #3119, since Aaron's patch is
cleaner and slightly faster.

Thank you Daniel for the idea!
History
Date User Action Args
2011-02-12 16:06:10eric.araujounlinkissue3119 superseder
2009-06-29 00:19:33alexandre.vassalottisetstatus: open -> closed
superseder: pickle.py is limited by python's call stack
messages: + msg89802

dependencies: - pickle.py is limited by python's call stack
resolution: duplicate
2008-07-07 04:48:05gregory.p.smithsetdependencies: + pickle.py is limited by python's call stack
2008-07-07 04:47:48gregory.p.smithlinkissue3119 superseder
2008-06-29 20:12:02habnabitsetnosy: + habnabit
messages: + msg68965
2008-04-28 19:08:42bklinesetmessages: + msg65927
2008-04-27 07:55:11cyhawksetmessages: + msg65877
title: pickling of large recursive structures fails -> eliminate recursion in pickling
2008-04-27 02:48:21alexandre.vassalottisetnosy: + alexandre.vassalotti
type: crash -> enhancement
messages: + msg65870
2008-04-25 17:33:42bklinesetnosy: + bkline
type: crash
messages: + msg65799
2008-03-28 00:12:52jceasetnosy: + jcea
2008-03-25 16:15:12cyhawksetfiles: + nonrecursivepickler-fixed.py
messages: + msg64493
2008-03-25 16:13:06schmirsetnosy: + schmir
2008-03-25 16:04:13cyhawksetfiles: + picklertest.py
2008-03-25 16:03:38cyhawksetfiles: + nonrecursivepickler.py
messages: + msg64492
title: pickling of recursive sets of objects fails -> pickling of large recursive structures fails
2008-03-25 13:44:45cyhawkcreate