[Python-Dev] extremely slow exit for program having huge (45G) dict (python 2.5.2)

[Alexandre Vassalotti]

On Mon, Dec 22, 2008 at 7:34 PM, Antoine Pitrou <solipsis at pitrou.net> wrote:
>
>> Now, we should find a way to benchmark this without having to steal Mike's
>> machine and wait 30 minutes every time.
>
> So, I seem to reproduce it. The following script takes about 15 seconds to
> run and allocates a 2 GB dict which it deletes at the end (gc disabled of
> course).
> With 2.4, deleting the dict takes ~1.2 seconds while with 2.5 and higher
> (including 3.0), deleting the dict takes ~3.5 seconds. Nothing spectacular
> but the difference is clear.
>

I modified your script to delete the dictionary without actually
deallocating the items in it. You can speed up a dictionary
deallocation significantly if you keep a reference to its items and
delete the dictionary before deleting its items. In Python 2.4, the
same behavior exists, but is not as strongly marked as in Python 2.6
with pymalloc enabled.

I can understand that deallocating the items in the order (or
actually, the reverse order) they were allocated is faster, than doing
so in a rather haphazard manner (i.e., like dict). However, I am not
sure why pymalloc accentuate this behavior.

-- Alexandre

Python 2.6 with pymalloc, without pydebug

alex at helios:~$ python2.6 dict_dealloc_test.py
creating 397476 items...
 -> 6.613 s.
building dict...
 -> 0.230 s.
deleting items...
 -> 0.059 s.
deleting dict...
 -> 2.299 s.
total deallocation time: 2.358 seconds.

alex at helios:~$ python2.6 dict_dealloc_test.py
creating 397476 items...
 -> 6.530 s.
building dict...
 -> 0.228 s.
deleting dict...
 -> 0.089 s.
deleting items...
 -> 0.971 s.
total deallocation time: 1.060 seconds.


Python 2.6 without pymalloc, without pydebug

alex at helios:release26-maint$ ./python /home/alex/dict_dealloc_test.py
creating 397476 items...
 -> 5.921 s.
building dict...
 -> 0.244 s.
deleting items...
 -> 0.073 s.
deleting dict...
 -> 1.502 s.
total deallocation time: 1.586 seconds.

alex at helios:release26-maint$ ./python /home/alex/dict_dealloc_test.py
creating 397476 items...
 -> 6.122 s.
building dict...
 -> 0.237 s.
deleting dict...
 -> 0.092 s.
deleting items...
 -> 1.238 s.
total deallocation time: 1.330 seconds.


alex at helios:~$ python2.4 dict_dealloc_test.py
creating 397476 items...
 -> 6.164 s.
building dict...
 -> 0.218 s.
deleting items...
 -> 0.057 s.
deleting dict...
 -> 1.185 s.
total deallocation time: 1.243 seconds.

alex at helios:~$ python2.4 dict_dealloc_test.py
creating 397476 items...
 -> 6.202 s.
building dict...
 -> 0.218 s.
deleting dict...
 -> 0.090 s.
deleting items...
 -> 0.852 s.
total deallocation time: 0.943 seconds.



######

import random
import time
import gc


# Adjust this parameter according to your system RAM!
target_size = int(2.0  * 1024**3)  # 2.0 GB

pool_size = 4 * 1024
# This is a ballpark estimate: 60 bytes overhead for each
# { dict entry struct + float object + tuple object header },
# 1.3 overallocation factor for the dict.
target_length = int(target_size / (1.3 * (pool_size + 60)))

def make_items():
    print ("creating %d items..." % target_length)

    # 1. Initialize a set of pre-computed random keys.
    keys = [random.random() for i in range(target_length)]

    # 2. Build the values that will constitute the dict. Each value will, as
    #    far as possible, span a contiguous `pool_size` memory area.

    # Over 256 bytes per alloc, PyObject_Malloc defers to the system malloc()
    # We avoid that by allocating tuples of smaller longs.
    int_size = 200
    # 24 roughly accounts for the long object overhead (YMMV)
    int_start = 1 << ((int_size - 24) * 8 - 7)
    int_range = range(1, 1 + pool_size // int_size)

    values = [None] * target_length
    # Maximize allocation locality by pre-allocating the values
    for n in range(target_length):
       values[n] = tuple(int_start + j for j in int_range)
    return list(zip(keys,values))

if __name__ == "__main__":
    gc.disable()
    t1 = time.time()
    items = make_items()
    t2 = time.time()
    print " -> %.3f s." % (t2 - t1)

    print "building dict..."
    t1 = time.time()
    testdict = dict(items)
    t2 = time.time()
    print " -> %.3f s." % (t2 - t1)

    def delete_testdict():
       global testdict
       print "deleting dict..."
       t1 = time.time()
       del testdict
       t2 = time.time()
       print " -> %.3f s." % (t2 - t1)

    def delete_items():
       global items
       print "deleting items..."
       t1 = time.time()
       del items
       t2 = time.time()
       print " -> %.3f s." % (t2 - t1)

    t1 = time.time()
    # Swap these, and look at the total time
    delete_items()
    delete_testdict()
    t2 = time.time()
    print "total deallocation time: %.3f seconds." % (t2 - t1)