Is Python's heap allocator slowing my code drastically as overall memory usage increases?
<p>I have a program that needs to continually - at set intervals, within certain time constraints - pop/update a dict of lists of lists of varying objects. </p>

<pre><code>def update_dwindow_tables(cpos):
  # remove old tables
  kill_ids = [(f,l) for f,l in dwindow_tables if l == cpos]
  for kid in kill_ids:
    dwindow_tables.pop(kid)  
  # add new tables / append with new rows  
  for f,i,l in window_ids:                         # len == 100
    k = (f+cpos,f+i+l+cpos)
    try:
      table = dwindow_tables[k]
    except KeyError:
      table = list()
      dwindow_tables[k] = table      
    table += [[f,i,l,s,ss,fcalc,None,None,list()] \
                 for fcalc in FEATURE_INFO \        # len == 4
                   for s in SYM_RANGE \             # len == 6
                     for ss in FEATURE_INFO[fcalc]] # len == 5
</code></pre>

<p>When overall memory usage is 'low' and I run this I get acceptable/expected results:</p>

<pre><code>def test_with_noallocs(passes=25):
  cpos = 1
  dwindow_tables.clear() # start fresh
  subprocess.Popen(['free']) # show current memory
  for ii in range(passes):
    t = timed(update_dwindow_tables,1,cpos) # simple timer
    print(str(ii),'::',str(t))
    cpos += 1

&gt;&gt;&gt; test_with_noallocs()
             total       used       free     shared    buffers     cached
Mem:       7939812    3235144    4704668      11040     179312    2340784
-/+ buffers/cache:     715048    7224764
Swap:      6026236          4    6026232
0 :: 0.07612323760986328
1 :: 0.018736600875854492
2 :: 0.08361983299255371
3 :: 0.01877737045288086
4 :: 0.021776199340820312
5 :: 0.10514140129089355
6 :: 0.01875615119934082
7 :: 0.12712812423706055
8 :: 0.020363807678222656
9 :: 0.14745235443115234
10 :: 0.020594120025634766
11 :: 0.020571231842041016
12 :: 0.17327523231506348
13 :: 0.020349502563476562
14 :: 0.022448301315307617
15 :: 0.019313335418701172
16 :: 0.2052304744720459
17 :: 0.018848657608032227
18 :: 0.020733118057250977
19 :: 0.022453784942626953
20 :: 0.02028656005859375
21 :: 0.2401261329650879
22 :: 0.019221067428588867
23 :: 0.021938323974609375
24 :: 0.022317171096801758
</code></pre>

<p>As overall memory usage grows I run into issues:</p>

<pre><code>def test_with_allocs(passes=8,memjumps=7):    
  mhold = [] 
  cpos = 1
  dwindow_tables.clear() # start fresh
  for i in range(memjumps):
    subprocess.Popen(['free']) # show current memory
    for ii in range(passes):
      t = timed(update_dwindow_tables,1,cpos) # simple timer
      print(str(ii),'::',str(t))
      cpos += 1
    mhold.append([0] * 62500000) # alloc ~ 500MB
    print('-'*80)

...

&gt;&gt;&gt; test_with_allocs()
             total       used       free     shared    buffers     cached
Mem:       7939812    3291616    4648196      11040     179384    2340792
-/+ buffers/cache:     771440    7168372
Swap:      6026236          4    6026232
0 :: 0.02623128890991211
1 :: 0.07842659950256348
2 :: 0.01869797706604004
3 :: 0.02117013931274414
4 :: 0.09816169738769531
5 :: 0.017796039581298828
6 :: 0.11702108383178711
7 :: 0.020305156707763672
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    3786144    4153668      11040     179384    2340792
-/+ buffers/cache:    1265968    6673844
Swap:      6026236          4    6026232
0 :: 2.1014063358306885    &lt;--- YIKES!
1 :: 0.02068185806274414
2 :: 0.0225675106048584
3 :: 0.7974197864532471
4 :: 0.02149367332458496
5 :: 0.019992589950561523
6 :: 0.021541118621826172
7 :: 0.8673183917999268
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    4294676    3645136      11040     179384    2340792
-/+ buffers/cache:    1774500    6165312
Swap:      6026236          4    6026232
0 :: 1.3272449970245361    &lt;--- YIKES!
1 :: 0.020661592483520508
2 :: 0.023934364318847656
3 :: 1.5896172523498535    &lt;--- YIKES!
4 :: 0.02139139175415039
5 :: 0.020427465438842773
6 :: 0.020937681198120117
7 :: 0.022132158279418945
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    4802688    3137124      11040     179384    2340792
-/+ buffers/cache:    2282512    5657300
Swap:      6026236          4    6026232
0 :: 3.582160711288452     &lt;--- YIKES!
1 :: 0.0217897891998291
2 :: 0.021826744079589844
3 :: 0.0232698917388916
4 :: 0.022684097290039062
5 :: 0.02332758903503418
6 :: 0.026173830032348633
7 :: 2.3785290718078613    &lt;--- YIKES!
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    5307360    2632452      11040     179392    2340800
-/+ buffers/cache:    2787168    5152644
Swap:      6026236          4    6026232
0 :: 1.2985937595367432    &lt;--- YIKES!
1 :: 0.02199387550354004
2 :: 0.027379512786865234
3 :: 0.02257084846496582
4 :: 0.026216983795166016
5 :: 0.024593830108642578
6 :: 3.0734689235687256    &lt;--- YIKES!
7 :: 0.023942232131958008
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    5798440    2141372      11040     179392    2340800
-/+ buffers/cache:    3278248    4661564
Swap:      6026236          4    6026232
0 :: 1.329371690750122     &lt;--- YIKES!
1 :: 0.02473139762878418
2 :: 0.023987293243408203
3 :: 0.0245821475982666
4 :: 0.02610492706298828
5 :: 3.6783151626586914    &lt;--- YIKES!
6 :: 0.023839950561523438
7 :: 0.023787736892700195
--------------------------------------------------------------------------------
             total       used       free     shared    buffers     cached
Mem:       7939812    6287984    1651828      11040     179400    2340800
-/+ buffers/cache:    3767784    4172028
Swap:      6026236          4    6026232
0 :: 1.3231782913208008     &lt;--- YIKES!
1 :: 0.02602362632751465
2 :: 0.027123451232910156
3 :: 0.02720165252685547
4 :: 0.02463078498840332
5 :: 4.431311845779419      &lt;--- YIKES!
6 :: 0.0224149227142334
7 :: 0.025854110717773438
--------------------------------------------------------------------------------
</code></pre>

<p>I assume this has to do with how Python's heap allocator works? All I could find was a few old posts, and a few pages in the docs, giving an overview but nothing more specific. Maybe someone could explain this, and whether there's a simple work-around(or I'm just missing something obvious,) before I start drudging though the source. </p>