title: Fastest way to cross-tabulate two massive logical vectors in R
body: <p>For two logical vectors, <code>x</code> and <code>y</code>, of length > 1E8, what is the fastest way to calculate the 2x2 cross tabulations?</p>
  
  <p>I suspect the answer is to write it in C/C++, but I wonder if there is something in R that is already quite smart about this problem, as it's not uncommon.</p>
  
  <p>Example code, for 300M entries (feel free to let N = 1E8 if 3E8 is too big; I chose a total size just under 2.5GB (2.4GB).  I targeted a density of 0.02, just to make it more interesting (one could use a sparse vector, if that helps, but type conversion can take time).</p>
  
  <pre><code>set.seed(0)
  N = 3E8
  p = 0.02
  x = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)
  y = sample(c(TRUE, FALSE), N, prob = c(p, 1-p), replace = TRUE)
  </code></pre>
  
  <p>Some obvious methods:</p>
  
  <ol>
  <li><code>table</code></li>
  <li><code>bigtabulate</code></li>
  <li>Simple logical operations (e.g. <code>sum(x &amp; y)</code>)</li>
  <li>Vector multiplication (boo)</li>
  <li><code>data.table</code></li>
  <li>Some of the above, with <code>parallel</code> from the <code>multicore</code> package (or the new <code>parallel</code> package)</li>
  </ol>
  
  <p>I've taken a stab at the first three options (see my answer), but I feel that there must be something better and faster.</p>
  
  <p>I find that <code>table</code> works very slowly.  <code>bigtabulate</code> seems like overkill for a pair of logical vectors.  Finally, doing the vanilla logical operations seems like a kludge, and it looks at each vector too many times (3X? 7X?), not to mention that it fills a lot of additional memory during processing, which is a massive time waster.</p>
  
  <p>Vector multiplication is usually a bad idea, but when the vector is sparse, one may get an advantage out of storing it as such, and then using vector multiplication.</p>
  
  <p>Feel free to vary <code>N</code> and <code>p</code>, if that will demonstrate anything interesting behavior of the tabulation functions.  :)</p>
  
  <hr>
  
  <p>Update 1. My first answer gives timings on three naive methods, which is the basis for believing <code>table</code> is slow.  Yet, the key thing to realize is that the "logical" method is grossly inefficient.  Look at what it's doing:</p>
  
  <ul>
  <li>4 logical vector operations</li>
  <li>4 type conversions (logical to integer or FP - for <code>sum</code>)</li>
  <li>4 vector summations</li>
  <li>8 assignments (1 for the logical operation, 1 for the summation)</li>
  </ul>
  
  <p>Not only that, but it's not even compiled or parallelized.   Yet, it still beats the pants off of <code>table</code>.  Notice that <code>bigtabulate</code>, with <em>an extra type conversion</em> (<code>1 * cbind...</code>) still beats <code>table</code>.</p>
  
  <p>Update 2.  Lest anyone point out that logical vectors in R support <code>NA</code>, and that that will be a wrench in the system for these cross tabulations (which is true in most cases), I should point out that my vectors come from <code>is.na()</code> or <code>is.finite()</code>.  :)  I've been debugging <code>NA</code> and other non-finite values - <a href="https://stackoverflow.com/questions/9167376/how-to-force-an-error-if-non-finite-values-na-nan-or-inf-are-encountered">they've been a headache for me recently</a>.  If you don't know whether or not all of your entries are <code>NA</code>, you could test with <code>any(is.na(yourVector))</code> - this would be wise before you adopt some of the ideas arising in this Q&amp;A.</p>
  
  <hr>
  
  <p>Update 3. Brandon Bertelsen asked a very reasonable question in the comments: why use so much data when a sub-sample (the initial set, after all, is a sample ;-)) might be adequate for the purposes of creating a cross-tabulation?  Not to drift too far into statistics, but the data arises from cases where the <code>TRUE</code> observations are very rare, for both variables.  One is a result of a data anomaly, the other due to a possible bug in code (possible bug because we only see the computational result - think of variable <code>x</code> as "Garbage In", and <code>y</code> as "Garbage Out".  AS a result, the question is whether the issues in the output caused by the code are solely those cases where the data is anomalous, or are there some other instances where good data goes bad?  (This is why I asked a question about <a href="https://stackoverflow.com/questions/9167376/how-to-force-an-error-if-non-finite-values-na-nan-or-inf-are-encountered">stopping when a <code>NaN</code>, <code>NA</code>, or <code>Inf</code> is encountered</a>.)</p>
  
  <p>That also explains why my example has a low probability for <code>TRUE</code> values; these really occur much less than 0.1% of the time.</p>
  
  <p>Does this suggest a different solution path?  Yes: it suggests that we may use two indices (i.e. the locations of <code>TRUE</code> in each set) and count set intersections.  I avoided set intersections because I was burned awhile back by Matlab (yes, this is R, but bear with me), which would first sort elements of a set before it does an intersection.  (I vaguely recall the complexity was even more embarrassing: like <code>O(n^2)</code> instead of <code>O(n log n)</code>.)</p>