title: Calculating sum of 2D array is slow
body: <p>I'm building an Android app using RenderScript. I want to create a 2D array that contains a sum of all the ints in the rectangle from the origin up till (x, y). </p>
  
  <p>As stated <a href="https://developer.android.com/guide/topics/renderscript/compute" rel="nofollow noreferrer">here</a>, RenderScript is a C99-derived language. Any function with the <code>RS_KERNEL</code> keyword will be called once for every pixel by the framework. No guarantees are made in which order this will be called. From Java/Kotlin <code>generateGridPixelCount</code> is called by providing it a piece of allocated memory. Every item is set by the returned value accordingly.</p>
  
  <p>So, for example:</p>
  
  <pre><code>   Input                Output
                    -----------------
                    | 0 | 0 | 0 | 0 |
  -------------     -----------------
  | 1 | 1 | 1 |     | 0 | 1 | 2 | 3 | 
  -------------     -----------------
  | 0 | 1 | 1 |     | 0 | 1 | 3 | 5 |
  -------------     -----------------
  | 1 | 1 | 1 |     | 0 | 2 | 5 | 8 |
  -------------     -----------------
  </code></pre>
  
  <p>For small arrays this is doable, but when the array is as big as the screen (1080x2280), the function I've written takes ages.</p>
  
  <pre><code>static bool shouldCheckPixel(uint x, uint y) {
      return (x + y) % (width / stepSize) == 0 || (x - y) % (width / stepSize) == 0;
  }
  
  int RS_KERNEL generateGridPixelCount(uint x, uint y) {
      int pixelCount = 0;
  
      for (int dx = 0; dx &lt; x; dx++) {
          for (int dy = 0; dy &lt; y; dy++) {
              if (shouldCheckPixel(dx, dy)) {
                  pixelCount++;
              }
          }
      }
  
      return pixelCount;
  }
  </code></pre>
  
  <p>However, if <code>pixelCount++;</code> is removed or the if statement is removed, it finishes almost instantly. It's when it's combined when it gets slow.</p>
  
  <p>Previous <code>RS_KERNEL</code> function loop over the output. This can be reversed:</p>
  
  <pre><code>void RS_KERNEL generateGridPixelCount(uchar4 input, uint x, uint y) {
     if (shouldCheckPixel(x, y)) {
        for (int x = 0; x &lt; dx; x++) {
           for (int y = 0; y &lt; dy; y++) {
              rsAtomicInc(*pixelArray[x][y]);
           }
        }
     }
  }
  </code></pre>
  
  <p>What's the best way to calculate this array?</p>