[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Aaron Gallagher added the comment:

Definitely not interested in pickle at all anymore.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Changes by Aaron Gallagher <_...@habnab.it>:


--
nosy:  -habnabit

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
priority: normal -> low
stage: patch review -> needs patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

It would be nice to support unlimitedly nested structures. C stack is more hard 
limit than Python stack. But the code of the pickle module (especially C 
implementation) is complicated and hardly optimized. I think it would be not 
easy to implement stackless version without significant loss of speed and 
readability. You can try, but I don't have much hope.

--
versions: +Python 3.7 -Python 3.6

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Tomas Gavenciak]

Tomas Gavenciak added the comment:

The issue is still present in Python 2.7.12 and Python 3.5.2, and the 
implementation has not been changed in the master branch either.
You can test it with the attached program constructing a graph (simplified, but 
a realistic application), or with the following obviously deep construction:

import pickle, _pickle
a=()
for i in range(1000): a = (a,)
pickle.dumps(a) # or _pickle.dumps(a)

Any further comments or thoughts on the solution?

--
versions: +Python 3.6 -Python 3.1
Added file: http://bugs.python.org/file43897/graphtest.py

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Stéphane Wirtel]

Stéphane Wirtel added the comment:

hello, I think we can close this issue because Python 3.1 is not supported. or 
we keep it if this issue is confirmed for Python 3.6.

--
nosy: +matrixise

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Tomas Gavenciak]

Tomas Gavenciak added the comment:

Hey all,

I would like to patch the C _pickle module to be non-recursive and help this 
patch go through. I have an idea on how to do that with a very small amount of 
changes below and I would like to get feedback and improvements before 
implementing it in a particular way or getting into details (basically to check 
if that is acceptable and whether I missed something major).

Also, what is missing in the Python patch to get it merged?

== Nonrecursive _pickle:

First, observe that all the save_* recursive calls do not rely on the return 
value of save_* except for error checking (which is propagated as -1 to the 
top). Also, almost all work in save_* is done before calling save() recursively 
(most of the work after calling save()s is decref or other minor cleanup).

I would propose a linked list of structures acting as a stack of objects and 
byte-sequences to be written (for the marks and opcodes). Imagine something 
like the following (a rough sketch, I need to check all the required info 
properly later):

struct _PickleStack {_PickleStack* next; PyObject *obj; char write_opcode; /* 
... objects to decref / cleanup after the write */ /* possibly pers_save flags 
*/ };

The pickle stack would be a part of Pickler and save() would push a value onto 
that stack instead of recursion. (The order of save() and calls within save_*() 
needs to be reversed, though.)

Most objects would push a fixed number of objects to the pickle stack, for 
lists and dicts I would make pickle stack entries for all the items at once 
(e.g. as in batch_list()). An alternative would be to store the last item and 
the open iterator, but that seems wasteful.

This should not slow things down significantly (if at all), as the only 
overhead is having own stack of small structures (likely less than stackframe 
size of save_*). If frequent de/allocation will be a problem, I would modify 
the allocation strategy later (to blocks or such).

Are there any issues with changing the working of save() internally? The 
functionality of reduce, custom Picklers, persistent ids and dispatch tables 
should stay the same. The unpickling is not recursive and needs no changes (and 
has its own custom stack impl).

Looking forward to your comments.

--
nosy: +gavento, serhiy.storchaka

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Mark Lawrence]

Changes by Mark Lawrence breamore...@yahoo.co.uk:


--
nosy:  -BreamoreBoy

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Éric Araujo]

Changes by Éric Araujo mer...@netwok.org:


--
superseder: eliminate recursion in pickling - 

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Aaron Gallagher habna...@gmail.com added the comment:

Here's a patch that fixes the unit tests. A new test was added that tried to 
test the C implementation of this though none exists.

--
keywords: +patch
Added file: http://bugs.python.org/file18073/pickle4.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Mark Lawrence]

Mark Lawrence breamore...@yahoo.co.uk added the comment:

Sean has stated that the patch seems fine, what needs to be done to take this 
forward?

--
nosy: +BreamoreBoy

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Sean Reifschneider]

Sean Reifschneider j...@tummy.com added the comment:

Sorry for the delay in getting to this patch.

I've reviewed this patch and it seems fine to me.  The only thing I see 
outstanding is the recommendation made by Alexandre about changing the C module 
to also implement this.

Aaron: You may want to take your question on the implementation to the 
python-dev mailing list: Whether it is necessary to implement it in the C 
module, and if so suggestions on how or help on doing it.  Is that something 
you can do, Aaron?

--
nosy: +jafo
priority:  - normal

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Sean Reifschneider]

Sean Reifschneider j...@tummy.com added the comment:

Ugh, I forgot to check the output of my test run before submitting the last 
reply.  With the patch applied, make test fails with:

test_pickle
Fatal Python error: Cannot recover from stack overflow.
Fatal Python error: Cannot recover from stack overflow.
make: *** [test] Aborted (core dumped)

This is on Python 3 trunk, with the pickle3.patch applied (which applied 
cleanly).

For the Misc/NEWS I propose (in the Library section):

- Issue #3119: pickle.py can now handle deeply-nested data-structures
  without reaching the Python call stack limit.  NOTE: the pickle save()
  method is now a generator, though sub-classes of Pickler shouldn't
  override save().

--

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Tennessee Leeuwenburg]

Changes by Tennessee Leeuwenburg tleeuwenb...@gmail.com:


--
keywords: +needs review -patch
stage:  - patch review

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Aaron Gallagher habna...@gmail.com added the comment:

Okay, here's a new version for the py3k trunk. I'm assuming that this is 
not going to make it into 2.x at all, because of the API changes. This 
patch only touches the python version of the code and adds a unit test 
for testing whether pickle works with arbitrary nesting depth in 
test.pickletest. The test is disabled for the C pickle tests currently, 
since it causes python to run out of stack space and crash.

So, does _pickle.Pickler's API need to be changed as well? Right now, 
pickle._Pickler.dump expects save (and save expects the other save_* 
methods) to either return None or an iterable, where the iterable yields 
either None or further iterables. I'm sure it wouldn't be hard to make 
_pickle.Pickler.dump work the same way, but since C doesn't have 
generators, I don't know how exactly the API would translate.

--
versions: +Python 3.1 -Python 2.6, Python 3.0
Added file: http://bugs.python.org/file13654/pickle3.patch

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Tennessee Leeuwenburg]

Tennessee Leeuwenburg tleeuwenb...@gmail.com added the comment:

Aaron,

Could you please upload another patch against the current trunk, then
the issue could be flagged as requiring a patch review?

Thanks,
-Tennessee

--
nosy: +tleeuwenb...@gmail.com

___
Python tracker rep...@bugs.python.org
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Aaron Gallagher [EMAIL PROTECTED] added the comment:

Alright, sorry this took so long. Hopefully this can still be included in 
3.0.
Included is a patch that no longer uses collections.deque and also adds a 
test case to test/test_pickle.py. The test catches RuntimeError and fails 
the unittest. I didn't see anything that would behave like the opposite of 
assertRaises except letting the exception propagate.

Added file: http://bugs.python.org/file11168/pickle2.patch

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Alexandre Vassalotti]

Alexandre Vassalotti [EMAIL PROTECTED] added the comment:

On some benchmark of my own, I get a good 2x slowdown when this patch is
applied. The benchmark consists of loading ~1.4 millions objects (mostly
dict, list, str and int) from a pickle string. It is basically a torture
test for the inner function calls overhead.

Anyway, the slowdown doesn't bother me much. I think a stackless
pickle module would be well appreciated by many Python users. 

There is a few things that stops me from applying this patch. First, the
patch will break subclasses of Pickler that relies on the save() method
(Although the method is an implementation detail that shouldn't used).
Therefore, any patches that modifies the API of save() is straight out
for 2.x. And for Python 3.0, your patch should also remove recursion
from the _pickle module (the transparent C accelerator for pickle).

--
nosy: +alexandre.vassalotti

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Gregory P. Smith]

Changes by Gregory P. Smith [EMAIL PROTECTED]:


--
superseder:  - eliminate recursion in pickling

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Ralf Schmitt]

Changes by Ralf Schmitt [EMAIL PROTECTED]:


--
nosy: +schmir

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

Aaron Gallagher [EMAIL PROTECTED] added the comment:

Ah, I didn't know that a list would be as fast for appending and popping. 
I knew that lists were optimized for .append() and .pop(), but I didn't 
know that a list would be just as fast as a deque if it was just used as a 
stack.

And I'll be happy to write unit tests if it can be pointed out to me how 
exactly they can be written. Should it just test to make sure pickling a 
deeply nested object hierarchy can be pickled without raising a 
RuntimeError? I tried to make this as transparent as possible of a change.

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Antoine Pitrou]

Antoine Pitrou [EMAIL PROTECTED] added the comment:

Hi,

Le mercredi 02 juillet 2008 à 20:43 +, Aaron Gallagher a écrit :
 Aaron Gallagher [EMAIL PROTECTED] added the comment:
 
 Ah, I didn't know that a list would be as fast for appending and popping. 
 I knew that lists were optimized for .append() and .pop(), but I didn't 
 know that a list would be just as fast as a deque if it was just used as a 
 stack.

If you have a few minutes to spare, the best would be to measure the
speed of both possibilities, and opt for the fastest. 

 And I'll be happy to write unit tests if it can be pointed out to me how 
 exactly they can be written. Should it just test to make sure pickling a 
 deeply nested object hierarchy can be pickled without raising a 
 RuntimeError?

Yes, exactly. Just create a very deeply nested object (a list should be
sufficient I suppose), pickle it, unpickle it, and check that the result
is equal to the original. No need to do more. Don't bother catching the
eventual RuntimeError, if it is raised the test will be failed anyway.

Since your patch only regards the pickle module (not cPickle) I suppose
the test could go directly into Lib/test/test_pickle.py.

(oh and don't forget to check the test case fails without your
patch :-))

Thanks !

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Jesús Cea Avión]

Changes by Jesús Cea Avión [EMAIL PROTECTED]:


--
nosy: +jcea

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue3119] pickle.py is limited by python's call stack

[Aaron Gallagher]

New submission from Aaron Gallagher [EMAIL PROTECTED]:

Currently, pickle.py in the stdlib is limited by the python call stack. 
For deeply recursive data structures, the default recursion limit of 1000 
is not enough. The patch attached modifies pickle.py to instead use a 
deque object as a call stack. Pickler.save and other methods that increase 
the recursion depth are now generators which may yield either another 
generator or None, where yielding a generator adds it to the call stack.

--
components: Library (Lib)
files: pickle.patch
keywords: patch
messages: 68262
nosy: habnabit
severity: normal
status: open
title: pickle.py is limited by python's call stack
type: behavior
versions: Python 2.6, Python 3.0
Added file: http://bugs.python.org/file10638/pickle.patch

___
Python tracker [EMAIL PROTECTED]
http://bugs.python.org/issue3119
___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com