Fei Yan

Fei Yan

A curious programmer

Categories

Rust文本处理的性能及优化

本文有 9807 字，大约需要 24 分钟可以读完, 创建于 2019-11-29

作为一门秉承零成本抽象这一极具挑战的目标为语言设计核心的静态变成语言，用Rust语言来编写一些文本处理程序可以不需要可以优化就能达到很高的性能。 但是如果我们对已经写就的文本处理程序的性能不甚满意，觉得不够快或者想将它推向性能更高的境地，即需要进一步优化，可能还不得不额外下一些功夫才能做到。

背景

大概一年前，出于实际工作内容的需要，我写过一个简单的针对产品问题报告系统上的数据到处记录的分析程序；最初的目标是在解决问题的同时顺便提高自己对Rust语言的理解； 毕竟对于学习一门难度比较高的技术而言，读多少文档和书都不如拿一些实践中需要解决实际的问题来练手效率更高。

这个问题的核心技术是典型的CSV文本文件格式解析，CSV格式本来就是一种由严格语法定义的文本格式，因而毋宁说这里的核心编程问题域就是文本处理。 只不过因为内部流程的复杂性和牵扯到这一流程之中的人员数量的庞大，导出数据中的文本字段内还有各种各样没有经过良好格式化的数据，需要从解析好的CSV格式中做二次分解和提炼。

二次解析复杂性

因此在既有的csv库的处理之上，问题本身还需要大量的二次解析处理，甚至包括在一个长度可能超过数万个字符的单一字段内，分解出内部较为复杂的结构集合，以便做后续的统计、归并和显示。实现这一功能本身不是特别困难， 熟悉了Rust的语法之后，适用它自身内置的Option/Map/Vec/Iterator等基础核心数据结构之后，配合它自身优雅的函数式编程设施和模式匹配，可以很快熟练写出想要的各种变换逻辑。

具体到文本解析，则不能不提到正则表达式处理，毕竟手写的字符串搜索和子串引用slice机制虽然好用，却往往可能会沦为不成熟优化，因为复杂文本的处理最好还是交给专业的正则表达式库更合理。

数据量增大之下的性能考验

一开始版本的程序仅仅是处理几千条记录，此时的输入文件虽然超过80MB，里面的记录有数千条，总体而言不到两秒钟的运行效率还算是差强人意，实际使用的时候，基本鼠标单击一下稍微停顿即可以完成。 随着报表数据越来越多（做出基本的功能之后，总想让它发挥更大的效力），对输入数据的要求就更高，慢慢地它需要能高效地处理300MB以上的报表输入，于此同时内部二次解析的复杂度也随着新需求的加入而变得更加复杂。

此时处理时间已经接近了10秒，这么长的运行时间对于一个迷你的小工具而言太长了一点，以至于实际用鼠标单击它的时候能够感受到明显的停顿，优化的需求迫在眉睫。

优化分析

基于程序本身所使用到的基本技术，可以有下面几个优化方向

  • 运算缓存
  • 多线程并行化处理
  • 第三方库

火焰图

当然没有benchmark数据的性能优化都是很危险的，由于Rust的底层采用的是LLVM的编译工具链，因此生成火焰图的方法也非常简单直接。只需要在Cargo.toml中加入如下的选项确保生成的二级制文件中包含符号表

[profile.release]
debug=true

为了解析Rust自身的符号，我们可以借助rust-unmangle工具在C++符号被解析之后，二次调用它进行转换即可。在Rust的项目目录下，只要执行如下的命令即可生成火焰图文件：

perf record --call-graph dwarf,16384 -e cpu-clock -F 997 target/release/analyzer 
perf script | stackcollapse-perf.pl | stackcollapse-recursive.pl | c++filt | rust-unmangle | flamegraph.pl > flame.svg

需要注意的是生成的SVG矢量图文件是可以点击缩放的，但是需要用合适的工具打开而不能使用默认的图片查看器。 图形里面的每一个图形的柱体是可以点击层层深入进去的；如果没有合适的工具，使用FireFox浏览器也是一个不错的选择。

运算缓存

这种优化其实是算法级别的优化，关键是找到有很多重复、或者循环的运算，将其缓存起来减少重复计算或者不必要的循环。 这类的手法实施起来没有多少难度，和别的编程语言中的做法也是类似的，可惜的是很多时候能做的也不是很多。

更多缓存和封装的做法其实相对不那么符合函数式编程的思想一些，有时候不得不将很漂亮优雅的函数式pipeline用法拆开，或者将中间的缓存结果放入新的参数传入函数，从而使得代码的可读性变得更差一些。

第三方库

这里主要的第三方库有两个，一个是解析字符串正则表达式的regex库。

Regex解析

本身使用的时候已经有意选择了性能最高的一个可用的正则库，因此换用其它正则表达式库的思路就不太可行了。

还有一个思路是尽量去简化正则表达式的复杂性，比如减少不必要的正则表达式分组操作，减少正则匹配算法中的回溯操作。可惜这一方法在第一次写就的时候已经优化过了，没有多少剩余的空间可以做文章了。

唯一剩下的思路就是看是否自己使用的方法不对，或者库本身是否提供了一些底层API或者高级技巧等。 稍微翻阅一下Regex的文档，发现该库的作者提供了两个优化性能的思路

  • 减少拷贝，使用解析时候的生存周期里的字符串引用，而不是采用显式的String对象来保存解析的字段
  • 减少不必要的按解析次数执行的内存分配，而采用复用匹配组捕获的数据结构的方法

减少拷贝

其实CSV文本格式的规范已经决定了在读入文本字段的时候，不得不对从磁盘读取出来的文本内容做拷贝，而不能用直接引用。因为对于复杂的CSV格式而言，分隔符之间可能会出现转义字段，符合规范的解析器不得不将转移的字符提取出来做连接，返回给用户修改之后的字符串。这是第一道从操作系统的IO缓冲区到用户接口数据结构的拷贝。

CSV库所建议的不必要的拷贝，其实是发生在上述的解析之后的临时内存区域经由serde这一抽象的接口(trait)反序列化到用户自定义的数据结构的时候的拷贝。显然去掉这一层拷贝可以节约大量操作系统用于内存分配的时间；这一开销在很多情况下是惊人的，甚至是很多高性能的C、C++程序的秘密武器。

可惜这种方法对我的工具并没有很好的借鉴意义，其深层次的原因是我的程序需要将解析出来的数据结构临时保存起来，等所有的数据都解析完之后，做排序和二次处理；而文档建议的优化方法要求引用的内存上的相关处理必须要在解析下一条记录的时候被释放。 如果regex库内部提供可以使用生存周期更长的内存的方法，那么这种方法也不失为一个很好的优化；可惜它没有这样的机制。 此时如果强行引用解析器提供的内存，Rust贴心的编译器检查利器Borrow Checker就会拦截非法的内存引用。

使用高级API

优化的第一步是理清默认API的底层大概做了什么事情。 由于最复杂的解析需要从一个字段中搜索几十甚至上百个子记录，因而关注的重心就是captures_iter方法（严格的性能分析其实需要按照perf和flamegraph的工具来判断和检验，这里直觉和实际的火焰图分析是重合的）。

captures_iter的内存开销

正则表达式运算库的内部往往是通过DFA状态机来实现的，默认的库API很好地隐藏了内部的解析细节，用户只需要调用captures_iter方法就可以得到一个实现了迭代器类型的结构，很方便地和其它的函数式pipeline连接起来。 实际接收代码则会根据其返回的封装过的CapturesMatch结构来读取内部的分组的匹配信息。

其结构的实现如下

pub fn captures_iter<'r, 't>(
        &'r self,
        text: &'t str,
) -> CaptureMatches<'r, 't> {
    CaptureMatches(self.0.searcher_str().captures_iter(text))
}

返回的结构其实是使用了Captures结构

pub struct CaptureMatches<'r, 't>(re_trait::CaptureMatches<'t, ExecNoSyncStr<'r>>);
impl<'r, 't> Iterator for CaptureMatches<'r, 't> {
    type Item = Captures<'t>;

    fn next(&mut self) -> Option<Captures<'t>> {
        self.0.next().map(|locs| Captures {
            text: self.0.text(),
            locs: locs,
            named_groups: self.0.regex().capture_name_idx().clone(),
        })
    }
}

显然默认的captures_iter()方法会每次新构造一个Catpures结构体出来，这里产生的对象其实是一个临时的对象，因为每次解析完毕之后，用户代码仅仅是取出内部匹配的分组，就不再使用了。

Captures的实际封装数据如下

pub struct Captures<'t> {
    text: &'t str,
    locs: re_trait::Locations,
    named_groups: Arc<HashMap<String, usize>>,
}
高效的captures_read方法

按照文档的建议，这里使用captures_read方法可以实现复用返回匹配结果的缓冲区的目的，减少不必要的临时对象分配。 它的实现如下

pub fn captures_read<'t>(
    &self,
    locs: &mut CaptureLocations,
    text: &'t str,
) -> Option<Match<'t>> {
    self.captures_read_at(locs, text, 0)
}

显然解决问题的关键在于这个CaptureLocations结构，其实在上面的默认API的实现里面已经出现了。

不出意外它果然是一个保存匹配位置的一个Vec,这才是内部无法将临时对象分配在栈上的关键原因，而动态堆内存的分配代价又比较高，这个事实对C/C++程序员而言完全不陌生。

CaptureLocations的定义如下：

pub struct CaptureLocations(re_trait::Locations);
pub struct Locations(Vec<Slot>);
pub type Slot = Option<usize>;

为了复用这个对象，我们需要在外侧循环调用的地方，自行定义一个mutable的对象，然后在每次调用之前，传入即可。 考虑到我们想达到最佳的性能，在单线程的处理中，同一个正则表达式，我们仅仅需要一个对象即可，而不需要每次去分配。

多线程并行化处理

默认情况下，这类简单的文本处理程序都是采用单线程的思路来写就的，改造为多线程就会多多少少面临一些挑战，尤其是需要共享变量读写的情况居多的时候，多线程的挑战比单线程要多得多，因为程序的执行状态会变得更见难以用走读代码的方式来分析。

借助于火焰图分析工具，可以看出该处理程序的大部分CPU时间耗费在基于正则表达式的二次结构化解析上。这些操作本身互相之间的关联比较小，是显然可以被并行化的，多线程应该可以大大加速处理过程。 这方面使用经典的map/reduce思路，只需要将实际解析的部分放入类似线程池一样的调度器中执行即可。

由于Rust本身提供了强大的用于确保线程安全的静态代码检查；绝大部分情况下，只要保证代码可以编译通过，运行期出错的可能性基本就很小了。

使用rayon库

rayon库提供了方便易用的par_iter，允许我们将代码稍微改动之后，将自动获取并发执行的好处，比如原来的代码

let mut results: Vec<ParsedRecords> = Vec::new();
// parsed raw records from csv
let raw_records = parse_from_csv(reader);

results = raw_records
        .iter()
        .map(|rc| ParsedRecords::new(*rc, group, &regexes))
        .collect();
//further transformation on parsed results

只需要修改iter()为par_iter()的调用，并将最后的collect方法替换为rayon自己实现的collect方法

raw_records
    .par_iter()
    .map(|rc| {
            ParsedRecord::new(*rc, group, &regexes)
        }
    })
    .collect_into_vec(&mut result);

由于事先已经用火焰图确认过这个二次解析构造耗费最大部分的CPU时间，这次替换和改造可以看到立竿见影的性能提升：运行时间瞬间减小到原来的30%~50%，几乎有两三倍的性能提升!

并行版本的regex问题

并行版本能工作的前提是没有数据的多线程访问问题，当然如果有问题，编译器会自动拦截阻止编译通过。 大部分的解析工作没有什么障碍，因为Rust默认的移动语义和显示mutable设计使得这些潜在的问题马上自动显现出来，只要按照错误提示修改然后在编译器的胁迫下乖乖就范即可。

唯一麻烦的问题就是上述的正则表达式；使用该库的同时，我们不得不面对如下两个麻烦的问题。

Regex对象的CaptureLocation共享

库的官方文档提供了很好的例子，建议我们用lazy_static!宏来避免多次编译正则表达式，实现更好的性能；可惜如果我们想使用上述提到的共享CaptureLocation对象，我们需要一个mutable的对象。

这里的限制应该是目前regex库自己施加的使用限制，我们无法自由地构造一个可以复用的CaptureLocation对象出来，而必须由一个编译好的Regex对象来获取；由于Mutable的需要，我们不得不将Regex本身从lazy_static!宏中提取出来，单独保存。 好在这个Regex对象本身还是可以保持只读，多个线程引用一个只读的变量状态毫无问题。

不妙的是，par_iter显式地将我们卷入多线程环境（我们想要更好的性能），编译器不允许在多个线程中共享mutable正则表达式，当然那样做也是错误的。 好在多线程编程的工具箱中，我们还可以使用ThreadLocal这样的数据结构，只要保证每个线程使用自己的mutable对象就好了，问题自然而然得到解决。

####　封装多个正则表达式 可以用一个简单的enum来表述各种正则表达式类型，然后提供给外部调用

pub struct RegexInfo {
    pub regex: Regex,
    pub location: &'static LocalKey<RefCell<CaptureLocations>>,
}

pub enum RegexCategory {
    FieldSep,
    StateChange,
    StateChangeEx,
    //...
}

同时我们需要给外部提供一个看起来像全局但是多线程安全的接口

pub struct RegexReposiotry {
    field_sep: RegexInfo,
    state_change: RegexInfo,
    state_change_ex: RegexInfo,
    //...
}

impl RegexReposiotry {
    pub fn get_regex(&self, category: &RegexCategory) -> &RegexInfo {
        match category {
            FieldSep => &self.field_sep,
            StateChange => &self.state_change,
            StateChangeEx => &self.state_change_ex,
            //...
        }
    }
}

Thread Local变量的创建和维护

为了构造Thread Local的变量，我们不得不借助于thread_local!宏来构造，因此可以用一些临时的值先填充之

lazy_static! {
    static ref DUMMY: Regex =
        Regex::new("(.*) xxxx ([a-zA-Z ]+) to ([a-zA-Z ]+)").unwrap();
}

thread_local! {
    static LOC_FIELDSEP: RefCell<CaptureLocations> = RefCell::new(DUMMY.capture_locations().clone());
    static LOC_STAGECHAGE: RefCell<CaptureLocations> = RefCell::new(DUMMY.capture_locations().clone());
    static LOC_STAGECHAGE_EX: RefCell<CaptureLocations> = RefCell::new(DUMMY.capture_locations().clone());
    //.... more
}

静态的指针值指向的并不是我们真正用于解析的正则表达式的匹配缓冲。 实际的正则表达式构造的时候，我们再重新替换真正的正则表达式对应的变量，并且拷贝之。

构造的实现如下

pub fn create_regexes() -> RegexReposiotry {
    use RegexCategory::*;
    RegexReposiotry{
        field_sep: create_regex_info("(, )?(201[789]-[0-9]{2}-[0-9]{2} [0-9]{2}:[0-9]{2}) ", FieldSep),
        state_change: create_regex_info(
            "(.*) The state of the problem changed from ([a-zA-Z ]+) [tT]o ([a-zA-Z ]+)", StateChange
        ),
        state_change_ex: create_regex_info("(.*) State changed from ([a-zA-Z ]+) to ([a-zA-Z ]+)", StateChangeEx),
        //...
    }
}

这里为简化起见，将正则表达式静态地写入在构造实现中，但是其实也可以经由创建者自己指定的方法传入。 实际的结构初始化由下面的内部函数来实现：

fn create_regex_info(pattern: &str, pat: RegexCategory) -> RegexInfo {
    let regex = Regex::new(pattern).unwrap();
    let loc: &'static _ = match pat {
        FieldSep => &LOC_FIELDSEP,
        StateChange => &LOC_STAGECHAGE,
        StateChangeEx => &LOC_STAGECHAGE_EX,
        //...
    };
    loc.with(|f| {
        *f.borrow_mut() = regex.capture_locations();
    });

    RegexInfo {
        location: loc,
        regex,
    }
}

其中的中间初始化location变量的部分，我们采用RefCell本身提供的with方法，调用*f.borrow_mut()来修改内部的捕获位置缓冲区为真正的正则表达式对象对应的缓冲区向量。

多线程解析

实际解析的代码则可以经由上述的正则封装，实现如下

fn parsing_using_regex_and_key_string<'a, F>(
    rem: &'a str,
    regexes: &RegexReposiotry,
    pattern: &'a str,
    cat: &RegexCategory,
    func: F,
) -> Option<(&'a str, ExtraInfo<'a>)>
where
    F: Fn(&mut CaptureLocations, &'a str) -> (&'a str, ExtraInfo<'a>),
{
    match rem.find(pattern) {
        None => None,
        Some(_) => {
            let regex_info = &regexes.get_regex(cat);
            let mut ret: Option<(&'a str, ExtraInfo<'a>)> = None;
            regex_info.location.with(|loc| {
                let mut marker_loc: RefMut<_> = loc.borrow_mut();
                ret = regex_info
                    .regex
                    .captures_read(&mut *marker_loc, rem)
                    .map(|_| func(&mut *marker_loc, rem))
            });
            ret
        }
    }
}

这里的关键在于中间的regex_info.location.with(|loc| {})调用实际发生的时候，不同的线程会得到不同的CaptureLocation内容；其内容在实际被写入的时候，会基于线程的不同而写入不同的内存位置。

唯一有些不太符合直接的地方在于mutable变量的获取的地方，不得不借助于RefMut结构将其传递如captures_read中，而不能直接采用实际的类型。或许将来的Rust语言版本会改进这一难以理解的做法。

相关文章

Leave a Comment

Your email address will not be published. Required fields are marked *

Markdown is supported.