# mhtirogla

> Low-level knowledge hub for building systems: algorithms, data structures, protocols and infrastructure. Each entry has an Overview (decision-level) and a Deep dive (code, constants, pitfalls). Raw markdown per entry at /raw/<slug>.md; everything in one file at /llms-full.txt; structured index at /index.json. MCP server: `mhtirogla mcp` (tools: search, get_entry, system_graph, list_systems, list).

## Machine learning
Model building blocks, data, classical ML, reinforcement learning and evaluation.
- [Loss functions](/raw/loss-functions.md) [Foundations · low]: The scalar a model minimizes: cross-entropy for classes and tokens, MSE or Huber for values, each with a stable form and simple gradient.
- [Weight initialization](/raw/weight-initialization.md) [Foundations · low]: Pick initial weight variance so activations and gradients keep their scale through depth; He for ReLU, Glorot for tanh, scaled-down residual outputs for transformers.
- [Normalization layers](/raw/normalization-layers.md) [Foundations · low]: Standardize activations per batch, token or group with a learned scale so deep nets train fast and stably; RMSNorm in LLMs, BatchNorm in convnets.
- [Regularization](/raw/regularization.md) [Foundations · low]: Techniques that trade training fit for generalization: weight decay, dropout, early stopping, label smoothing and data mixing, with the exact update rules and defaults.
- [Contrastive learning](/raw/contrastive-learning.md) [Foundations · medium]: Train an encoder so two views of the same thing score higher than every other pair in the batch; InfoNCE with a temperature, no labels needed.
- [Attention variants](/raw/attention-variants.md) [Modern layers · low]: Multi-head, multi-query, grouped-query, sliding-window and latent attention; same softmax(QKᵀ/√d)V core, different trade-offs between quality and KV-cache size.
- [Rotary position embedding (RoPE)](/raw/rotary-position-embedding.md) [Modern layers · low]: Encode position by rotating pairs of query and key dimensions by position-dependent angles, so attention scores depend only on relative distance; the LLM default.
- [Mixture of experts (MoE)](/raw/mixture-of-experts.md) [Modern layers · low]: Replace one FFN with many expert FFNs and a router sending each token to its top-k; parameters scale with E, per-token compute with k.
- [Embeddings](/raw/embeddings.md) [Modern layers · low]: A learned table mapping discrete ids to dense vectors: gather forward, sparse scatter-add backward, row-wise optimizers to keep huge tables cheap.
- [Byte-pair encoding (BPE) tokenization](/raw/bpe-tokenization.md) [Data · low]: Learn a subword vocabulary by repeatedly merging the most frequent adjacent pair; byte-level BPE encodes any input losslessly with 32k-200k tokens.
- [Data loading pipelines](/raw/data-loading-pipelines.md) [Data · medium]: Turn files on disk into shuffled, sharded, resumable GPU batches fast enough that the accelerator never waits.
- [Near-duplicate detection with MinHash LSH](/raw/near-duplicate-detection-minhash.md) [Data · medium]: Estimate set Jaccard similarity from k min-hashes and find similar pairs with banded LSH buckets; the standard dedup for web crawls, training corpora and sequence collections.
- [Data augmentation](/raw/data-augmentation.md) [Data · low]: Generate label-preserving variants of each training example on the fly to enlarge the effective dataset and bake in invariances.
- [Negative sampling](/raw/negative-sampling.md) [Data · low]: Train by contrasting each observed positive with a few sampled negatives instead of normalising over every candidate; the choice of sampler decides bias and quality.
- [Feature store](/raw/feature-store.md) [Data · medium]: One definition per feature feeds a history store for training and a latest-value store for serving, so training and inference see the same values as of the same moment.
- [Linear and logistic regression](/raw/linear-and-logistic-regression.md) [Classical ML · low]: Fit a weighted sum of features to a number (least squares) or a probability (logistic); the baseline every model must beat.
- [Gradient-boosted decision trees (GBDT)](/raw/gradient-boosted-trees.md) [Classical ML · medium]: Add small regression trees one at a time, each fitted to the loss gradient; histogram splits over 256 bins make it the strongest tabular default.
- [k-means clustering](/raw/k-means.md) [Classical ML · low]: Partition points into k clusters by alternating nearest-centroid assignment and centroid averaging; k-means++ seeding makes it dependable.
- [PCA and SVD](/raw/pca-svd.md) [Classical ML · low]: Find orthogonal directions of maximum variance by an SVD of the centred data; randomized SVD gets the top k components in a few passes.
- [Naive Bayes classifier](/raw/naive-bayes-classifier.md) [Classical ML · low]: Count how often each feature occurs per class and score a new item by summed log-likelihoods; trains in one pass, updates and merges by adding counts.
- [Isolation forest](/raw/isolation-forest.md) [Classical ML · low]: Score each record by how few random axis-aligned splits it takes to isolate it in a small forest of random trees; anomalies are few and different, so they isolate fast.
- [Density-based clustering (DBSCAN)](/raw/dbscan-clustering.md) [Classical ML · medium]: Group points that are packed densely, label the rest as noise: no k, arbitrary shapes, two parameters (eps, minPts), cost set by the neighbour index.
- [Generalized linear models (GLMs)](/raw/generalized-linear-models.md) [Classical ML · medium]: Linear model for counts, rates, positive amounts and proportions: a linear score pushed through a link, fitted by iteratively reweighted least squares.
- [Feature hashing (the hashing trick)](/raw/feature-hashing.md) [Classical ML · low]: Hash each feature name to an index in a fixed-size vector, with a second hash for the sign, so no vocabulary is needed and memory is fixed.
- [Q-learning and DQN](/raw/q-learning-dqn.md) [Reinforcement learning · medium]: Learn action values by bootstrapping toward r + γ·max Q(s′, ·); DQN adds a replay buffer, a frozen target network and Huber loss.
- [Policy gradient and PPO](/raw/policy-gradient-ppo.md) [Reinforcement learning · medium]: Raise the log-probability of actions in proportion to their advantage; PPO clips the probability ratio so several epochs on one rollout stay safe.
- [AlphaZero self-play](/raw/alphazero-self-play.md) [Reinforcement learning · medium]: A policy-value net guides PUCT search; search visit counts and game results become its training targets, so it learns from its own improved play.
- [Multi-armed bandits](/raw/multi-armed-bandits.md) [Reinforcement learning · medium]: Choose among K options repeatedly while learning their payoffs: epsilon-greedy, UCB1 and Thompson sampling keep total regret low where a fixed split or a fixed exploration rate pays forever.
- [Evaluation metrics](/raw/evaluation-metrics.md) [Evaluation · low]: Precision, recall, ROC AUC, average precision, log loss, NDCG and pass@k computed correctly, plus paired confidence intervals for comparing models.
- [Calibration](/raw/calibration.md) [Evaluation · low]: Make predicted probabilities match observed frequencies: measure with ECE, fix post hoc with temperature, Platt or isotonic scaling on held-out data.
- [LLM-as-judge](/raw/llm-as-judge.md) [Evaluation · medium]: Grade open-ended outputs with a language model under a rubric, then correct its known biases by order swapping, voting and calibration against human labels.
- [Two-tower retrieval](/raw/two-tower-retrieval.md) [Recommendation & ranking · medium]: Two separate encoders map users/queries and items into one vector space; item vectors are precomputed and searched by nearest neighbour, so recall over millions costs one small forward pass.
- [Learning to rank](/raw/learning-to-rank.md) [Recommendation & ranking · medium]: Train a scorer on query-grouped data so that the order it induces maximizes NDCG; LambdaMART (boosted trees with NDCG-weighted pair gradients) is the production default.
- [Matrix factorization for collaborative filtering](/raw/collaborative-filtering-matrix-factorization.md) [Recommendation & ranking · medium]: Learn a short latent vector per row and per column from the observed cells only; a missing cell is predicted by the dot product of its two vectors.
- [Deep ranking models for recommendation](/raw/deep-recommendation-models.md) [Recommendation & ranking · medium]: Embedding tables plus a feature-interaction net predict several feedback signals per candidate; a weighted sum of them is the ranking score.
- [Click-probability prediction (CTR models)](/raw/ctr-prediction-models.md) [Recommendation & ranking · medium]: Learn p(action | user, item, context) from hashed categorical features with interaction terms (FM, Wide & Deep, DCN, DLRM), then keep it calibrated, since downstream multiplies it.
- [Object detection](/raw/object-detection.md) [Vision models · medium]: A network turns an image into scored, classified boxes in one pass; anchor-based, anchor-free and set-prediction heads differ in how they assign labels and remove duplicates.
- [Non-maximum suppression](/raw/non-maximum-suppression.md) [Vision models · low]: Keep the best-scoring candidate in each neighbourhood and drop the rest; greedy NMS, Soft-NMS and 1-D peak picking share one loop.
- [Multi-object tracking](/raw/multi-object-tracking.md) [Vision models · medium]: Turn per-frame detections (camera boxes or radar plots) into persistent IDs by predicting each track, gating, assigning and managing track births and deaths.
- [Optical character recognition (text recognition)](/raw/ocr-text-recognition.md) [Document understanding · medium]: Find text lines in an image, read each crop with a CTC or attention model, then correct with a lexicon and score confidence for review routing.
- [Document image preprocessing](/raw/document-image-preprocessing.md) [Document understanding · low]: Turn a scan or phone photo into an upright, evenly lit, binarised or normalised grey page so layout analysis and OCR read it reliably.
- [PDF text extraction](/raw/pdf-text-extraction.md) [Document understanding · low]: Rebuild words, lines, columns and reading order from the glyph positions a born-digital PDF stores, and route pages without usable text to OCR.
- [HTML main-text extraction](/raw/html-text-extraction.md) [Document understanding · medium]: Decode bytes, tolerate broken markup, drop non-content nodes and score text blocks by length and link density to keep the main run, with headings, metadata and offsets for citation.
- [Text chunking](/raw/text-chunking.md) [Document understanding · low]: Cut documents into token-bounded pieces along structure boundaries, keeping offsets and section paths, so each piece embeds well and can be cited.
- [Named entity recognition](/raw/named-entity-recognition.md) [Language processing · medium]: Find the character spans of entities in text and give each a type, by labelling every token and decoding a valid label sequence.
- [Entity linking](/raw/entity-linking.md) [Language processing · medium]: Map each mention to a knowledge-base id, or to NIL, by generating candidates from an alias table, scoring them on prior and context, and thresholding.
- [Text classification](/raw/text-classification.md) [Language processing · medium]: Assign one or more labels to a text; climb a ladder from regexes to linear models on n-grams, embeddings, fine-tuned encoders and LLM prompts, only as far as the data and budget demand.
- [Language identification](/raw/language-identification.md) [Language processing · low]: Score a text's character n-grams against per-language statistics, after a cheap script check, and return an ISO 639 code with a confidence or "und".
- [Text normalization](/raw/text-normalization.md) [Language processing · low]: Rewrite messy text into one canonical form for matchers and models, or into spoken words for speech output (and back), keeping a map to the original offsets.
- [Template-based text generation](/raw/template-text-generation.md) [Language processing · low]: Realise facts as sentences by filling slots in alternative templates, with agreement, referring expressions and seeded variation; every word traces to data or a template.
- [Intent classification and slot filling](/raw/intent-classification-slot-filling.md) [Language processing · medium]: Turn one utterance into an intent label and typed slot values with a joint model: a sentence-level classifier plus a token-level BIO tagger on a shared encoder.
- [Dialogue state tracking](/raw/dialogue-state-tracking.md) [Language processing · medium]: Keep a structured belief of the user's goal (slot → value, plus requests) and update it every turn from NLU output, the old state and the last system action.
- [Voice activity detection](/raw/voice-activity-detection.md) [Speech · low]: Per-frame speech/non-speech decision with smoothing, from an energy threshold over a tracked noise floor up to small neural nets.
- [RNN transducer (RNN-T)](/raw/rnn-transducer.md) [Speech · medium]: Streaming sequence model that sums all monotone alignments in a frame-by-label lattice and conditions each label on earlier ones.
- [Connectionist temporal classification (CTC) loss](/raw/ctc-loss.md) [Speech · low]: Alignment-free sequence loss that sums the probability of every frame-to-label alignment with a blank symbol, using a dynamic program.

## Neural network training & inference
Autodiff, optimizers, numerics, GPU kernels, multi-GPU parallelism and fast inference.
- [Transformer block](/raw/transformer-architecture.md) [Architectures · low]: The decoder-only pre-norm block (attention plus MLP on a residual stream) behind every modern LLM, with exact shapes, parameter, FLOP and KV-cache counts.
- [Convolutional networks](/raw/convolutional-networks.md) [Architectures · low]: Layers that slide a small shared kernel over a grid, giving translation equivariance and few parameters; still the most compute-efficient choice for many vision tasks.
- [Diffusion models](/raw/diffusion-models.md) [Architectures · low]: Train a network to undo Gaussian noise at every noise level, then generate by integrating from pure noise to data; the standard for images, video and audio.
- [Reverse-mode automatic differentiation](/raw/reverse-mode-autodiff.md) [Automatic differentiation · low]: Record the forward computation on a tape, then sweep it backwards once to get the gradient of a scalar loss for all inputs.
- [SGD with momentum](/raw/sgd-momentum.md) [Optimizers & schedules · low]: Gradient descent plus a decaying velocity buffer that averages minibatch noise and speeds up progress along shallow, consistent directions.
- [AdamW](/raw/adamw.md) [Optimizers & schedules · low]: Adam's per-parameter adaptive steps with weight decay applied directly to the weights; the default optimizer for transformers and LLM pretraining.
- [Learning-rate warmup and cosine decay](/raw/learning-rate-warmup-cosine.md) [Optimizers & schedules · low]: Ramp the learning rate up linearly for the first ~1% of steps, then decay it along a half cosine to ~10% of peak.
- [Mixed-precision training](/raw/mixed-precision-training.md) [Numerics & memory · low]: Run matmuls in bf16/fp16/fp8 on tensor cores while keeping master weights, optimizer state and reductions in fp32; about 2x speed, half the activation memory.
- [Gradient checkpointing](/raw/gradient-checkpointing.md) [Numerics & memory · low]: Save only some activations in the forward pass and recompute the rest during backward, trading about 33% extra compute for O(√n) activation memory.
- [Tiled matrix multiplication](/raw/tiled-matmul.md) [GPU kernels · low]: Block GEMM into tiles held in shared memory and registers, so each byte loaded from DRAM feeds many FMAs; the core of fast GEMM.
- [FlashAttention](/raw/flash-attention.md) [GPU kernels · low]: Exact attention computed tile by tile in on-chip SRAM with online softmax, so the N×N score matrix never touches HBM; 2-4x faster, O(N) memory.
- [Kernel fusion](/raw/kernel-fusion.md) [GPU kernels · low]: Merge chains of memory-bound GPU ops into one kernel, so intermediates stay in registers instead of round-tripping through HBM.
- [GPU compute shaders](/raw/gpu-compute-shaders.md) [GPU kernels · low]: The vendor-neutral GPU launch model of Metal, Vulkan and WebGPU: a grid of workgroups, shared memory, barriers and subgroups, driven by recorded command buffers.
- [Ring all-reduce](/raw/ring-allreduce.md) [Multi-GPU parallelism · low]: Sum a buffer across N workers via reduce-scatter then all-gather around a ring; each link carries 2(N−1)/N of the buffer, which is bandwidth-optimal.
- [ZeRO and FSDP sharding](/raw/zero-fsdp-sharding.md) [Multi-GPU parallelism · low]: Data parallelism that shards optimizer state, gradients and weights across ranks and gathers weights just in time; per-GPU model memory drops from 16Ψ to 16Ψ/N.
- [Tensor parallelism](/raw/tensor-parallelism.md) [Multi-GPU parallelism · low]: Split each layer's weight matrices across GPUs (Megatron-style column then row splits) so one layer's math runs on t devices with one all-reduce per block.
- [Pipeline parallelism](/raw/pipeline-parallelism.md) [Multi-GPU parallelism · low]: Split the model's layers into stages on different GPUs and stream micro-batches through them; 1F1B scheduling bounds activation memory, the bubble costs (p−1)/m.
- [Collective communication](/raw/collective-communication.md) [Multi-GPU parallelism · low]: The family of group exchanges (broadcast, reduce, all-gather, reduce-scatter, all-to-all) and the latency-plus-bytes cost model that picks ring, tree or direct algorithms by message size and topology.
- [Weight quantization](/raw/weight-quantization.md) [Inference · low]: Store weights as 8/4-bit integers with per-group scales; decode is memory-bound, so 4-bit weights give about 3-4x tokens/s and fit 4x larger models.
- [Paged KV cache](/raw/paged-kv-cache.md) [Inference · low]: Store each sequence's attention keys/values in fixed-size blocks mapped through a block table, like virtual memory pages; near-zero fragmentation and copy-on-write sharing.
- [Continuous batching](/raw/continuous-batching.md) [Inference · low]: Schedule LLM inference per iteration, not per request; finished sequences leave and new ones join the running batch every step, which keeps the GPU full.
- [Speculative decoding](/raw/speculative-decoding.md) [Inference · low]: A cheap draft proposes γ tokens, the big model verifies them in one pass, and rejection sampling keeps the target's exact distribution at 2-3x speed.
- [Dynamic batching](/raw/dynamic-batching.md) [Inference · medium]: Queue independent requests and dispatch them as one batch when it is full or the oldest has waited max_delay; bounded extra latency buys throughput.
- [LLM pretraining](/raw/llm-pretraining.md) [Training recipes · medium]: How a decoder-only LLM is pretrained in practice: data mix, tokens per parameter, batch and LR schedules, bf16, 3D/4D parallelism, checkpoints and loss-spike handling.
- [LLM fine-tuning](/raw/llm-fine-tuning.md) [Training recipes · medium]: Adapting a pretrained LLM with supervised fine-tuning, LoRA/QLoRA adapters and preference optimization (DPO), and evaluating that it improved without forgetting.
- [Image model training](/raw/image-model-training.md) [Training recipes · medium]: Proven setups for training image classifiers and diffusion models: optimizers and LRs, augmentation, label smoothing, EMA, resolution schedules and aspect buckets.
- [Knowledge distillation](/raw/knowledge-distillation.md) [Training recipes · medium]: Train a small student to match a large teacher's softened outputs (plus the hard labels) so it keeps most of the teacher's accuracy at a fraction of the cost.
- [Token sampling](/raw/sampling-strategies.md) [Decoding & sampling · low]: Turn a vector of scores into one chosen item with temperature, top-k, top-p, min-p, repetition penalties and a seed.
- [Beam search decoding](/raw/beam-search-decoding.md) [Decoding & sampling · medium]: Keep the k best partial sequences by summed log-probability at every step, set finished ones aside, and return the best (n-best) by a length-normalised score.

## Agentic AI
The parts of an LLM agent: tool protocols, the agent loop, context and memory, multi-agent orchestration, sandboxing and evaluation.
- [Tool calling](/raw/tool-calling.md) [Tool protocols · low]: The model emits a structured call (id, name, JSON arguments) instead of prose; your code validates, runs it and returns a result tagged with the same id.
- [Constrained decoding](/raw/constrained-decoding.md) [Tool protocols · low]: Force LLM output to match a regex, JSON schema or grammar by masking, at every step, the tokens that would leave the language.
- [Context window management](/raw/context-window-management.md) [The agent loop · low]: Keep an agent's growing history inside the model's window by truncating, clearing and summarizing old turns in a cheap-to-lossy ladder, at turn boundaries.
- [Prompt caching](/raw/prompt-caching.md) [The agent loop · low]: Reuse the attention keys/values of a repeated prompt prefix, so an agent's growing context is prefilled once and later turns pay only for the new tokens.
- [Tool retrieval (selecting tools for a request)](/raw/tool-retrieval.md) [The agent loop · medium]: Index tool descriptions, filter by the caller's permissions, rank against the request and put only the top few definitions in context, in a stable order.
- [Human-in-the-loop approval](/raw/human-in-the-loop-approval.md) [The agent loop · medium]: Classify each proposed action as auto, ask or deny; park asks as durable pending records a human approves, edits or rejects, executing once, with timeouts that deny.
- [Memory consolidation](/raw/memory-consolidation.md) [Memory and retrieval · medium]: Periodically merge near-duplicate memories, resolve contradictions, decay the unused and cap the store, so an agent's long-term memory stays small, current and cheap to search.
- [Model routing and cascades](/raw/llm-routing.md) [Multi-agent orchestration · medium]: Send each request to the cheapest model that will answer it well enough, by rules, a learned router, or a cascade that escalates from small to large on low confidence.
- [Prompt injection defense](/raw/prompt-injection-defense.md) [Safety and operations · medium]: Treat every untrusted string as data, track where values came from, and make tool calls and rendered output depend on provenance, not on what the model says.

## Statistics & experimentation
Hypothesis tests, A/B experiments, rating and label models, anomaly detection and forecasting.
- [Hypothesis testing](/raw/hypothesis-testing.md) [Tests & intervals · medium]: Pick a test statistic, compare it to its distribution under "no effect", read off a p-value, and control error rates across one test or many.
- [Bayesian rate estimation](/raw/bayesian-rate-estimation.md) [Tests & intervals · low]: Estimate a conversion or event rate from few observations with a Beta-Binomial or Gamma-Poisson update: two counters, an honest interval, and P(B beats A) directly.
- [Robust statistics](/raw/robust-statistics.md) [Tests & intervals · low]: Location and scale estimates (median, MAD, trimmed mean, Huber M-estimator) that stay correct when a minority of the data is garbage.
- [A/B testing (online controlled experiments)](/raw/ab-testing.md) [Online experiments · medium]: Randomly split units into arms by a salted hash, log exposure, compare metrics with a confidence interval, and guard the result with sample-ratio, guardrail and peeking checks.
- [CUPED (variance reduction with pre-experiment covariates)](/raw/cuped-variance-reduction.md) [Online experiments · low]: Subtract the part of each unit's outcome that a pre-experiment covariate predicts; the effect estimate stays unbiased and its variance shrinks by 1 - rho^2.
- [Experiment layering (overlapping experiments)](/raw/experiment-layering.md) [Online experiments · low]: Partition the tunable parameters into layers, hash each unit with a per-layer salt so layers are independent, and give experiments inside a layer disjoint bucket ranges.
- [Sequential probability ratio test](/raw/sequential-probability-ratio-test.md) [Online experiments · medium]: Add up the log-likelihood ratio per observation and stop when it crosses a fixed bound; the least data of any test with the same error rates (for two point hypotheses).
- [Bayesian average rating](/raw/bayesian-average-rating.md) [Ratings, labels & latent models · low]: Score = (C·m + sum of ratings)/(C + n): the posterior mean under a prior worth C ratings, so items with few ratings sit near the global mean.
- [Item response theory](/raw/item-response-theory.md) [Ratings, labels & latent models · low]: Answer probability is a logistic curve of ability minus item difficulty (1PL), with item slope (2PL) and a guessing floor (3PL); fit items by marginal ML, score people, measure precision by information.
- [Time-series anomaly detection](/raw/time-series-anomaly-detection.md) [Anomaly & change detection · medium]: Predict the expected value from a seasonal baseline, scale the residual by a robust spread (MAD), threshold at a chosen false-alarm rate, then merge flags into incidents.
- [Control charts (Shewhart, CUSUM, EWMA)](/raw/statistical-process-control.md) [Anomaly & change detection · medium]: Estimate normal behaviour from healthy data, then signal when values leave limits (Shewhart) or small deviations add up (CUSUM, EWMA); tune by average run length.
- [Time-series forecasting (baselines, model families, backtests)](/raw/time-series-forecasting.md) [Forecasting · medium]: The end-to-end recipe: fix horizon and uncertainty, beat naive baselines, choose a model family, and validate with rolling-origin backtests and scale-free metrics.
- [Exponential smoothing (ETS, Holt-Winters)](/raw/exponential-smoothing.md) [Forecasting · low]: Forecast by keeping a few running states (level, trend, seasonal) updated by a fraction of each forecast error; O(1) memory per series and a strong baseline.
- [STL decomposition (seasonal-trend with loess)](/raw/stl-decomposition.md) [Forecasting · low]: Split a series into trend, seasonal and remainder with iterated loess smoothing; the seasonal shape may drift and robust weights keep outliers out of it.
- [Time-series cross-validation (rolling origin)](/raw/time-series-cross-validation.md) [Forecasting · low]: Estimate forecast error by repeatedly training on the past and testing on the next h steps, moving the origin forward; never trains on the future.

## Networking
Transport protocols, kernel I/O paths and load balancing.
- [TCP CUBIC](/raw/tcp-cubic.md) [Transport & congestion control · low]: Loss-based TCP congestion control whose window grows as a cubic function of time since the last loss; the default on Linux, Windows and macOS.
- [BBR congestion control](/raw/bbr-congestion-control.md) [Transport & congestion control · low]: Model-based congestion control that paces at the measured bottleneck bandwidth and caps inflight near one BDP, instead of reacting to loss.
- [QUIC](/raw/quic.md) [Transport & congestion control · medium]: Encrypted, multiplexed transport over UDP with 1-RTT setup, independent streams and connection migration; the transport of HTTP/3.
- [epoll event loop](/raw/epoll-event-loop.md) [Server I/O · low]: One thread waits on thousands of non-blocking sockets with epoll_wait and handles only ready ones; the core of nginx, Redis and tokio.
- [io_uring](/raw/io-uring.md) [Server I/O · low]: Linux async I/O through two shared-memory rings (submissions in, completions out), batching or eliminating syscalls for sockets and files alike.
- [Zero-copy I/O](/raw/zero-copy-io.md) [Server I/O · low]: Move bytes between files, sockets and NICs by passing page references instead of copying through user space: sendfile, splice, MSG_ZEROCOPY, kTLS.
- [Kernel-bypass networking](/raw/kernel-bypass-networking.md) [Server I/O · low]: User space (DPDK, AF_XDP) or an in-driver eBPF hook (XDP) handles packets straight from NIC rings, skipping sockets, for 10-40 Mpps per core.
- [Length-prefix framing](/raw/length-prefix-framing.md) [Framing & serialization · low]: Split a byte stream (TCP, TLS, pipes) into messages by writing each message's length before it; O(1) boundary detection with no escaping.
- [WebSockets](/raw/websockets.md) [Framing & serialization · low]: Full-duplex message framing over one upgraded HTTP connection; the standard way to push real-time data to browsers.
- [Zero-copy serialization](/raw/zero-copy-serialization.md) [Framing & serialization · low]: Wire formats laid out like in-memory structs (FlatBuffers, Cap'n Proto, SBE, rkyv) so readers access fields in place with no decode pass or allocation.
- [Maglev hashing](/raw/maglev-hashing.md) [Load balancing · low]: Consistent hashing into a fixed prime-size lookup table filled by per-backend permutations; O(1) lookups, near-perfect balance, little disruption on backend changes.
- [Power of two choices](/raw/power-of-two-choices.md) [Load balancing · low]: Pick two random backends and send to the less loaded one; exponentially better balance than random, with no global state and no herding.
- [Anycast](/raw/anycast.md) [Load balancing · low]: Announce one IP prefix from many sites over BGP; routing sends each client to its preferred site, and a failed site leaves by withdrawing the route.
- [Reverse proxy](/raw/reverse-proxy.md) [Load balancing · medium]: A server-side intermediary that terminates client connections and forwards each request to one of a pool of upstream servers, with routing, health checks, timeouts and safe retries.
- [HTTP/1.1 message parsing](/raw/http-1-1-parsing.md) [HTTP & RPC · low]: Parse HTTP/1.1 requests and responses incrementally from a byte stream: RFC 9112 body-length rules, chunked decoding and the strictness that stops request smuggling.
- [HTTP/2](/raw/http-2.md) [HTTP & RPC · low]: Binary multiplexed framing for HTTP over one TCP connection: streams, per-stream and per-connection credit windows, HPACK header compression and the limits that contain abuse.
- [HTTP caching semantics](/raw/http-caching-semantics.md) [HTTP & RPC · low]: The rules (RFC 9111) that decide whether a stored response is still fresh, and how a cheap conditional request revalidates it when it is not.
- [HTTP range requests](/raw/http-range-requests.md) [HTTP & RPC · low]: Ask for byte offsets with Range and get a 206 slice back; the standard way to resume, seek and read big remote files piecewise.
- [Server-sent events](/raw/server-sent-events.md) [HTTP & RPC · low]: One long-lived HTTP response carries text events one way; each event may carry an id, so a reconnecting client names its last one and the server resumes.
- [Long polling](/raw/long-polling.md) [HTTP & RPC · low]: The client asks "anything after cursor X?"; the server holds the request until there is news or a timeout, and the client immediately asks again.
- [Resumable uploads](/raw/resumable-uploads.md) [HTTP & RPC · low]: Open an upload session, send the body in offset-addressed chunks, and after any failure ask the server how much it committed and continue from there.
- [Webhook delivery](/raw/webhook-delivery.md) [HTTP & RPC · medium]: Reliable server-to-server HTTP callbacks: signed POSTs, 2xx-means-done, retries over days with jitter, endpoint disabling, SSRF guards and idempotent receivers.
- [DNS message format and client lookups](/raw/dns-protocol.md) [DNS & naming · low]: Binary query/response format of DNS (RFC 1035) and how a stub client uses it: record types, name compression, UDP/TCP/EDNS sizes, TTL caching.
- [Public Suffix List](/raw/public-suffix-list.md) [DNS & naming · low]: Find the registrable domain (eTLD+1) of a host name by matching the longest rule in a community-maintained list of shared suffixes.
- [IP multicast](/raw/ip-multicast.md) [Routing & forwarding · low]: Send each datagram once to a class D group address; the network copies it to every joined receiver, and sequence numbers let receivers find loss.
- [SPF, DKIM and DMARC sender authentication](/raw/dkim-spf-dmarc.md) [Messaging & email protocols · low]: SPF authorizes sending IPs, DKIM signs the message, DMARC requires either to match the visible From domain and says what to do on failure.
- [Mobile push delivery](/raw/mobile-push-delivery.md) [Messaging & email protocols · medium]: Sending notifications through APNs and FCM: HTTP/2 requests, token hygiene, collapse keys, TTL and priority, and the retry rules that keep you un-throttled.

## Compression
Entropy coding, LZ coding, transforms and integer/float codecs.
- [Huffman coding](/raw/huffman-coding.md) [Entropy coding · low]: Optimal prefix code with whole-bit codeword lengths; table-driven decoding at about one symbol per few cycles, the entropy stage of DEFLATE, JPEG and zstd literals.
- [Arithmetic coding](/raw/arithmetic-coding.md) [Entropy coding · low]: Encodes a whole message as one number in [0,1), spending fractional bits per symbol; pairs with adaptive context models for the best ratios.
- [Asymmetric numeral systems (ANS)](/raw/asymmetric-numeral-systems.md) [Entropy coding · low]: Entropy coder that packs fractional bits into a single integer state; arithmetic-coding ratio at Huffman-like speed, the entropy stage of zstd and LZFSE.
- [LZ77](/raw/lz77.md) [LZ / dictionary coding · low]: Replace repeated byte strings with (distance, length) back-references into a sliding window; the parsing stage of gzip, LZ4, zstd, Brotli and xz.
- [LZ4](/raw/lz4.md) [LZ / dictionary coding · low]: Byte-aligned LZ77 with no entropy stage; compresses at hundreds of MB/s and decompresses at several GB/s per core, for when speed beats ratio.
- [Zstandard (zstd)](/raw/zstd.md) [LZ / dictionary coding · low]: LZ77 plus Huffman and FSE entropy coding, with levels from LZ4-like speed to xz-like ratio, all decoding at about 1-2 GB/s.
- [Dictionary compression](/raw/dictionary-compression.md) [LZ / dictionary coding · low]: Prime the compressor with shared, pre-trained content so small messages can reference it; often 2-5x better ratio on sub-KB records.
- [Burrows-Wheeler transform (BWT)](/raw/burrows-wheeler-transform.md) [Transforms · low]: Reversible permutation that sorts every character by the context following it, clustering equal bytes into runs; the core of bzip2 and of FM-index text search.
- [Delta encoding](/raw/delta-encoding.md) [Transforms · low]: Store differences between consecutive values instead of the values, turning sorted IDs, timestamps and counters into small numbers that pack into few bits.
- [Varint (LEB128)](/raw/varint-leb128.md) [Integer codecs · low]: Variable-length integers in 7-bit groups with a continuation bit; small numbers take 1 byte, the wire format of Protobuf, WebAssembly and DWARF.
- [Bit packing and PFOR](/raw/bit-packing-pfor.md) [Integer codecs · low]: Store blocks of integers with exactly b bits each and patch rare outliers separately (PFOR); the fastest integer codec family, billions of values per second.
- [Stream VByte](/raw/stream-vbyte.md) [Integer codecs · low]: Integer codec that keeps 2-bit lengths in a separate control stream, so one table-driven SIMD shuffle decodes 4 integers without branches.
- [Roaring bitmaps](/raw/roaring-bitmaps.md) [Integer codecs · low]: Compressed set of 32-bit integers in 64K-value chunks, each a sorted array, bitmap or run list; fast intersections, the standard for bitmap indexes.
- [Gorilla XOR compression](/raw/gorilla-xor-compression.md) [Float & time-series codecs · low]: Time-series codec: delta-of-delta timestamps plus XOR of consecutive float bit patterns, storing only changed bits; about 1.4 bytes per point.

## Databases & storage
Indexes, durability, transactions, buffer management and query execution.
- [B+ tree](/raw/b-plus-tree.md) [Indexes · low]: Balanced high-fanout search tree with all values in linked leaves; the default on-disk index for point lookups and range scans.
- [LSM-tree](/raw/lsm-tree.md) [Indexes · medium]: Buffer writes in memory, flush them as immutable sorted files and merge in the background; turns random writes into sequential I/O.
- [Inverted index](/raw/inverted-index.md) [Indexes · medium]: Map each term to a sorted, compressed list of the documents containing it; the core of full-text search and other fast set queries.
- [LSM compaction](/raw/lsm-compaction.md) [Indexes · medium]: Compaction policies (leveled, tiered, time-window, FIFO) decide which sorted files to merge and when, trading write, read and space amplification and purging tombstones.
- [Index-free adjacency](/raw/index-free-adjacency.md) [Indexes · low]: Store each node's edges as direct references to neighbouring records, so a hop costs O(degree) pointer reads instead of an index search; know when plain tables or CSR beat it.
- [Write-ahead log](/raw/write-ahead-log.md) [Durability & recovery · low]: Append each change to a checksummed sequential log and fsync it before touching data pages; the basis of crash durability in nearly every database.
- [ARIES recovery](/raw/aries-recovery.md) [Durability & recovery · medium]: Three-pass crash recovery (analysis, redo, undo) for steal/no-force buffer pools; repeats history, then rolls back losers with compensation log records.
- [Group commit](/raw/group-commit.md) [Durability & recovery · low]: Let concurrent committers share one log write and fsync; throughput grows with concurrency while each commit still waits at most about two fsyncs.
- [Point-in-time recovery](/raw/point-in-time-recovery.md) [Durability & recovery · medium]: Periodic base backups plus a continuously archived change log let you rebuild the state as of any instant, then branch from there.
- [Log-structured storage](/raw/log-structured-storage.md) [Durability & recovery · medium]: Make the log the store: append every write, point an index at the newest copy, reclaim space by copying live records forward.
- [MVCC](/raw/mvcc.md) [Transactions & concurrency control · medium]: Keep timestamped versions of each row so readers see a consistent snapshot without blocking writers; the default concurrency control in modern databases.
- [Two-phase locking](/raw/two-phase-locking.md) [Transactions & concurrency control · low]: Transactions take shared/exclusive locks and release none until they stop acquiring; strict 2PL holds them to commit and guarantees serializability.
- [Optimistic concurrency control](/raw/optimistic-concurrency-control.md) [Transactions & concurrency control · low]: Run transactions without locks, record what they read, and validate at commit that nothing changed; fastest when conflicts are rare.
- [Deadlock detection](/raw/deadlock-detection.md) [Transactions & concurrency control · low]: Find transactions waiting on each other in a cycle (wait-for graph), abort one, or order lock requests so no cycle can form.
- [Buffer pool](/raw/buffer-pool.md) [Buffer management · medium]: The database's own page cache (frames, page table, pin counts, dirty bits, replacement) so it, not the OS, controls eviction, write order and I/O.
- [Columnar storage](/raw/columnar-storage.md) [Data layout · medium]: Store each column contiguously so analytic scans read only the columns they need, compress well and run as tight SIMD loops.
- [Slotted pages](/raw/slotted-pages.md) [Data layout · low]: Fixed-size page layout for variable-length records, with a slot array growing from the front and data from the back; stable record IDs despite compaction.
- [Chunked array storage](/raw/chunked-array-storage.md) [Data layout · medium]: Cut an N-dimensional array into a regular grid of independently compressed blocks, so a slice read touches only the overlapping blocks and writers to different blocks run in parallel.
- [Time partitioning](/raw/time-partitioning.md) [Data layout · low]: Cut a table into fixed-interval time blocks so queries read only overlapping blocks and retention drops a whole block as one metadata change.
- [Time-series chunk storage](/raw/time-series-chunk-storage.md) [Data layout · medium]: Store each series as immutable compressed chunks of consecutive samples behind a small time index; a range query decodes only the chunks that overlap it.
- [Content-addressed storage](/raw/content-addressed-storage.md) [Data layout · low]: Store each blob under the hash of its bytes: immutable, deduplicated by construction, self-verifying on every read, and composable into Merkle trees.
- [Vectorized execution](/raw/vectorized-execution.md) [Query execution · medium]: Query operators pass batches of about 1-2K values per column instead of single tuples, amortizing interpretation overhead and enabling tight SIMD loops.
- [Hash join](/raw/hash-join.md) [Query execution · low]: Build a hash table on the smaller input's join key and probe it with every row of the larger one; the linear-time workhorse for equi-joins.
- [Sort-merge join](/raw/sort-merge-join.md) [Query execution · low]: Sort both inputs on the key, then advance two cursors in lockstep and emit matching runs; cheap on sorted inputs and good for range joins.
- [Chunked backfill](/raw/chunked-backfill.md) [Schema & migrations · low]: Process old data in bounded key ranges, one short transaction per chunk, with a saved checkpoint and idempotent writes, so a crash resumes and live traffic never waits.
- [Change data capture](/raw/change-data-capture.md) [Data pipelines · medium]: Decode the database's own commit log into row-change events in commit order, with a resume position, so any consumer can mirror the data exactly.
- [Rollup aggregation](/raw/rollup-aggregation.md) [Data pipelines · medium]: Fold raw events into one mergeable partial aggregate per time bucket and dimension key, then merge fine buckets into coarser ones, so long ranges read few rows and stay exact.
- [Entity resolution](/raw/entity-resolution.md) [Product analytics · medium]: Decide which records describe the same real-world thing: block to cut the pair space, score pairs with a probabilistic model, cluster the matches transitively.
- [XML Streaming Parser](/raw/xml-streaming-parser.md) [File & document formats · low]: Tokenize XML into start, text and end events in constant memory, so a few fields can be extracted from huge, broken or hostile documents.

## Distributed systems
Consensus, replication, time, partitioning and membership.
- [Raft](/raw/raft.md) [Consensus · medium]: Leader-based consensus on a replicated log; one leader per term, majority commit; the default for a strongly consistent replicated state machine.
- [Multi-Paxos](/raw/multi-paxos.md) [Consensus · medium]: Paxos run once per log slot with a stable leader that skips phase 1; the foundation of Chubby, Spanner and much production consensus.
- [State-machine snapshots](/raw/state-machine-snapshots.md) [Consensus · medium]: Periodically save the state a log has produced at index i so the log prefix can be deleted; recovery and catch-up become load snapshot plus replay suffix.
- [Chain replication](/raw/chain-replication.md) [Replication · medium]: Replicas in a line: writes enter at the head and commit at the tail, reads hit the tail; f+1 nodes tolerate f failures.
- [Quorum replication](/raw/quorum-replication.md) [Replication · medium]: Leaderless replication: write to W of N replicas, read from R; overlap (R + W > N) makes reads see the latest completed write.
- [CRDTs](/raw/crdts.md) [Replication · medium]: Data types whose replicas accept writes independently and always converge by merging, with no coordination: counters, sets, maps, registers, text.
- [Primary-backup replication](/raw/primary-backup-replication.md) [Replication · medium]: One node orders all writes and ships them to standbys; the acknowledgement rule (none, one, all) sets what a crash loses, and an external arbiter decides who takes over.
- [Anti-entropy repair](/raw/anti-entropy-repair.md) [Replication · medium]: Replicas compare hash trees of a key range, descend only into differing subtrees and stream just those ranges, healing silent divergence in the background.
- [Hinted handoff](/raw/hinted-handoff.md) [Replication · medium]: Park a write meant for a down replica as a tagged hint on a healthy node, replay it when the replica returns, and count it toward the write quorum only if availability matters more than consistency.
- [Lamport clocks](/raw/lamport-clocks.md) [Time & ordering · low]: One integer per process, max-plus-one on receive; gives a total order consistent with causality using 8 bytes per timestamp.
- [Vector clocks](/raw/vector-clocks.md) [Time & ordering · low]: One counter per node; comparing two vectors tells whether events are ordered or concurrent, which is exactly what conflict detection needs.
- [Hybrid logical clocks](/raw/hybrid-logical-clocks.md) [Time & ordering · low]: A 64-bit timestamp that tracks wall-clock time but never goes backwards and respects causality; the default timestamp for MVCC databases without atomic clocks.
- [Clock synchronization](/raw/clock-synchronization.md) [Time & ordering · medium]: Estimate a clock's offset from four timestamps, filter out queueing noise, and steer the clock smoothly; NTP gets about a millisecond, PTP with hardware timestamps under a microsecond.
- [Distributed ID generation](/raw/distributed-id-generation.md) [Time & ordering · low]: Mint unique, roughly time-sorted IDs on many nodes with no per-ID coordination: Snowflake (time, worker, sequence) or UUIDv7 (time, random).
- [Consistent hashing](/raw/consistent-hashing.md) [Partitioning · low]: Hash nodes and keys onto a ring; each key belongs to the next node clockwise, so membership changes move only about 1/n of keys.
- [Rendezvous hashing](/raw/rendezvous-hashing.md) [Partitioning · low]: Score every node with hash(key, node) and pick the highest: minimal key movement and exact weights without a ring, at O(n) per lookup.
- [Jump consistent hash](/raw/jump-consistent-hash.md) [Partitioning · low]: Five lines, zero memory, near-perfect balance: maps a 64-bit key to one of n numbered buckets, moving only 1/(n+1) of keys when n grows.
- [Range partitioning](/raw/range-partitioning.md) [Partitioning · low]: Cut the sorted key space into contiguous half-open ranges kept in a boundary map; split hot or big ranges, merge small ones, move ranges between nodes.
- [Online resharding](/raw/online-resharding.md) [Partitioning · medium]: Split or move a shard while it serves traffic by copying a snapshot, replaying changes until the lag is tiny, then flipping a versioned routing table.
- [Scatter-gather query](/raw/distributed-scatter-gather-query.md) [Partitioning · medium]: Send a query only to shards that can match, merge their small partial results, and bound the wait for stragglers.
- [SWIM gossip membership](/raw/swim-gossip.md) [Membership & failure detection · medium]: Each node probes one random peer per period, asks k others on timeout, and piggybacks membership updates; constant load per node at any cluster size.
- [Phi accrual failure detector](/raw/phi-accrual-failure-detector.md) [Membership & failure detection · low]: Instead of a fixed heartbeat timeout, output a continuous suspicion level φ from the observed heartbeat interval distribution; adapts to each link's jitter.
- [Presence tracking](/raw/presence-tracking.md) [Membership & failure detection · medium]: Heartbeats refresh per-connection TTLs; a user is online while any connection lives, with a grace period that hides reconnect flaps.
- [Two-phase commit](/raw/two-phase-commit.md) [Coordination · medium]: Atomic commit across shards: participants durably vote yes, then the coordinator logs and broadcasts one decision; blocks if the coordinator is lost.
- [Leases](/raw/leases.md) [Coordination · low]: A lock that expires on its own: bounded-time ownership that survives crashes and partitions, given bounded clock drift and fencing tokens on writes.
- [Fencing tokens](/raw/fencing-tokens.md) [Coordination · low]: A number that grows with every lock grant and is checked by the protected resource, so a paused ex-holder's late write is rejected.
- [Saga pattern](/raw/saga-pattern.md) [Coordination · medium]: Split a cross-service operation into local transactions, each paired with an undo; on failure run the undos in reverse, or retry forward.
- [Transactional outbox](/raw/transactional-outbox.md) [Coordination · medium]: Write the event as a row in the same local transaction as the state change; a relay publishes it later at-least-once, so state and events never diverge.
- [Config distribution](/raw/config-distribution.md) [Coordination · medium]: A control plane pushes versioned resource changes over long-lived streams; each node validates, ACKs or NACKs and keeps its last good copy, so a bad change stops at a canary.
- [Desired-state reconciliation](/raw/desired-state-reconciliation.md) [Coordination · medium]: Declare the target in a store; controllers repeatedly diff actual against desired from full state and apply idempotent fixes, so missed events only delay convergence.
- [Watch notifications](/raw/watch-notifications.md) [Coordination · medium]: A store numbers every write; clients list at revision R, then watch from R+1 and receive an ordered change stream with no gap, no duplicate, and a resume point.
- [Partitioned commit log](/raw/partitioned-commit-log.md) [Logs, queues & fan-out · medium]: A topic split into replicated append-only partitions: key hash keeps per-key order, offsets give position, and a high watermark limits readers to fully replicated records.
- [Segmented log](/raw/segmented-log.md) [Logs, queues & fan-out · low]: Split an append-only log into files named by their first offset, write only the newest, and find any record by binary search plus a sparse index.
- [Consumer offsets](/raw/consumer-offsets.md) [Logs, queues & fan-out · low]: Each consumer group stores one integer per partition, the next position to read, so a restarted consumer resumes where it left off with at-least-once delivery.
- [Durable job queue](/raw/durable-job-queue.md) [Logs, queues & fan-out · medium]: Persisted tasks that workers lease for a visibility timeout, ack on success and retry with backoff; at-least-once execution that survives worker and queue crashes.
- [Dead-letter queue](/raw/dead-letter-queue.md) [Logs, queues & fan-out · low]: A side queue for messages that keep failing: after N delivery attempts or a permanent error, park them with the reason so the main queue keeps moving.
- [Event deduplication window](/raw/event-deduplication.md) [Logs, queues & fan-out · low]: Keep the ids of recently accepted events for a time window and drop repeats; memory stays bounded by rotating time buckets instead of per-entry timers.
- [Pub/sub fan-out](/raw/pubsub-fanout.md) [Logs, queues & fan-out · medium]: Deliver one published message to every subscriber of a topic by sharing one encoded payload and giving each connection a bounded queue with an explicit slow-consumer policy.
- [Fan-out on write](/raw/fanout-on-write.md) [Logs, queues & fan-out · medium]: Append each new item id to every follower's precomputed, capped list so a read is one fetch; pull the few huge authors at read time instead.
- [Message sequence numbers](/raw/message-sequence-numbers.md) [Logs, queues & fan-out · low]: A per-stream counter on every message lets the receiver detect loss, duplicates and reordering, ack cheaply and resume after reconnect with "send from N".
- [Windowed stream aggregation](/raw/stream-windowed-aggregation.md) [Stream & batch processing · medium]: Group events by event-time window per key, keep one partial aggregate per slice, and emit a window when the watermark passes its end.
- [DAG workflow execution](/raw/dag-workflow-execution.md) [Stream & batch processing · medium]: Run a graph of dependent tasks by releasing each one when its inputs are done, longest chain first, and skip any task whose input hashes are unchanged.
- [Durable workflow execution](/raw/durable-workflow-execution.md) [Stream & batch processing · medium]: Ordinary code made crash-proof by logging every side-effect result and replaying the code from that log; activities run at least once, workflow logic must be deterministic.
- [Incremental sync cursors](/raw/incremental-sync-cursors.md) [Client sync & collaboration · medium]: The client keeps one opaque token; each pull returns only the changes after it plus the next token, so sync cost scales with what changed, not with the dataset.
- [Offline mutation queue](/raw/offline-mutation-queue.md) [Client sync & collaboration · medium]: Apply actions locally at once and queue them durably; on reconnect replay the queue idempotently, then re-apply unconfirmed ones on the server state.
- [Fractional indexing](/raw/fractional-indexing.md) [Client sync & collaboration · low]: Give every list item a sortable string key and generate a new key strictly between its neighbours, so a move or insert writes one row.
- [Three-way merge](/raw/three-way-merge.md) [Client sync & collaboration · medium]: Merge two descendants against their common ancestor: take whichever side changed, report a conflict only where both changed the same spot differently.
- [Deterministic simulation testing](/raw/deterministic-simulation-testing.md) [Testing & replay · medium]: Run the whole system in one thread under a seeded scheduler with simulated network, disk and clock, so every failure replays from its seed.
- [Open-loop load generation](/raw/open-loop-load-generation.md) [Testing & replay · medium]: Send requests on a fixed or random schedule regardless of replies, and time each from its intended send time, so stalls show up in the tail.
- [Halo exchange](/raw/halo-exchange.md) [HPC communication & scheduling · medium]: Each rank stores its block plus a border copy of its neighbours' edge cells, refreshed by small messages every step; communication scales with block surface, not volume.
- [Lag-compensated turn timer with a refilling quota](/raw/turn-clock-lag-quota.md) [Other · low]: A server-side turn timer that credits back each move's measured network lag, capped per move and by a quota that refills a fixed amount per move.

## Multiplayer & game networking
Real-time state sync, latency hiding, bandwidth and matchmaking.
- [Authoritative server](/raw/authoritative-server.md) [Sync models · medium]: One process owns the state and steps it at a fixed tick; clients send inputs and show returned snapshots, so a lying client only affects its own inputs.
- [Deterministic lockstep](/raw/deterministic-lockstep.md) [Sync models · medium]: Every peer runs the same deterministic simulation and exchanges only inputs; bandwidth ignores unit count, at the cost of input delay.
- [Deterministic fixed-point math](/raw/deterministic-fixed-point-math.md) [Sync models · low]: Bit-identical simulation math across CPUs, compilers and builds: integer fixed-point formats, the float traps (FMA, x87, fast-math, libm), deterministic trig, sqrt and RNG.
- [Client-side prediction](/raw/client-side-prediction.md) [Latency hiding · medium]: The client applies its own inputs immediately, then on each server state rewinds to it and replays unacknowledged inputs (reconciliation).
- [Entity interpolation](/raw/entity-interpolation.md) [Latency hiding · low]: Render remote entities a fixed delay in the past, blending the two buffered snapshots around that time: ~2 snapshot intervals of latency buy smooth motion.
- [Lag compensation](/raw/lag-compensation.md) [Latency hiding · medium]: The server rewinds other players' hitboxes to the moment the shooter saw them, so hits land where the shooter aimed despite latency and interpolation delay.
- [Rollback netcode](/raw/rollback-netcode.md) [Latency hiding · medium]: Run the game immediately on predicted remote inputs; when real inputs arrive and differ, restore a saved state and re-simulate to the present (GGPO).
- [Snapshot delta compression](/raw/snapshot-delta-compression.md) [Bandwidth · low]: Encode each client's snapshot as the difference from the last snapshot that client acknowledged, so unchanged entities and fields cost zero to a few bits.
- [State quantization](/raw/state-quantization.md) [Bandwidth · low]: Store floats as small fixed-point integers sized to the precision needed (bounded positions, smallest-three quaternions), cutting size 2-4x before any delta coding.
- [Interest management](/raw/interest-management.md) [Bandwidth · medium]: Send each client only the entities relevant to it (spatial area of interest, visibility, team), ordered by priority accumulators to fit a per-packet byte budget.
- [Bitstream serialization](/raw/bitstream-serialization.md) [Bandwidth · low]: A bit writer and reader over a byte buffer that stores each field in exactly the bits its range needs: booleans in 1 bit, bounded integers in ceil(log2(span+1)) bits.
- [Reliable UDP](/raw/reliable-udp.md) [Game transport · low]: Transport over UDP: each packet carries a sequence number, an ack and a 32-bit ack history; only chosen messages are made reliable.
- [Elo rating](/raw/elo-rating.md) [Rating & matchmaking · low]: One number per competitor, moved by K × (actual − expected score) after each pairwise result; expected score is logistic in the rating difference.
- [Glicko-2](/raw/glicko-2.md) [Rating & matchmaking · low]: Rating plus rating deviation (RD) and volatility per player, so new or inactive players move fast and established ones move slowly.
- [Matchmaking queue](/raw/matchmaking-queue.md) [Rating & matchmaking · medium]: Pair waiting participants into fair matches by rating and latency, widening tolerances the longer each ticket waits, so queues stay short at the edges of the skill curve.
- [Swiss-system pairing](/raw/swiss-pairing.md) [Rating & matchmaking · medium]: Each round pairs competitors with equal scores, never twice and with balanced sides; a bye covers odd counts, and about log2(N) rounds expose a winner.

## Audio & video
Video and audio coding, streaming and packaging, real-time media, audio processing, image codecs and camera pipelines.
- [GOP structure](/raw/gop-structure.md) [Video coding · low]: How an encoder orders I, P and B frames into groups of pictures: the knob behind seekability, compression, latency and stream switching.
- [Adaptive quantization](/raw/adaptive-quantization.md) [Video coding · low]: Per-block QP offsets driven by local texture energy: spend bits on flat areas where blocking shows, save them where texture masks the error.
- [Adaptive bitrate streaming](/raw/adaptive-bitrate-streaming.md) [Streaming & packaging · medium]: The client fetches short HTTP segments and picks each segment's rendition from throughput estimates, buffer level, or both, trading stalls against quality and switches.
- [Common Encryption (CENC)](/raw/common-encryption-cenc.md) [Streaming & packaging · low]: ISO/IEC 23001-7 fixes how MP4 samples are encrypted and where key ID, IVs and clear/protected byte ranges are stored, so one file serves many DRM systems.
- [Video transcoding ladder](/raw/video-transcoding-ladder.md) [Streaming & packaging · medium]: Turn one source into resolution x bitrate x codec renditions chosen from measured rate-quality points, cut on aligned keyframes so players can switch mid-stream.
- [A/V sync and media clocks](/raw/av-sync-clocks.md) [Streaming & packaging · low]: How audio and video stay lip-synced: per-stream timebases, PTS/DTS, PCR and RTCP clock mapping, and a master clock that slave streams chase by dropping, repeating or resampling.
- [Perceptual quality metrics (PSNR, SSIM, VMAF)](/raw/perceptual-quality-metrics.md) [Streaming & packaging · low]: Full-reference scores that say how bad a compressed picture looks: PSNR (pixel error), SSIM (structure), VMAF (learned fusion), and when each one lies.
- [RTP and RTCP](/raw/rtp-rtcp.md) [Real-time communication · low]: RTP stamps each media packet with sequence number, media-clock timestamp and source ID; RTCP reports loss, jitter, round trip and clock mapping within a bandwidth cap.
- [Jitter buffer](/raw/jitter-buffer.md) [Real-time communication · medium]: A receiver-side buffer holds packets just long enough, a delay tracked from recent arrivals, to reorder them and hand out media at a steady rate.
- [Selective forwarding unit](/raw/selective-forwarding-unit.md) [Real-time communication · medium]: A server receives each participant's media once and forwards chosen packets to every other participant, picking the quality layer per receiver without decoding anything.
- [NAT traversal (STUN, ICE, TURN)](/raw/nat-traversal.md) [Real-time communication · medium]: Learn your public address with STUN, swap candidate addresses over signalling, test pairs with ICE checks, and fall back to a TURN relay if no direct path works.
- [SRTP](/raw/srtp.md) [Real-time communication · low]: Per-packet encryption, authentication and replay protection for RTP and RTCP that keeps the headers readable, with the packet index derived from the 16-bit sequence number.
- [Linear predictive coding (LPC)](/raw/linear-predictive-coding.md) [Audio coding · low]: Predict each sample from the previous p; code only the small prediction error plus p coefficients. Core of FLAC, speech codecs and the Opus SILK layer.

## Hardware & OS
What the machine really does: caches, SIMD, virtual memory, the page cache, durable writes and zero-allocation I/O.
- [CPU caches and the memory hierarchy](/raw/cpu-caches-and-memory-hierarchy.md) [CPU · low]: Sizes, line widths and latencies of L1/L2/L3/DRAM on modern x86 and Apple M-series, and the data-layout rules that follow from them.
- [Roofline model](/raw/roofline-model.md) [CPU · low]: Bound a kernel's speed by min(peak FLOP/s, arithmetic intensity × memory bandwidth) to know whether to optimize compute or data movement.
- [SIMD programming](/raw/simd-programming.md) [CPU · low]: Process 4-16 lanes per instruction with AVX2, AVX-512 or NEON via Rust std::arch, with runtime dispatch and a portable fallback.
- [Branch prediction](/raw/branch-prediction.md) [CPU · low]: How CPUs guess branch outcomes, what a misprediction costs, and when to replace branches with conditional moves, masks or sorted data.
- [Structure of arrays and hot/cold splitting](/raw/data-oriented-design-soa.md) [CPU · low]: Store each field in its own array and keep rarely used fields apart, so a loop reads only the bytes it needs and the compiler can vectorize it.
- [Virtual memory and the TLB](/raw/virtual-memory-and-tlb.md) [Memory · low]: How page tables and TLBs translate every address, what TLB reach means, and when 2 MiB or 1 GiB huge pages pay off on Linux.
- [mmap and the page cache](/raw/mmap-and-page-cache.md) [Memory · low]: How read() and mmap reach file data through the kernel page cache, what readahead and madvise do, and why databases use their own buffer pool instead.
- [Copy-on-write fork](/raw/copy-on-write-fork.md) [Memory · low]: fork() gives the child the parent's whole address space by sharing pages read-only and copying one only when someone writes it; vfork and posix_spawn skip even that.
- [fsync, O_DSYNC and O_DIRECT](/raw/fsync-and-direct-io.md) [Storage I/O · low]: What fsync, fdatasync, O_DSYNC, O_DIRECT and F_FULLFSYNC really guarantee on Linux and macOS, and the exact call sequences for crash-safe files.
- [SSD and NVMe internals](/raw/ssd-and-nvme-internals.md) [Storage I/O · low]: NAND pages and erase blocks, the FTL, garbage collection and write amplification, NVMe queues and queue depth, and 4 KiB alignment, with the numbers that matter.
- [CRC32C checksums](/raw/crc32c-checksums.md) [Storage I/O · low]: The Castagnoli CRC-32 with dedicated instructions on x86 (SSE4.2) and ARMv8. It is the standard fast integrity check for storage blocks, logs and network frames.
- [File system watching](/raw/file-system-watching.md) [Storage I/O · low]: Treat OS change notices as hints, debounce them, and rescan and diff a snapshot whenever notices overflow or may be lost.
- [Buffer pools for zero-allocation I/O](/raw/buffer-pools-zero-alloc-io.md) [Buffers · low]: Preallocate a fixed set of aligned I/O buffers and recycle them through a free list, so the hot path never mallocs, faults or unmaps. The bounded count doubles as back pressure.
- [System call interface](/raw/system-call-interface.md) [Kernel mechanisms · low]: The controlled gate between user code and the kernel: number and arguments in registers, a trap instruction, a validated handler, a result or error code.
- [Context switching](/raw/context-switching.md) [Kernel mechanisms · low]: Handing a core to another task by saving and loading registers, stack and address space; the hidden cache and TLB cost outweighs the direct one.
- [Interrupt handling](/raw/interrupt-handling.md) [Kernel mechanisms · low]: How a device signal reaches a CPU handler through an interrupt controller and vector table, and how top/bottom halves, polling switch-over and coalescing keep load bounded.
- [Process supervision](/raw/process-supervision.md) [Processes & terminals · low]: A parent process starts services, reaps their exits and restarts them under a delay and burst-limit policy, then stops them with SIGTERM before SIGKILL.
- [Cgroups and namespaces](/raw/cgroups-namespaces.md) [Processes & terminals · low]: Linux namespaces limit what a process can see; cgroup v2 limits and accounts what it may use. Containers, sandboxes and job schedulers are built from the two.
- [Checkpoint and restart](/raw/checkpoint-restart.md) [Processes & terminals · medium]: Periodically save enough state to resume a computation after a crash, preemption or move, with an interval that balances save cost against lost work.
- [DMA and IOMMU](/raw/dma-and-iommu.md) [Virtualization · low]: How devices move data by direct memory access, and how an IOMMU gives each device its own address space, faults on stray accesses and lets user space or guests own a device safely.
- [Static timing analysis](/raw/static-timing-analysis.md) [Chip design & EDA · medium]: Propagate latest/earliest arrival forward and required times backward through a DAG; slack = required - arrival, and the minimum-slack path is the critical one.

## Embedded, industrial & energy
Firmware and device buses, real-time scheduling, industrial control, safety-critical design, power grids and batteries.
- [Watchdog timer](/raw/watchdog-timer.md) [Firmware & peripherals · low]: A hardware down-counter that resets the chip unless software proves, in time and in a plausible pattern, that it is still healthy.
- [Fixed-rate control loop](/raw/fixed-rate-control-loop.md) [Firmware & peripherals · low]: Run a controller at an exact period using absolute deadlines and a fixed dt, so jitter never accumulates and the math stays valid.
- [PWM generation](/raw/pwm-generation.md) [Firmware & peripherals · low]: A timer's counter, period and compare registers draw the pulse train; preload, dead time and DMA make duty changes glitch-free, shoot-through-free and cheap.
- [Memory protection unit](/raw/memory-protection-unit.md) [Firmware & peripherals · low]: A handful of base/size regions with permissions, checked on every access by the CPU, give microcontroller tasks isolation and stack-overflow traps without an MMU.
- [A/B partition updates](/raw/ab-partition-ota-updates.md) [Firmware & peripherals · medium]: Two bootable slots and a small atomic metadata block: write the new image to the idle slot, try it once, and fall back by itself unless it reports healthy.
- [Preemptive priority scheduling](/raw/preemptive-priority-scheduling.md) [Real-time scheduling · low]: Always run the highest-priority ready task, switching the instant a higher one becomes ready; selection is O(1) with one FIFO per priority and a bitmap.
- [Alarm management](/raw/alarm-management.md) [Industrial control · medium]: Turn raw process limits into a few actionable operator alarms with delay, deadband, acknowledge and shelving states, plus flood measurement.
- [Hot-standby redundancy](/raw/hot-standby-redundancy.md) [Safety-critical design · medium]: A second, always-current controller shadows the primary and takes over within a few cycles of silence; epochs stop the old primary from fighting back.
- [Fault tree analysis](/raw/fault-tree-analysis.md) [Safety-critical design · medium]: Write the unwanted top event as AND/OR logic over component failures, reduce it to minimal cut sets, then compute its probability and each failure's share.
- [Safety-critical coding standards](/raw/safety-critical-coding-standards.md) [Safety-critical design · medium]: Which rule sets (MISRA C, CERT C, JPL Power of Ten, Rust lint subsets) apply when software must not fail, what they forbid, and how to enforce them in CI.
- [Model checking and formal proof](/raw/formal-verification-model-checking.md) [Safety-critical design · medium]: Exhaustively explore a model's reachable states (or prove its invariants with a solver or proof assistant) to find rule violations with a shortest counterexample trace.

## Data structures & hashing
Hash tables, hash functions, trees, sketches and buffers.
- [Swiss table](/raw/swiss-table.md) [Hash tables · low]: Open-addressing hash table that filters 8-16 slots at once with 1-byte hash tags and SIMD, giving fast lookups at 87.5 % load.
- [Robin Hood hashing](/raw/robin-hood-hashing.md) [Hash tables · low]: Linear probing where an inserting key evicts any resident closer to its home slot, keeping probe lengths short and uniform at 90 % load.
- [Cuckoo hashing](/raw/cuckoo-hashing.md) [Hash tables · low]: Every key lives in one of two candidate buckets, so lookups read at most two cache lines; inserts evict residents to their alternate bucket.
- [Fast hash functions](/raw/fast-hash-functions.md) [Hash functions · low]: Non-cryptographic hashes built from 64×64→128-bit multiplies and xor-shifts; pick by key size, trust level and whether the hash is persisted.
- [Adaptive radix tree (ART)](/raw/adaptive-radix-tree.md) [Ordered structures · low]: Byte-wise radix tree whose nodes resize between 4, 16, 48 and 256 children; ordered, space-efficient, and close to hash-table speed in memory.
- [Skip list](/raw/skip-list.md) [Ordered structures · low]: Sorted linked list with random express lanes; O(log n) search, simple inserts, and easy lock-free or single-writer concurrent reads.
- [d-ary heap](/raw/d-ary-heap.md) [Ordered structures · low]: Array heap with d children per node (d = 4 typical): half the binary heap's depth, siblings in one cache line, faster priority queues.
- [Interval tree](/raw/interval-tree.md) [Ordered structures · low]: Index of ranges that answers "which intervals overlap this point or range?" in O(log n + k); static sorted-array form is the compact, cache-friendly choice.
- [Bloom filter](/raw/bloom-filter.md) [Probabilistic structures · low]: Bit array answering "definitely not present" or "probably present" in about 10 bits per key for 1 % false positives; inserts are cheap, deletes impossible.
- [Xor filter](/raw/xor-filter.md) [Probabilistic structures · low]: Static membership filter where 3 slots xor to the key's fingerprint; 1.23× the space minimum and 3 memory reads per query.
- [HyperLogLog](/raw/hyperloglog.md) [Probabilistic structures · low]: Counts distinct elements in kilobytes with about 1 % error by tracking the longest run of leading zero bits in hashed values per bucket.
- [Count-min sketch](/raw/count-min-sketch.md) [Probabilistic structures · low]: d rows of w counters estimate any item's frequency in a stream, overestimating by at most ε·N with probability 1-δ, in fixed tiny memory.
- [SPSC ring buffer](/raw/spsc-ring-buffer.md) [Buffers · low]: Bounded wait-free queue for exactly one producer and one consumer thread, built from an array and two indices with acquire/release ordering.
- [Minimal perfect hashing](/raw/minimal-perfect-hashing.md) [Succinct & static structures · low]: A hash function mapping n fixed keys to 0..n-1 without collisions, in 1.5-4 bits per key; the keys themselves are not stored.
- [Rank/select bitvectors](/raw/rank-select-bitvectors.md) [Succinct & static structures · low]: Bitvector plus small count tables: ones before position i and position of the k-th one in O(1); Elias-Fano builds compressed sorted lists on it.

## Concurrency
Memory ordering, lock-free structures, memory reclamation and scheduling.
- [Memory ordering](/raw/memory-ordering.md) [Memory model · low]: What Relaxed, Acquire, Release and SeqCst atomics actually guarantee, what they cost on x86 and ARM, and which one each pattern needs.
- [False sharing](/raw/false-sharing.md) [Memory model · low]: Independent variables written by different cores on one cache line force the line to bounce between cores; pad or regroup hot data to fix it.
- [Futex-based mutex](/raw/futex-mutex.md) [Locks · low]: A mutex that is one atomic word in user space and enters the kernel (futex wait/wake) only under contention; how std and glibc locks work.
- [Seqlock](/raw/seqlock.md) [Locks · low]: Readers copy shared data optimistically and retry if a sequence counter changed; zero reader writes, so reads scale perfectly with a single fast writer.
- [MPMC bounded queue](/raw/mpmc-bounded-queue.md) [Lock-free structures · low]: Vyukov's array queue for many producers and consumers: each slot carries a sequence number, so one CAS per operation claims a slot without locks.
- [Sharded counters](/raw/sharded-counters.md) [Lock-free structures · low]: Split one hot counter into per-core or per-thread cells on separate cache lines; increments stay local and reads sum the cells.
- [Epoch-based reclamation](/raw/epoch-based-reclamation.md) [Memory reclamation · low]: Threads announce a global epoch while touching shared lock-free data; garbage retired in epoch e is freed once the epoch reaches e + 2.
- [Hazard pointers](/raw/hazard-pointers.md) [Memory reclamation · low]: Readers publish the exact pointers they are about to dereference; a reclaimer frees retired objects that no published hazard names, giving bounded garbage.
- [RCU (read-copy-update)](/raw/rcu.md) [Memory reclamation · low]: Readers access shared data with no locks or atomic writes; writers publish a new copy and free the old one after a grace period.
- [Work-stealing deque](/raw/work-stealing-deque.md) [Task scheduling · medium]: Per-worker deque: the owner pushes and pops at the bottom without contention, idle workers steal from the top; the core of Rayon, Tokio and Go.
- [Actor model](/raw/actor-model.md) [Task scheduling · medium]: Isolated units of state that interact only by queued messages and handle one at a time: no locks on state, and the same code runs local or remote.
- [Supervision trees](/raw/supervision-trees.md) [Task scheduling · medium]: Workers crash on surprises; supervisors only start, watch and restart them, with a restart-rate limit that escalates to their parent.

## Sorting, searching & vector search
Sorting, search in arrays and strings, selection and nearest-neighbour search.
- [Radix sort](/raw/radix-sort.md) [Sorting · low]: Non-comparison sort that distributes keys by 8-bit digits; several times faster than comparison sorts on large arrays of integers, floats or fixed-size keys.
- [Pattern-defeating quicksort (pdqsort)](/raw/pdqsort.md) [Sorting · low]: Introsort successor: quicksort with adaptive pivots, linear on sorted and equal-heavy input, heapsort fallback; the unstable sort of Go and (until 1.81) Rust.
- [External merge sort](/raw/external-merge-sort.md) [Sorting · medium]: Sort data larger than RAM: write memory-sized sorted runs, then k-way merge them with large sequential buffers; terabytes in one merge pass.
- [Eytzinger binary search](/raw/eytzinger-binary-search.md) [Searching · low]: Sorted array stored in BFS order so binary search walks an implicit tree with prefetchable addresses; 2-2.5x faster than binary search beyond cache.
- [SIMD substring search](/raw/simd-string-search.md) [Searching · low]: Find bytes or substrings by comparing 16-64 haystack positions per instruction against the needle's first and last byte, then verifying the rare candidates.
- [Suffix array](/raw/suffix-array.md) [Searching · low]: Sorted array of all suffix start positions of a text; finds every occurrence of any substring by binary search, at 4-5 bytes per text byte.
- [Top-k selection](/raw/top-k-selection.md) [Selection · low]: Keep the k best of n items without sorting all n - bounded min-heap for streams, quickselect for arrays, threshold pruning to skip most items.
- [HNSW](/raw/hnsw.md) [Vector search · medium]: Hierarchical Navigable Small World: a layered proximity graph searched greedily from a sparse top layer; the default in-memory approximate nearest-neighbour index.
- [IVF-PQ](/raw/ivf-pq.md) [Vector search · medium]: Inverted file plus product quantization: cluster vectors into lists, store each as a few bytes of codes, scan only the nearest lists via table lookups.
- [Nearest-neighbour search with filters](/raw/filtered-vector-search.md) [Vector search · medium]: Combine approximate nearest-neighbour search with attribute predicates by pre-filtering, post-filtering or filter-aware graph traversal, chosen by how many items pass.
- [Hybrid search and rank fusion](/raw/hybrid-search-rank-fusion.md) [Vector search · low]: Merge a keyword (BM25) result list and a vector (ANN) list into one ranking, by ranks (RRF) or by normalized scores (convex combination).
- [Cross-encoder reranking](/raw/cross-encoder-reranking.md) [Vector search · medium]: Re-score the top-k candidates of a cheap first stage with a model that reads query and candidate together; more accurate than separate embeddings, but one model call per pair.
- [Unicode text tokenization for search](/raw/unicode-text-tokenization.md) [Text retrieval · low]: Turn multilingual text into index terms: segment words (UAX 29 style, CJK bigrams), normalize, case-fold and accent-fold, identically at index and query time.
- [BM25 ranking](/raw/bm25-ranking.md) [Text retrieval · low]: The standard lexical relevance score: IDF-weighted term frequency with saturation (k1) and length normalization (b); default in Lucene, Elasticsearch and SQLite FTS5.
- [Aho-Corasick multi-pattern matching](/raw/aho-corasick.md) [Text retrieval · low]: Find all occurrences of many fixed patterns in one pass over the text, in time independent of the pattern count, using a trie with failure links.
- [Linear-time regular expression matching](/raw/regex-engine.md) [Text retrieval · medium]: Match a regular expression in O(pattern x text) worst case by tracking all live parse positions at once, then cache the state sets as a lazily built DFA for speed.
- [Top-k pruning with score upper bounds](/raw/block-max-wand.md) [Full-text retrieval · medium]: Skip documents that provably cannot enter the top-k, using per-list and per-block maximum scores against the current k-th best score (WAND, Block-Max WAND, MaxScore).
- [Sorted-list intersection](/raw/posting-list-intersection.md) [Full-text retrieval · low]: Intersect sorted id lists by merging, galloping from the short list into the long one, and skipping whole compressed blocks, shortest list first.
- [Myers diff](/raw/myers-diff.md) [Diff & near-duplicates · medium]: Greedy O(ND) shortest edit script between two sequences, the default of git and GNU diff; fast when the inputs are similar.
- [SimHash](/raw/simhash.md) [Diff & near-duplicates · low]: Charikar's random-hyperplane sketch: a 64-bit fingerprint per document whose Hamming distance tracks cosine similarity, searchable in sub-linear time by exact block matches.
- [Perceptual hashing](/raw/perceptual-hashing.md) [Diff & near-duplicates · low]: Compact fingerprints (64 to 256 bits) of an image that stay close under resizing and recompression, compared by Hamming distance; pHash, dHash and Meta's PDQ.
- [Robots exclusion protocol](/raw/robots-exclusion.md) [Web crawling · low]: Decide per URL whether a crawler may fetch it from a host's robots.txt (RFC 9309): status-code rules, group choice, longest-match Allow/Disallow, 24 h cache.
- [URL normalization](/raw/url-normalization.md) [Web crawling · low]: Rewrite a URL to one canonical key, in safe RFC 3986 steps plus lossy, site-dependent ones (tracking parameters, query order, fragments), and keep the original beside the key.
- [Smith-Waterman local alignment](/raw/smith-waterman-alignment.md) [Sequence alignment & genomics · medium]: Dynamic programming that finds the highest-scoring pair of similar substrings of two sequences under a substitution score and affine gap penalties, in O(nm) time.
- [Multiple sequence alignment](/raw/multiple-sequence-alignment.md) [Sequence alignment & genomics · medium]: Aligns N sequences into columns by merging them pairwise up a guide tree as profiles, optionally refined or guided by consistency; exact search is NP-hard.

## Financial infrastructure
Order books, matching engines, ledgers, money types, payments and low-latency trading plumbing.
- [Limit order book](/raw/limit-order-book.md) [Markets & trading · low]: Per-symbol store of resting orders as FIFO queues per price level; array-indexed ticks plus intrusive lists give O(1) add, cancel and best-price lookup.
- [Matching engine](/raw/matching-engine.md) [Markets & trading · medium]: Single-threaded, deterministic loop that journals sequenced orders, matches them by price-time priority against a limit order book and emits trades.
- [Pre-trade risk checks](/raw/pre-trade-risk-checks.md) [Markets & trading · low]: Constant-time gate in front of order entry that rejects fat-finger, over-limit and runaway orders using worst-case exposure counted over open orders.
- [Market data feeds (ITCH / MoldUDP64)](/raw/market-data-feeds.md) [Markets & trading · low]: Exchange order-by-order data as fixed binary messages in sequenced UDP multicast packets; receivers dedupe A/B lines, detect gaps by sequence number and recover.
- [FIX protocol (session layer)](/raw/fix-protocol.md) [Markets & trading · low]: Tag=value order-entry protocol over TCP with per-direction sequence numbers, heartbeats and resend so sessions survive disconnects without losing or duplicating orders.
- [Money representation](/raw/money-representation.md) [Ledgers & money · low]: Store money as integer minor units with an explicit currency exponent, compute in wider integers, and round once with a named rounding mode.
- [Double-entry ledger](/raw/double-entry-ledger.md) [Ledgers & money · low]: Append-only journal of transactions whose postings sum to zero per currency; balances are derived, so money can only move, never appear or vanish.
- [Event sourcing](/raw/event-sourcing.md) [Ledgers & money · low]: Persist state changes as an append-only stream of immutable events per entity; current state is a fold over them, guarded by expected-version appends.
- [Corporate-action adjustment](/raw/corporate-action-adjustment.md) [Ledgers & money · low]: Keep raw bars plus a tiny table of cumulative backward factors, built by one reverse scan over events and applied at read time, versioned by as-of date.
- [Idempotency keys](/raw/idempotency-keys.md) [Payments · low]: Client-chosen unique key per logical operation, stored with a request fingerprint and the final response, so retries replay the first result instead of acting twice.
- [Payment state machine](/raw/payment-state-machine.md) [Payments · medium]: Persisted state machine for a payment lifecycle (authorize, capture, void, refund) that treats timeouts as unknown, retries with the same key and applies webhooks idempotently.
- [Reconciliation](/raw/reconciliation.md) [Payments · low]: Match internal ledger records against bank and processor statements by reference, then amount and date window; every unmatched or mismatched item becomes an exception.
- [Low-latency hot path](/raw/low-latency-hot-path.md) [Latency engineering · low]: Rules for microsecond trading paths: one pinned busy-polling thread per stage, no allocation, syscalls, locks or page faults after startup, kernel-bypass I/O, and measured tails.
- [Black-Scholes-Merton formula](/raw/black-scholes.md) [Pricing & risk models · low]: Closed-form European option price and Greeks from spot, strike, time, rates and volatility; Newton inversion gives implied volatility. About 30 ns each.
- [Binomial lattice pricing](/raw/binomial-lattice-pricing.md) [Pricing & risk models · medium]: Recombining price tree with risk-neutral probabilities and backward induction; the cheapest way to price early-exercise claims, O(N²) time and O(N) memory.
- [Yield curve bootstrapping](/raw/yield-curve-bootstrapping.md) [Pricing & risk models · medium]: Turn quoted deposits, futures and swaps into a discount curve by solving one new maturity per instrument so that every quote reprices exactly.
- [Value at Risk and Expected Shortfall](/raw/value-at-risk.md) [Pricing & risk models · medium]: A loss threshold exceeded with probability 1−α over h days, plus the mean loss beyond it; three estimators trade speed for realism.
- [Ranked-slot auction (GSP and VCG)](/raw/generalized-second-price-auction.md) [Auctions & market makers · medium]: Rank bidders by bid × quality, give them the k positions in order, and charge each the minimum bid that would keep their rank (GSP); VCG is the truthful reference.

## Game AI & search
Search and decision-making for agents in games and other adversarial settings: game trees, imperfect information, game characters.
- [Alpha-beta search](/raw/alpha-beta-search.md) [Game-tree search · medium]: Minimax that skips branches which cannot change the result; with iterative deepening, PVS and aspiration windows it is the core of classical adversarial search.
- [Monte Carlo tree search](/raw/monte-carlo-tree-search.md) [Game-tree search · medium]: Grows a search tree one simulation at a time, picking visits by a bandit rule (UCT or PUCT) and backing up averages; the search behind AlphaZero.
- [Transposition table](/raw/transposition-table.md) [Game-tree search · low]: A fixed-size, lossy hash table of search results keyed by a state hash; gives ordering and cutoffs for repeated states, shared lock-free between threads.
- [Candidate ordering and pruning](/raw/move-ordering-and-pruning.md) [Game-tree search · low]: The heuristics that make alpha-beta and branch-and-bound fast: try likely-best candidates first (TT, captures, killers, history) and skip or reduce the rest (null move, LMR, futility).
- [NNUE incremental evaluation](/raw/nnue-incremental-evaluation.md) [Game-tree search · low]: Efficiently updatable neural network: a huge sparse first layer whose output (the accumulator) is patched per move, then tiny int8 layers; fast neural eval.
- [Batched MCTS inference](/raw/batched-mcts-inference.md) [Game-tree search · medium]: Feed an accelerator from tree search driven by a learned evaluator: virtual loss gathers leaves within a tree, parallel searches fill batches, an async queue overlaps CPU and GPU.
- [Bitboards](/raw/bitboards.md) [State representation · low]: One 64-bit word per set of up to 64 items, so set algebra becomes shifts, ANDs and table lookups; magic bitboards give ray queries in one multiply.
- [Zobrist hashing](/raw/zobrist-hashing.md) [State representation · low]: A state's hash is the XOR of one random 64-bit key per (item, slot) fact that holds in it, updated in a few XORs per change.
- [Compact state encoding](/raw/compact-position-encoding.md) [State representation · low]: Pack a state of a sparse grid into a few fixed bytes (24 for chess: occupancy bitmap plus nibbles) for training data and dedupe, with canonical symmetric forms.

## Graphics & UI
GPU rendering, 2D vector graphics, image processing, text rendering, UI layout and frameworks, and game-engine structure.
- [Bézier curves](/raw/bezier-curves.md) [2D vector graphics · low]: Smooth curves defined by 3-4 control points, evaluated and split with repeated linear interpolation (de Casteljau) and flattened to lines with a closed-form segment count.
- [Physically based shading (microfacet BRDF)](/raw/physically-based-shading.md) [3D rendering · medium]: Cook-Torrance microfacet BRDF with GGX distribution, height-correlated Smith masking and Schlick Fresnel, driven by base colour, metallic and roughness; the standard surface model of real-time and film renderers.
- [Render graph (frame graph)](/raw/render-graph.md) [3D rendering · medium]: Passes declare what they read and write; a per-frame compile drops unused passes, orders the rest, shares memory between short-lived resources and derives the barriers.
- [Monte Carlo denoising (feature-guided filtering)](/raw/monte-carlo-denoising.md) [Ray tracing & volumes · medium]: Smooth a noisy estimate with edge-stopping weights taken from cheap, noise-free side buffers (albedo, normal, depth), after dividing out texture.
- [Wavefront ray scheduling (stage queues)](/raw/wavefront-ray-scheduling.md) [Ray tracing & volumes · medium]: Split the per-item loop into small stage kernels joined by memory queues, so each launch runs one kind of work on a full, compacted batch.
- [GPU command buffers](/raw/gpu-command-buffers.md) [GPU APIs & presentation · low]: Record GPU work as a flat list of commands on the CPU, submit it in batches, and reuse its memory through a ring of frames in flight guarded by fences.
- [Image resampling filters](/raw/image-resampling-filters.md) [Image processing · low]: Resize an image by convolving with a kernel (box, triangle, cubic, Lanczos) whose width scales with the shrink factor, done as two separable 1-D passes with precomputed weights.
- [Tone mapping (HDR to display range)](/raw/tone-mapping-hdr.md) [Image processing · low]: Compress scene-referred linear light to a display's range in three steps: expose, apply a curve to luminance, then encode (sRGB, PQ or HLG) and dither.
- [Color space conversion](/raw/color-space-conversion.md) [Image processing · low]: Convert pixels between transfer curves (sRGB, linear light), primaries (sRGB, Display P3, XYZ) and Y'CbCr, using tables for the curve and 3x3 matrices for the rest.
- [Rope](/raw/rope.md) [Documents, editors & terminals · low]: A balanced tree of small string chunks with cached byte and newline counts, so seek, insert, delete and snapshot cost O(log n) instead of O(n).
- [List virtualization (windowing)](/raw/list-virtualization.md) [UI layout & styling · low]: Create and lay out only the items inside the viewport plus a little overscan, and fake the full scroll extent, so frame cost depends on the screen, not on N.
- [Signals and fine-grained reactivity](/raw/fine-grained-reactivity-signals.md) [UI frameworks & reactivity · medium]: A dependency graph of signals, memos and effects where reads auto-subscribe, so a state change re-runs exactly the outputs that used it, with no tree diff.
- [Statecharts](/raw/statecharts.md) [UI frameworks & reactivity · low]: State machines with nesting, parallel regions, history and entry/exit actions, so UI and animation logic stays linear in size instead of exploding.
- [Entity-component-system (ECS)](/raw/entity-component-system.md) [Game engine architecture · medium]: Store each attribute type in its own packed array keyed by an id, and run update functions over exactly the ids that have the attributes they need.

## Geometry & geospatial
Transforms and robust predicates, computational geometry, CAD surfaces, spatial indexes, map projections and geocoding.
- [Quaternion rotations](/raw/quaternion-rotations.md) [Transforms & predicates · low]: Unit quaternions as 3D rotations: 4 floats, cheap composition, no gimbal lock, plus the conversions, interpolation choices and numerical care needed in practice.
- [k-d tree](/raw/kd-tree.md) [Spatial indexes · low]: A binary tree that splits k-dimensional points by one coordinate per level, giving fast nearest-neighbour and box queries on static low-dimensional data.
- [R-tree](/raw/r-tree.md) [Spatial indexes · low]: A balanced tree of nested bounding boxes that indexes rectangles and points, answering window and nearest-neighbour queries by pruning whole subtrees.
- [Geospatial cell index (geohash, S2, H3)](/raw/geospatial-cell-index.md) [Spatial indexes · low]: Map a lat/lon to a 64-bit cell id on a hierarchical grid, so "near" becomes an integer range scan in any ordinary sorted index.
- [Geodesic distance (haversine, Vincenty, Karney)](/raw/geodesic-distance.md) [Maps & projections · low]: Shortest-path distance between two lat/lon points on the Earth: haversine on a sphere (about 0.5% error), Vincenty or Karney on the WGS84 ellipsoid (sub-millimetre).

## Physics simulation
Rigid-body simulation for games and robotics: broadphase, narrowphase, contact solving.
- [Spatial hashing](/raw/spatial-hashing.md) [Broadphase · low]: Uniform grid stored in a hash table: bucket objects by cell, test only neighbouring cells; O(n) neighbour search for many similar-sized objects such as particles.
- [Bounding volume hierarchy](/raw/bounding-volume-hierarchy.md) [Broadphase · low]: Binary tree of nested bounding boxes; prunes overlap and ray queries to O(log n) for any size distribution, and supports cheap insert/remove for moving objects.
- [Sweep and prune](/raw/sweep-and-prune.md) [Broadphase · low]: Sort box endpoints along an axis and sweep: only intervals that overlap on that axis are tested; near-linear per frame thanks to temporal coherence.
- [Separating axis theorem](/raw/separating-axis-theorem.md) [Narrowphase · low]: Convex shapes are disjoint iff some axis separates their projections; testing face normals and edge crosses gives overlap, depth and contact normal.
- [GJK and EPA](/raw/gjk-epa.md) [Narrowphase · low]: GJK decides whether (and how far apart) two convex shapes are from their support functions alone; EPA expands its simplex into penetration depth and normal.
- [Sequential impulse solver](/raw/sequential-impulse-solver.md) [Contact solving · medium]: Iterative contact solver applying impulses one constraint at a time with accumulated clamping and warm starting; the standard solver for stacking and friction in real-time physics engines.
- [Rigid-body dynamics](/raw/rigid-body-dynamics.md) [Rigid-body dynamics · low]: Advance one 3D rigid body per step from force and torque: semi-implicit Euler for position, an inertia tensor in the body frame, and quaternion orientation updated by the exponential map.

## Robotics & control
Feedback control, state estimation, kinematics, motion planning, localization and mapping, and geometric vision.
- [PID controller](/raw/pid-control.md) [Control · low]: Drive a measured value to a setpoint with three terms on the error: proportional, integral, derivative. The default feedback loop for motors, heaters, drones and gimbals.
- [Model predictive control](/raw/model-predictive-control.md) [Control · medium]: Each tick, solve a small optimization over a predicted horizon, apply only the first input, repeat. Handles constraints and multiple inputs that a PID loop cannot.
- [Kalman filter](/raw/kalman-filter.md) [State estimation · low]: Optimal recursive estimator for a linear system with Gaussian noise: fuses a motion model with noisy measurements into a state estimate plus its covariance.
- [Extended Kalman filter](/raw/extended-kalman-filter.md) [State estimation · low]: Kalman filter for nonlinear motion and measurement models: linearize f and h with Jacobians at the current estimate each step. The default estimator in robot navigation.
- [Rigid-body transforms (SE(3) poses)](/raw/rigid-body-transforms.md) [Kinematics & frames · low]: Represent, compose, invert, integrate and interpolate 3D poses as unit quaternion plus translation, with exp/log maps for small motions and uncertainty.

## Graphs
Traversal, shortest paths, connectivity, flow and scheduling on graphs.
- [BFS and DFS](/raw/bfs-dfs.md) [Traversal & ordering · low]: The two basic graph traversals; BFS gives hop distances and levels, DFS gives discovery/finish order for cycles, components and topological order.
- [Topological sort](/raw/topological-sort.md) [Traversal & ordering · low]: Order the vertices of a DAG so every edge points forward; the core of build systems, schedulers and dependency resolution, with cycle detection for free.
- [Dijkstra's algorithm](/raw/dijkstra.md) [Shortest paths · low]: Single-source shortest paths with non-negative edge weights by settling vertices in order of distance with a priority queue.
- [A* search](/raw/a-star.md) [Shortest paths · low]: Dijkstra ordered by cost-so-far plus an admissible estimate of the remaining cost; optimal paths while exploring far fewer nodes toward the goal.
- [Contraction hierarchies (shortcut-based shortest paths)](/raw/contraction-hierarchies.md) [Shortest paths · medium]: Rank the nodes, remove them one by one while adding shortcut edges that keep distances intact, then answer queries with two tiny searches that only climb the ranking.
- [Union-find](/raw/union-find.md) [Connectivity · low]: Disjoint-set forest with union by size and path compression; merges sets and answers same-set queries in effectively constant time.
- [Minimum spanning tree](/raw/minimum-spanning-tree.md) [Connectivity · low]: Cheapest set of edges connecting all vertices; Kruskal sorts edges and joins components with union-find, Prim grows one tree, Boruvka merges in parallel rounds.
- [Max flow (Dinic)](/raw/max-flow-dinic.md) [Flow & matching · low]: Maximum s-t flow by BFS level graphs and blocking flows; also gives the min cut, bipartite matching and assignment with capacities.
- [Assignment problem (Hungarian / Jonker–Volgenant)](/raw/assignment-problem-hungarian.md) [Flow & matching · medium]: Optimal one-to-one matching of rows to columns in O(n³) by growing a matching along shortest augmenting paths over dual potentials.
- [Graph partitioning](/raw/graph-partitioning.md) [Graph analytics · medium]: Split a graph into k balanced parts with few edges between them; multilevel coarsen-partition-refine (METIS, KaHIP) for quality, streaming heuristics (LDG, Fennel) for one-pass scale.

## Numerics & scientific computing
Differential equations, linear algebra, FFT, floating point, optimization and randomness.
- [Explicit Euler](/raw/explicit-euler.md) [ODE solvers · low]: Step an ODE forward by its current slope, y += h·f(t, y); first-order, one evaluation per step, the baseline every other integrator is measured against.
- [Runge-Kutta 4](/raw/runge-kutta-4.md) [ODE solvers · low]: The classic four-stage, fourth-order ODE step; error drops 16× when the step halves, with no derivatives or past steps needed.
- [Adaptive Runge-Kutta (Dormand-Prince)](/raw/adaptive-runge-kutta.md) [ODE solvers · low]: An embedded 5(4) Runge-Kutta pair estimates each step's error for free and resizes the step to meet a tolerance; the default non-stiff solver.
- [Stiff solvers (implicit, BDF)](/raw/stiff-solvers-implicit-bdf.md) [ODE solvers · low]: Implicit steps solve a small nonlinear system so fast decaying modes stay stable at any step size; BDF methods are the stiff-ODE workhorse.
- [Verlet / leapfrog](/raw/verlet-leapfrog.md) [Physics integrators · low]: Half-kick, drift, half-kick: a second-order, time-reversible, symplectic integrator with one force evaluation per step whose energy error stays bounded for millions of steps.
- [Semi-implicit Euler](/raw/semi-implicit-euler.md) [Physics integrators · low]: Update velocity from forces first, then position with the new velocity: explicit Euler cost, but symplectic and stable; the default game-physics integrator.
- [Finite differences](/raw/finite-differences.md) [PDE methods · low]: Replace derivatives with weighted differences of grid values; simple stencils plus a stability condition (CFL) turn PDEs like heat, advection and waves into array loops.
- [Finite elements](/raw/finite-elements.md) [PDE methods · medium]: Writes the PDE in weak form, approximates it with piecewise polynomials on a mesh and assembles a sparse system; handles any geometry.
- [Spectral methods](/raw/spectral-methods.md) [PDE methods · low]: Represent the solution by a global Fourier or Chebyshev series; derivatives become multiplications by ik in coefficient space, giving exponential convergence for smooth problems.
- [Gaussian quadrature](/raw/gaussian-quadrature.md) [PDE methods · low]: Approximate an integral by a weighted sum of n function values at roots of orthogonal polynomials; exact for polynomials up to degree 2n-1.
- [LU and Cholesky factorization](/raw/lu-cholesky.md) [Linear algebra · low]: Factor A = PLU (any square matrix, partial pivoting) or A = LLᵀ (SPD) once in O(n³), then solve each right-hand side in O(n²).
- [Sparse matrices (CSR)](/raw/sparse-matrices-csr.md) [Linear algebra · low]: Compressed sparse row stores only nonzeros as row pointers, column indices and values; SpMV streams them once, so it is memory-bandwidth bound.
- [Conjugate gradient](/raw/conjugate-gradient.md) [Linear algebra · low]: Krylov iteration for symmetric positive definite Ax = b using one matrix-vector product and two dot products per step; converges in about √κ iterations.
- [Multigrid](/raw/multigrid.md) [Linear algebra · low]: Smooths high-frequency error on the fine grid and solves the smooth remainder on coarser grids; O(n) elliptic solves at any resolution.
- [Sparse direct solver](/raw/sparse-direct-solver.md) [Linear algebra · medium]: Solve sparse Ax = b exactly by reordering, symbolic analysis, numeric LLᵀ/LU and triangular solves; fill-in, not flops per entry, decides the cost.
- [Fill-reducing ordering](/raw/fill-reducing-ordering.md) [Linear algebra · medium]: Permute a sparse symmetric matrix before Cholesky/LU so the factor has few new nonzeros; minimum degree, nested dissection and RCM trade quality, speed and parallelism.
- [Incomplete factorization preconditioners](/raw/incomplete-factorization-preconditioners.md) [Linear algebra · medium]: Sparse approximate LU or Cholesky factors (ILU, IC) that precondition Krylov solvers: fewer iterations than Jacobi, less memory than a direct solve.
- [Fast Fourier transform](/raw/fast-fourier-transform.md) [Core numerics · low]: Computes the DFT in O(n log n) by recursively splitting into even and odd halves; the basis of fast convolution and spectral methods.
- [Newton root finding](/raw/newton-root-finding.md) [Core numerics · low]: Linearize at the guess and jump to the tangent root; quadratic convergence near a simple root, made robust by brackets (1D) or line search.
- [Floating-point error](/raw/floating-point-error.md) [Core numerics · low]: How IEEE 754 rounding error accumulates and how to contain it: compensated (Kahan/Neumaier) and pairwise summation, error-free transformations with FMA, ULP comparisons.
- [L-BFGS](/raw/l-bfgs.md) [Optimization & randomness · low]: Quasi-Newton minimizer that approximates the inverse Hessian from the last m gradient differences via the two-loop recursion; O(m·n) memory and work per step.
- [PRNGs (PCG, xoshiro)](/raw/prng-pcg-xoshiro.md) [Optimization & randomness · low]: Small, fast, statistically strong non-cryptographic generators: PCG32 and xoshiro256**, with seeding, parallel streams and unbiased ranges.
- [Monte Carlo integration](/raw/monte-carlo.md) [Optimization & randomness · low]: Estimate an expectation by averaging random samples; error falls as σ/√N in any dimension, and variance reduction (antithetic, control variates, importance sampling) shrinks σ.

## Optimization & solvers
LP and MIP, constraint programming, SAT and SMT, metaheuristics, and routing, scheduling and packing heuristics.
- [Simplex method](/raw/linear-programming-simplex.md) [LP, MIP & convex solvers · low]: Solves linear programs by walking along the edges of the feasible polytope from vertex to vertex, one basis swap (pivot) at a time; the workhorse behind MIP solvers.
- [Mixed-integer programming (branch and bound)](/raw/mixed-integer-programming.md) [LP, MIP & convex solvers · medium]: Solves LPs with integer variables by solving the LP relaxation, branching on a fractional variable, and pruning subtrees whose LP bound cannot beat the incumbent.
- [Cutting planes](/raw/cutting-planes.md) [LP, MIP & convex solvers · medium]: Valid inequalities added to an LP relaxation to cut off its fractional optimum without removing any integer point; the engine of branch-and-cut MIP solvers.
- [Presolve reductions](/raw/presolve-reductions.md) [LP, MIP & convex solvers · medium]: Cheap, provably safe reductions run before the solver (fix variables, drop rows, tighten bounds and coefficients) so LP and MIP solves start from a smaller, tighter model.
- [Column generation](/raw/column-generation.md) [LP, MIP & convex solvers · medium]: Solve a huge LP by keeping only a few columns and pricing new ones from a subproblem until none can improve; gives the Dantzig-Wolfe bound.
- [Interior-point method (primal-dual, Mehrotra)](/raw/interior-point-method.md) [LP, MIP & convex solvers · medium]: Follows the central path with Newton steps on the perturbed KKT system, one sparse Cholesky per iteration; Mehrotra's predictor-corrector makes it fast.
- [CDCL SAT solving](/raw/cdcl-sat-solving.md) [SAT, SMT & constraint programming · medium]: Search for a satisfying assignment, learn a new constraint from every dead end, and jump back past irrelevant choices; handles industrial formulas with millions of clauses.
- [Two watched literals](/raw/two-watched-literals.md) [SAT, SMT & constraint programming · low]: Unit propagation for SAT that watches just two literals per clause, so backtracking costs nothing and long clauses are rarely touched.
- [Binary decision diagrams](/raw/binary-decision-diagrams.md) [SAT, SMT & constraint programming · low]: A reduced ordered BDD stores a Boolean function as a shared DAG that is unique per variable order, so equivalence is one integer compare and counting is one pass.
- [Constraint propagation (constraint programming)](/raw/constraint-propagation.md) [SAT, SMT & constraint programming · medium]: Variables with finite domains, propagators that prune impossible values to a fixpoint, and backtracking search with trail undo between decisions.
- [Large neighbourhood search (ruin and recreate)](/raw/large-neighborhood-search.md) [Metaheuristics & local search · medium]: Repeatedly remove a chunk of a solution and rebuild it with a heuristic or exact solver; learn which operator pairs pay off.
- [Time-window feasibility](/raw/time-window-feasibility.md) [Routing & scheduling · low]: Keep earliest/latest start and slack per segment so "does this insertion or move keep every window?" costs O(1) instead of a walk down the sequence.
- [Job-shop scheduling](/raw/job-shop-scheduling.md) [Routing & scheduling · medium]: Model jobs as chains of operations, resource order as a choice of arc directions, and minimise the longest path; build with dispatching rules, improve by swapping critical neighbours or solve with CP.
- [Bin packing](/raw/bin-packing.md) [Packing & supply planning · low]: Pack items of given sizes into the fewest fixed-capacity bins; sort descending, then first-fit, gives at most 11/9 of optimal and runs in O(n log n).

## Signal processing & communications
Digital filters and spectra, radio physical and MAC layers, channel coding and satellite positioning.
- [IIR and FIR filters](/raw/iir-fir-filters.md) [Filters & spectra · low]: Two ways to shape a sampled signal's spectrum: FIR (finite taps, always stable, exact linear phase) or IIR (feedback, a few coefficients, cheap but phase-distorting).
- [Short-time Fourier transform and spectrogram](/raw/stft-spectrogram.md) [Filters & spectra · low]: Slide a window over a signal and FFT each frame to get a time-frequency picture; the front end of audio ML, vibration and radar analysis.
- [Phase-locked loop (digital)](/raw/phase-locked-loop.md) [Filters & spectra · low]: Feedback loop that locks a local oscillator to the phase and frequency of an input tone; the core of carrier recovery, clock recovery and GNSS tracking.
- [Reed-Solomon codes](/raw/reed-solomon-codes.md) [Channel coding · low]: Byte-oriented MDS code: n-k parity symbols correct (n-k)/2 unknown symbol errors or n-k known erasures; the workhorse for bursts, QR codes, discs and storage.
- [Convolutional codes and the Viterbi decoder](/raw/convolutional-codes-viterbi.md) [Channel coding · low]: Streaming error-correcting code: each output bit is a parity of the last K input bits; the Viterbi decoder finds the most likely path through a 2^(K-1)-state trellis.

## Systems building blocks
Caching, timers, flow control and memory allocation.
- [LRU and CLOCK](/raw/lru-and-clock.md) [Cache eviction · low]: LRU evicts the least recently used entry via hash map plus linked list; CLOCK approximates it with a reference bit, so hits take no lock.
- [W-TinyLFU](/raw/w-tinylfu.md) [Cache eviction · low]: An LRU window plus segmented LRU, guarded by a 4-bit Count-Min sketch that admits a newcomer only if it beats the victim's frequency.
- [S3-FIFO](/raw/s3-fifo.md) [Cache eviction · low]: Three FIFO queues (small, main, ghost) that evict one-hit wonders quickly and keep reused objects; low miss ratios with no list moves on hits.
- [Hierarchical timing wheel](/raw/hierarchical-timing-wheel.md) [Timers · low]: Timers bucketed by expiry into wheels of slots, coarser wheels for far deadlines: O(1) insert and cancel for millions of timeouts.
- [Token bucket](/raw/token-bucket.md) [Flow control & resilience · low]: A bucket of up to b tokens refilled at rate r; requests spend tokens, enforcing an average rate while allowing bursts of b.
- [GCRA](/raw/gcra.md) [Flow control & resilience · low]: Generic Cell Rate Algorithm: a token bucket stored as one theoretical arrival time per key, updated with one compare-and-swap; exact limits in 8 bytes.
- [Exponential backoff with jitter](/raw/exponential-backoff-jitter.md) [Flow control & resilience · low]: Retry after delays that grow geometrically and are randomized, so failed clients spread out instead of hammering a recovering service in synchronized waves.
- [Circuit breaker](/raw/circuit-breaker.md) [Flow control & resilience · low]: Stop calling a failing dependency for a while, probe it with trial calls, and resume on recovery: fail fast instead of piling up timeouts.
- [Backpressure](/raw/backpressure.md) [Flow control & resilience · low]: Bound every queue and make a full queue push back on the producer by blocking, dropping, rejecting or withholding credit.
- [Distributed rate limiting](/raw/distributed-rate-limiting.md) [Flow control & resilience · medium]: Enforce one rate limit across N servers: a central atomic counter, a limit split per node, or batched token leases, trading exactness against coordination cost.
- [Sliding-window counters](/raw/sliding-window-counters.md) [Flow control & resilience · low]: Count events in the last W seconds with a ring of sub-bucket counters; the two-bucket weighted estimate gives rate limits in 16 bytes per key.
- [Graceful draining](/raw/graceful-draining.md) [Flow control & resilience · low]: On a termination signal, stop taking new work, finish in-flight work until a deadline, tell clients to reconnect elsewhere, then exit; clients resume from a token.
- [Arena allocator](/raw/arena-allocator.md) [Memory allocation · low]: Allocate by bumping a pointer through big chunks and free everything at once: a few instructions per allocation for objects sharing a lifetime.
- [Slab allocator](/raw/slab-allocator.md) [Memory allocation · low]: Pre-carve pages into equal-size slots per size class with an in-place free list: O(1) alloc and free, no external fragmentation, cache-warm reuse.
- [Cache invalidation](/raw/cache-invalidation.md) [Caching patterns · medium]: Make writes remove cached copies by key, group tag or prefix, broadcast the removal to every node, and guard refills with tokens so stale values never return.
- [Recurrence rule expansion](/raw/recurrence-rule-expansion.md) [Calendars & recurring schedules · medium]: Expand an RFC 5545 RRULE lazily, in local wall-clock time, into concrete instants; store the rule, materialise only a bounded horizon.
- [Distributed tracing](/raw/distributed-tracing.md) [Observability & alerting · medium]: Give each request a 128-bit id, record timed spans linked by parent ids, pass the ids in a header across every hop, and join the spans back into a tree afterwards.
- [Health checking](/raw/health-checking.md) [Observability & alerting · low]: Decide per backend whether to route to it using probes and real-traffic errors, with consecutive-count hysteresis, capped ejection and a panic fallback.
- [Escalation policies](/raw/escalation-policies.md) [Observability & alerting · medium]: Route each incident through ordered levels on timers until someone acknowledges it, with rotation lookup, dedup keys, snooze, loops and durable timers.
- [Deterministic bucketing](/raw/deterministic-bucketing.md) [Builds & rollouts · low]: Hash a stable unit id with a per-purpose salt into a bucket; "in" means bucket below the percentage, so assignment is stateless, repeatable and only grows on ramp-up.
- [Hierarchical state machine](/raw/hierarchical-state-machine.md) [Rules, state machines & events · low]: Nest states so a substate inherits its parent's reactions and only overrides what differs, with ordered entry and exit actions along the path.
- [Rete rules engine](/raw/rete-rules-engine.md) [Rules, state machines & events · medium]: Match many rules against changing facts by caching partial matches in a shared network, so each change only does the work it actually affects.
- [Complex event processing](/raw/complex-event-processing.md) [Rules, state machines & events · medium]: Standing pattern queries run as per-key state machines over the live event stream, with time-based expiry; events flow through stored queries instead of queries scanning stored data.

## Security
Crypto primitives you can actually use, auth, secrets and defending real systems.
- [AEAD (AES-GCM, ChaCha20-Poly1305)](/raw/aead-aes-gcm-chacha20.md) [Crypto primitives · low]: Authenticated encryption that encrypts and detects tampering in one call; the only kind of symmetric encryption you should use.
- [Password hashing (Argon2id)](/raw/password-hashing-argon2.md) [Crypto primitives · low]: Memory-hard, salted, deliberately slow hashing so stolen password databases can't be cracked cheaply on GPUs.
- [Digital signatures (Ed25519)](/raw/digital-signatures-ed25519.md) [Crypto primitives · low]: Small, fast, deterministic public-key signatures that prove who produced a message; the default for tokens, releases and protocols.
- [Cryptographic hashes (SHA-2, BLAKE3)](/raw/crypto-hash-sha2-blake3.md) [Crypto primitives · low]: Collision-resistant fingerprints of data; SHA-256 for interoperability, BLAKE3 for speed, HMAC/HKDF for keyed uses.
- [TLS 1.3](/raw/tls-1-3.md) [Crypto primitives · medium]: The standard encrypted, authenticated transport; one round trip, only forward-secret AEAD suites, and little left to misconfigure.
- [ECDSA signatures](/raw/ecdsa-signatures.md) [Crypto primitives · low]: The elliptic-curve signature standardised in FIPS 186-5 (P-256) and used by secp256k1 ledgers; 64-byte signatures, but a repeated or biased nonce leaks the private key.
- [ECDH key exchange (X25519, P-256)](/raw/ecdh-key-exchange.md) [Crypto primitives · low]: Each side multiplies the other's public curve point by its own scalar and both get the same point; always validate the peer key and run the result through a KDF.
- [Message authentication codes (HMAC, CMAC, Poly1305, KMAC)](/raw/message-authentication-codes.md) [Crypto primitives · low]: A keyed short tag proving a message is unmodified and came from a key holder; pick HMAC, CMAC, KMAC or a one-time polynomial MAC by what primitive you already have.
- [HKDF key derivation (extract-and-expand)](/raw/key-derivation-hkdf.md) [Crypto primitives · low]: HMAC-based two-step key derivation: extract a uniform pseudorandom key from any secret, then expand it into as many context-bound keys as you need.
- [Sessions vs tokens](/raw/session-vs-token-auth.md) [Authentication & authorization · low]: Opaque server-side sessions in cookies for browsers, short-lived signed tokens between services; revocation decides most cases.
- [OAuth 2 and OpenID Connect](/raw/oauth2-oidc.md) [Authentication & authorization · low]: Delegated authorization (OAuth 2) and login on top of it (OIDC); use authorization code + PKCE for every user-facing client.
- [Passkeys (WebAuthn)](/raw/passkeys-webauthn.md) [Authentication & authorization · low]: Phishing-resistant login with a per-site key pair held by the device or password manager; the server stores only a public key.
- [Authorization models (RBAC, ABAC, ReBAC)](/raw/authorization-models.md) [Authentication & authorization · low]: How to decide who may do what to which object; roles for coarse rules, relationships for sharing, and checks on every object.
- [JSON Web Token (JWT)](/raw/jwt.md) [Authentication & authorization · low]: A signed, URL-safe token carrying claims; the verifier's job is the checklist (pinned algorithm, key by kid, exp, aud, iss), not the format.
- [One-time codes (HOTP, TOTP)](/raw/totp-hotp.md) [Authentication & authorization · low]: Short numeric codes derived from a shared secret plus a counter or the clock (HOTP, TOTP), or random codes sent by SMS or email; safe only with expiry, single use and attempt limits.
- [Password-authenticated key exchange (PAKE)](/raw/password-authenticated-key-exchange.md) [Authentication & authorization · low]: Both sides blind a Diffie-Hellman message with a password-derived group element, so an attacker gets one guess per run and nothing to brute-force offline.
- [AKA (authentication and key agreement)](/raw/aka-authentication.md) [Authentication & authorization · medium]: Symmetric-key challenge-response in which a chip and its home server prove knowledge of one key, with a sequence number for freshness, and derive session keys.
- [OWASP Top 10 risks](/raw/owasp-top-risks.md) [Application security · low]: The web and API vulnerability classes that cause most real breaches, each with the one structural fix that removes it.
- [Input validation and injection](/raw/input-validation-and-injection.md) [Application security · low]: Keep untrusted data as data: parse it into types at the boundary, and never splice it into code, queries, shells or HTML.
- [JSON Schema validation](/raw/json-schema-validation.md) [Application security · low]: Compile a JSON Schema once, then check every untrusted document against it, within hard size and depth limits, and report failures as JSON Pointers.
- [Unicode confusables](/raw/unicode-confusables.md) [Application security · medium]: UTS #39 maps every string to a "skeleton" so look-alikes collide, and restricts script mixing so most spoofs never get registered.
- [Coverage-guided fuzzing](/raw/coverage-guided-fuzzing.md) [Application security · medium]: Mutate inputs, run an instrumented target, and keep any input that reaches a new code edge; feedback turns blind guessing into incremental search.
- [Secrets management](/raw/secrets-management.md) [Operational security · low]: Keep keys and passwords out of code and logs, give workloads short-lived identity instead of static keys, and make rotation routine.
- [Software supply chain security](/raw/supply-chain-security.md) [Operational security · low]: Control what code enters your build and prove what comes out: lockfiles, vetted updates, hardened CI, signed artifacts with provenance.
- [Least privilege and isolation](/raw/least-privilege-and-isolation.md) [Operational security · low]: Assume every component will be compromised and limit what it can then reach: narrow identities, separate accounts, sandboxed processes.
- [Tamper-evident audit log](/raw/tamper-evident-audit-log.md) [Operational security · medium]: An append-only log whose Merkle root, signed per batch, lets anyone verify an entry is present and history was never rewritten, with log-size proofs.
- [Signed update metadata (TUF)](/raw/signed-update-metadata.md) [Operational security · medium]: Separate signing roles with thresholds sign small metadata pinning file hashes, versions and expiry, so clients detect rollback, freeze and mix-and-match and recover by rotating the root.
- [Envelope encryption](/raw/envelope-encryption.md) [Applied cryptography · medium]: Encrypt each object with its own data key and wrap that key under a KMS-held key, so rotation re-wraps 60 bytes and deleting a key shreds data.
- [Format-preserving encryption](/raw/format-preserving-encryption.md) [Applied cryptography · low]: Encrypt a digit or character string into another string of the same length and alphabet with a keyed Feistel network, reversible with the key and a context tweak, without a lookup table.
- [Secure memory zeroization](/raw/secure-memory-zeroization.md) [Applied cryptography · low]: Keep secrets in one locked, fixed-size, non-copyable region, erase them with writes the compiler must keep, and exclude them from dumps and swap.
- [Shamir secret sharing (k-of-n)](/raw/shamir-secret-sharing.md) [Multi-party & privacy-preserving crypto · low]: Split a secret into n shares so any k reconstruct it and any k-1 reveal nothing at all, using a random polynomial over a finite field.
- [Policy engines (PDP/PEP, Cedar, Rego, ReBAC)](/raw/policy-engine.md) [Access control & request signing · medium]: Decide allow/deny for (principal, action, resource, context) in a separate engine with default deny, forbid-wins and an auditable list of determining policies.
- [Row-level security (multi-tenant isolation in the data layer)](/raw/row-level-security.md) [Access control & request signing · low]: Append a policy predicate to every query inside the database, so a forgotten WHERE tenant_id = ? in application code cannot leak another tenant's rows.
- [Capability-based security (object capabilities)](/raw/capability-based-security.md) [Access control & request signing · low]: Authority is a handle you hold, not an identity you have: code can only act on objects it was explicitly given handles to, and handles can only be narrowed and passed on.
- [Signed URLs](/raw/signed-urls.md) [Access control & request signing · low]: A URL carrying its expiry and a MAC or signature over method, path and query, so a verifier holding the key needs no lookup.
- [Transparency log](/raw/transparency-log.md) [Certificates & PKI · medium]: A public append-only Merkle tree whose signed heads let anyone verify an entry is present and history was only extended, with log-size proofs.
- [Mutual TLS](/raw/mutual-tls.md) [Certificates & PKI · low]: TLS where the client also proves a certificate key, so every connection carries a verified, rotatable machine identity.
- [Workload identity (SPIFFE-style)](/raw/workload-identity.md) [Certificates & PKI · medium]: A local agent works out which workload is calling, then hands it a short-lived signed identity that it renews automatically; no secret is shipped in advance.
- [SSH protocol (transport, auth, channels)](/raw/ssh-protocol.md) [Secure channels & messaging · low]: A three-layer protocol on one TCP connection: encrypted packet transport, user authentication, then multiplexed channels with windows for shells, files and port forwards.
- [WireGuard](/raw/wireguard.md) [Secure channels & messaging · low]: A UDP tunnel whose peers are public keys, with a 1-RTT Noise handshake, one fixed cipher suite and a key-to-address routing table.
- [Hardware security module (HSM)](/raw/hardware-security-modules.md) [Hardware trust · medium]: A tamper-resistant device or service that generates keys, signs, decrypts and wraps with them internally, and releases a key only as ciphertext.
- [Secure boot chain](/raw/secure-boot-chain.md) [Hardware trust · low]: Each boot stage verifies the signature of the next before running it, anchored in an immutable ROM key hash, with version counters against downgrade and a TPM log of what ran.
- [Replay protection window](/raw/replay-protection-window.md) [Hardware trust · low]: A highest-seen counter plus a bitmap of the last W numbers rejects duplicates and stale messages in O(1) with a few hundred bytes of state.
- [Process sandboxing](/raw/process-sandboxing.md) [Sandboxing & isolation · medium]: Run risky work in a separate, deliberately powerless process and let a small privileged broker do the few things it needs, over a narrow pipe.
- [Bot detection](/raw/bot-detection.md) [Abuse & bot defense · medium]: Combine declared identity, rate and timing, network, behaviour and integrity signals into one score per client, then map thresholds to allow, log, limit, challenge or block.
- [Behavioral biometrics](/raw/behavioral-biometrics.md) [Abuse & bot defense · medium]: Build a per-user profile of input timing and motion, score each new session by distance to it, and feed the result into a risk score instead of a verdict.
- [Device fingerprinting](/raw/device-fingerprinting.md) [Abuse & bot defense · medium]: Collect stable and volatile device signals, hash the stable core for exact lookup, fuzzy-match the rest with drift tolerance, and feed the result into a risk score.
- [Reputation scoring](/raw/reputation-scoring.md) [Abuse & bot defense · medium]: Turn per-entity good/bad event counts into a trust score that forgets old evidence, borrows strength from parent groups for new keys, and maps to allow, challenge or block.
- [Data masking](/raw/data-masking.md) [Privacy engineering · medium]: Hide sensitive field values from people and systems that don't need them, by masked copies or role-based masking at read time, while keeping joins and formats working.

## Programming languages
Which language for which job, and what each costs you.
- [Choosing a language](/raw/choosing-a-language.md) [Choosing · low]: The master decision table: which language for which job, what it costs in speed, memory, hiring and build pain, and when to mix them.
- [Rust](/raw/rust.md) [Systems languages · low]: C-level speed without a garbage collector, with memory and data-race safety checked at compile time; paid for in learning curve and compile time.
- [C and C++](/raw/c-and-cpp.md) [Systems languages · low]: Maximum control and the largest native ecosystem (engines, drivers, HPC, finance), at the price of undefined behavior and memory-safety bugs you must actively prevent.
- [Zig](/raw/zig.md) [Systems languages · low]: A small, explicit C replacement: no hidden allocations or control flow, compile-time code instead of macros, and the best cross-compiling toolchain around; still pre-1.0.
- [Go](/raw/go.md) [Managed & backend · low]: A small, boring language with goroutines, a low-pause GC, fast compiles and single static binaries; the default for network services and infrastructure tools.
- [Java and Kotlin](/raw/java-and-kotlin.md) [Managed & backend · low]: The JVM: near-native speed after JIT warmup, low-pause GCs, virtual threads and the deepest enterprise ecosystem; Kotlin is the nicer language on top.
- [C#](/raw/csharp.md) [Managed & backend · low]: Fast managed language on .NET: JIT or native AOT, value types and spans for low-allocation code, async/await, and Unity/Godot for games.
- [Python](/raw/python.md) [Dynamic & glue · low]: The fastest language to write and the home of ML and data science; slow as an interpreter, fast when C/CUDA libraries do the work.
- [TypeScript and JavaScript](/raw/typescript-and-javascript.md) [Dynamic & glue · low]: The only first-class browser language, also a fast-enough server runtime with a single-threaded event loop; TypeScript adds static types that vanish at runtime.
- [SQL](/raw/sql.md) [Specialized · low]: The declarative language for relational data: you state the result, the planner picks the algorithm; mastering indexes, joins and transactions beats any ORM.
- [CUDA and GPU languages](/raw/cuda-and-gpu-languages.md) [Specialized · low]: Programming GPUs: thousands of lockstep threads, bound by memory bandwidth; libraries first, Triton for fused kernels, CUDA C++ for peak speed.
- [Erlang and Elixir](/raw/erlang-elixir.md) [Specialized · low]: The BEAM VM: millions of isolated, preemptively scheduled processes with supervisors that restart failures; unmatched for connection-heavy, always-on systems, weak at number crunching.
- [WebAssembly](/raw/webassembly.md) [Specialized · low]: A portable, sandboxed bytecode that browsers and server runtimes compile to near-native code; pick it for hot kernels, safe plugins and one codebase everywhere, not for DOM glue.

## Compilers & runtimes
Parsing, type checking, IR and optimization, code generation, binaries, interpreters, JITs and garbage collectors.
- [Recursive-descent parsing](/raw/recursive-descent-parsing.md) [Parsing & syntax trees · low]: Hand-written top-down parser with one function per grammar rule; simple, fast, with full control over error messages and recovery.
- [Pratt parsing](/raw/pratt-parsing.md) [Parsing & syntax trees · low]: Table-driven expression parsing with one loop and a numeric binding power per operator; the compact core of precedence handling in hand-written parsers.
- [Incremental parsing](/raw/incremental-parsing.md) [Parsing & syntax trees · medium]: Reparse only the region an edit damaged and splice the new subtrees into the old tree, sharing everything else; O(edit) instead of O(file).
- [Name resolution](/raw/name-resolution.md) [Names & types · low]: Bind every use of a name to its declaration with a scope stack, handling shadowing, hoisting and closure capture in one AST walk.
- [Bidirectional type checking](/raw/bidirectional-type-checking.md) [Names & types · medium]: Split checking into two mutually recursive modes, check against a known type and synthesize an unknown one, so annotations are needed only at a few points.
- [SSA form](/raw/ssa-form.md) [IR & program analysis · low]: Give every variable exactly one definition, merging at joins with phi functions; def-use becomes explicit and optimizations turn sparse and cheap.
- [Control-flow graph](/raw/control-flow-graph.md) [IR & program analysis · low]: Split a linear instruction list into basic blocks and connect them by jumps; the graph every optimizer, SSA builder and dataflow pass walks.
- [Dataflow analysis](/raw/dataflow-analysis.md) [IR & program analysis · medium]: Compute a fact per program point (live variables, reaching definitions, available expressions) by iterating transfer functions over the CFG to a fixed point.
- [Escape analysis](/raw/escape-analysis.md) [IR & program analysis · medium]: Prove which allocations never outlive or leave their creator, then put them on the stack, split them into scalars, or drop their locks.
- [Structured control flow](/raw/structured-control-flow.md) [IR & program analysis · medium]: Turn a jump graph into nested block, loop and if constructs with numbered breaks; reducible graphs need no duplication.
- [Instruction selection](/raw/instruction-selection.md) [Code generation · medium]: Cover the IR with target instruction patterns at least cost; greedy maximal munch is simple, dynamic programming over a tree or DAG is optimal.
- [Register allocation](/raw/register-allocation.md) [Code generation · medium]: Map unlimited virtual registers onto a few machine registers, spilling the rest to the stack; linear scan is fast, graph coloring and splitting allocators give better code.
- [Linking and relocation](/raw/linking-and-relocation.md) [Code generation · medium]: The linker merges object files, matches each undefined name to one definition, assigns addresses and patches every recorded reference (relocation); dynamic linking defers part of that to load time.
- [WebAssembly binary format](/raw/webassembly-binary-format.md) [Code generation · low]: A section-based module container with LEB128 integers and structured, typed code, so untrusted bytes are validated in one pass and compiled as they stream in.
- [Bytecode compilation](/raw/bytecode-compilation.md) [Code generation · low]: Flatten an AST into compact linear instructions with a constant pool, backpatched jumps and slot-numbered locals, so a small loop can execute it.
- [FFI bindings generation](/raw/ffi-bindings-generation.md) [Code generation · medium]: Describe a library's C-ABI surface once (header, attributes or IDL) and generate the declarations, converters and wrappers for each caller language.
- [Debug info (DWARF)](/raw/debug-info-dwarf.md) [Binaries & debugging · medium]: DWARF stores a tree of typed entries (DIEs), a line-number bytecode, unwind tables and location expressions that map machine state back to source; pick it for ELF/Mach-O debug builds.
- [Code coverage instrumentation](/raw/code-coverage-instrumentation.md) [Binaries & debugging · low]: Insert counters into compiled code to record which blocks, edges or lines ran; a spanning tree of the control-flow graph cuts the counters needed.
- [JIT compilation](/raw/jit-compilation.md) [Interpreters & JITs · medium]: Run cold code in a cheap tier, count executions, and compile only what gets hot, trading warm-up time and memory for peak speed.
- [Inline caches](/raw/inline-caches.md) [Interpreters & JITs · medium]: Per-call-site cache of "this object shape, that slot or target", turning dynamic property and method lookup into a compare and a load.
- [Hidden classes (shapes)](/raw/hidden-classes-shapes.md) [Interpreters & JITs · low]: Objects that gained the same properties in the same order share one layout descriptor, so a property is an index and the layout is one comparable id.
- [Deoptimization](/raw/deoptimization.md) [Interpreters & JITs · medium]: Speculate with guards, and on failure rebuild the slow-tier frames from compile-time metadata and resume there, so optimized code may assume the common case.
- [On-stack replacement](/raw/on-stack-replacement.md) [Interpreters & JITs · medium]: Count loop back-edges, compile code that can start at a loop header, and copy the live frame state into it, so one running call gets faster.
- [Value tagging and NaN-boxing](/raw/value-tagging-nan-boxing.md) [Interpreters & JITs · low]: Pack the type and the payload of any value into one 64-bit word, using spare low bits of aligned pointers or the unused payload of NaNs, so type tests are one mask compare.
- [Closures and upvalues](/raw/closures-upvalues.md) [Interpreters & JITs · low]: How interpreters and compilers let a function keep using its enclosing variables after they return: flat closures, open and closed upvalues, closure conversion, capture by value or reference.
- [Executable memory under W^X](/raw/executable-memory-w-xor-x.md) [Interpreters & JITs · low]: How JITs and code generators emit machine code under W^X: RW to RX flips, dual mappings, per-thread write toggles, and the instruction-cache flush.
- [Instruction metering](/raw/instruction-metering.md) [Interpreters & JITs · low]: Charge a fuel budget per instruction or per basic block and trap at zero, so untrusted code is bounded by work done, deterministically.
- [Hot reloading](/raw/hot-reloading.md) [Interpreters & JITs · medium]: Replace code in a running process by swapping an indirection point, then migrate the live state to the new layout at a safe moment.
- [Mark-sweep garbage collection](/raw/mark-sweep-gc.md) [Garbage collection · low]: Find everything reachable from the roots, free the rest in place; handles cycles, never moves objects, and is the base of most production collectors.
- [Generational garbage collection](/raw/generational-gc.md) [Garbage collection · medium]: Split the heap by age, collect the small young region often and cheaply, and rarely touch old data; wins whenever most objects die young.
- [Incremental and concurrent garbage collection](/raw/incremental-concurrent-gc.md) [Garbage collection · medium]: Trace the heap in small steps or on other threads while the program runs, and use barriers to keep the collector's view correct.
- [Reference counting](/raw/reference-counting.md) [Garbage collection · low]: Keep a count of owners in each object, free it when the count hits zero; deterministic and local, but pays on every copy and leaks cycles.
- [Code symbol indexing](/raw/code-symbol-indexing.md) [Developer tooling · medium]: Extract definitions and references per file, give each symbol a stable string id, and store symbol to occurrences, re-indexing only files whose content hash changed.
- [Language server protocol](/raw/language-server-protocol.md) [Developer tooling · medium]: One JSON-RPC conversation over a pipe lets any editor drive any language's analysis server; the cost is keeping a live, edited document in sync and answering before it changes.
- [Text position encoding](/raw/text-position-encoding.md) [Developer tooling · low]: Store byte offsets, convert to (line, column) on demand with a line-start table and binary search, and count columns in the unit the peer negotiated.

## Cloud services
What each cloud building block is for, what it costs, and when to self-host.
- [Cloud providers compared](/raw/cloud-providers-compared.md) [Choosing · medium]: AWS, GCP and Azure sell breadth and managed services; Hetzner, OVH, Cloudflare and neoclouds sell raw compute, bandwidth or GPUs at a fraction of the price.
- [Self-host vs managed](/raw/self-host-vs-managed.md) [Choosing · medium]: Managed services trade a 2-5x price premium for not paging your team; self-hosting wins once the bill is large, steady and the system is well understood.
- [VMs and bare metal](/raw/vms-and-bare-metal.md) [Compute · low]: Rented virtual machines and dedicated servers: instance families, local NVMe vs network disks, spot pricing, and when a $100 bare-metal box beats a $1000 VM.
- [Containers and Kubernetes](/raw/containers-and-kubernetes.md) [Compute · low]: Containers package a service with its dependencies; Kubernetes schedules them across machines. Use the smallest orchestrator that does the job.
- [Serverless functions](/raw/serverless-functions.md) [Compute · low]: Lambda, Cloud Run functions, Azure Functions and Cloudflare Workers run code per request and bill per millisecond; ideal for spiky or glue workloads, costly at steady high load.
- [GPU cloud](/raw/gpu-cloud.md) [Compute · low]: Where to rent GPUs for training and inference: hyperscalers for integration, neoclouds for price, spot and marketplaces for cheap batch work; interconnect decides multi-node training.
- [Object storage](/raw/object-storage.md) [Data services · low]: S3-compatible blob storage at cents per GB-month with 11 nines durability; pick by egress price, request price and latency, not by storage price alone.
- [Managed databases](/raw/managed-databases.md) [Data services · low]: RDS, Aurora, Cloud SQL, Spanner, DynamoDB, Cosmos DB and the Postgres startups: what each is for, what it costs, and the limits that bite.
- [Caches and queues](/raw/caches-and-queues.md) [Data services · low]: Managed Redis/Valkey and Memcached for hot data; SQS, Pub/Sub, Service Bus, Kafka and NATS for moving work and events. Pick by delivery semantics, ordering and throughput.
- [CDN and edge](/raw/cdn-and-edge.md) [Network & edge · medium]: CDNs cache content in hundreds of PoPs near users, cutting latency and egress bills; edge compute runs small code there. Bandwidth price spreads 10x between providers.
- [DNS and load balancers](/raw/dns-and-load-balancers.md) [Network & edge · low]: DNS routes users to a region, L4 load balancers spread connections, L7 balancers route requests; managed ones cost per hour plus per unit of traffic.
- [Observability](/raw/observability.md) [Operations · medium]: Metrics, logs and traces tell you what broke and why; the cost is driven by log volume and metric cardinality, so design for both from day one.
- [Cost control](/raw/cost-control.md) [Operations · medium]: Cloud bills grow from idle resources, egress, cross-zone traffic and on-demand pricing; tagging, budgets, commitments, spot and architecture fixes cut them 30-70 %.
- [Infrastructure as code](/raw/infrastructure-as-code.md) [Operations · medium]: Declare servers, networks, DNS and permissions in versioned files and let a tool converge reality to them; Terraform/OpenTofu for most teams, Pulumi or CDK when you want a real language.