Noam Raphael wrote:

Should something be done about it?

It's very difficult to do something useful about it. Even if you manage to determine how much memory you want to release, it's nearly impossible to actually release the memory to the operating system, because of the many layers of memory management software that all need to agree that the memory should be reused somewhere else (instead of keeping it on that layer, just in case somebody using that layer wants some memory). Regards, Martin

...

It's very difficult to do something useful about it. Even if you manage to determine how much memory you want to release, it's nearly impossible to actually release the memory to the operating system, because of the many layers of memory management software that all need to agree that the memory should be reused somewhere else (instead of keeping it on that layer, just in case somebody using that layer wants some memory).

I checked - when doing the same thing with lists, all the memory was released for use by other Python objects, and most of it was released for use by the operating system.

Put another way, it is difficult to assure that the memory is released back to the operating system. We don't control that part. What could be done is to add a test for excess dummy entries and trigger a periodic resize operation. That would make the memory available for other parts of the currently running script and possibly available for the O/S. The downside is slowing down a fine-grained operation like pop(). For dictionaries, this wasn't considered worth it. For sets, I made the same design decision. It wasn't an accident. I don't plan on changing that decision unless we find a body of real world code that would be better-off with more frequent re-sizing. Raymond

On 12/29/05, Raymond Hettinger wrote:

What could be done is to add a test for excess dummy entries and trigger a periodic resize operation. That would make the memory available for other parts of the currently running script and possibly available for the O/S.

The downside is slowing down a fine-grained operation like pop(). For dictionaries, this wasn't considered worth it. For sets, I made the same design decision. It wasn't an accident. I don't plan on changing that decision unless we find a body of real world code that would be better-off with more frequent re-sizing.

The computer scientist in me prefers O() terms over changes in a constant factor, but that's only me. Perhaps a note about it should be added to the documentation, though? Noam

On Thursday, December 29, 2005 "Martin v. Löwis" wrote:

Noam Raphael wrote:

In this specific case, perhaps. malloc will typically return memory to the system only if that memory is at the end of the heap. If there is more memory after block to be released, it can't return the memory block, because it won't punch a whole into the heap.

So as soon as you have more than one object, things become interesting.

Different systems use different, enhance strategies, of course. For example, Linux glibc malloc will allocate "large" blocks through mmap (instead of sbrk), such blocks then can be returned individually.

MSVC 7.1 and 8.0 malloc always uses the Windows heap functions (HeapAlloc & friends) if running on Windows 2000 or newer (malloc.c and heapinit.c). So it seems that for both Linux (gcc) and Win (msvc) the memory is released to the operating system. Of course, fragmentation is still an issue, but now it's on the OS side of things.

I did a little test using MSVC 8.0 on WinXP. I allocated 128 MB using 128 different buffers of 1 MB each, freed half of them (alternatively) then freed the remaining half. I monitored memory usage using the Task Manager and memory is really freed as indicated by both the "Mem Usage" and "VM Size" process counters and also by the global "Commit Charge". After exiting the process the commit charge remains the same, suggesting that all the memory was indeed released. Even if the Windows heap documentation says that once memory is allocated, it won't be released until the heap is destroyed, this seems to not be true when allocating large chunks. There probably is a threshold after which VirtualAlloc is used. #include #include #include #define COUNT 128 void main() { char** ptr = malloc(COUNT * sizeof(char*)); int i; for (i = 0; i < COUNT; ++i) { ptr[i] = malloc(1024 * 1024); // Touch memory to really commit it. SecureZeroMemory(ptr[i], 1024 * 1024); } printf("Mem allocated\n"); Sleep(5000); for (i = 0; i < COUNT; i += 2) free(ptr[i]); printf("Half memory deallocated\n"); Sleep(10000); for (i = 1; i < COUNT; i += 2) free(ptr[i]); printf("Full memory deallocated\n"); Sleep(10000); }

Noam Raphael wrote:

On 12/29/05, Raymond Hettinger wrote:

...

What could be done is to add a test for excess dummy entries and trigger a periodic resize operation. That would make the memory available for other parts of the currently running script and possibly available for the O/S.

The downside is slowing down a fine-grained operation like pop(). For dictionaries, this wasn't considered worth it. For sets, I made the same design decision. It wasn't an accident. I don't plan on changing that decision unless we find a body of real world code that would be better-off with more frequent re-sizing.

The computer scientist in me prefers O() terms over changes in a constant factor, but that's only me. Perhaps a note about it should be added to the documentation, though?

The computer scientist in me agrees with you, but the practical application developer in me argues that every microsecond adds up. - Josiah

Martin v. Löwis wrote:

Adal Chiriliuc wrote:

...

MSVC 7.1 and 8.0 malloc always uses the Windows heap functions (HeapAlloc & friends) if running on Windows 2000 or newer (malloc.c and heapinit.c).

So it seems that for both Linux (gcc) and Win (msvc) the memory is released to the operating system.

How so? HeapFree does not return the memory to the system. From

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/memory/base...

"Once the pages are committed, they are not decommitted until the process is terminated or until the heap is destroyed by calling the HeapDestroy function."

http://www.python.org/sf/1389051 agrees with the microsoft documentation. (where imaplib runs out of memory after read- ing 2 megabytes of a 14 megabyte message). </F>

On 12/29/05, Noam Raphael wrote:

On 12/29/05, Donovan Baarda wrote:

...

Without some sort of fancy overkill size hinting or history tracking, that's probably as good a heuristic as you can get.

I'm sorry, but it's not correct. There's a simple resize scheduling algorithm that is proven to take, when you sum things up, O(1) per each simple operation, and that keeps the amount of used memory always proportional to the number of elements in the set.

I'm not saying that practically it must be used - I'm just saying that it can't be called a heuristic, and that it doesn't involve any "fancy overkill size hinting or history tracking". It actually means something like this: 1. If you want to insert and the table is full, resize the table to twice the current size. 2. If you delete and the number of elements turns out to be less than a quarter of the size of the table, resize the table to half of the current size.

I'm neutral on doing this. I'd like to point out that if we decide not to do this, there's an easy way to shrink dicts and sets under user control, which means that you only have to pay attention in the rare cases where it matters: create a new dct or set from the old one automatically creates one of the right size. E.g. s = set(s) replaces the set s (which may once have had 1M items and now has nearly 1M empty slots) by one with the "optimal" number of slots. Ditto for dicts: d = dict(d) -- --Guido van Rossum (home page: http://www.python.org/~guido/)

On Thu, 2005-12-29 at 17:17 +0100, Fredrik Lundh wrote:

Noam Raphael wrote:

...

I'm not saying that practically it must be used - I'm just saying that it can't be called a heuristic, and that it doesn't involve any "fancy overkill size hinting or history tracking". It actually means something like this: 1. If you want to insert and the table is full, resize the table to twice the current size. 2. If you delete and the number of elements turns out to be less than a quarter of the size of the table, resize the table to half of the current size.

sure sounds like a heuristic algorithm to me... (as in "not guaranteed to be optimal under all circumstances, even if it's probably quite good in all practical cases")

</F>

My problem with this heuristic is it doesn't work well for the probably-fairly-common use-case of; fill it, empty it, fill it, empty it, fill it...etc. As Guido pointed out, if you do have a use-case where a container gets very big, then shrinks and doesn't grow again, you can manually cleanup by creating a new container and del'ing the old one. If the implementation is changed to use this heuristic, there is no simple way to avoid the re-allocs for this use-case... (don't empty, but fill with None... ugh!). My gut feeling is this heuristic will cause more pain than it would gain... -- Donovan Baarda http://minkirri.apana.org.au/~abo/

Noam Raphael wrote:

On 12/29/05, Fredrik Lundh wrote:

...

Noam Raphael wrote:

...

I'm not saying that practically it must be used - I'm just saying that it can't be called a heuristic, and that it doesn't involve any "fancy overkill size hinting or history tracking". It actually means something like this: 1. If you want to insert and the table is full, resize the table to twice the current size. 2. If you delete and the number of elements turns out to be less than a quarter of the size of the table, resize the table to half of the current size.

sure sounds like a heuristic algorithm to me... (as in "not guaranteed to be optimal under all circumstances, even if it's probably quite good in all practical cases")

I'm not saying it's optimal, but it is really amortized O(1) per insert/delete. I looked up in "Introduction to Algorithms" for this, and it has a complicated explanation. A simple explanation is that after every resize the table is exactly half-full. Let's say it has n elements and the table size is 2*n. To get to the next resize, you have to do at least n/2 removals of elements, or n insertion of elements. After that, you do a resize operation. In either case, you do an O(n) resize operation after at least O(n) insertions/removals which are O(1) operations. This means that the toal cost remains O(n) per n simple operations, which you can say is O(1) per simple operation.

I hope that if you read this slowly it makes sense...

This is understood by (I would expect) most people here (hash-tables are (theoretically and practically) average as you state, but (theoretically) worst-case as Martin states). For resizing, a quick-and-dirty rule of thumb is that if you are overallocating by a factor of f(n), the amount of work you will be performing per insertion is ~cn/f(n) (1 <= c <= 2). As per recent discussions on lists, Python chooses f(n) to be n/8. (at least in the list case) This says that every insertion is taking around ~8 memory copies if/when the list is resized up, but practical experience has shown that it also tends to minimize memory usage as the list grows. It's all about tradeoffs. Increasing general memory usage for the sake of a lower constant or not is a tradeoff. As is resizing or not resizing as a list gets smaller. Would changing the overallocation strategy change Python's performance? Likely, but possibly not noticable. Would it change Python memory usage? Yes. A vast majority of list use would cause larger allocations than currently performed by the list allocator. Want to test it? Create a micro benchmark which tests repeated append performance with the two list allocation strategies and remember to note the memory usage of Python after each test. - Josiah