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 上でコードを作成。
• 環境設定は次の通り。
  • 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");
}