Excessive peak memory consumption by the Python parser

@freddrake

BPO	26415
Nosy	@freddrake, @rhettinger, @pfmoore, @vstinner, @tiran, @tjguk, @benjaminp, @encukou, @methane, @berkerpeksag, @zware, @serhiy-storchaka, @eryksun, @zooba, @tyomitch, @stratakis, @pablogsal
PRs	bpo-26415: reduce peak memory consumption by the parser #10995
Files	crash.zip python_memleak.py patch patch patch devguide_patch patch

^{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:

assignee = 'https://github.com/serhiy-storchaka'
closed_at = <Date 2020-05-23.00:28:30.620>
created_at = <Date 2016-02-22.23:06:20.050>
labels = ['interpreter-core', '3.8', 'performance']
title = 'Excessive peak memory consumption by the Python parser'
updated_at = <Date 2020-05-23.00:28:30.617>
user = 'https://github.com/tyomitch'

bugs.python.org fields:

activity = <Date 2020-05-23.00:28:30.617>
actor = 'pablogsal'
assignee = 'serhiy.storchaka'
closed = True
closed_date = <Date 2020-05-23.00:28:30.620>
closer = 'pablogsal'
components = ['Interpreter Core']
creation = <Date 2016-02-22.23:06:20.050>
creator = 'A. Skrobov'
dependencies = []
files = ['42011', '42091', '42101', '43261', '43664', '43665', '44370']
hgrepos = []
issue_num = 26415
keywords = ['patch']
message_count = 34.0
messages = ['260704', '260840', '260859', '260860', '260865', '260868', '260870', '260874', '260889', '260930', '261334', '261345', '261346', '261347', '261349', '261362', '261427', '261503', '265412', '267534', '267585', '267602', '267618', '267620', '267622', '270002', '272772', '272786', '274393', '299022', '330197', '331240', '331848', '369673']
nosy_count = 18.0
nosy_names = ['fdrake', 'rhettinger', 'paul.moore', 'vstinner', 'christian.heimes', 'tim.golden', 'benjamin.peterson', 'petr.viktorin', 'methane', 'berker.peksag', 'zach.ware', 'serhiy.storchaka', 'eryksun', 'steve.dower', 'xcombelle', 'A. Skrobov', 'cstratak', 'pablogsal']
pr_nums = ['10995']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue26415'
versions = ['Python 3.8']

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
user 0m9.859s
sys 0m2.085s
$ time python2.7 -c 'import crash'

real 0m0.484s
user 0m0.401s
sys 0m0.083s
$ time python3.4 -c 'import crash'

real 0m12.327s
user 0m10.106s
sys 0m2.236s
$ time python3.4 -c 'import crash'

real 0m0.435s
user 0m0.367s
sys 0m0.069s

$ 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:

Program received signal SIGSEGV, Segmentation fault.
0x000000000048ecb4 in PyObject_Malloc (nbytes=72) at ../Objects/obmalloc.c:932
932	../Objects/obmalloc.c: No such file or directory.
(gdb) bt
#0  0x000000000048ecb4 in PyObject_Malloc (nbytes=72) at ../Objects/obmalloc.c:932
#1  0x000000000048f8be in _PyObject_DebugMallocApi (id=111 'o', nbytes=40) at ../Objects/obmalloc.c:1469
#2  0x000000000048fa2b in _PyObject_DebugReallocApi (api=111 'o', p=0x0, nbytes=40) at ../Objects/obmalloc.c:1520
#3  0x000000000048f83c in _PyObject_DebugRealloc (p=0x0, nbytes=40) at ../Objects/obmalloc.c:1441
#4  0x0000000000418a02 in PyNode_AddChild (n1=0x7fff85cbffb8, type=318, str=0x0, lineno=1, col_offset=6446977)
    at ../Parser/node.c:98
#5  0x0000000000418f53 in push (s=0xa6b680, type=318, d=0x8bfc70 <dfas+2480>, newstate=1, lineno=1, col_offset=6446977)
    at ../Parser/parser.c:126
#6  0x000000000041946c in PyParser_AddToken (ps=0xa6b680, type=262144, str=0x7fff85cba720 "11", lineno=1, 
    col_offset=6446977, expected_ret=0x7fffffffd324) at ../Parser/parser.c:252
#7  0x0000000000419f19 in parsetok (tok=0xa5f650, g=0x8c0ac0 <_PyParser_Grammar>, start=257, err_ret=0x7fffffffd300, 
    flags=0x7fffffffd2ec) at ../Parser/parsetok.c:198
#8  0x0000000000419cb6 in PyParser_ParseFileFlagsEx (fp=0xa19b70, filename=0xa53b00 "crash.py", 
    g=0x8c0ac0 <_PyParser_Grammar>, start=257, ps1=0x0, ps2=0x0, err_ret=0x7fffffffd300, flags=0x7fffffffd2ec)
    at ../Parser/parsetok.c:106

My Python is 64-bit, but my computer only has 2GB physical RAM.

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".
What I don't understand is, what could possibly require gigabytes of memory for this task?

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.

(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:

The compression thing
the reducing of heap fragmentation
Could each sub bug have it's own bug tracker and mark them blocking for the main bug ?

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/ .

@serhiy

@serhiy: incredibly, this patch from 2.5 years ago required very minor changes to apply to the latest master. Shows how ossified the parser is :-)

Now posted as #10995

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.

Navigation Menu

Repository navigation

Excessive peak memory consumption by the Python parser #70603

16 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Excessive peak memory consumption by the Python parser #70603

Description

Activity

tyomitch commented on Feb 22, 2016

tyomitch commented on Feb 25, 2016

tiran commented on Feb 25, 2016

tiran commented on Feb 25, 2016

tyomitch commented on Feb 25, 2016

eryksun commented on Feb 25, 2016

tyomitch commented on Feb 25, 2016

eryksun commented on Feb 25, 2016

tyomitch commented on Feb 26, 2016

serhiy-storchaka commented on Feb 27, 2016

16 remaining items

tyomitch commented on Jun 7, 2016

tyomitch commented on Jul 8, 2016

xcombelle commented on Aug 15, 2016

tyomitch commented on Aug 15, 2016

tyomitch commented on Sep 5, 2016

tyomitch commented on Jul 24, 2017

serhiy-storchaka commented on Nov 21, 2018

tyomitch commented on Dec 6, 2018

tyomitch commented on Dec 14, 2018

pablogsal commented on May 23, 2020

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions