系统内核
  1. 首页
  2. 系统内核

列表

并查集深度实战：从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解

并查集深度实战：从等价划分、路径压缩到按秩合并与可撤销/持久化的工程全解

系统拆解并查集（Disjoint Set Union）的第一性原理：用有根森林表示等价类划分，find/union 如何把"是否连通"转化为"根是否相同"。从朴素实现的 O(n) 退化陷阱出发，推导两大核心优化——路径压缩（迭代版，规避 Python 递归爆栈）与按秩/按大小合并——二者叠加把摊还复杂度钉死在反阿克曼函数 α(n)（物理可观测尺度内 α(n)≤4，近似常数）。进而展开变体谱系：加权/种类并查集、可撤销并查集（仅按大小合并+栈回滚，禁用路径压缩）、持久化并查集、DSU on tree、离线动态连通性、网格并查集。给出 Kruskal MST/连通分量/图像分割/等式约束/类型合一 等应用对照表、12 项生产陷阱清单（递归压缩爆栈、索引混淆、可撤销误用压缩等）与可复现 Python 工具箱。与本站 布隆过滤器/Count-Min Sketch/HyperLogLog/布谷鸟哈希 共同构成"概率与高性能数据结构工程"系列，前者提供确定性精确的等价类划分，后者提供概率近似的集合成员/频率/基数估计，工程栈中互补共存。
Linux内核 2026年10月09日
布谷鸟哈希深度实战：从双哈希候选、驱逐重定位到分桶与 Stash 的生产级工程全解

布谷鸟哈希深度实战：从双哈希候选、驱逐重定位到分桶与 Stash 的生产级工程全解

系统拆解布谷鸟哈希的第一性原理：每个键只有两个候选桶（双哈希），查询最坏 O(1) 且与负载率无关；推导插入时"踢走占用者（evict/kick）"的驱逐重定位算法、其终止性与失败概率，以及临界负载率 α*≈0.49（k=2）的由来；解析 Stash 旁路数组把溢出概率压到 O(1/√N) 的工程技巧、rehash 扩容换种子打破置换环的方法。展开 d-left hashing、分桶布谷鸟（b=4 推到负载率 0.99+）、计数布谷鸟、并发布谷鸟（多核锁粒度/tombstone 退化）等变体，并给出 Cuckoo Filter——可删、比 Bloom 省 1.5~2 倍空间的近似成员查询替身。附带可插拔双哈希、带 Stash 与自动扩容的生产级 Python 实现（插入/查询/删除/重建），与链地址/线性探测/布隆的分工对照表，以及 12 项生产陷阱清单（哈希相关性、MAX_LOOP、Stash 增长、扩容换种子、并发 tombstone、分桶 b 过大等）。与本站《布隆过滤器》(16214)、《Count-Min Sketch》(16270)、《HyperLogLog》(16312) 共同构成"概率与高性能数据结构工程"系列，补齐确定性 O(1) 查询 + 可删除 + 高负载率维度。
Linux内核 2026年10月09日
FlashAttention 算法深度解析：从 IO-Aware 优化到 GPU 硬件极致

FlashAttention 算法深度解析：从 IO-Aware 优化到 GPU 硬件极致

FlashAttention 通过 IO-Aware 的 Tiling + Recomputation 策略，将 Self-Attention 的 HBM 访问复杂度从 O(N²) 降至 O(N²/d)，在不牺牲数学精度的前提下实现 2-4× 端到端训练加速。本文深入推导 Online Softmax 数学基础、解析 FlashAttention/2/3 三代算法演进、剖析 Hopper/Tensor Core 适配优化，并给出一套完整的工程性能分析框架。
GPU并行计算 2026年10月09日
HyperLogLog 深度实战：从 Flajolet-Martin 草图、调和均值估计到 HLL++ 稀疏表示与可合并基数估计的工程全解

HyperLogLog 深度实战：从 Flajolet-Martin 草图、调和均值估计到 HLL++ 稀疏表示与可合并基数估计的工程全解

系统拆解 HyperLogLog 的第一性原理：从 Flajolet-Martin 草图、LogLog 分桶到 HLL 用调和均值替代算术均值抑制离群桶，把标准误差压到 1.04/√m；推导哈希分桶、ρ(rank) 寄存器、原始估计量 E=α·m²/Σ2^{-M[j]} 与 α_m 校正常数、误差表；解析小基数 Linear Counting 混合与 HLL++ 的 empirical bias correction、稀疏表示（varint 编码）与 64 位修正；论证逐桶 max 的可合并性如何支撑分布式/流式基数聚合；给出与 Bloom/Count-Min 的分工对照表、可合并的生产级 Python 实现（dense/sparse 切换、序列化、merge）与 12 项生产陷阱清单（哈希一致性、p 不可变、合并前不可先平均、误差带展示等）。与本站《布隆过滤器》(16214)、《Count-Min Sketch》(16270) 共同构成概率数据结构工程三部曲。
Linux内核 2026年10月09日
Linux 内核 NAPI 网络接收机制深度工程实战：从硬中断到零拷贝的完整数据通路

Linux 内核 NAPI 网络接收机制深度工程实战：从硬中断到零拷贝的完整数据通路

深入剖析 Linux 内核 NAPI(New API)网络接收机制的核心架构与工程实战，涵盖混合中断轮询模型、Gro合并机理、多队列分发(RPS/RSS)、busy polling 超低延迟优化、XDP协同、page_pool 回收机制。结合 25G Mellanox 网卡调优案例，从单核 2.1MPS 到8核14.8MPS，逐层拆解 NAPI 调度流程、poll函数实现、net_rx_action主循环、ADQ通道隔离及中断延迟机制。
Linux内核 2026年10月09日