双语

The quadratic problem nobody fixed
2 months ago
- 正则表达式引擎在查找所有匹配时存在O(n²)复杂度问题，这是自1970年代就存在的长期难题
- RE2、Go的regexp和Rust的regex crate等引擎承诺的线性时间匹配仅适用于单个匹配，而非全部匹配
- 当处理类似'.*a|b'的模式和'bbbb...'这类输入时，会出现三角累加工作量，导致平方级复杂度
- Aho-Corasick算法(1975)针对固定字符串能以线性时间解决问题，但不适用于正则表达式
- Hyperscan/Vectorscan采用'最早匹配'语义实现线性时间，但会改变匹配结果
- RE#引入双通道算法，在不改变语义的前提下实现线性时间全局匹配
- RE#提供'加固'模式，即使面对对抗性输入也能保证线性时间，但会牺牲部分性能
- 由于更高效的DFA缓存处理，RE#在处理大型字典时性能优于Aho-Corasick
- RE#暂不支持捕获组和惰性量词，专注于POSIX语义和布尔运算
- 名为're'的grep工具利用RE#的布尔运算符实现高级搜索功能
Everything old is new again: memory optimization
2 months ago
- AI反社会人格者买光了全球的内存条，导致消费级设备内存短缺
- 在多年的忽视后，内存优化突然变得至关重要
- 一个简单的Python词频统计脚本就占用了1.3MB内存
- 相同功能的C++程序仅占用100kB（是Python内存占用的7.7%）
- C++通过避免字符串对象、使用string_view实现了更低的内存占用
- C++运行时本身占用70kB内存，其中大部分用于异常处理
- 禁用C++的异常支持后，内存占用可降至21kB（降低98.4%）
- Python的高内存占用源于其运行时环境和内置功能
Debunking Zswap and Zram Myths
2 months ago
- 除非有特殊理由需要使用zram，否则建议优先选择zswap
- zswap与内核内存管理集成，压缩RAM中的页面，并将冷数据分层存储到磁盘
- zram作为有固定容量限制的压缩RAM块设备，满载时可能导致OOM或LRU倒置问题
- 避免zram与磁盘交换分区同时运行，这会导致活跃工作集被推至慢速磁盘而冷页却留在快速RAM中
- 若使用zram，建议配合systemd-oomd或earlyoom等用户空间OOM管理器
- zram在服务器环境中存在内存使用隔离和cgroup隔离问题
- zswap能自动在压缩RAM和磁盘之间分层存储数据，在内存压力下优雅降级
- zram的块设备架构使其像普通存储设备一样工作，导致诸如不必要预读等低效行为
- zswap通过与内存管理集成，可根据压力动态平衡LRU
- 当zram被冷数据填满时会发生LRU倒置，迫使热数据写入磁盘，性能急剧下降
- zram虽然支持回写功能，但需手动配置且缺乏自动分层机制
- zswap通过拒绝压缩率低的页面并将其发送至磁盘，能更好地处理不可压缩数据
- 使用zram可能通过将压力转移至页缓存而增加SSD磨损，导致更多磁盘I/O
- zswap通过充当写入缩减过滤器来减少磁盘写入，可吸收高频页面瞬态
- 出于安全考虑，Fedora默认采用纯zram方案以避免敏感数据持久化存储
- 由于与内核内存管理更好集成及优雅降级特性，zswap适用于大多数使用场景
GitHub is once again down
2 months ago
- GitHub多项服务包括Actions、Issues、Pull Requests、Webhooks、Codespaces及登录功能出现错误率升高现象
- 大部分服务已显现恢复迹象
- Issues、Pull Requests和Webhooks服务仍存在性能降级问题
- GitHub正在积极调查该事件
- 预计下一次更新将在UTC时间21:00前发布
Two Studies in Compiler Optimisations
2 months ago
- 编译器优化可以将看似简单的代码转化为高效的机器码，这通常需要深入理解编译器内部机制才能预测或解释其行为。
- LLVM优化流水线包含多个优化阶段（如InstCombine和CodeGenPrepare），每个阶段针对编译过程中不同层级的优化机会。
- 使用`[[assume]]`属性或断言等编译器提示，可以通过提供变量关系的额外信息来启用特定优化。
- 优化过程中的模式匹配（如InstCombine的窥孔优化）能识别常见代码模式并进行转换，例如用条件移动指令替代除法运算。
- 指令选择阶段（如LLVM的SelectionDAG）会执行目标平台特定的优化，例如将多个字节加载合并为单个宽位加载操作。
- 模板函数有时能通过内联前的常量传播和循环展开，促成更早阶段的优化。
- 编译器优化对代码结构极其敏感：由于优化阶段顺序或模式匹配限制，微小改动可能导致完全不同的优化结果。
- 面向尺寸的优化（`-Os`）有时会抑制本可提升性能的优化，此时需要手动介入（如使用`#pragma unroll`指令）。
- 通过LLVM优化流水线可视化工具等途径理解编译器内部机制，能帮助开发者编写更易被优化的代码。
An Extensive Benchmark of C and C++ Hash Tables
2 months ago
- 文章提出了一个针对C和C++哈希表的基准测试套件，旨在解决现有基准测试中的不足。
- 测试了三种哈希表配置：32位整数键与32位值、64位整数键与448位值、16字符C字符串键与64位值。
- 基准测试包括插入、删除、替换和查找操作，并通过不同负载因子下的性能表现进行衡量。
- 结果展示了多种哈希表的性能表现，包括absl::flat_hash_map、ankerl::unordered_dense、boost::unordered_flat_map和Verstable。
- 关键发现表明，在高负载因子下，SIMD和混合开放寻址/分离链接表表现良好，而基于节点的分离链接表速度较慢。
- 文章最后根据具体用例和性能需求，给出了选择哈希表的建议。
Comprehensive C++ Hashmap Benchmarks (2022)
2 months ago
- 基准测试评估了29种不同的C++哈希表实现，涵盖多种分配器和哈希函数，共计174种组合和1914项基准评估
- 关键测试包括：映射复制、元素插入与删除、随机插入访问、迭代遍历，以及针对整型和字符串的查找操作
- 不同实现间性能差异显著，部分实现在特定领域表现突出，如搜索速度、内存占用或插入/删除效率
- 作者自研的ankerl::unordered_dense::map被强调为全能型选手，具有快速的搜索和迭代性能
- Google的absl::flat_hash_map和absl::node_hash_map在大规模映射中表现优异，但对哈希质量敏感
- Boost的unordered_map在查找速度上较std::unordered_map有显著提升，但在插入、删除和复制操作上较慢
- 专用分配器（如PoolAllocator）可提升基于节点的容器的内存使用效率和性能
- 哈希质量对性能影响重大，std::hash和boost::hash因缺乏雪崩效应在整型处理上表现欠佳
- 测试环境采用隔离核心、禁用频率调节等控制措施，配合特定编译器标志确保结果一致性
- 最终结果以可排序筛选的详细表格呈现，方便用户根据特定性能指标进行查询
Ohm's Peg-to-WASM Compiler
2 months ago
- Ohm 是一个用于 JavaScript 和 TypeScript 的解析工具包，适用于自定义文件格式或构建语言工具。
- 版本 18 是一次完全重写，将语法编译为 WebAssembly，相比先前版本实现了超过 50 倍的速度提升和仅 10% 的内存占用。
- 先前版本采用 AST 解释和 PExpr 树，其中解析表达式通过诸如 'eval' 的方法进行评估。
- 新引擎将语法编译为 WebAssembly，避免了解释开销并内联表达式代码。
- CST 节点通过 Wasm 线性内存中的碰撞分配器管理，采用基于区域的管理方式以降低开销。
- 终端节点通过标记化的 32 位值进行优化，避免每个字符的单独分配。
- 分块绑定使用固定大小的块，通过消除数组大小调整并使回溯成本低廉来提升性能。
- 记忆化采用块稀疏表高效存储解析结果，条目打包为 i32 值。
- 参数化规则通过静态特化处理，为每个参数组合生成唯一的规则体。
- 优化的空格跳过避免在需要之前为空白字符创建 CST 节点，从而提升许多语法解析的性能。
- 额外优化包括单次使用规则内联和预分配固定结构元素的节点。
- 该版本以 beta 形式通过 npm 发布，并感谢资助者和贡献者，如 Alex Warth。

Hasty Briefsbeta

#performance

The quadratic problem nobody fixed

Everything old is new again: memory optimization

Debunking Zswap and Zram Myths

GitHub is once again down

Two Studies in Compiler Optimisations

An Extensive Benchmark of C and C++ Hash Tables

Comprehensive C++ Hashmap Benchmarks (2022)

Ohm's Peg-to-WASM Compiler