title: Efficient handling of list of small vectors with Compile
body: <p>Often we need to process data consisting of a list of coordinates: <code>data = {{x1,y1}, {x2,y2}, ..., {xn,yn}}</code>.  It could be 2D or 3D coordinates, or any other arbitrary length list of fixed length small vectors.</p>
  
  <p>Let me illustrate how to use <code>Compile</code> for such problems using the simple example of summing up a list of 2D vectors:</p>
  
  <pre><code>data = RandomReal[1, {1000000, 2}];
  </code></pre>
  
  <p>First, obvious version:</p>
  
  <pre><code>fun1 = Compile[{{vec, _Real, 2}},
    Module[{sum = vec[[1]]},
     Do[sum += vec[[i]], {i, 2, Length[vec]}];
     sum
     ]
    ]
  </code></pre>
  
  <p>How fast is it?</p>
  
  <pre><code>In[13]:= Do[fun1[data], {10}] // Timing
  Out[13]= {4.812, Null}
  </code></pre>
  
  <p>Second, less obvious version:</p>
  
  <pre><code>fun2 = Compile[{{vec, _Real, 1}},
    Module[{sum = vec[[1]]},
     Do[sum += vec[[i]], {i, 2, Length[vec]}];
     sum
     ]
    ]
  
  In[18]:= Do[
    fun2 /@ Transpose[data],
    {10}
    ] // Timing
  
  Out[18]= {1.078, Null}
  </code></pre>
  
  <p>As you can see, the second version is much faster.  Why?  Because the crucial operation, <code>sum += ...</code> is an addition of numbers in <code>fun2</code> while it's an addition of <em>arbitrary length</em> vectors in <code>fun1</code>.</p>
  
  <p>You can see a practical application of the same "optimization" <a href="https://stackoverflow.com/questions/8008995/chaos-game-for-dna-sequences/8009589#8009589">in this asnwer of mine</a>, but many other examples could be given where this is relevant.</p>
  
  <p>Now in this simple example the code using <code>fun2</code> is not longer or much more complex than <code>fun1</code>, but in the general case it very well might be.</p>
  
  <p><strong>How can I tell <code>Compile</code> that one of its arguments is not an arbitrary <code>n*m</code> matrix, but a special <code>n*2</code> or <code>n*3</code> one, so it can do these optimization automatically rather than using a generic vector addition function to add tiny length-2 or length-3 vectors?</strong></p>
  
  <hr>
  
  <h2>Addendum</h2>
  
  <p>To make it more clear what's happening, we can use <code>CompilePrint</code>:</p>
  
  <p><code>CompilePrint[fun1]</code> gives</p>
  
  <pre><code>        1 argument
          5 Integer registers
          5 Tensor registers
          Underflow checking off
          Overflow checking off
          Integer overflow checking on
          RuntimeAttributes -&gt; {}
  
          T(R2)0 = A1
          I1 = 2
          I0 = 1
          Result = T(R1)3
  
  1   T(R1)3 = Part[ T(R2)0, I0]
  2   I3 = Length[ T(R2)0]
  3   I4 = I0
  4   goto 8
  5   T(R1)2 = Part[ T(R2)0, I4]
  6   T(R1)4 = T(R1)3 + T(R1)2
  7   T(R1)3 = CopyTensor[ T(R1)4]]
  8   if[ ++ I4 &lt; I3] goto 5
  9   Return
  </code></pre>
  
  <p><code>CompilePrint[fun2]</code> gives</p>
  
  <pre><code>        1 argument
          5 Integer registers
          4 Real registers
          1 Tensor register
          Underflow checking off
          Overflow checking off
          Integer overflow checking on
          RuntimeAttributes -&gt; {}
  
          T(R1)0 = A1
          I1 = 2
          I0 = 1
          Result = R2
  
  1   R2 = Part[ T(R1)0, I0]
  2   I3 = Length[ T(R1)0]
  3   I4 = I0
  4   goto 8
  5   R1 = Part[ T(R1)0, I4]
  6   R3 = R2 + R1
  7   R2 = R3
  8   if[ ++ I4 &lt; I3] goto 5
  9   Return
  </code></pre>
  
  <p>I chose to include this rather than the considerably lengthier C version, where the timing difference is even more pronounced.</p>