Performance problems with index validation code for drawElements

• Component: WebGL
• Status: RESOLVED FIXED

[Kenneth Russell]

The code added in https://bugs.webkit.org/show_bug.cgi?id=31239 which validates indices during drawElements calls is inefficient and performs repeated work every frame. It is difficult to optimize these checks for all usage patterns, but a simple cache of the maximum index per element array buffer can bring a large speedup in the common case.

[Kenneth Russell]

Created attachment 44734 [details]
Patch

Added a cache of the maximum index for each element type to WebGLBuffer, querying it before iterating through the indices in the client-side copy of the buffer's data. Hoisted checks of the size of the element array itself into validateElementArraySize to avoid duplicating code.

Because this is a performance fix I wasn't able to write a layout test for it. A manual test, manual-tests/webgl/ManyPlanetsDeepHiRes.html, was added which runs 50% faster after this fix. All previous layout tests for out-of-range indices continue to pass.

[WebKit Review Bot]

style-queue ran check-webkit-style on attachment 44734 [details] without any errors.

[Oliver Hunt]

Comment on attachment 44734 [details]
Patch

What happens if I write an out of range value into the array?  Afaict that won't invalidate the cache

[Kenneth Russell]

The only way to upload data to the GL's element array is via bufferData or bufferSubData.

If there is any way that mutating a WebGL[T]Array can cause the client-side data referred to by the WebGLBuffer to change, that is a separate preexisting bug that needs to be filed. The current validation code would already be wrong in that case. Data with an out of range value could be uploaded to the GL, and then the source WebGLUnsignedByte/UnsignedShortArray could be mutated to change the out of range value to a valid one. The validation code would pass, since it is looking at client-side data, but the GL's uploaded version could still cause a crash.

[Darin Fisher (:fishd, Google)]

Comment on attachment 44734 [details]
Patch

> Index: WebCore/html/canvas/WebGLBuffer.cpp
...
> +void WebGLBuffer::setCachedMaxIndex(unsigned long type, long value)
> +{
> +    int numEntries = sizeof(m_maxIndexCache) / sizeof(MaxIndexCacheEntry);

nit: You should probably change "i" and "numEntries" to be size_t.


> Index: WebCore/html/canvas/WebGLBuffer.h
...
> +        // Optimization for index validation. For each type of index
> +        // (i.e., UNSIGNED_SHORT), cache the maximum index in the
> +        // entire buffer.
> +        // 
> +        // This is sufficient to eliminate a lot of work upon each
> +        // draw call as long as all bound array buffers are at least
> +        // that size.
> +        struct MaxIndexCacheEntry {
> +            unsigned long type;
> +            long maxIndex;
> +        };
> +        // OpenGL ES 2.0 only has two valid index types (UNSIGNED_BYTE
> +        // and UNSIGNED_SHORT), but might as well leave open the
> +        // possibility of adding others.
> +        MaxIndexCacheEntry m_maxIndexCache[4];
> +        unsigned m_nextAvailableCacheEntry;

nit: If I were writing this code, I would just have two member variables:

  long m_unsignedByteMaxIndex;
  long m_unsignedShortMaxIndex;

Then I'd have a case-switch in the set function that hits an ASSERT_NOT_REACHED
if given an unknown type.  That way it is really obvious that we should add
another variable in the future.  I think this is simpler, but I agree that your
solution avoids the need to make any future code changes, which might be nice.


> Index: WebCore/html/canvas/WebGLRenderingContext.cpp
...
> -    if (offset < 0 || !validateIndexArray(count, type, offset, numElements) || !validateRenderingState(numElements)) {
> +     if (offset < 0
> +         || !validateElementArraySize(count, type, offset)
> +         || ((!validateIndexArrayConservative(type, numElements) || !validateRenderingState(numElements))
> +               && (!validateIndexArrayPrecise(count, type, offset, numElements) || !validateRenderingState(numElements)))) {

nit: I think it would help readability to break this out into a separate
helper function or multiple if checks.


> Index: WebCore/manual-tests/webgl/ManyPlanetsDeepHiRes.html

Since this is mostly a copy of ManyPlanetsDeep.html, can you please
re-factor to avoid duplication?  Maybe the original HTML file can be
loaded as an IFRAME w/ a query parameter to adjust the values of the
call to makeSphere.

[Oliver Hunt]

(In reply to comment #4)
> The only way to upload data to the GL's element array is via bufferData or
> bufferSubData.
> 
> If there is any way that mutating a WebGL[T]Array can cause the client-side
> data referred to by the WebGLBuffer to change, that is a separate preexisting
> bug that needs to be filed. The current validation code would already be wrong
> in that case. Data with an out of range value could be uploaded to the GL, and
> then the source WebGLUnsignedByte/UnsignedShortArray could be mutated to change
> the out of range value to a valid one. The validation code would pass, since it
> is looking at client-side data, but the GL's uploaded version could still cause
> a crash.

Ken, ah so you're caching the bounds when the array is bound?  I was assuming a better way would be to cache on set otherwise every time you rebind an object it would need its bounds recomputed.

[Kenneth Russell]

(In reply to comment #6)
> (In reply to comment #4)
> > The only way to upload data to the GL's element array is via bufferData or
> > bufferSubData.
> > 
> > If there is any way that mutating a WebGL[T]Array can cause the client-side
> > data referred to by the WebGLBuffer to change, that is a separate preexisting
> > bug that needs to be filed. The current validation code would already be wrong
> > in that case. Data with an out of range value could be uploaded to the GL, and
> > then the source WebGLUnsignedByte/UnsignedShortArray could be mutated to change
> > the out of range value to a valid one. The validation code would pass, since it
> > is looking at client-side data, but the GL's uploaded version could still cause
> > a crash.
> 
> Ken, ah so you're caching the bounds when the array is bound?  I was assuming a
> better way would be to cache on set otherwise every time you rebind an object
> it would need its bounds recomputed.

No, the caches are computed lazily, when the index buffer is referenced by a drawElements call. The caches are cleared whenever new user data is uploaded into the index buffer via bufferData or bufferSubData.

[Kenneth Russell]

Created attachment 44910 [details]
Revised patch

Changed int variables in WebGLBuffer::setCachedMaxIndex to size_t.

Split complex if statement in WebGLRenderingContext::drawElements into a few separate ifs.

Refactored JavaScript code in ManyPlanetsDeep into ManyPlanetsDeep.js. I tried sourcing ManyPlanetsDeep.html as an iframe but the computation of the canvas's size broke, so this was the most easily achievable refactoring.

I left the caching code as is. The current code is not that complex and is future-proof.

[WebKit Commit Bot]

Comment on attachment 44910 [details]
Revised patch

Rejecting patch 44910 from commit-queue.

Failed to run "['/Users/eseidel/Projects/CommitQueue/WebKitTools/Scripts/svn-apply', '--reviewer', 'Darin Fisher', '--force']" exit_code: 1
Last 500 characters of output:
------------
|Index: WebCore/manual-tests/webgl/ManyPlanetsDeep.html
|===================================================================
|--- WebCore/manual-tests/webgl/ManyPlanetsDeep.html	(revision 52167)
|+++ WebCore/manual-tests/webgl/ManyPlanetsDeep.html	(working copy)
--------------------------
No file to patch.  Skipping patch.
2 out of 2 hunks ignored
patching file WebCore/manual-tests/webgl/ManyPlanetsDeepHiRes.html
patching file WebCore/manual-tests/webgl/resources/ManyPlanetsDeep.js

Full output: http://webkit-commit-queue.appspot.com/results/128313

[WebKit Commit Bot]

Comment on attachment 44910 [details]
Revised patch

Rejecting patch 44910 from commit-queue.

Failed to run "['/Users/eseidel/Projects/CommitQueue/WebKitTools/Scripts/svn-apply', '--reviewer', 'Darin Fisher', '--force']" exit_code: 1
Last 500 characters of output:
------------
|Index: WebCore/manual-tests/webgl/ManyPlanetsDeep.html
|===================================================================
|--- WebCore/manual-tests/webgl/ManyPlanetsDeep.html	(revision 52167)
|+++ WebCore/manual-tests/webgl/ManyPlanetsDeep.html	(working copy)
--------------------------
No file to patch.  Skipping patch.
2 out of 2 hunks ignored
patching file WebCore/manual-tests/webgl/ManyPlanetsDeepHiRes.html
patching file WebCore/manual-tests/webgl/resources/ManyPlanetsDeep.js

Full output: http://webkit-commit-queue.appspot.com/results/127359

[Eric Seidel (no email)]

I think svn-apply might be failing to create the directory if WebCore/manual-tests/webgl/ is a new directory.

[Eric Seidel (no email)]

Filed bug 32588 about the svn-apply failure.

[Kenneth Russell]

(In reply to comment #11)
> I think svn-apply might be failing to create the directory if
> WebCore/manual-tests/webgl/ is a new directory.

The directory already exists.

[Kenneth Russell]

(In reply to comment #12)
> Filed bug 32588 about the svn-apply failure.

svn-apply applies the patch successfully to a clean workspace on my machine. Is it possible that that commit bot's workspace is out of date and doesn't have this file checked out?

[Chris Marrin]

Sorry, I just saw this. Why are there files from manual-tests in this patch? This was a directory I created before we could add WebGL tests to LayoutTests. Now that we can we should really put tests there. To that end my team agreed that we should delete manual-tests/webgl. All the tests there are in other places (on my blog, in the WebGL public repo). So I deleted the directory, which may be causing some of your headaches. We can recover it, of course. But I think we should leave it deleted and use LayoutTests.

[Kenneth Russell]

(In reply to comment #15)
> Sorry, I just saw this. Why are there files from manual-tests in this patch?
> This was a directory I created before we could add WebGL tests to LayoutTests.
> Now that we can we should really put tests there. To that end my team agreed
> that we should delete manual-tests/webgl. All the tests there are in other
> places (on my blog, in the WebGL public repo). So I deleted the directory,
> which may be causing some of your headaches. We can recover it, of course. But
> I think we should leave it deleted and use LayoutTests.

I wasn't aware that this directory had been deleted. Clearly this just happened today. I only just picked up the deletion in my own workspaces.

It will be basically impossible to write an automated test to verify the performance improvement associated with this fix. The relative performance of affected test cases depends on the speeds of both the CPU and GPU. It isn't possible to quantify it in a manner such as "this test must be within X% of the performance of this other one". I'm open to suggestions on what to do but for expediency I would prefer to just drop the test from this patch. I could check it in to the WebGL public repository.

[Chris Marrin]

In cases like this, I don't think it's crucial that a test be contrived that shows performance improvement. It just needs to show proper functionality, to show that this patch doesn't break anything.

[Kenneth Russell]

(In reply to comment #17)
> In cases like this, I don't think it's crucial that a test be contrived that
> shows performance improvement. It just needs to show proper functionality, to
> show that this patch doesn't break anything.

OK. Revised patch to follow.

[Kenneth Russell]

Created attachment 44930 [details]
Revised patch

Removed manual test, the directory of which has been deleted. Updated ChangeLog to indicate that existing layout tests cover the affected functionality and continue to pass.

[WebKit Review Bot]

style-queue ran check-webkit-style on attachment 44930 [details] without any errors.

[WebKit Commit Bot]

Comment on attachment 44930 [details]
Revised patch

Clearing flags on attachment: 44930

Committed r52205: <http://trac.webkit.org/changeset/52205>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.