Vec と VecDeque の速度比較

# 本記事のまとめ
* 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]((https://play.rust-lang.org/)) 上でコードを作成。
* 環境設定は次の通り。
    * edition: 2018
    * version: stable (1.47.0)
    * mode: debug
* コードは下節に示している。
* 検証手順を簡単に示すと次のようになる。
    1. `0u8` を `VEC_SIZE` (=200,000) 個含む `Vec` または `VecDeque` を生成する。
    1. `pop()` などの関数を実行し、すべての要素を除くのにかかる時間を計測。

## 実行結果（計測結果）の一例
* Front からの pop：`VecDeque` の方が圧倒的に（50 倍以上）速かった。

    ```sh
    vec.remove(0): 0.853 sec elapsed.
    vecdeque.pop_front(): 0.009 sec elapsed.
    ```
* Back からの pop：`Vec` の方が速かった。

    ```sh
    vec.pop(): 0.007 sec elapsed.
    vecdeque.pop_back(): 0.009 sec elapsed.
    ```
* `drain` 操作：`VecDeque` の方が 5 倍以上速かった。

    ```sh
    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 の記事](https://qiita.com/pseudo_foxkeh/items/5d5226e3ffa27631e80d)を参考にさせていただいた。

```rust
#![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");
}
```