如果您是授权合作伙伴、《世界报》订阅者,或希望获得访问此内容的授权,请联系:licensing[@]groupelemonde.fr,并附上包含您的IP地址和请求ID (RID) 的此错误页面的副本。
英文版:您的流量已被识别为自动化(机器人活动)。如果您是授权合作伙伴、《世界报》订阅者,或希望请求访问此内容的权限,请联系:licensing[@]groupelemonde.fr,并附上显示您的IP地址和请求ID (RID) 的此错误页面的副本。
IP:47.245.80.60
RID:a12c3984f47d46b29d12000000000001
## 正则表达式引擎中长期存在的缺陷
数十年以来,正则表达式引擎一直错误地宣传了查找*所有*匹配项的线性时间复杂度。虽然单次匹配的性能可以是线性的,但迭代所有匹配项会引入隐藏的二次方时间复杂度(O(m*n²)),这个问题早在 1970 年代就被发现。这是因为当引擎在搜索多个重叠匹配项时,可能会陷入重复扫描输入的困境——例如,将 `.*a|b` 模式应用于一串 ‘b’ 字符。
这个问题影响了几乎所有引擎(RE2、Go、Rust 的 regex crate、.NET),并且即使在那些旨在避免回溯的引擎中仍然存在。一种解决方案是限制搜索范围——在第一次匹配后停止可以恢复线性时间,但会改变预期的行为。
作者的项目 RE# 旨在解决这个问题。它采用两遍扫描方法:反向扫描以标记潜在的匹配起点,然后进行正向扫描以确定每个点的最长匹配项。一种“加固”模式即使在面对恶意输入时也能保证线性时间,但会降低简单模式的性能。RE# 的性能与现有引擎相媲美或超越现有引擎,尤其是在复杂模式上,利用了跳跃加速和高效 DFA 构建等技术。
虽然 RE# 目前不支持捕获组和惰性量词,但它提供了布尔运算符和独特的流处理方法,使其成为真正高效可靠的正则表达式匹配的重要一步。
## 理想的衰落:对现代计算的批判性审视
本文认为备受赞誉的“Unix哲学”——强调简洁、单一用途工具和可组合性——在很大程度上已经消亡,而现代计算则是一个复杂且常常设计糟糕的“垃圾堆”。作者认为,这种哲学的模糊性(存在多种解释)使其能够方便地适应,最终侵蚀了其核心原则。
虽然欣赏精简工具和shell脚本的*理念*,但作者指出现实世界的例子——例如令人惊讶的复杂的`cat`命令和多功能的`curl`——违背了该哲学的原则。这种趋势超出了Unix世界;Windows和GUI软件优先考虑集成、功能丰富的体验,而不是简约的、链式工具,常常牺牲效率来换取用户友好性。
核心问题不在于技术,而在于社会。开发者过度概括,寻求“一刀切”的解决方案,而这些解决方案不可避免地无法满足多样化的需求。此外,开源最初的反叛精神已被稀释,变得越来越公司化和顺从。作者提倡批判性思维,拥抱多样性,并优先考虑可修改性,敦促读者定义自己的原则,而不是盲目地追随趋势或意识形态。最终,认识到计算的内在复杂性是构建更好系统的关键。
## Baochip-1x 的 BIO:一种基于 RISC-V 的 I/O 协处理器
BIO 是一种为 Baochip-1x 设计的 I/O 协处理器,Baochip-1x 是一款 22 纳米开源 SoC。作为树莓派 PIO 的替代方案,BIO 旨在将 I/O 任务从主 CPU 卸载,实现实时应用至关重要的确定性时序。
最初的探索涉及复制 PIO 的架构,但 FPGA 实现显示其资源消耗出乎意料地大——甚至超过了 CPU 核心的面积并影响了时序。这促使转向基于 RISC-V 的设计,利用四个紧凑的 RV32E 核心,并配备专门的寄存器队列用于核心间通信和 I/O 控制。
BIO 利用“快照到量子”机制实现精确的时序,并通过 BDMA 扩展支持 DMA。开发者可以使用汇编语言或利用基于 Zig 的新型 C 工具链来编程 BIO,从而实现更复杂的功能。与 PIO 相比,BIO 以牺牲峰值速度来换取面积效率,但它提供了一个更灵活且可能更具可扩展性的解决方案,可以舒适地适应 FPGA 约束,并在 ASIC 实现中实现更高的时钟速率。
代码和文档等资源可在 GitHub 上获取,Baochip-1x 可通过 Crowd Supply 购买。