New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Excessive peak memory consumption by the Python parser #70603
Comments
I have a one-line module that assigns a tuple->int dictionary: holo_table = {(0, 0, 0, 0, 0, 0, 1, 41, 61, 66, 89): 9, (0, 0, 0, 70, 88, 98, 103, 131, 147, 119, 93): 4, [35MB skipped], (932, 643, 499, 286, 326, 338, 279, 200, 280, 262, 115): 5} When I try to import this module, Python grinds 100% of my CPU for like half an hour, then ultimately crashes with a MemoryError. How much memory does it need to parse 35MB of data, of a rather simple structure? Attaching the module, zipped to 10MB. |
A practical note: if, instead of importing crash.py, I do a json.loads, with a few extra transformations: with open("crash.py") as f: holo_table={tuple(int(z) for z in k.split(', ')):v for k,v in json.loads(f.readlines()[0][13:].replace('(','"').replace(')','"')).iteritems()} --the whole data structure loads in a jiffy. Makes me wonder why this roundabout approach is so much more efficient than the native parsing. |
It takes about 12 seconds to byte compile crash.py on my computer and less than half a second to import about 28 MB of byte code: $ rm -rf crash.pyc __pycache__/
$ time python2.7 -c 'import crash' real 0m11.930s real 0m0.484s real 0m12.327s real 0m0.435s |
$ python2.7 --version
Python 2.7.10
$ python3.4 --version
Python 3.4.3
$ uname -r -o
4.3.5-300.fc23.x86_64 GNU/Linux Intel(R) Core(TM) i7-4900MQ CPU @ 2.80GHz |
Mine is on Windows. I've now installed both 2.7.10 and 3.4.3 to reconfirm, and it's still the same, on both of them, except that on 3.4.3 it crashes with a MemoryError much faster (within a couple minutes). |
I don't think this is Windows related. Are you using 32-bit Python? On Linux, if I limit the process address space to 2 gigs, it crashes almost immediately: $ ulimit -v 2000000
$ python-dbg -c 'import crash'
Segmentation fault It runs out of memory while parsing the file:
|
My Python is 64-bit, but my computer only has 2GB physical RAM. |
That explains why it takes half an hour to crash. It's thrashing on page faults. Adding another paging file or increasing the size of your current paging file should allow this to finish parsing... eventually in maybe an hour or two. The design of the parser isn't something I've delved into very much, but possibly the dynamic nature of Python prevents optimizing the memory footprint here. Or maybe no one has seen the need to optimize parsing containers (dicts, sets, lists, tuples) that have constant literals. This is an inefficient way to store 35 MiB of data, as opposed to XML, JSON, or a binary format. |
Yes, I understand that this is a matter of memory consumption, which is why I submitted this ticket as "resource usage". |
I though this might be tokenizer issue, but this is just large memory consumption for AST tree. Simpler example: ./python -c 'import ast; ast.parse("0,"*1000000, mode="eval")' It takes over 450MB of memory on 32-bit system, over 450 bytes per tuple item. Increase the multiplier to 10000000 leads to swapping and failing with MemoryError. Of course it would be nice to decrease memory consumption, but this looks rather as new feature. |
OK, I've now looked into it with a fresh build of 3.6 trunk on Linux x64. Peak memory usage is about 3KB per node: $ /usr/bin/time -v ./python -c 'import ast; ast.parse("0,"*1000000, mode="eval")'
Command being timed: "./python -c import ast; ast.parse("0,"*1000000, mode="eval")"
...
Maximum resident set size (kbytes): 3015552
... Out of the 2945 MB total peak memory usage, only 330 MB are attributable to the heap use: $ valgrind ./python -c 'import ast; ast.parse("0,"*1000000, mode="eval")'
==21232== ...
==21232== HEAP SUMMARY:
==21232== in use at exit: 3,480,447 bytes in 266 blocks
==21232== total heap usage: 1,010,171 allocs, 1,009,905 frees, 348,600,304 bytes allocated
==21232== ... So, apparently, it's not the nodes themselves taking up a disproportionate amount of memory -- it's the heap getting so badly fragmented that 89% of its memory allocation is wasted. gprof confirms that there are lots of mallocs/reallocs going on, up to 21 per node: $ gprof python
Flat profile: Each sample counts as 0.01 seconds. So, I suppose what needs to be done is to try reducing the number of reallocs involved in handling an AST node; the representation of the nodes themselves doesn't need to change. |
Yeah, the Python parser+compiler badly uses the memory allocator. See my "benchmark" for the memory allocator: python_memleak.py. The classical pattern of memory fragmentation is:
All objects must allocated on the heap, not mmap(). So the maximum size of a single object must be 128 KB (usual threshold used in malloc() to switch beetween the heap memory and mmap). We can try various hacks to reduce the fragmentation, but IMHO the only real fix is to use a different memory allocator for the compiler and then free everything allocated by the parser+compiler at once. We already have an "arena" memory allocator: Include/pyarena.h, Python/pyarena.c. It is already used by the parser+compiler, but it's only used for AST objects in practice. The parser uses the PyMem allocator API (ex: PyMem_Malloc). |
My misc notes about memory fragmentation: https://haypo-notes.readthedocs.org/heap_fragmentation.html |
libapr library of Apache is designed to group all memory allocations required to handle an HTTP request. It is possible to release *all* memory allocations of the request at once. It looks like the the "pool" object: |
On my computer peak memory usage in non-debug build is about 450 MB. Peak memory usage in debug build is about 730 MB. I'm not sure this is due to memory fragmentation. |
@serhiy: if your build is 32-bit, then every node is half the size, as it mostly consists of pointers. The amount of heap fragmentation can also depend on gcc/glibc version. |
The attached patch for the parser reduces "Maximum resident set size (kbytes)" threefold, for the degenerate example of 'import ast; ast.parse("0,"*1000000, mode="eval")', by eliminating many CST nodes that have a single child. According to the comment in node.c -- "89% of PyObject_REALLOC calls in PyNode_AddChild passed 1 for the size" -- the memory saving should be generally applicable, and not limited just to this degenerate case. Modules/parsermodule.c is not yet updated to match. Please tell if you want me to do that, in case that my proposed change to the parser is acceptable. |
I've now tried it with "perf.py -r -m", and the memory savings are as follows: ### 2to3 ### ### chameleon_v2 ### ### django_v3 ### ### fastpickle ### ### fastunpickle ### ### json_dump_v2 ### ### json_load ### ### nbody ### ### regex_v8 ### ### tornado_http ### So, on these benchmarks, the saving is not threefold, of course; but still quite substantial (up to 30%). The run time difference, on these benchmarks, is between "1.04x slower" and "1.06x faster", for reasons beyond my understanding (variability of background load, possibly?) |
Ping? This patch is two months old now. |
Now that bpo-26526 landed (thanks to everybody involved!), I'm requesting a review on an updated version of my patch, which addresses the excessive memory consumption by the parser. The description of my original patch still applies:
My new patch updates Modules/parsermodule.c to accept such "compressed" nodes, so that everything still builds cleanly and passes the tests. |
It seems to me a simpler solution would be allocate all nodes for a parse tree in an arena. |
An arena might help reclaim the memory once the parsing is complete, but it wouldn't reduce the peak memory consumption by the parser, and so it wouldn't prevent a MemoryError when parsing a 35MB source on a PC with 2GB of RAM. |
Benjamin Peterson: "It seems to me a simpler solution would be allocate all nodes for a parse tree in an arena." Exactly, that's the real fix. Just make sure that deallocating this arena does punch holes in the "heap memory". For example, on Linux, it means using mmap() rather than sbrk() to allocate memory. A. Skrobov: "An arena might help reclaim the memory once the parsing is complete, but it wouldn't reduce the peak memory consumption by the parser, and so it wouldn't prevent a MemoryError when parsing a 35MB source on a PC with 2GB of RAM." Parsing a 35 MB source doesn't seem like a good idea :-) I think that it's ok to have a memory peak, but it's not ok to not release the memory later. Do you have a solution avoid the memory peak *and* don't create memory fragmentation? |
My current patch avoids the memory peak *and* doesn't add any memory fragmentation on top of whatever is already there. In other words, it makes the parser better in this one aspect, and it doesn't make it worse in any aspect. |
(Updating the issue title, to avoid confusion between two orthogonal concerns) |
Fixing whitespace in the patch, and including an update for the docs |
Looks that there is two bug as partial solution of the main bug which is reduce memory consumption of the parser:
A. Skrobov Can you describe the big picture of your patch, without I don't understand the logic of your modifications. |
Xavier, the big picture description of my patch is in http://bugs.python.org/file43665/devguide_patch The heap fragmentation was observed by Victor, not by myself. Victor, could you please create a new ticket for your python_memleak.py reproducer? |
Updated the comment for Init_ValidationGrammar() |
To bump this year-old issue, I have delivered a talk at EuroPython 2017, explaining what my patch does, how it does what it does, and why it's a good thing to do. You can watch my talk at https://www.youtube.com/watch?v=dyRDmcsTwhE&t=1h52m38s |
Do you mind to create a pull request for reviewing? I can not promise that it will be merged, but it will have a chance. For reference, the article about this patch (on Russian): https://habr.com/post/314062/ . |
I've run pyperformance (0.7.0) with my updated patch, and posted results at the PR page. They look encouraging enough. |
Closing as we have a new parser in 3.9 and the current one will be removed in Python 3.10. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: