本記事のまとめ

Rust の Vec と VecDeque の以下の関数の速度を比較した。
- Vec: remove(index), drain(range), pop()
- VecDeque: pop_front(), drain(range), pop_back()
Vec と VecDeque を使うのならば、次のように使い分けるのが良さそう。
- 最後列（back）から pop する場合は Vec。
- 最前列（front）から pop する場合は VecDeque。
- drain を使う場合は VecDeque。

背景

これまで Rust で FIFO 操作を行う際にも Vec を使用していた。
- 具体的には vec.remove(0) を用いて最初の要素を "pop" していた。
より良いものを求めてググってみて、VecDeque という front/back の両方から pop できる型があることを知った。
Front からの pop 操作に関してどちらの方が速いのか知るため、これらを用いた front からの pop にかかる時間を比較した。
ついでに back からの pop と、drain 操作の速度も比較した。

Rust Playground 上でのテスト

Rust Playground 上でコードを作成。
環境設定は次の通り。
- edition: 2018
- version: stable (1.47.0)
- mode: debug
コードは下節に示している。
検証手順を簡単に示すと次のようになる。
1. 0u8 を VEC_SIZE (=200,000) 個含む Vec または VecDeque を生成する。
2. pop() などの関数を実行し、すべての要素を除くのにかかる時間を計測。

実行結果（計測結果）の一例

Front からの pop：VecDeque の方が圧倒的に（50 倍以上）速かった。
```
vec.remove(0): 0.853 sec elapsed.
vecdeque.pop_front(): 0.009 sec elapsed.
```

Back からの pop：Vec の方が速かった。

vec.pop(): 0.007 sec elapsed.
vecdeque.pop_back(): 0.009 sec elapsed.

drain 操作：VecDeque の方が 5 倍以上速かった。

vec.drain(..1): 0.806 sec elapsed.
vec.drain(..10): 0.090 sec elapsed.
vec.drain(5..15): 0.092 sec elapsed.
vecdeque.drain(..1): 0.043 sec elapsed.
vecdeque.drain(..10): 0.014 sec elapsed.
vecdeque.drain(5..15): 0.016 sec elapsed.

コード

処理速度の計測のためのマクロはこちらの Qiita の記事を参考にさせていただいた。

# ![allow(dead_code)] // この行でコンパイラのwaringsメッセージを止めます。

use std::collections::VecDeque;
use std::time::Instant;

// 10 の倍数に設定すること
const VEC_SIZE: usize = 200000;

macro_rules! measure {
  ( $x:expr) => {
    {
      let start = Instant::now();
      let result = $x;
      let end = start.elapsed();
      println!("{}.{:03} sec elapsed.", end.as_secs(), end.subsec_millis());
      result
    }
  };
}

fn main() {
    println!("size of a vector: {}\n", VEC_SIZE);
    
    println!(">>> remove elements from the front >>>");
    let mut a: Vec<u8> = vec![0u8; VEC_SIZE];
    print!("vec.remove(0): ");
    measure!({
        while !a.is_empty() {
            let _ = a.remove(0);
        }
    });
    
    let mut a: VecDeque<u8> = VecDeque::new();
    for _ in 0..VEC_SIZE {
        a.push_back(0);
    }
    print!("vecdeque.pop_front(): ");
    measure!({
        while !a.is_empty() {
            let _ = a.pop_front();
        }
    });
    println!("<<< remove elements from the front <<<\n");
    
    println!(">>> drain elements from the front >>>");
    let mut a: Vec<u8> = vec![0u8; VEC_SIZE];
    print!("vec.drain(..1): ");
    measure!({
        while !a.is_empty() {
            let _ = a.drain(..1);
        }
    });
    
    let mut a: Vec<u8> = vec![0u8; VEC_SIZE];
    print!("vec.drain(..10): ");
    measure!({
        while !a.is_empty() {
            let _ = a.drain(..10);
        }
    });
    let mut a: Vec<u8> = vec![0u8; VEC_SIZE];
    print!("vec.drain(5..15): ");
    measure!({
        while a.len() > 10 {
            let _ = a.drain(5..15);
        }
        let _ = a.drain(..10);
    });
    
    let mut a: VecDeque<u8> = VecDeque::new();
    for _ in 0..VEC_SIZE {
        a.push_back(0);
    }
    print!("vecdeque.drain(..1): ");
    measure!({
        while !a.is_empty() {
            let _ = a.drain(..1);
        }
    });
    
    let mut a: VecDeque<u8> = VecDeque::new();
    for _ in 0..VEC_SIZE {
        a.push_back(0);
    }
    print!("vecdeque.drain(..10): ");
    measure!({
        while !a.is_empty() {
            let _ = a.drain(..10);
        }
    });
    
    let mut a: VecDeque<u8> = VecDeque::new();
    for _ in 0..VEC_SIZE {
        a.push_back(0);
    }
    print!("vecdeque.drain(5..15): ");
    measure!({
        while a.len() > 10 {
            let _ = a.drain(5..15);
        }
        let _ = a.drain(..10);
    });
    println!("<<< drain elements from the front <<<\n");
    
    println!(">>> remove elements from the back >>>");
    let mut a: Vec<u8> = vec![0u8; VEC_SIZE];
    print!("vec.pop(): ");
    measure!({
        while !a.is_empty() {
            let _ = a.pop();
        }
    });
    
    let mut a: VecDeque<u8> = VecDeque::new();
    for _ in 0..VEC_SIZE {
        a.push_back(0);
    }
    print!("vecdeque.pop_back(): ");
    measure!({
        while !a.is_empty() {
            let _ = a.pop_back();
        }
    });
    println!("<<< remove elements from the back <<<\n");
}