如何评价 GCC 的 C++ 11 正则表达式？ 第1页

GCC 4.9的C++11 <regex>是我写的。没抄boost。

我没细致地测过速度，但是仅仅是个简单的dfs实现，速度应当和boost的差不多。有一套备选实现是Thompson NFA（bfs），禁止back reference，保证多项式级别复杂度（具体来说是O(n_captures * (regex_string.size() + sum_interval_repeat_length) * input_string.size()), 有可能可以用immutable data structure把n_captures去掉，但那样常数就不是大个一星半点了），trunk里有个regex_constants::__polynomial作开关。多项式实现的好处是可用作安全的暴露给用户的服务。在现在的trunk，NFA要保证线性的行为的话控制状态数（目前用宏控制状态数阈值，编译regex时超过该数就抛异常）就行了，也不要乱capture东西（nosub）。做clang fuzzer的kcc同学fuzz过我的bfs，没出什么问题。

已知问题是由于使用递归实现，快是快了点，但是容易爆栈。这这真是不好意思啊都怪我当时太naive全是我的错QAQ。我理想的解法是用类似make_context和swap_context的函数把执行栈开到堆上，每次递归的时候瞄一眼frame pointer，超过了就抛异常，或者接segmented stack。这样编译器各种对函数的优化还是能波及到regex引擎（较之于维护一个在堆上的数据栈来说）。虽然感觉这改动很费劲，但是这也为兹瓷coroutine铺路。

我已经完全重构了一遍，但是libstdc++的维护者没空review，肯定赶不上2016年release，只好先搁着了。计划在这之后做栈优化。也说不定试试编译到DFA优化或者别的魔改。比如现在NFA是在一个vector里面乱序分配的，节点之间都用index指来指去，可能对缓存不是很友好。可以把节点好好排个序，除非遇到branch不然顺序往下读就行了，就跟汇编指令一样。DFA优化即便是带capture我也感觉可行 - 只是感觉。当然，back reference是统统不能有的。这些Russ Cox的博客里都提到了。

这还是大学里做gsoc写的。现在工作了基本没空加很多新优化了，最多修修bug。所以尽人事听天命吧。

写标准regex和自己发明regex最大的不同是得为别人设计的天花乱坠的feature买单。反正我是不开心的。那些讨厌的feature我都没优化。

另外，locale你大爷的。