[ TOPIC ]
algorithmic-optimization
40 real merged PRs across 11 projects, ordered easiest to hardest. Read them in order to see how algorithmic-optimization shows up in production code, then go deeper with the free papers and talks below.
[ 01 // REAL PRs ]
Next (mid) · 24
enhance: sort merged rerank results without per-comparison map lookups
This PR teaches how to optimize sorting by avoiding per-comparison map lookups, using struct-based sorting for performance, and demonstrates careful regression testing to ensure ordering correctness.
fix: accumulate RetrieveResultCache size instead of recomputing it per merge
This PR teaches how to turn a quadratic-time accumulation pattern into a linear one by incrementally tracking the size of a merged protobuf message, with careful attention to what data is retained and how to conservatively estimate memory usage.
Cache the finalized cardinality in `uniq_v2` statistics
This PR demonstrates how to optimize expensive repeated computations by caching results, including how to safely memoize in a concurrent context and add targeted performance regression tests.
enhance: [3.0] sort merged rerank results without per-comparison map lookups
This PR demonstrates how to optimize sorting by avoiding repeated map lookups in comparators, using struct slices and stable sorting, and shows how to rigorously test for behavioral equivalence and tuple alignment.
fs: fix glob early return skipping sibling entries
This PR teaches how to fix a subtle bug in a tree traversal algorithm by correctly using a cache to avoid skipping valid sibling entries, and demonstrates how to write a deterministic regression test for order-dependent bugs.
enhance: resolve the destination column by index in AppendFieldData
This PR demonstrates how to optimize a hot code path by replacing repeated map construction with fast-path index-based access, falling back to a map only when necessary, and includes clear benchmarking and robust testing.
fix: support vector output with order_by
This PR teaches how to handle late materialization of complex data types (like vectors) in query execution plans to support efficient ORDER BY queries with vector outputs.
Avoid deep copy of AccessRights in getGrantQueriesImpl when it is only read
This PR teaches how to optimize performance by avoiding unnecessary deep copies of complex data structures, with careful attention to when mutation is required and how to validate the change with targeted regression tests.
lightning: optimize CSV field unescaping
This PR teaches how to replace a regular-expression-based string unescaping routine with a more efficient manual byte-scanning algorithm, including how to preserve edge-case behavior and add targeted benchmarks and tests.
Prune row groups for column-constant OR
This PR teaches how to optimize query execution by pruning row groups using cross-column OR predicates and demonstrates careful test coverage and code review for correctness and maintainability.
[CPUManager] Skip partially acquired cores during full cores allocation
This PR teaches how to robustly handle heterogeneous hardware topologies in CPU allocation logic by replacing naive integer division with per-structure queries, improving correctness and testability.
CPUMANAGER: spread CPUs across cores using topology
This PR teaches how to improve CPU allocation by spreading CPU assignments across physical cores using topology-aware round-robin selection, with comprehensive tests covering diverse CPU layouts.
[Quantity] Fix scaledValue to round negative Quantity values away from zero
This PR teaches how to correctly implement rounding away from zero for negative numbers in scaling functions, including handling edge cases and ensuring consistency between different numeric backends with thorough testing.
fs: stop stat()ing every entry in recursive readdir
This PR teaches how to optimize recursive directory reading by reducing expensive stat() calls using file type info from the OS binding, with careful error handling and API consistency.
gh-150820: Speed up json.dumps() for small documents
This PR teaches how to optimize Python code by avoiding unnecessary closure creation in a hot path, resulting in measurable performance gains for common-case usage.
bpf: extract L3/L4 rewrite+checksum helpers for sharing codebase
This PR teaches how to refactor protocol-specific packet rewriting logic into reusable helpers while considering code complexity and compiler output in a systems context.
enhance: reduce Tantivy index build write amplification [3.0]
This PR teaches how to reduce write amplification in index building by tuning memory budgets and merge policies for in-memory and sealed index writers.
enhance: reduce Tantivy index build write amplification
This PR teaches how to reduce write amplification in text index builds by carefully managing memory budgets and merge policies for in-memory and sealed index segments.
enhance: reduce Tantivy index build write amplification [2.6]
This PR teaches how to reduce write amplification in index building by tuning memory budgets and merge policies for different index build modes.
planner: optimize duplicate removal for common-handle batch point get
This PR demonstrates how to efficiently deduplicate and filter values in-place in a batch processing context, replacing repeated slice deletion with a more optimal approach and validating the results with targeted tests.
executor, util: fix hash join v2 null build key
This PR teaches how to correctly handle NULL values in hash join algorithms to prevent subtle bugs, including how to write targeted regression tests for join edge cases.
[MLIR] Fix control-flow sinking through nested regions
This PR demonstrates how to correctly implement control-flow sinking in the presence of nested regions, highlighting the importance of dominance and region ancestry checks in compiler transformations.
[mlir][Printer] Honor --mlir-elide-resource-strings-if-larger when serializing of large blobs
This PR teaches how to avoid unnecessary memory and CPU usage by precomputing output size and short-circuiting expensive serialization when a size limit is exceeded.
gh-154085: Avoid duplicating diff line values
This PR teaches how to avoid duplicating profiling sample counts in flamegraph diff calculations by carefully weighting self and inclusive samples, with thorough tests validating the correctness of the approach.
Go deep (senior) · 16
Fix lazy materialization OOB and a Merge LOGICAL_ERROR from unused text index virtual columns
This PR teaches how to maintain invariants between query plan steps by pruning unused virtual columns after DAG rewrites, preventing subtle header mismatches that can cause out-of-bounds errors and logical failures in query engines.
Add multiplicity-aware combine support and fix LIST state combination
This PR teaches how to correctly handle aggregate state combination with multiplicities in query optimizations, especially for list-backed aggregates, and demonstrates robust testing and plan stability practices.
gh-154701: prevent executor self-links in JIT cold exits
This PR teaches how to detect and fix subtle infinite loop bugs in a JIT compiler by preventing self-referential executor links during cold exits, illustrating advanced error handling in low-level optimization code.
Fix codegen of NotMask on x64
This PR teaches how to fix subtle code generation bugs in a JIT compiler for SIMD mask operations, including how to generalize bit-masking logic, optimize IR transformations, and add targeted regression tests.
planner: fix countAfterAccess for IndexJoin in Skyline Pruning Comparison (#70791)
This PR teaches how to accurately estimate row counts for index join candidates in a query planner by adjusting for join key NDV, ensuring fair comparison and optimal index selection during skyline pruning.
JIT/Interp: Remove `MAYBENULL` TypeHandle -> RuntimeType Helper uses
This PR teaches how to refactor low-level runtime helpers by replacing special-case helper functions with inlined logic and specialized opcodes, improving clarity and performance in a complex system.
planner: keep min/max row estimates aligned after correlated column split (#70793)
This PR demonstrates how to maintain consistent row estimate bounds for correlated index paths during query optimization to avoid incorrect pruning, including the reasoning and regression test coverage needed for robust planner changes.
planner: fix countAfterAccess for IndexJoin in Skyline Pruning Comparison
This PR teaches how to adjust row count estimation for index join selection in a query optimizer by accounting for join key NDV, ensuring fairer candidate comparison and demonstrating robust regression testing for plan choice correctness.
Fix wrong results with parallel_hash JOIN and read-in-order-through-join
This PR teaches how to reason about and enforce data stream order preservation through different join algorithms to ensure correctness of downstream query optimizations that rely on sorted input.
Fix Top-N window elimination for nullable ordering expressions
This PR teaches how to conservatively analyze SQL expression nullability to ensure correctness in query optimization, especially when rewriting window functions with potentially nullable ordering expressions.
[DAG] Add computeKnownBits(FREEZE(X)) handling
This PR teaches how to extend static analysis (known bits propagation) in a compiler's intermediate representation to correctly handle 'freeze' nodes, including subtle interactions with poison values and code generation consequences.
[RISCV] Attach VLMAX range attribute for vsetvli/vsetvlimax in InstCombine
This PR teaches how to compute and attach precise value range metadata to target-specific intrinsics, enabling generic analyses to reason about their results without target-specific knowledge.
Add intrinsics for integer minimum and maximum
Shows how to add efficient integer min/max intrinsics to a compiler backend to improve codegen and optimization.
Fix Wasm SCC profile weights for #133120
This PR demonstrates how to correctly update profile weights during control flow rewrites in a JIT compiler and how to add targeted regression tests for subtle codegen bugs.
[SelectionDAG] Preserve CTTZ_ELTS lane count during expansion
This PR teaches how to correctly preserve logical vector lane counts during target-specific legalization in a compiler backend, avoiding subtle bugs in vectorized intrinsic lowering.
[CodeGenPrepare] Failure to hoist bitcast to legal type causes register splitting
This PR demonstrates how to hoist bitcast instructions in LLVM IR to reduce register pressure and avoid register splitting, including careful handling of edge cases and legality checks.
[ 02 // MUST-READ PAPERS ]
Free to read, ranked by citations.
[ 03 // FREE VIDEOS & TALKS ]
Ranked by views.
other topics