Linux内核

基数树(Radix Tree / Patricia Trie)深度实战:从路径压缩、二进制切分到 Linux 页缓存 xarray 与路由最长前缀匹配的工程全解

在「字典树(Trie / 前缀树)深度实战」一文中,我们拆解了 Trie 如何用「字符沿边展开」把前缀共享做到极致,却也暴露了一个结构性代价:当插入大量长键且共享前缀稀疏时,Trie 会膨胀出无数只含单个子节点的「瘦链」节点,内存与指针开销被白白浪费。基数树(Radix Tree,又名 Patricia Trie、压缩前缀树)正是为消灭这些瘦链而生的——它通过**路径压缩(path compres…

哈希表深度实战:从散列函数、拉链/开放寻址到 Robin Hood、完美哈希与并发哈希映射的工程全解

哈希表(Hash Table,又称散列表)是计算机科学里把「均摊 O(1) 查找」从理论变成工业现实的基石:字典、缓存、索引、去重、集合、计数、符号表,底层几乎都是它。本系列已覆盖布隆过滤器、Count-Min Sketch、HyperLogLog、Cuckoo 哈希等「概率/高性能」变体,却独缺最通用的那一枚——标准哈希表本身。本文从散列函数的第一性原理讲起,拆解拉链法与开放寻址的本质差异、负载…

Intel 处理器微架构性能分析:Top-down Microarchitecture Analysis(TMA)方法论文深度实战

> 执行摘要:当一段推理代码跑得比预期慢,绝大多数工程师的第一反应是"加机器"或"换更快的卡"。但在你动硬件之前,真正的问题往往是:**CPU 的每一个时钟周期到底被浪费在了哪里?** CPI(每指令周期数)只能告诉你"慢",却无法告诉你"为什么慢"。Intel 的 Top-down Microarchitecture Analysis(TMA,顶层微架构分析法)把每一个流水线槽位(Pipelin…

Linux 内核 Slab 分配器深度实战:从伙伴系统到对象缓存架构

深入剖析 Linux 内核 Slab 分配器的设计哲学与实现:从伙伴系统的对象缓存需求出发,详解 kmem_cache 数据结构、SLUB 快速路径与慢速路径、三种变体(Slab/Slub/SLOB)对比、缓存着色优化、per-CPU/NUMA 感知分配、自定义缓存实战、调试工具(slub_debug/kmemleak)、常见陷阱诊断,以及 cgroup v2 与 Rust 生态新趋势。