Hasty Briefs - Daily Tech News Brief

Bilingual

Writing that changed how I think about programming languages
a year ago
- Andy Wingo's simple semi-space collector made Cheney/copying/compacting garbage collectors practical and understandable.
- CF Bolz-Tereick's 'Implementing a Toy Optimizer' introduced forwarding pointers for instruction rewrites, replacing find-and-replace methods.
- CF Bolz-Tereick's 'A Knownbits Abstract Domain for the Toy Optimizer, Correctly' used Z3 as a proof engine and verifier for Python code.
- Chris Fallin's 'Cranelift, Part 3: Correctness in Register Allocation' advocated proving correctness on a single input for meaningful crashes or correct allocations.
- Russ Cox's 'Regular Expression Matching: the Virtual Machine Approach' demystified regex engines and coroutines with a 50-line implementation.
- Andrej Karpathy's 'micrograd' provided a library-free neural network implementation, making machine learning more accessible.
- Fil Pizlo's 'How I implement SSA form' introduced an Identity tag for union-find, saving space and introducing Phi/Upsilon form and TBAA-style heap effects.
- Fil Pizlo's 'Speculation in JavaScriptCore' detailed JSC's optimizer workings and Fil's optimization philosophy.
- Chandler Carruth's 'Modernizing Compiler Design for Carbon Toolchain' explained aggressive compile-time budgets and per-layer compiler architecture.
- Allison Kaptur's 'A Python Interpreter Written in Python' clarified bytecode interpreters and CPython internals.
- Eli Bendersky's 'Parsing expressions by precedence climbing' offered an easier alternative to recursive descent parsers.
- Takashi Kokubun's 'Ruby JIT Challenge' showcased a novel approach to register allocation using a virtual stack of physical registers.
- Abdulaziz Ghuloum's 'An Incremental Approach to Compiler Construction' simplified compilers into single-pass, feature-by-feature implementations.
- Fernando Borretti's 'Lessons from Writing a Compiler' highlighted a stripey implementation strategy for compilers.
- The 'egg: Fast and extensible equality saturation' paper expanded optimizer thinking by generating all expression versions and selecting the best.
- Chris Fallin's 'Cranelift: Using E-Graphs for Verified, Cooperating Middle-End Optimizations' demonstrated e-graphs' practicality in production compilers.
- Phil Zucker's 'Acyclic Egraphs and Smart Constructors' explored acyclic egraphs, with insights deepening over time.
- Bob Nystrom's Reddit comment and Adrian Sampson's 'Flattening ASTs' discussed compact AST storage and parallel abstract interpretation possibilities.
Variadic Switch
a year ago
- The article discusses the challenge of generating a sequence of case labels followed by a statement in C++.
- It explores various strategies to optimize switch statements into jump tables, including dispatch tables, macros, recursive switches, and fold tricks.
- The article highlights the limitations of current C++ features and proposes potential improvements with C++26 expansion statements.
- Different compiler behaviors (GCC, Clang, MSVC) are analyzed regarding jump table generation and optimization.
- A generic visit implementation is discussed, including handling of void return types and move-only return types.
- The article concludes with a look at how C++26 expansion statements could simplify the implementation of a generic visit function.
The Scalar Select Anti-Pattern
a year ago
- The article discusses the 'Scalar Select Anti-Pattern' in stateful services with event loops.
- Event loops often need refactoring due to inefficiencies in handling multiple events.
- Three main event sources in an LSP server: file modifications, client requests, and compilation outputs.
- The 'scalar select' approach picks one event arbitrarily, leading to overhead when multiple events are ready.
- Optimizations include prioritization, selective backpressure, elimination, and coalescing of events.
- Prioritization suggests processing writes over reads over accepts.
- Selective backpressure allows ignoring certain requests while processing others.
- Elimination involves dropping redundant requests based on subsequent events.
- Coalescing combines multiple similar events into a single processing batch.
- The solution is to adopt a batched approach, processing all available events at once to improve efficiency under load.
- The 'batch_stream' function is introduced to wait for and process all available events, not just one.
A leap year check in three instructions
a year ago
- A fast leap year check using bit-twiddling and magic numbers is introduced.
- The standard leap year check involves modulo operations for 4, 100, and 400.
- Optimizations include replacing modulo operations with bit masking and multiplication tricks.
- A branchless version of the leap year check is presented for predictable performance.
- A brute-force approach using z3 solver finds optimal constants for a 32-bit fast leap year check.
- The fast method works correctly for years 0 to 102499 and is explained via bit manipulation.
- A 64-bit version extends the correct range up to year 5965232499.
- Benchmarks show the fast method is 3.8x faster for random inputs but slightly slower for predictable ones.
Push Ifs Up and Fors Down
a year ago
- Push Ifs Up: Move conditional checks (ifs) to the caller to centralize control flow, reduce redundant checks, and simplify functions.
- Benefits of Pushing Ifs Up: Fewer overall checks, easier identification of dead branches, and centralized complex logic in one place.
- Dissolving Enum Refactor: A pattern where pulling up conditions reveals redundant or triplicated logic.
- Push Fors Down: Operate on batches of objects for performance gains, amortizing startup costs, and enabling vectorized processing.
- Performance Benefits: Batch processing can significantly improve performance, especially in hot paths handling many entities.
- Expressiveness: Batch operations can also enhance code expressiveness, as seen in libraries like jQuery.
- Composition: Combining 'push ifs up' and 'push fors down' can optimize both control flow and data processing.
- Example: FFT-based polynomial multiplication shows how batch processing can outperform individual evaluations.
- TigerBeetle Architecture: Uses batch processing in the data plane to amortize decision-making costs in the control plane.
Fast Allocations in Ruby 3.5
a year ago
- Ruby 3.5 introduces significant speed improvements in object allocation, making it up to six times faster.
- Benchmarks compare positional and keyword parameters with and without YJIT, showing consistent speedups.
- Positional parameters see a 1.8x speedup without YJIT and 2.3x with YJIT, regardless of parameter count.
- Keyword parameters show increasing speedups with more parameters, up to 3x without YJIT and over 6.5x with YJIT.
- The optimization involves inlining the `Class#new` method, eliminating stack frames and parameter copies.
- Inlining improves inline cache hits and reduces overhead by avoiding conversions between Ruby and C calling conventions.
- A downside is a small backward incompatibility where the `Class#new` frame is missing in stack traces.
- Memory usage increases slightly due to more instructions at call sites, but the impact is minimal (0.5% growth in instruction sequence size).
Improving performance of original dav1d video decoder
a year ago
- Optimized memory organization in CPU cachelines by reducing structure sizes to 64 bytes or less.
- Manually aligned enums to strict values to fit into 1 byte and optimized space usage.
- Compressed 'int' in structures to 'uint16_t' (2 bytes) to reduce memory waste.
- Used 'pahole' to identify and optimize holes in structures, improving cache efficiency.
- Achieved performance improvements: ~3% for 1080p and ~1% for 4K.
- Reduced the size of 'Dav1dFrameContext' from 5648 bytes to 5384 bytes, saving 4 cachelines.
- Benchmarked using 'hyperfine' on old and new servers, showing consistent performance gains.
- Highlighted the importance of data alignment and structure optimization for 64-bit processors.
- Emphasized the practicality of optimizing existing C/C++ projects over rewriting in new languages like Rust.
Compiling a Neural Net to C for a 1,744× speedup
a year ago
- A neural network (NN) with logic gates as activation functions was trained to learn a 3×3 kernel function for Conway’s Game of Life.
- The NN was compiled to C, resulting in a 1,744× speedup in inference time.
- The project involved extracting and optimizing a learned logic circuit from the NN, reducing it to a 300-line single-threaded C program.
- Differentiable Logic Cellular Automata (DLCA) combines neural networks with cellular automata, replacing traditional kernel functions with learned NN models.
- Training the NN required careful initialization, including biasing gate weights towards pass-through gates to ensure gradient flow.
- The final C implementation uses bit-parallelism to process 64 cells simultaneously, significantly boosting performance.
- Benchmarks showed the C implementation achieving 24,400 fps compared to the Python/JAX implementation's 14 fps.
- Future directions include optimizing the circuit further with SIMD or GPU compute shaders and exploring larger circuits like fluid simulation.
TPDE: A Fast Adaptable Compiler Back-End Framework
a year ago
- TPDE is a fast adaptable compiler back-end framework designed for quick machine code generation.
- It avoids extra IR translation steps, reducing compilation latency significantly.
- TPDE performs compilation in a single pass, combining instruction selection, register allocation, and instruction encoding.
- The framework adapts to existing code representations in SSA form and uses an IR-specific adapter.
- Performance results show TPDE compiles LLVM-IR 8-24x faster than LLVM -O0 while maintaining run-time performance.
- Demonstrated benefits in JIT contexts like WebAssembly and database query compilation by avoiding extra IR translation.
Simpler Backoff
a year ago
- Exponential backoff with jitter is commonly used for service calls.
- Traditional approach involves calculating delays dynamically with potential for bugs.
- Simplified version uses a lookup table for delays, making it more readable and maintainable.
- Lookup table approach reduces variables and scope, simplifying reasoning about behavior.
- Edits to backoff schedule and attempts are safer and easier with the lookup table method.
'I happened to be sitting next to Bill Joy at UCB when he wrote the first "yes"'
a year ago
- The code snippet shows modifications to a FreeBSD utility, likely the 'yes' command.
- Changes include adding buffer handling for output optimization.
- The utility now supports custom strings passed as arguments, defaulting to 'y'.
- Buffer management is introduced to reduce system calls by batching writes.
- Capsicum security framework is utilized for sandboxing the utility.
Microsoft Trace: End-to-End Generative Optimization for AI Agents
a year ago
- Trace is a new AutoDiff-like tool for training AI systems end-to-end with general feedback.
- It generalizes back-propagation by capturing and propagating an AI system's execution trace.
- Implemented as a PyTorch-like Python library, Trace allows users to write Python code directly and optimize parts using Trace primitives.
- Supports various optimizers including OPRO, TextGrad, and OptoPrime (Trace's proposed algorithm).
- Trace can be installed via pip and requires Python >= 3.9.
- Features include computation graph visualization, LLM backend support (LiteLLM or AutoGen), and feedback-driven optimization.
- Trace has been applied in various domains like parallel programming, NLP prompt optimization, and robotic arm control.
- The project is open for contributions under Microsoft's Open Source Code of Conduct.
Low-Level Optimization with Zig
a year ago
- Optimization is crucial for performance, cost savings, and system simplicity.
- Low-level languages like Zig provide more intent and verbosity, aiding compiler optimizations.
- Zig's 'comptime' feature allows for compile-time code generation and optimization, enhancing performance.
- Zig's 'comptime' can generate optimized code for known compile-time values, improving runtime efficiency.
- Zig's approach to optimization and 'comptime' makes it easier to write performant and clean code.
FFS Optimizations with Dirhash
a year ago
- OpenBSD's filesystem subsystem is divided into VFS (Virtual File System), UFS (Unix File System), and FFS (Fast File System).
- VFS provides a unified interface to file systems, UFS organizes files in a Unix-like manner, and FFS handles disk storage with OpenBSD-specific optimizations.
- Optimizations in OpenBSD's filesystem are limited, with softdep no longer available since g2k23.
- dirhash is an in-memory hash table for large directories, improving file lookup performance from O(n) to O(1).
- The default dirhash cache size is 5MB, adjustable via sysctl (vfs.ffs.dirhash_maxmem).
- Increasing dirhash_maxmem can optimize performance, especially for systems with many files or large directories.
- A practical approach is to set a high value (e.g., 50MB), run 'find /' to populate the cache, and then adjust based on actual usage.
- Systems with ample RAM can benefit from larger dirhash cache sizes without significant overhead.
The Hashtable Packing Problem (2020)
a year ago
- The Hashtable Packing Problem is part of a project to optimize bitboard-based move generation in chess.
- The problem is proven to be strongly NP-complete, making optimal solutions impractical.
- Definitions include a Hashtable as a list of integers representing occupied and empty buckets.
- A Hashtable Packing involves arranging multiple hashtables in memory without overlapping occupied buckets.
- The problem is reduced to the 3-Partition Problem, which is strongly NP-complete.
- Magic Bitboards in chess involve optimizing hashtables for piece attacks, which is complex and intertwined.
- Due to NP-completeness, optimal solutions for Magic Bitboards are impractical, suggesting the use of heuristics.
Rethinking Losses for Diffusion Bridge Samplers
a year ago
- Diffusion bridges are deep-learning methods for sampling from unnormalized distributions.
- Log Variance (LV) loss outperforms reverse Kullback-Leibler (rKL) loss when using the reparametrization trick.
- For diffusion bridges or learned diffusion coefficients, LV loss does not maintain equivalence with rKL loss.
- rKL loss with the log-derivative trick (rKL-LD) avoids conceptual problems and outperforms LV loss.
- Experimental results show rKL-LD loss leads to better performance in diffusion bridges.
- rKL-LD requires less hyperparameter optimization and offers more stable training.
What I talk about when I talk about IRs
a year ago
- Compiler intermediate representations (IRs) should allow decisions based on local information.
- Control-flow constructs like loops and conditionals are decomposed into simpler comparisons and jumps in IRs.
- Explicit jumps and labels transform code into a control-flow graph (CFG), enabling more flexible optimizations.
- Basic blocks and extended basic blocks (EBBs) are key components in CFGs, with differing opinions on their merits.
- Abstract interpretation on graphs allows for advanced optimizations.
- Stack-based IRs use implicit shared state (the stack), while register-based IRs use explicit named inputs and outputs.
- Static single assignment (SSA) ensures each variable is defined once, simplifying analysis and optimization.
- Static single information (SSI) form refines SSA by encoding metadata about variables, enabling more precise analysis.
- Sea of nodes (SoN) IR design reifies both data and control dependencies, allowing for more flexible instruction ordering.
- Other related IR designs include value dependence graphs (VDG), value state dependence graphs (VSDG), and program dependence graphs (PDG).
Revisiting Knuth's "Premature Optimization" Paper
10 months ago
- Knuth's famous quote 'premature optimization is the root of all evil' is often misinterpreted.
- The original paper discusses the use of 'goto' statements and performance trade-offs in structured programming.
- Knuth emphasizes that small optimizations (e.g., loop unrolling) are worthwhile if they are in critical code sections.
- Benchmarking is essential to identify which parts of a program truly benefit from optimization.
- Modern compilers do not always optimize effectively, sometimes requiring manual intervention (e.g., assembly tweaks).
- Using well-optimized library functions (e.g., STL, fast hash tables) is often better than manual micro-optimizations.
- A 10% performance improvement can be significant, especially in frequently used library functions.
Nano-Vllm: Lightweight vLLM implementation built from scratch
10 months ago
- Lightweight vLLM implementation with fast offline inference comparable to vLLM.
- Readable codebase with clean implementation in ~1,200 lines of Python code.
- Includes optimization suite: prefix caching, Tensor Parallelism, Torch compilation, CUDA graph, etc.
- Install via pip: `pip install git+https://github.com/GeeeekExplorer/nano-vllm.git`.
- Option to fetch model weights manually using `huggingface-cli download`.
- API mirrors vLLM's interface with minor differences in `LLM.generate` method.
- Example usage provided in `example.py` and benchmark in `bench.py`.
- Tested on RTX 4070 Laptop (8GB) with Qwen3-0.6B model.
- Performance results show Nano-vLLM outperforming vLLM in throughput (1,434.13 vs. 1,361.84 tokens/s).
Modelling API rate limits as diophantine inequalities
10 months ago
- Understand the rate limit constraint of 10 requests per hour.
- Tasks have a retry pattern at minutes 0, 10, and 30 after start.
- Mathematically model the problem using Diophantine inequalities.
- Use integer linear programming to ensure no 60-minute window exceeds the rate limit.
- Implement a Go program to check if scheduling a new task violates constraints.
- Optimize the solution using a sliding window technique for efficiency.
- Highlight the intersection of software problems and mathematical solutions.

Hasty Briefsbeta

#optimization

Writing that changed how I think about programming languages

Variadic Switch

The Scalar Select Anti-Pattern

A leap year check in three instructions

Push Ifs Up and Fors Down

Fast Allocations in Ruby 3.5

Improving performance of original dav1d video decoder

Compiling a Neural Net to C for a 1,744× speedup

TPDE: A Fast Adaptable Compiler Back-End Framework

Simpler Backoff

'I happened to be sitting next to Bill Joy at UCB when he wrote the first "yes"'

Microsoft Trace: End-to-End Generative Optimization for AI Agents

Low-Level Optimization with Zig

FFS Optimizations with Dirhash

The Hashtable Packing Problem (2020)

Rethinking Losses for Diffusion Bridge Samplers

What I talk about when I talk about IRs

Revisiting Knuth's "Premature Optimization" Paper

Nano-Vllm: Lightweight vLLM implementation built from scratch

Modelling API rate limits as diophantine inequalities