title: Why is finding the intersection of integer sets faster with a Vec compared to BTreeSet?
body: <p>I need to find out how many integers are present in both of two given sets, fast. The sets are written to only once but this operation will be performed many times with different pairs of sets. The sets contain 5-30 integers and the largest of these integers is 840000.</p>
  
  <p>I have initially tried to iterate over one <code>Vec</code> and for each element check if its present in the other <code>Vec</code>. I then decided to use <code>BTreeSet</code> instead since it should be significantly faster at checking if an integer is present in the set, but that does not seem to be the case. The <code>Vec</code> implementation takes ~72ms and the BTreeSet ~96ms when called on couple thousands of sets in release mode under stable Rust 1.34 with same performance when using nightly.</p>
  
  <p>This is the <code>Vec</code> implementation:</p>
  
  <pre class="lang-rust prettyprint-override"><code>use std::cmp;
  
  fn main() {
      let mut sets = Vec::with_capacity(1000);
      for i in 1..1000 {
          let mut set = Vec::new();
          for j in 1..i % 30 {
              set.push(i * j % 50000);
          }
          sets.push(set);
      }
      for left_set in sets.iter() {
          for right_set in sets.iter() {
              calculate_waste(left_set, right_set);
          }
      }
  }
  
  fn calculate_waste(left_nums: &amp;Vec&lt;usize&gt;, right_nums: &amp;Vec&lt;usize&gt;) -&gt; usize {
      let common_nums = left_nums.iter().fold(0, |intersection_count, num| {
          intersection_count + right_nums.contains(num) as usize
      });
      let left_side = left_nums.len() - common_nums;
      let right_side = right_nums.len() - common_nums;
      let score = cmp::min(common_nums, cmp::min(left_side, right_side));
      left_side - score + right_side - score + common_nums - score
  }
  </code></pre>
  
  <p>And this is the <code>BTreeSet</code> implementation:</p>
  
  <pre class="lang-rust prettyprint-override"><code>use std::cmp;
  use std::collections::BTreeSet;
  
  fn main() {
      let mut sets = Vec::with_capacity(1000);
      for i in 1..1000 {
          let mut set = BTreeSet::new();
          for j in 1..i % 30 {
              set.insert(i * j % 50000);
          }
          sets.push(set);
      }
      for left_set in sets.iter() {
          for right_set in sets.iter() {
              calculate_waste(left_set, right_set);
          }
      }
  }
  
  fn calculate_waste(left_nums: &amp;BTreeSet&lt;usize&gt;, right_nums: &amp;BTreeSet&lt;usize&gt;) -&gt; usize {
      let common_nums = left_nums.intersection(&amp;right_nums).count();
      let left_side = left_nums.len() - common_nums;
      let right_side = right_nums.len() - common_nums;
      let score = cmp::min(common_nums, cmp::min(left_side, right_side));
      left_side - score + right_side - score + common_nums - score
  }
  </code></pre>
  
  <p>It was ran with the command (<code>-w 50</code> makes it ignore the first 50 runs):</p>
  
  <pre class="lang-none prettyprint-override"><code>hyperfine "cargo run --release" -w 50 -m 100
  </code></pre>
  
  <p>Full code of the program available <a href="https://github.com/HeIIoImRandom/hash_code_2019" rel="nofollow noreferrer">here</a>.</p>
  
  <p>Is the <code>BTreeSet</code> implementation slower because there are too few integers in the set to allow its O(log n) access time to shine? If so, is there anything else I can do to speed up this function?</p>