我从kostyas基准中获取了Rust Brainfuck解释器的代码，并尝试对其进行优化。

在Reddit上还有关于Rust在基准测试中性能较差的讨论。

在我进行改进之前，代码需要16.81s才能完成基准测试并使用6.2Mb的内存，之后代码仅需要4.89s可以运行，但是内存消耗几乎没有变化。

如何改善代码并减少内存使用量？

更改后的文件也位于Github上。 


use std::fs::File;
use std::path::Path;
use std::io::prelude::*;
use std::vec::Vec;
use std::io;
use std::env;
use std::collections::BTreeMap;

struct Tape {
  pos: usize,
  tape: Vec<isize>
}

impl Tape {
  fn new() -> Tape { Tape { pos: 0, tape: vec![0] } }
  fn get(&self) -> isize { self.tape[self.pos] }
  fn getc(&self) -> u8 { self.get() as u8 }
  fn inc(&mut self) { self.tape[self.pos] += 1; }
  fn dec(&mut self) { self.tape[self.pos] -= 1; }
  fn advance(&mut self) { self.pos += 1; if self.tape.len() <= self.pos { self.tape.push(0) } }
  fn devance(&mut self) { if self.pos > 0 { self.pos -= 1; } }
}

struct Program {
  code: Vec<u8>,
  bracket_map: BTreeMap<usize, usize>
}

impl Program {
  fn new(content: Vec<u8>) -> Program {
    let mut code = Vec::new();
    let mut bracket_map = BTreeMap::new();
    let mut leftstack = Vec::new();

    for (pc, b) in content.iter().filter(|&&x| x == b'+' || x == b'-' || x == b'.' || x == b','
            || x == b'<' || x == b'>' || x == b'[' || x == b']').map(|&x| x).enumerate() {
      if b == b'[' {
        leftstack.push(pc);
      } else if b == b']' {
        if let Some(left) = leftstack.pop() {
          bracket_map.insert(left, pc);
          bracket_map.insert(pc, left);
        }
      }
      code.push(b);
    }
    Program{ code: code, bracket_map: bracket_map }
  }

  fn run(&self) {
    let mut pc: usize = 0;
    let mut tape = Tape::new();
    let mut stdout = io::stdout();

    while pc < self.code.len() {
      match self.code[pc] {
        b'+' => tape.inc(),
        b'-' => tape.dec(),
        b'>' => tape.advance(),
        b'<' => tape.devance(),
        b'[' => { if tape.get() == 0 { pc = self.bracket_map[&pc]; } },
        b']' => { if tape.get() != 0 { pc = self.bracket_map[&pc]; } },
        b'.' => { stdout.write(&[tape.getc()]).unwrap(); stdout.flush().unwrap() },
        _ => unreachable!()
      }
      pc += 1;
    }
  }
}

fn main() {
  let mut buf = Vec::new();
  {
    let arg1 = env::args().nth(1).unwrap();
    let path = Path::new(&arg1);
    let mut file = File::open(&path).unwrap();
    file.read_to_end(&mut buf).unwrap();
  }
  Program::new(buf).run();
}


更多信息：该程序使用rustc -C opt-level=3 brainfuck/brainfuck.rs -o brainfuck_rs编译，内存使用情况由ruby脚本确定。 C ++的regading内存使用率更好，它仅需要1.6Mb。

用于基准测试的Brainfuck rogram：

 Benchmark brainf*ck program
>++[<+++++++++++++>-]<[[>+>+<<-]>[<+>-]++++++++
[>++++++++<-]>.[-]<<>++++++++++[>++++++++++[>++
++++++++[>++++++++++[>++++++++++[>++++++++++[>+
+++++++++[-]<-]<-]<-]<-]<-]<-]<-]++++++++++.


我每晚都在使用Rust在4个rust-nightly-bin-1.2.0_2015.06.06-1上运行的Arch Linux上的Intel(R) Core(TM) i5-2450M CPU @ 2.50GHz。

评论

您是否有理由认为可以进一步优化内存使用？当前的数字非常好，在当前时代，6 MB（我想您是说MB而不是Mb）可以忽略不计。
我不太了解rust标准库，但是您可以使用基于哈希表的容器而不是BTreeMap来压缩几个周期（甚至可以节省内存）。
改进的很大一部分来自删除哈希表。散列太慢。
@glampert Yah; Rust的哈希表并不是特别快。
使用VecMap是明显的改进。在那之后，您可能需要编写一个JIT或实现一个优化的优化器。您也许可以避免一些不安全的分支，但这不太有帮助。

#1 楼

配置文件

您只能改进您可以测量的范围。因此，首先让我们运行callgrind来检查我们大部分时间都花在了什么地方：

 $ rustc -C opt-level=3 -g brainfuck.rs
$ valgrind --tool=callgrind --dump-instr=yes --collect-jumps=yes --simulate-cache=yes ./brainfuck ahpla.bf
$ callgrind_annotate callgrind.out.*


我们最终将得到类似于以下配置文件的内容：

--------------------------------------------------------------------------------
Profile data file 'callgrind.out.29071' (creator: callgrind-3.11.0)
--------------------------------------------------------------------------------
I1 cache: 32768 B, 64 B, 8-way associative
D1 cache: 32768 B, 64 B, 8-way associative
LL cache: 16777216 B, 64 B, 16-way associative
Timerange: Basic block 0 - 10458028484
Trigger: Program termination
Profiled target:  ./brainfuck ahpla.bf (PID 29071, part 1)
Events recorded:  Ir Dr Dw I1mr D1mr D1mw ILmr DLmr DLmw
Events shown:     Ir Dr Dw I1mr D1mr D1mw ILmr DLmr DLmw
Event sort order: Ir Dr Dw I1mr D1mr D1mw ILmr DLmr DLmw
Thresholds:       99 0 0 0 0 0 0 0 0
Include dirs:
User annotated:
Auto-annotation:  off

--------------------------------------------------------------------------------
            Ir             Dr            Dw  I1mr  D1mr  D1mw  ILmr  DLmr  DLmw
--------------------------------------------------------------------------------
49,487,884,719 13,086,961,954 6,269,022,579 2,411 3,281 1,553 2,167 2,109 1,422  PROGRAM TOTALS

--------------------------------------------------------------------------------
            Ir            Dr            Dw I1mr D1mr D1mw ILmr DLmr DLmw  file:function
--------------------------------------------------------------------------------
16,380,206,099 5,113,395,424 1,588,909,048   12    4    1   12    4    .  brainfuck.rs:brainfuck::main::h21788f29898deec2 [/home/zeta/misc/brainfuck]
14,242,423,355 2,080,022,568 3,380,036,673    2    0    0    2    .    .  /checkout/src/liballoc/btree/search.rs:alloc::btree::search::search_tree::h9cb21dc425abeb49 [/home/zeta/misc/brainfuck]
 4,593,384,291   895,564,901           241    6    0    0    6    .    .  /checkout/src/liballoc/vec.rs:brainfuck::main::h21788f29898deec2
 2,917,813,479             .             .    .    .    .    .    .    .  /checkout/src/libcore/slice/mod.rs:alloc::btree::search::search_tree::h9cb21dc425abeb49
 2,426,711,760   808,903,920             0    1    1    0    1    .    .  /checkout/src/libcore/cmp.rs:alloc::btree::search::search_tree::h9cb21dc425abeb49
 1,848,909,595 1,848,909,577             0    3    0    0    3    .    .  /checkout/src/liballoc/raw_vec.rs:brainfuck::main::h21788f29898deec2
 1,560,016,932   780,008,466   260,002,823    1    1    0    1    .    .  /checkout/src/libcore/option.rs:brainfuck::main::h21788f29898deec2
 1,560,016,926   520,005,642             0    1    0    0    1    .    .  /checkout/src/liballoc/btree/node.rs:alloc::btree::search::search_tree::h9cb21dc425abeb49
 1,300,014,107   260,002,821   260,002,823    .    .    .    .    .    .  /checkout/src/liballoc/btree/map.rs:brainfuck::main::h21788f29898deec2
 1,097,796,554             .             .    .    .    .    .    .    .  /checkout/src/libcore/iter/mod.rs:alloc::btree::search::search_tree::h9cb21dc425abeb49
 1,040,011,284   260,002,821   780,008,463    .    .    .    .    .    .  /checkout/src/liballoc/btree/node.rs:brainfuck::main::h21788f29898deec2
   260,003,033   260,002,823           207    0    0    3    0    0    1  /checkout/src/libcore/ptr.rs:brainfuck::main::h21788f29898deec2


您的程序执行了总共49,487,884,719条指令。其中只有16,380,206,099源自您的main，其余的源自其他功能。我们只能（半）直接控制30％的使用说明。不好。

瓶颈瓶颈

不幸的是，rustc内联了Program::new，Program::run和所有Tape函数。只是为了确保new()不会占用程序的大部分内容，让我们删除run一秒钟，然后再次检查：

 $ sed -i 's/.run();/;/'
$ rustc -C opt-level=3 -g brainfuck.rs
$ time ./brainfuck ahpla.bf

real 0m0.002s
user 0m0.004s
sys 0m0.000s
 new()几乎不需要时间。罪魁祸首是run()和BTreeMap。
 
内存使用情况
 
内存使用情况如何？好吧，这部分本身已经得到改善。您的代码在我的系统上使用1.6 MB。显然，BTreeMap的实现在内存使用方面得到了很大改进。
 
使用rustfmt和clippy 
 
虽然rustfmt的输出取决于个人喜好，但clippy可以提供有价值的输入。例如，map(|&x| x)是cloned。
 
对非瓶颈功能使用易于阅读的代码
 
您的filter占new的主导地位：
 
 
for (pc, b) in content.iter().filter(|&&x| x == b'+' || x == b'-' || x == b'.' || x == b','
            || x == b'<' || x == b'>' || x == b'[' || x == b']').map(|&x| x).enumerate() 

 
 
那是满口且难以维持的。既然这不是性能的关键部分，就让我们对其进行更改：
 
 
for (pc, b) in content.iter().filter(|x| b"+-,.[]<>".contains(x)).cloned().enumerate() 

 
 
这很容易阅读，不是吗？
 
使用常量较低的\ $ \ O（1）\ $数据结构进行跳转
 
如果使用Vec而不是BTreeMap，我们可以大大减少时间。我们牺牲了一点内存，但这几乎没有引起注意。
 
 BTreeMap s被实现为B树。树始终具有某种程度的间接：您必须遍历树结构并比较键或值。但是BTreeMap和std::map在基本水平上有所不同：BTreeMap做了额外的比较以在局部数组中找到正确的值，而std::map只需要找到正确的node。如果遍历整棵树，BTreeMap的额外成本并不明显，但是如果我们一遍又一遍地寻找单个元素，这会很烦人，尤其是在小的数据集中。
 
所以让我们使用Vec而是在我们使用它的同时采用所有其他建议：
 
 
struct Program {
    code: Vec<u8>,
    jumps: Vec<usize>,
}

impl Program {
    fn new(content: &[u8]) -> Program {
        let code: Vec<u8> = content
            .iter()
            .filter(|x| b"-+,.[]<>".contains(x))
            .cloned()
            .collect();

        let mut jumps = vec![0; code.len() + 1];
        let mut leftstack = Vec::new();

        for (pc, &b) in code.iter().enumerate() {
            if b == b'[' {
                leftstack.push(pc);
            } else if b == b']' {
                if let Some(left) = leftstack.pop() {
                    jumps[left] = pc;
                    jumps[pc] = left;
                }
            }
        }
        Program { code, jumps }
    }

    fn run(&self) {
        let mut pc: usize = 0;
        let mut tape = Tape::new();
        let mut stdout = io::stdout();

        while pc < self.code.len() {
            match self.code[pc] {
                b'+' => tape.inc(),
                b'-' => tape.dec(),
                b'>' => tape.advance(),
                b'<' => tape.devance(),
                b'[' => {
                    if tape.get() == 0 {
                        pc = self.jumps[pc];
                    }
                }
                b']' => {
                    if tape.get() != 0 {
                        pc = self.jumps[pc];
                    }
                }
                b'.' => {
                    stdout.write(&[tape.getc()]).unwrap();
                    stdout.flush().unwrap()
                }
                _ => unreachable!(),
            }
            pc += 1;
        }
    }
}

 
 
这如何影响您的变体？
 
 
 $ ./bench.rb ./bf-cr ahpla.bf
ZYXWVUTSRQPONMLKJIHGFEDCBA
3.10s, 1.5Mb

$ ./bench.rb ./brainfuck-orig ahpla.bf
ZYXWVUTSRQPONMLKJIHGFEDCBA
9.73s, 1.5Mb
 
 
 
请注意，bench.rb报告的内存使用情况不稳定。无论哪种方式，我们都可以看到在这种情况下，Vec不会占用任何明显的内存，但是可以极大地改善运行时间。
 
由于我们使用callgrind进行了测量并发现， BTreeMap特定的方法有助于运行时。
 
结束语
 
 kostya后来添加了使用最小化AST的变体。那一个甚至更快，但是使用更多的内存，因为我们不再需要跳转了。但是，一个人可能可以改进它。
 
除了上述建议之外，您的代码还易于阅读和理解。干得好。