title: Improving performance of network coding-encoding
body: <p>I'm currently developing a Java-based library for network coding (http://en.wikipedia.org/wiki/Network_coding). This is very CPU-intensive and therefore need some help optimizing the encoding stage. What I'm essentially doing is that I'm creating random-linear combinations of the original data where addition is XOR and multiplication is a Galois-field multiplication (in GF(2^16)).</p>
  
  <p>I've come as far as I'm capable with the optimizations. For instance I'm using tricks like this: <a href="http://groups.google.com/group/comp.dsp/browse_thread/thread/cba57ae9db9971fd/7cd21eec39ddae1a?hl=en&amp;lnk=gst&amp;q=Sarwate+Galois#7cd21eec39ddae1a" rel="nofollow">http://groups.google.com/group/comp.dsp/browse_thread/thread/cba57ae9db9971fd/7cd21eec39ddae1a?hl=en&amp;lnk=gst&amp;q=Sarwate+Galois#7cd21eec39ddae1a</a> to make the multiplications faster.</p>
  
  <p>I'm therefore looking for tips on how to optimize this further. It's hard to profile since the profilers I've used doesn't give you any hints on which operation is the most expensive (e.g. is it the array-lookup or the XOR). So I'm at the point where I'm sort of randomly trying out different ideas and test if it improves the overall performance. </p>
  
  <p>More specifically some potential areas of improvement that I need help on are:</p>
  
  <ul>
  <li>How can I make sure that Java can skip the bounds-checking on the array-operations?</li>
  <li>How can I retrieve the bytecode that actually executes after the HotSpot is done optimizing?</li>
  </ul>
  
  <p>Here's the core of the algorithm. It might be hard to understand out of context but if you see any unnecessarily expensive operations I'm doing then please let me know!</p>
  
  <pre><code>int messageFragmentStart = 0;
  int messageFragmentEnd = fragmentCharSize;
  
  int coefficientIndex = fragmentID * messageFragmentsPerDataBlock;
  final int resultArrayIndexStart = fragmentID * fragmentCharSize;
  
  for (int messageFragmentIndex = 0; messageFragmentIndex &lt; messageFragmentsPerDataBlock; messageFragmentIndex++) {
      final int coefficientLogValue = coefficientLogValues[coefficientIndex++];
      int resultArrayIndex = resultArrayIndexStart;
      for (int i = messageFragmentStart; i &lt; messageFragmentEnd; i++) {
          final int logSum = coefficientLogValue + logOfDataToEncode[i];
          final int messageMultipliedByCoefficient = expTable[logSum];                        
          resultArray[resultArrayIndex++] ^= messageMultipliedByCoefficient;
      }
      messageFragmentStart += fragmentCharSize;
      messageFragmentEnd = Math.min(messageFragmentEnd + fragmentCharSize, maxTotalLength);
  }
  </code></pre>