[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


--
resolution:  -> fixed
stage: patch review -> resolved
status: open -> closed

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Neil Schemenauer  added the comment:


New changeset 85b6b70589c187639aeebc560d67e9cc04abb4d8 by Neil Schemenauer in 
branch 'master':
bpo-37448: Use radix tree for pymalloc address_in_range(). (GH-14474)
https://github.com/python/cpython/commit/85b6b70589c187639aeebc560d67e9cc04abb4d8


--

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[STINNER Victor]

STINNER Victor  added the comment:

See also bpo-43593 "pymalloc is not aware of Memory Tagging Extension (MTE) and 
crashes".

--

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[STINNER Victor]

STINNER Victor  added the comment:

See also bpo-43313: "feature: support pymalloc for subinterpreters. each 
subinterpreter has pymalloc_state".

--
nosy: +vstinner

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


Added file: https://bugs.python.org/file49834/perf_compare_radix4x.txt

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


Added file: https://bugs.python.org/file49833/perf_compare_noradix.txt

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Karthikeyan Singaravelan]

Change by Karthikeyan Singaravelan :


--
nosy: +inada.naoki

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Tim Peters]

Change by Tim Peters :


--
nosy: +tim.peters

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


--
keywords: +patch
pull_requests: +14291
pull_request: https://github.com/python/cpython/pull/14474

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


Added file: https://bugs.python.org/file48446/obmalloc_overhead.py

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

Change by Neil Schemenauer :


Added file: https://bugs.python.org/file48445/pyperf_radix_compare.txt

___
Python tracker 

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

[issue37448] obmalloc: radix tree for tracking arena address ranges

[Neil Schemenauer]

New submission from Neil Schemenauer :

This patch implements an alternative version of obmalloc's address_in_range().  
It uses a radix tree to map the areas of memory covered by obmalloc arenas.  
pymalloc_free() uses address_in_range() to determine if a block of memory is 
controlled by obmalloc or has been allocated by the system allocator.  The 
address_in_range() function must be fast.

The current version of address_in_range() uses a slightly memory unsanitary 
scheme.  I.e. it reads memory that has possibly not been initialized.  In 
theory that is not allowed and could cause a crash.  In practice, it has worked 
reliability for many years.  There is some ugly logic in obmalloc.c to disable 
sanity checking (e.g. ASN, TSAN, MSAN).  One advantage of this radix tree 
approach is that it doesn't have this unsanitary behavior.

Another small advantage of the radix tree approach is that it is independent 
from the OS page size.  With the current address_in_range() scheme, the size of 
obmalloc pools are limited to the size of the OS page size.  If larger, a 
segmentation fault could occur.  Bug #37211 (obmalloc: eliminate limit on pool 
size) allows for larger pools but at the cost of some additional code 
complexity and some additional memory overhead.

This patch has been discussed quite a bit on the python-dev list.  Thread 
subjects are:
obmalloc (was Have a big machine and spare time? Here's a possible Python 
bug.)
radix tree arena map for obmalloc

That discussion focuses quite a bit on the value of increasing the obmalloc 
arena and pool sizes.  This proposed patch keeps the sizes the same.  We can 
evaluate changing the sizes as a different issue.

I have run the pyperformance benchmark suite to compare performance of the 
radix tree with the status quo.  I think there is no significant difference for 
the programs that are part of the suite.  The pyperformance comparision report 
is attached.

If we do decide to go with larger pool and arena sizes, the radix tree approach 
actually uses less memory than the "big pools PR" (Bug #37211).  Attached is 
Tim's program to compare memory overheads of the different approaches.

I think it is worth considering using the radix tree by default on 64-bit 
platforms.  It seems to be not any slower than the status quo, does not have 
the memory unsanitary behavior and gives us the ability to easily increase pool 
sizes if we decide we want to.

--
components: Interpreter Core
messages: 346903
nosy: nascheme
priority: normal
severity: normal
stage: patch review
status: open
title: obmalloc: radix tree for tracking arena address ranges
type: enhancement

___
Python tracker 

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