title: In C# why is it faster to Create a HashSet from a List, instead of starting with a HashSet?
body: <p>I have a method that takes an upper limit, and returns a list of primes numbers up to that limit.</p>
  
  <pre><code>    public static List&lt;int&gt; AllPrimesUnder(int upperLimit)
  </code></pre>
  
  <p>I later decided that I really just needed to do lookups on the list, often just asking the question "Is This Prime". Since I was dealing with all primes under values like a million, I realized that HashSet was the structure I should be using. Certainly the lookup using the result of the method was faster, but the method its self was <em>slower</em>.</p>
  
  <p>I believe the reason it's slower is because HashSet checks for duplicates before adding, while a List just shoves it on the end. What surprised me, and what spawned the question and title, is why starting with a List and using it to create HashSet, like so: </p>
  
  <pre><code>    hashSet = new HashSet&lt;int&gt;(Prime.AllPrimesUnder(1000000));
  </code></pre>
  
  <p>is faster than using a Hashset internal to the method, enabling a call like this:</p>
  
  <pre><code>    hashSet = Prime.AllPrimesUnder_Hash(1000000);
  </code></pre>
  
  <p>If the slowdown is in the duplicate checking, it should have to do the same amount of checking no matter what, right? This is likely where my understanding is failing me.</p>
  
  <p>Here are the times I'm getting for primes under one million.</p>
  
  <ul>
  <li>0.1136s Pure Hash</li>
  <li>0.0975s Pure List (<em>expected to be faster</em>)</li>
  <li>0.0998s Pure List Converted to Hash (<em>not expected</em>)</li>
  </ul>
  
  <p>If the reason for this can be explained in simple terms, I'd love to hear it. I suppose at a minimum what I'm looking for is enough of an understanding to know if I should start with a List or a HashSet if the end result will be a large HashSet of items.</p>
  
  <p>I've added the body of the prime method below, but note that all interaction with the data structure is identical (code wise) between the two. I don't believe how I add data to the structure should effect the anomaly. </p>
  
  <pre><code>    public static List&lt;int&gt; AllPrimesUnder(int upperLimit)
      {
          List&lt;int&gt; primeList = new List&lt;int&gt;();
          primeList.Add(2);
          int testNumber = 3;
          bool isPrime;
  
          while (testNumber &lt;= upperLimit)
          {
              isPrime = true;
  
              foreach (int prime in primeList)
              {
                  if (testNumber % prime == 0)
                  {
                      isPrime = false;
                      break;
                  }
                  if (testNumber &lt; prime*prime)
                      break;
              }
  
              if (isPrime)
                  primeList.Add(testNumber);
  
              testNumber++;
          }
  
          return primeList;
      }
  </code></pre>
  
  <p><strong>Edit: By request I am adding the code for the Hash method. If it looks nearly identical that's because it is.</strong></p>
  
  <pre><code>public static HashSet&lt;int&gt; AllPrimesUnder_Hash(int upperLimit)
  {
      HashSet&lt;int&gt; primeHash = new HashSet&lt;int&gt;();
      primeHash.Add(2);
      int testNumber = 3;
      bool isPrime;
  
      while (testNumber &lt;= upperLimit)
      {
          isPrime = true;
  
          foreach (int prime in primeHash)
          {
              if (testNumber % prime == 0)
              {
                  isPrime = false;
                  break;
              }
              if (testNumber &lt; prime*prime)
                  break;
          }
  
          if (isPrime)
              primeHash.Add(testNumber);
  
          testNumber++;
      }
  
      return primeList;
  }
  </code></pre>
  
  <p><strong>Also by request is the (ugly hackish) code I used to test the execution time:</strong></p>
  
  <pre><code>        Stopwatch stopWatch = new Stopwatch();
          int iterations = 1;
          HashSet&lt;int&gt; hashSet = new HashSet&lt;int&gt;();
          List&lt;int&gt; list = new List&lt;int&gt;();
  
          stopWatch.Restart();
          for (int i = 0; i &lt; iterations; i++)
          {
              hashSet = Prime.AllPrimesUnder_Hash(1000000);
          }
          stopWatch.Stop();
  
          Console.WriteLine("Hash: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));
  </code></pre>
  
  <p>//////////////////////////</p>
  
  <pre><code>        stopWatch.Restart();
          for (int i = 0; i &lt; iterations; i++)
          {
              hashSet = new HashSet&lt;int&gt;(Prime.AllPrimesUnder(1000000));
          }
          stopWatch.Stop();
  
  
          Console.WriteLine("List converted: " + (stopWatch.Elapsed.TotalSeconds / iterations).ToString("#.###################"));
  </code></pre>