I've added calls to vmmap to the script (using os.system) to check my guesss.

The relevant bit after the call to test_iter(1<<24):

REGION TYPE                      VIRTUAL
===========                      =======
MALLOC                            405.9M        see MALLOC ZONE table below
MALLOC guard page                    32K
MALLOC metadata                     376K
STACK GUARD                        56.0M
Stack                              8192K
VM_ALLOCATE                           4K
__DATA                             1720K
__LINKEDIT                         53.4M
__TEXT                             12.1M
__UNICODE                           544K
shared memory                         8K
===========                      =======
TOTAL                             538.1M

                                     VIRTUAL ALLOCATION      BYTES
MALLOC ZONE                             SIZE      COUNT  ALLOCATED  % FULL
===========                          =======  =========  =========  ======
DefaultMallocZone_0x100436000         404.9M     414059     390.6M     96%
DispatchContinuations_0x1007dc000      1024K         17       1056      0%
===========                          =======  =========  =========  ======
TOTAL                                 405.9M     414076     390.6M     96%

Memory usage:  14.3 MB



And after the call to test_iter(1<<13)


REGION TYPE                      VIRTUAL
===========                      =======
MALLOC                            208.9M        see MALLOC ZONE table below
MALLOC freed, no zone             456.0M
MALLOC guard page                    32K
MALLOC metadata                     392K
STACK GUARD                        56.0M
Stack                              8192K
VM_ALLOCATE                           4K
__DATA                             1720K
__LINKEDIT                         53.4M
__TEXT                             12.1M
__UNICODE                           544K
shared memory                         8K
===========                      =======
TOTAL                             797.1M

                                     VIRTUAL ALLOCATION      BYTES
MALLOC ZONE                             SIZE      COUNT  ALLOCATED  % FULL
===========                          =======  =========  =========  ======
DefaultMallocZone_0x100436000         207.9M     209467     197.0M     94%
DispatchContinuations_0x1007dc000      1024K         17       1056      0%
===========                          =======  =========  =========  ======
TOTAL                                 208.9M     209484     197.0M     94%


Memory usage: 462.6 MB



The total amount of "memory usage" is grown by about 450 MBytes  (according to psutils). This is explained by the change in MALLOC memory, before:



MALLOC                            405.9M        see MALLOC ZONE table below
MALLOC guard page                    32K
MALLOC metadata                     376K

Total: about 406 MByte

After:


MALLOC                            208.9M        see MALLOC ZONE table below
MALLOC freed, no zone             456.0M
MALLOC guard page                    32K
MALLOC metadata                     392K

Total: about 665 MByte.


The difference is about 260 MBytes, which is significant but less than the difference according to psutil. But: the psutil difference as calculated by the script is the difference in RSS, not VSIZE (which vmmap shows).

If I change the _mem function to use the VSIZE the before and after values are:

Memory usage: 2390.4 MB
Memory usage: 2846.4 MB

Difference: about 456 MByte, which is still higher than the output of vmmap. 

Note that the same behavior can be seen by a much simpler script:

    print "Large"
    x = list(range(1<<24))
    print _mem()
    del x
    print _mem()

    print

    print "Small"
    x = list(range(1<<23))
    print _mem()
    del x
    print _mem()

(where _mem is the same function as in testiterbug.py).

The output is:

Large
Memory usage: 527.3 MB
Memory usage:  19.3 MB

Small
Memory usage: 330.6 MB
Memory usage: 147.6 MB


With this script is see the same pattern with vmmap: with the "small" list a large amount of memory is in regions of type (MALLOC freed, no zone).

All of this clearly points towards malloc not releasing allocated memory to the system. This is perfectly fine and not a bug in either Python or the system.