Optimizing nested loop in run length encoding function I'm currently working on a tool that needs to decode, modify data, then re-encode that data using the Yaz0 format. Everything has been in a working state, but after running some code analysis on my program it turns out it is spending an obscene amount of time on the encoding portion (Over 95%). However, I cannot think of a way to make the loop in this function any more efficient than it already is.

So far I have compacted the inside for loop which used to have a break and two ifs inside it. I also tried using OpenMP, but since I am running async operations on all cores it just hindered performance. I haven't touched anything outside the loop because it is negligible as far as the analysis shows.

Here is a screenshot of the code analysis as well as the function in question. The code is compiled using Microsoft Visual Studio 2013 in debug mode and ran on Windows 8.1.



uint32_t simpleEnc(uint8_t *src, uint32_t size, uint32_t pos, uint32_t *pMatchPos)
{
  int32_t startPos = pos - 0x1000;
  uint32_t numBytes = 1;
  uint32_t matchPos = 0;
  int32_t diff = size - pos;

  if (startPos &lt; 0)
  {
    startPos = 0;
  }

  for (int i = startPos; i &lt; pos; i++)
  {
    for (int j = 0; j &lt; diff &amp;&amp; src[i + j] == src[j + pos]; j++)
    {
      if (j &gt; numBytes)
      {
        numBytes = j;
        matchPos = i;
      }
    }
  }

  *pMatchPos = matchPos;

  if (numBytes == 2)
  {
    numBytes = 1;
  }

  return numBytes;
}


Are there any performance optimizations I've missed? I know there is some barrier where this will just take a fair amount of time, but since this is the biggest bottleneck in the program I want it to be as fast as possible.
Output arguments

You currently use a pointer for your output argument. While this is a matter of preference, I found it confusing considering the other pointer argument indicates an array. I would use a reference for pMatchPos instead of a pointer.

const-correctness and immutability

In a pointer-math-heavy function like this, it is especially important to document which values can and cannot be changed within the function body. Use const to specify that a value is not mutable. This allows the compiler to do more error-checking, and makes the code easier to reason about.

Most of your function parameters aren't modified inside the function, so they can be marked const. Note especially src, which has two const modifiers, indicating its value cannot be changed, nor can the data it points to.

Also, startPos is only mutated when it is clamped to zero. You can rewrite this using std::max() (from the algorithm header) to put the initialization on one line, and then make it const as well. Note that using max() requires pos be a signed type, otherwise there will be overflow errors.

An improved beginning of your function would look like this:

uint32_t simpleEnc(uint8_t const * const src, uint32_t const size,
                   int32_t const pos, uint32_t&amp; pMatchPos) // note type changes, cf. above
{
    const int32_t startPos = std::max(0, pos - 0x1000);
    const int32_t diff = size - pos;


Magic numbers

I don't know what 0x1000 is supposed to represent, and neither will anyone else who doesn't intimately understand the algorithm. It would be better to assign it to a named constant. Something like

constexpr uint32_t BACKTRACK_AMOUNT = 0x1000; // Pick a more accurate name, though.


Naming

pMatchPos uses Hungarian notation. Please don't do this. Instead, try to come up with a more descriptive name, or just leave off the prefix.