算法与理论计算机2019arxiv.org
Base64 编码与解码速度接近内存拷贝
Base64 encoding and decoding at almost the speed of a memory copy
进阶 · 约 45 分钟读完前置知识：SIMD/AVX-512 指令集、Base64 编码原理、x86 汇编基础
导读
这篇论文研究如何用 AVX-512 指令（vpermb 和 vpmultishiftqb）实现接近内存拷贝速度的 Base64 编解码。作者 Wojciech Muła 等人给出了高度优化的 SIMD 实现，代码已开源。
HN 关注点：Base64 编解码是常见性能瓶颈，用最新 AVX-512 指令把速度推到接近 memcpy 的极限，对 HN 上的系统性能爱好者很有吸引力。
HN 评论精选
这几条评论里：质疑 1 补充 3
补充指出该实现依赖的指令只有很新的少数 Intel CPU 才支持
很好地利用了 AVX-512 VBMI！不过要注意，支持所用两条指令（vpermb 和 vpmultishiftqb）的 Intel 处理器并不多：Cannon Lake i3（因 Intel 10nm 工艺延期而少见），以及 2019 年 9 月发布的 Ice Lake i3/i5/i7。
emirp查看英文原文
Great use of AVX-512 VBMI! Note that not many Intel processors support the two specific CPU instructions used (vpermb and vpmultishiftqb). Cannon Lake Core i3 (not many of these around due to delays with intel's 10nm fabrication) Ice Lake Core i3, i5 and i7: Released in September 2019
质疑质疑 Base64 本身的必要性，认为优化它不如避免使用它
如果 Base64 解码速度对你的应用有影响，你应该反思为什么要用 Base64 传输数据——这是 1970 年代的巧妙 hack，不可读、浪费 30% 带宽、破坏压缩、浪费内存、通常难以随机访问，总体上是个坏主意。
londons_explore查看英文原文
If base64 decoding speed makes a difference in your application, you should be considering why you are transmitting data in base64, a neat hack from the 1970's, which is non-human-readable, wastes 30% of the network bandwidth, kills compression, wastes RAM, is typically hard to random-access, and is generally a bad idea all round.
补充推荐作者的其他 SIMD 优化工作
Wojciech Muła 真正精通 SIMD，他在该领域的其他工作非常值得一看：http://0x80.pl/articles/index.html
nathell查看英文原文
Wojciech Muła really groks SIMD. It's well worth exploring his other work in that area: http://0x80.pl/articles/index.html
补充提供开源代码链接
代码地址：https://github.com/WojciechMula/base64-avx512
cperciva查看英文原文
The code: https://github.com/WojciechMula/base64-avx512
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2019Hacker News 讨论帖344 分 · 115 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选