title: Testing each element in collection of collection only once
body: <p>I'm coding a CPU-raytracer for x86 consumer hardware (and in C++11, using gcc 4.7.1 so far).</p>
  
  <p>I'm using a kD-tree holding my triangles and am intersecting all triangles in a leaf with my given ray. This task takes most of the runtime according to my profiler (depending on the kd-tree and input and chosen parameters about ~50% or more of my runtime).</p>
  
  <pre><code>for (auto p : leaf.triangles) {
      p-&gt;intersect(ray, t, intersection); //void intersect(const Ray&amp; ray, float t, Intersection&amp; output)
  }
  </code></pre>
  
  <p>(p is of type pointer to an triangle somewhere else in a vector).</p>
  
  <p>My kd tree may be expanded deeper, but that forces me to have more leafs sharing the same triangle. Because I'm often forced to test adjacent leafs I will end up intersecting the same triangles over and over again. This may be my greatest bottleneck so far.</p>
  
  <p>A simple solution seemed some kind of list that would keep all the pointers I already intersected. I decided to use an <code>unordered_set&lt;Triangle*&gt;</code> because of its constant average cost for <code>find</code> and <code>emplace</code>.</p>
  
  <pre><code>unordered_set&lt;Triangle*&gt; alreadyTested; //used for all leafs a ray visits
  for (auto p : leaf.triangles) {
       if (alreadyTested.find(p) == alreadyTested.end()) {
            p-&gt;intersect(ray, t, intersection);
            alreadyTested.emplace(p);
       }
  }
  </code></pre>
  
  <p>compiled with GCC -O3</p>
  
  <p>My runtime overall increased by a factor of 4 to 8. My profiler tells me that <code>find</code> and <code>emplace</code> take about the same time as a single <code>intersect</code> negating any speed bonus. Missed jump predictions may be the reason of the massive slowdown.</p>
  
  <p>How do I do it right ("it" being calling intersect only once per triangle)?</p>