tag

#performance

17 pages tagged

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.17 Cache Behavior

5.17 Cache Behavior Problem Hash tables are expected constant time structures, but real performance often deviates from that expectation due to memory hierarchy effects. Poor cache locality can dominate runtime even when asymptotic complexity is optimal. You need to understand how hash table design interacts with CPU caches and memory access patterns. Solution Design hash-based structures to maximize spatial locality and minimize unpredictable memory access. Key principles: - Prefer contiguous...
algorithms hashing performance cache systems May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.24 Real-World Hash Table Design

5.24 Real-World Hash Table Design Problem You need to choose and implement a hash table that performs reliably under real workloads: mixed key types, uneven access patterns, deletions, resizing, and possible adversarial input. Pure theoretical designs often fail in production due to constant factors, memory layout, and edge cases. Solution Design the hash table as a layered system with explicit responsibilities: - hashing layer - indexing layer - collision handling...
algorithms hashing design systems performance May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.23 Cache-Aware Hashing

5.23 Cache-Aware Hashing Problem Hash tables often fail to achieve their theoretical performance because memory access patterns dominate runtime. Even with good hashing and controlled load factor, repeated cache misses can make operations significantly slower than expected. You need a design that aligns hash table behavior with CPU cache structure. Solution Structure the hash table to maximize spatial locality and reduce pointer chasing. Core strategies: - use contiguous storage for...
algorithms hashing cache performance systems May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.21 Consistent Performance Guarantees

5.21 Consistent Performance Guarantees Problem A hash-based structure may perform well on average but still fail in production due to unpredictable worst-case behavior. You need predictable performance bounds, not just good expected performance. This matters in systems where latency spikes are unacceptable: real-time services, interactive applications, databases, and network-facing APIs. Solution Control performance through a combination of design constraints: - bounded load factor - controlled collision handling - stable hash...
algorithms hashing performance guarantees worst-case May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.4 Load Factor and Resizing

5.4 Load Factor and Resizing Problem As a hash table grows, collisions increase and operations slow down. If the table never expands, performance degrades toward linear time. If it expands too aggressively, memory is wasted and resizing costs dominate. You need a policy that keeps operations fast while controlling memory usage. Solution Track the load factor and resize the table when it crosses a threshold. load_factor = size / capacity...
algorithms hashing load-factor resizing performance May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 12. Specialized Search and Sorted-Order Procedures ›

Branchless Binary Search

Branchless Binary Search Branchless binary search is a binary search variant designed to reduce branch mispredictions. A normal binary search repeatedly branches on whether the middle value is less than the target. On modern CPUs, this branch can be hard to predict because the search direction depends on the data. A branchless version keeps the same comparison logic but updates the search position using conditional moves, masks, or arithmetic expressions....
algorithms searching binary-search branchless performance
Deep Reads › CPython Internals › 8. Performance Internals ›

79. Memory Locality

79. Memory Locality Memory locality is the degree to which a program accesses memory that is close together in time and space. CPython is a dynamic object runtime. Most Python values are heap-allocated objects, accessed through pointers. This gives Python flexibility, but it also means execution often follows chains of references through memory. Example: total += obj.value At the machine level, this may touch: current frame evaluation stack local variable...
cpython python internals performance memory
Deep Reads › CPython Internals › 8. Performance Internals ›

72. Interpreter Dispatch

72. Interpreter Dispatch Interpreter dispatch is the mechanism that drives bytecode execution inside CPython. The compiler transforms Python source code into bytecode instructions. The interpreter loop then repeatedly fetches, decodes, and executes those instructions. Dispatch is the process that selects the implementation for each opcode and transfers control to it. This chapter focuses on the execution engine inside CPython: Python source ↓ compiler ↓ bytecode ↓ evaluation loop ↓ opcode...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

77. Dictionary Performance

77. Dictionary Performance Dictionaries are one of the most important data structures in CPython. Python uses dictionaries for: global namespaces module namespaces instance attributes class attributes keyword arguments caches sets internals JSON-like data configuration objects symbol tables Many Python operations ultimately become dictionary operations. Examples: x = globals()["name"] obj.attr module.value kwargs["limit"] Because dictionaries are everywhere, CPython invests heavily in dictionary performance. Modern CPython dictionaries are compact, cache-friendly, insertion-ordered hash tables...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

73. Inline Caches

73. Inline Caches Inline caches are small cache records stored near bytecode instructions. They let CPython remember facts discovered during previous executions of an instruction, then reuse those facts on later executions. The goal is simple: avoid repeating expensive dynamic lookups when the runtime situation has not changed. For example, this expression looks small: obj.name But generic attribute lookup may involve: look at obj type check descriptors check instance dictionary...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

80. Profiling CPython

80. Profiling CPython Profiling CPython means measuring where time, memory, allocations, and interpreter work are spent. It is the practical bridge between a performance suspicion and a performance explanation. A Python program can be slow for many different reasons: too many Python function calls slow attribute lookup large dictionary workloads excessive allocation poor memory locality I/O waiting bad algorithmic complexity C extension overhead lock contention garbage collection pauses Profiling separates...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

74. Specializing Adaptive Interpreter

74. Specializing Adaptive Interpreter The specializing adaptive interpreter is the optimization architecture introduced in modern CPython to reduce the cost of dynamic execution without requiring a full JIT compiler. Traditional interpreters execute generic bytecode instructions: LOAD_ATTR BINARY_OP CALL LOAD_GLOBAL These instructions must support every valid Python behavior. For example: a + b may mean: integer addition float addition string concatenation list concatenation custom __add__ custom __radd__ NumPy vector operation unsupported...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

76. Vectorcall

76. Vectorcall Vectorcall is CPython’s fast calling convention for many callable objects. Its purpose is to avoid building temporary argument containers for common function calls. Older generic calls often packaged positional arguments into a tuple and keyword arguments into a dictionary. That representation is flexible, but expensive. Vectorcall passes arguments as a compact C array of PyObject * pointers, often pointing directly into the interpreter stack. Conceptually: generic call: callable(args_tuple,...
cpython python internals performance
Deep Reads › CPython Internals › 10. Advanced Topics ›

95. JIT Work in CPython

95. JIT Work in CPython A Just-In-Time compiler, usually called a JIT, dynamically compiles frequently executed program paths into native machine code during runtime execution. Traditional CPython primarily uses interpretation: Python source ↓ bytecode ↓ evaluation loop ↓ C implementation A JIT changes this model: Python source ↓ bytecode ↓ runtime profiling ↓ native machine code generation ↓ direct CPU execution The goal is improving performance by reducing interpreter overhead....
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

78. Attribute Access Performance

78. Attribute Access Performance Attribute access is one of the most frequent operations in Python. It appears whenever code reads, writes, or deletes a named field on an object. obj.name obj.name = value del obj.name At source level, attribute access looks like a simple field operation. In CPython, it is a dynamic protocol involving object types, dictionaries, descriptors, slots, method binding, inheritance, inline caches, and specialization. A simple expression: obj.x...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

75. Function Call Fast Paths

75. Function Call Fast Paths Function calls are one of the most important performance paths in CPython. Python programs call functions constantly: len(xs) str(x) range(n) obj.method() f(a, b) callback(event) decorator(fn) A call looks simple at the source level, but CPython must support many callable forms: Python functions bound methods builtin functions builtin methods C extension callables classes objects with __call__ classmethod objects staticmethod objects partial objects decorated wrappers A generic...
cpython python internals performance
Deep Reads › CPython Internals › 8. Performance Internals ›

81. Benchmarking CPython

81. Benchmarking CPython Benchmarking CPython means measuring execution speed in a controlled, repeatable way. Profiling answers where time is spent. Benchmarking answers how much a change affects performance. A benchmark should compare two states: baseline candidate The baseline may be an older CPython build, an earlier version of a function, or a different implementation strategy. The candidate is the version being tested. The goal is not to get one impressive...
cpython python internals performance