Use VirtualAlloc to allocate memory arenas

[pitrou]

BPO	13483
Nosy	@loewis, @pitrou, @vstinner, @giampaolo, @tjguk, @tpn, @briancurtin
Files	va.patch tuples.py va.diff

^{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 = None
closed_at = <Date 2013-06-27.10:24:52.456>
created_at = <Date 2011-11-26.13:12:42.221>
labels = ['interpreter-core', 'OS-windows', 'performance']
title = 'Use VirtualAlloc to allocate memory arenas'
updated_at = <Date 2013-06-27.10:24:52.456>
user = 'https://github.com/pitrou'

bugs.python.org fields:

activity = <Date 2013-06-27.10:24:52.456>
actor = 'loewis'
assignee = 'none'
closed = True
closed_date = <Date 2013-06-27.10:24:52.456>
closer = 'loewis'
components = ['Interpreter Core', 'Windows']
creation = <Date 2011-11-26.13:12:42.221>
creator = 'pitrou'
dependencies = []
files = ['23784', '26069', '26070']
hgrepos = []
issue_num = 13483
keywords = ['patch']
message_count = 23.0
messages = ['148399', '148605', '148611', '148612', '148621', '148623', '148625', '163350', '163351', '189760', '189771', '189824', '189825', '189850', '189876', '190427', '191252', '191253', '191461', '191504', '191506', '191507', '191939']
nosy_count = 9.0
nosy_names = ['loewis', 'pitrou', 'vstinner', 'giampaolo.rodola', 'tim.golden', 'trent', 'brian.curtin', 'neologix', 'python-dev']
pr_nums = []
priority = 'low'
resolution = 'fixed'
stage = 'commit review'
status = 'closed'
superseder = None
type = 'resource usage'
url = 'https://bugs.python.org/issue13483'
versions = ['Python 3.4']

[pitrou]

Similar to issue bpo-11849, this patch proposes to use VirtualAlloc/VirtualFree to allocate the Python allocator's memory arenas (rather than malloc() / free()). It might help release more memory if there is some fragmentation, although I don't know how Microsoft's malloc() works.

[loewis]

The patch looks good to me.

To study Microsoft's malloc, see VC\crt\src\malloc.c. Typically, it uses HeapAlloc from the CRT heap, unless it's in 32-bit mode, and __active_heap is either __V6_HEAP or __V5_HEAP. This is determined at startup by __heap_select, inspecting an environment variable __MSVCRT_HEAP_SELECT. If that's not set, the CRT heap is used.

The CRT heap, in turn, is created with HeapCreate (no flags).

As an alternative approach, Python could consider completely dropping obmalloc on Windows, and using a Windows Low Fragementation Heap (LFH) instead, with HEAP_NO_SERIALIZE (as the heap would be protected by the GIL).

If we take the route proposed by this patch, I recommend also dropping all other CRT malloc() calls in Python, and make allocations from the process heap instead (that's a separate issue, though).

[pitrou]

The patch looks good to me.

To study Microsoft's malloc, see VC\crt\src\malloc.c. Typically, it
uses HeapAlloc from the CRT heap, unless it's in 32-bit mode, and
__active_heap is either __V6_HEAP or __V5_HEAP. This is determined at
startup by __heap_select, inspecting an environment variable
__MSVCRT_HEAP_SELECT. If that's not set, the CRT heap is used.

Ah, right, I guessed it was using HeapAlloc indeed. What would be more
interesting is how HeapAlloc works :)

I think it would be nice to know whether the patch has a chance of being
useful before committing it. I did it as a thought experiment after the
similar change was committed for Unix, but I'm not an expert in Windows
internals. Perhaps HeapAlloc deals fine with fragmentation? Tim, Brian,
do you know anything about this?

As an alternative approach, Python could consider completely dropping
obmalloc on Windows, and using a Windows Low Fragementation Heap (LFH)
instead, with HEAP_NO_SERIALIZE (as the heap would be protected by the
GIL).

I'm not sure that would serve the same purpose as obmalloc, which
(AFAIU) is very fast at the expense of compacity.

[tjguk]

'fraid not. I've never had to dig into the allocation stuff at this level.

[loewis]

I think it would be nice to know whether the patch has a chance of being
useful before committing it. I did it as a thought experiment after the
similar change was committed for Unix, but I'm not an expert in Windows
internals. Perhaps HeapAlloc deals fine with fragmentation?

Unfortunately, the implementation of HeapAlloc isn't really documented.
If Reactos is right, it looks like this: http://bit.ly/t2NPHh

Blocks < 1024 bytes are allocated from per-size free lists.

Blocks < Heap->VirtualMemoryThreshold are allocated through the free
list for variable-sized blocks of the heap.

Other blocks are allocated through ZwAllocateVirtualMemory, adding
sizeof(HEAP_VIRTUAL_ALLOC_ENTRY) in the beginning. I think this header
will cause malloc() to allocate one extra page in front of an arena.

> As an alternative approach, Python could consider completely dropping
> obmalloc on Windows, and using a Windows Low Fragementation Heap (LFH)
> instead, with HEAP_NO_SERIALIZE (as the heap would be protected by the
> GIL).

I'm not sure that would serve the same purpose as obmalloc, which
(AFAIU) is very fast at the expense of compacity.

I'd expect that LFH heaps are also very fast. The major difference I can
see is that blocks in the LFH heap still have an 8-byte header (possibly
more on a 64-bit system). So I wouldn't expect any speed savings, but
(possibly relevant) memory savings from obmalloc.

[briancurtin]

Tim, Brian, do you know anything about this?

Unfortunately, no. It's on my todo list of things to understand but I don't see that happening in the near future.

I'm willing to run tests or benchmarks for this issue, but that's likely the most I can provide.

[pitrou]

Le mardi 29 novembre 2011 à 22:39 +0000, Brian Curtin a écrit :

Brian Curtin <brian@python.org> added the comment:

> Tim, Brian, do you know anything about this?

Unfortunately, no. It's on my todo list of things to understand but I
don't see that happening in the near future.

I'm willing to run tests or benchmarks for this issue, but that's
likely the most I can provide.

Benchmarks would be nice indeed.

[loewis]

Here is a benchmark. Based on my assumption that this patch may reduce allocation overheads due to minimizing padding+fragmentation, it allocates a lot of memory, and then waits 20s so you can check in the process explorer what the "Commit Size" of the process is.

For the current 3.3 tree, in 32-bit mode, on a 64-bit Windows 7 installation, I get 464,756K for the unpatched version, and 450,436K for the patched version.

This is a 3% saving, which seems good enough for me.

[loewis]

Here is an updated patch.

[neologix]

Martin, do you think your latest patch can be committed?

[loewis]

Antoine's request for benchmarks still stands. I continue to think that it should be applied even in absence of benchmarks. In the absence of third opinions on this specific aspect, I don't think it can be applied.

[neologix]

I can't speak for Antoine, but I guess that the result of pybench
would be enough to make sure it doesn't introduce any regression
(which would be *really* suprising).
As for the memory savings, the benchmark you posted earlier is
conclusive enough IMO (especially since the it can be difficult to
come up with a scheme leading to heap fragmentation).