Under the Hood of Python Data Structures
summary
CPython source code and quick REPL experiments show lists as contiguous dynamic arrays that overallocate (~12.5%) using a shift-and-round formula when append is called (avoiding frequent reallocations), integers are cached for -5..256 (small-int cache -5..256), dicts start with eight index slots and use a separate entries table plus quadratic probing for collisions, sets are hash-only dicts, and tuples are single contiguous allocations and hashable when elements are. Empirical timings confirm dict/set lookup O(1) vs list linear scans; preallocation improves append-heavy cases.
AI-written summary · about
chapters (12)
- 0:00Introduction to Python internals
- 1:28Python implementation overview
- 3:40Compiled vs interpreted languages
- 5:04Variables and memory references
- 7:11Mutability in Python objects
- 9:21How lists are implemented
- 14:30Hash functions and hash tables
- 18:45Dictionaries in Python
- 20:29Sets and their implementation
- 21:53Performance of data structures
- 22:33Learning from Python internals
- 23:56Q&A session
related talks
42mOptimizing Code Performance for Python Internals
27mVariables and objects in Python: it's pointers all the way down
22mLow Level Python a Deep dive into the python sources
34mCPython internals and the VM
41mHow to write a JIT compiler in 30 minutes
23mApple Array Allocation
16mIntrepydd: Performance, Productivity, and Portability for Data Science Application Kernels
35mWhat Lies Beneath - A Deep Dive Into Clojure's Data Structures