Upgrade to Pro — share decks privately, control downloads, hide ads and more …

PyCon Ireland 2013: CPython objects implementat...

PyCon Ireland 2013: CPython objects implementation pearls

(via http://python.ie/pycon/2013/talks/cpython_objects_implementation_pearls/)
Speaker: Laurent Luce (http://twitter.com/laurentluce)

Knowing more about a programming language implementation helps to be more efficient when coding. CPython is the most-used implementation of Python, and its objects internals contain many pearls. We will cover some of the implementation pearls found in the list, dictionary, string and integer/long objects.

We will ask ourselves questions such as:
What is done internally to make the list append operation fast?
What is done to speed up key lookups in dictionaries?
what is done to optimize memory for integers/longs?

This talk will answer those questions and go over some other CPython internal pearls. I will use diagrams to clearly demonstrate the CPython concepts. We will point out differences between Python 2.x and Python 3.x.

Outline:

List object implementation pearls: - Append operation time-complexity. - Optimized sort algorithm called "timsort".

Dictionary object implementation pearls: - Resizing management. - Collision resolution.

String object implementation pearls: - Sharing small strings. - Find method algorithm.

Integer/Long object implementation pearls: - Sharing small integers/longs. - Blocks of integers.

PyCon Ireland

October 12, 2013
Tweet

More Decks by PyCon Ireland

Other Decks in Technology

Transcript

  1. list.append odds = [] 1 3 5 7 odds.append(1) odds.append(3)

    odds.append(5) odds.append(7) odds.append(9) 9
  2. Growth pattern (size >> 3) + (size < 9 ?

    3 : 6) + size Ask for 1 -> Get 4. Ask for 5 -> Get 8. Ask for 9 -> Get 16. 25, 35, 46, 58, 72, 88, … TODO: Graph
  3. list.sort if N < 64: Binary insertion sort else: Find

    natural runs. a0 <= a1 <= a2 <= … a0 > a1 > a2 > … Merge runs.
  4. Runs N = 2112. If minrun = 32: Two runs

    of length 2048 and 64 to merge. Costly. If minrun = 33: All merges balanced. q, r = divmod(N, minrun). Bad: q power of 2 and r > 0. q little larger than power of 2. Good: q power of 2 and r = 0. q slightly less than power of 2.
  5. 1st run 1 3 6 4 8 7 9 ...

    5 ... 2 1 3 0 33 2112 6 1 3 4 5 6 7 9 ... 41 0 33
  6. Merging runs A B C If A <= B +

    C: Merge smaller of A and C with B. 30 20 10 BC 30
  7. Galloping 10 12 16 21 24 27 32 36 38

    41 ... 2 4 5 7 9 13 14 18 23 ... 10 2 4 7 14 11 9 13 11 Happens when one run keeps winning. B[2**(k-1) - 1] < A[0] <= B[2**k - 1] Compare A[0] to B[0], B[1], B[3], B[7]... Uncertainty: 2**(k-1) - 1
  8. Pros/Cons of “timsort” • Does well on pre-existing order. •

    Does not do as well as the old “samplesort” on lists with many duplicates. • Requires a temp array of up to N/2 elements (random data).
  9. dict letters = {} letters[‘a’] = ‘first’ letters[‘b’] = ‘second’

    letters[‘z’] = ‘last’ letters {‘a’: ‘first’, ‘b’: ‘second’, ‘z’: ‘last’}
  10. Hash table and slot index Hash table with initial size

    of 8 slots. Slot index = hash(key) & (table_size - 1) Python hash function is very regular for ints and strings: map(hash, (0, 1, 2, 3)) = [0, 1, 2, 3] key ‘0’ -> slot 0 key ‘1’ -> slot 1...
  11. Slot index letters = {} ‘a’ ‘b’ letters[‘a’] = ‘first’

    letters[‘b’] = ‘second’ letters[‘z’] = ‘last’ ‘z’
  12. Collision resolution Bad scenario: Hash table of size 2**15 Adding

    keys: [2**16, 2**16+1, …] Key 2**16 -> Slot 2**16 & (2**15 - 1) = 0 Key 2**16 + 1 -> Slot 0. Linear probing If slot used: check slot + 1
  13. Linear probing data = {} data[2**15] = ‘first’ data[2**15+1] =

    ‘second’ data[2**15+2] = ‘third’ 2**15 2**15 +1 2**15 +2
  14. Collision resolution slot = ((5*slot) + 1) % 2**i Unlikely

    hash codes follow a 5*slot+1 recurrence. 0 -> 1 -> 6 -> 7 -> 4 -> 5 -> 2 -> 3 -> 0 slot = (5*slot) + 1 + perturb perturb >>= 5 use slot % 2**i next.
  15. Resizing fill = used slots + dummy slots if table

    usage >= 2/3: if used slots > 50000: Double the table size. else: Quadruple the table size.
  16. str.find a b c b a b b d c

    b ... b a c Mix between boyer-moore and horspool. b b b c c b a b b c d
  17. Bloom filter for (mask = i = 0; i <

    p_len; i++) mask |= (1 << (p[i] & 0x1F)); Is chr in string? mask & (1 << (chr & 0x1F))
  18. int a = 1000 0 40 1000 b = 1001

    a 1001 b del a del b
  19. Int a = 1000 b = 1000 a is b

    False a = 10 b = 10 a is b True