Stencil bits are often used for optimizations, for instance having full screen lighting passes only affect certain pixels.
Does the stencil test mechanism use any acceleration structures of any kind (like maybe dividing the screen into a coarser grid?) or do the perf benefits come solely from having a pre-pixel shader test that can early out waves of shaders?
I don't have a definite authoritive answer for you but I'm very confident that the answer is "yes". Here's why:
When using framebuffer objects, stencil attachments are usually combined with the depth attachment in a single texture (GL_DEPTH24_STENCIL8 or GL_DEPTH32F_STENCIL8). In fact, until recently, a combined depth and stencil was the only way to get a stencil buffer. It is now possible to create a stencil only attachment for an FBO.
This OpenGL wiki article on FBOs states (emphasis mine):
These color formats can be combined with a depth attachment with any of the required depth formats. Stencil attachments can also be used, again with the required stencil formats, as well as the combined depth/stencil formats. However, implementations are only required to support both a depth and stencil attachment simultaneously if both attachments refer to the same image.
This means that if you want stencil with no depth, you can use one of the required stencil formats. If you want depth with no stencil, you can use one of the required depth formats. But if you want depth and stencil, you must use a depth/stencil format and the same image in that texture must be attached to both the depth and stencil attachments.
All this strongly hints towards an accelerated storage format for stencils similar to the one used by depth buffers.
Also, empirically, over the years many rendering algorithms (e.g. stencil shadows) using the stencil buffer would have been prohibitively slow if stencil buffers did not use some form of accelerated structure.
The NV_packed_depth_stencil extension (2001) spec also provides interesting insight:
Many OpenGL implementations have chosen to interleave the depth and stencil buffers into one buffer, often with 24 bits of depth precision and 8 bits of stencil data.
and (emphasis mine)
Should the depth/stencil format support other standard types, like GL_FLOAT or GL_UNSIGNED_INT?
RESOLVED: No, this extension is designed to be minimalist. Supporting more types gains little because the new types will just require data format conversions. Our goal is to match the native format of the buffer, not add broad new classes of functionality.
