The SDL forums have moved to discourse.libsdl.org.
This is just a read-only archive of the previous forums, to keep old links working.

Does anyone (particularly Sam and Ryan) have any objections to pulling an external library into SDL? Because I have an idea that could significantly improve the performance of SDL's 3d-accelerated rendering, but it would require a multimap. Neither SDL nor the C standard library has a multimap implementation, but I could build one with uthash and utarray, which are both fairly small and BSD-licensed.

Mason

On 4/15/13 2:46 PM, Mason Wheeler wrote:

I'd rather we have a simple hashtable implementation in SDL.

What's the plan?

--ryan.



_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Ryan,
Can you elaborate on the reason why uthash is not attractive to you? Just wondering since I was looking at it possibly using it recently for the Embroidermodder 2 project. I came across it after looking at some hash benchmarks and the license is appealing. It's a single header so if the interface isn't to your liking, making a small wrapper around it should be fairly straight forward. Have you or Sam done any work on an SDL hash implementation?
- Swyped from my droid.

I think the problem is the fact it's an extra dependency.

That said, I'm not very fond of its use of macros at all :S (I guess
this is one place where C++ wins by far, templates would make this
trivial) I wonder if that's an issue too.

2013/4/15, Jonathan Greig:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Sik,
I completely understand about the extra dependency issue, although with it being a single header, it should be hardly a problem shipping it with the SDL sources. At least that's the way I look at it.
I don't particularly care for macros either so maybe that could be part of it too.
- Swyped from my droid.

What is the optimization?


On 04/15/2013 02:46 PM, Mason Wheeler wrote:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Same gut feel here - seems reasonable to extend SDL functionality via a copy-and-add of the single uthash.h file as the uthash license allows redistribution in source form. Judging from its test coverage, the code seems reasonably stable so that SDL maintainers would not have to expect a lot of future updates in the SDL source tree of this file either.

In my view it really comes down what the user benefit would actually be over a custom implementation inside a SDL based App (if possible).

On 4/15/2013 6:59 PM, Jonathan Greig wrote:

Here's the basic idea.

The internals of SDL's rendering API are atrocious, to put it bluntly. It does everything in Immediate Mode, which modern versions of OpenGL and Direct3D have moved away from because it's so slow. GLES doesn't even support Immediate Mode, so if you look at SDL's GLES renderer, it does the closest thing it can find to Immediate Mode, sending one call to OpenGL every time someone calls SDL_RenderCopy.


The way to do rendering fast is to keep the number of library calls to a minimum, and pass as much data as possible all at once in an array. Of course, that's not the way people use SDL; they use SDL to draw a bunch of sprites, one at a time. So to be fast, SDL has to keep track of the bookkeeping for them.


The way to do this is with a multimap, mapping textures to lists of drawing coordinates. You turn SDL_RenderCopy into an operation that adds a pair of rects to a texture's mapped list, and SDL_RenderPresent into an operation that iterates over the multimap and for each texture, builds two arrays of vertices (one for screen coordinates and one for texture coordinates) as buffers and passes them to the renderer all at once.


I've got a Delphi implementation that sped up my rendering significantly, about 3x faster than stock SDL rendering. With a multimap in C, I could port this concept to the SDL internals.


The one tricky thing here, the concept that my renderer has that SDL doesn't, is Z-order. If you're no longer deterministically drawing in the order in which draw calls are received, but instead grouping them by texture, which are in turn sorted by hash order (essentially random,) you need a Z-order parameter to make sure the right things draw on top of the right things, and what you end up with is an array of multimaps.


I know it probably sounds very complicated, but it's only a few hundred lines of code (plus the implementations of the hash and the dynamic array, because C doesn't have them built in) and it makes rendering *much* faster.


Mason



From: Ryan C. Gordon
To: SDL Development List
Sent: Monday, April 15, 2013 6:20 PM
Subject: Re: [SDL] External dependencies in the renderer?


On 4/15/13 2:46 PM, Mason Wheeler wrote:

I'd rather we have a simple hashtable implementation in SDL.

What's the plan?

--ryan.



_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Looking at the GLES2 renderer (which is probably the cleanest implementation we've got right now), isn't there an expectation with the design of the API that the RenderCopy operation is carried out immediately? So in theory, couldn't someone could call RenderCopy with an SDL_Texture * and two rects, then mess with the contents of the texture, then call RenderPresent?



On 16 April 2013 10:41, Mason Wheeler wrote:

I haven't even clicked on the link, so I can't say anything about
uthash. As an external piece of code, I'm hesitant to add it to SDL,
since that has caused annoyances in the past, unless there was a really
good reason.

(Doubly-so for a hashtable. I mean, a hashtable? Do we really need to
scour the internet for a hashtable?)

I imagine it's probably a fine piece of code in itself, though.

--ryan.


_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Um, is a hashtable needed for this idea as opposed to a regular array?
I mean, you're literally just adding entries to a queue, you don't
even need to retrieve them back. As for the Z order, just assign an
unique Z to each entry and be done with it. Sure, you may run out of
range, but at that point you probably have queued up enough primitives
to be worth flushing the batch.

Also yeah, I wonder about the textures too, although I guess you can
always force a flush in that case.

2013/4/15, Ryan C. Gordon:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

A hashtable is needed because this is *not* just a queue. To get good performance out of it, it has to be grouped by texture. The idea is that you select each texture once, and perform all of the drawing for it all at once. What we have now is just a queue, and it's horribly slow. On a complicated scene, it's the difference between a few dozen API calls, or a few tens of thousands of them. (Yes, I have rendered scenes that involved with SDL.)


Mason



From: Sik the hedgehog
To: SDL Development List
Sent: Monday, April 15, 2013 8:01 PM
Subject: Re: [SDL] External dependencies in the renderer?


Um, is a hashtable needed for this idea as opposed to a regular array?
I mean, you're literally just adding entries to a queue, you don't
even need to retrieve them back. As for the Z order, just assign an
unique Z to each entry and be done with it. Sure, you may run out of
range, but at that point you probably have queued up enough primitives
to be worth flushing the batch.

Also yeah, I wonder about the textures too, although I guess you can
always force a flush in that case.

2013/4/15, Ryan C. Gordon:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Ok, so the optimization assumes that a rendering bottleneck is the cost of
switching textures, and intends to minimize the number texture switches by
delaying primitives, then re-ordering them by texture and Z.

I've seen this before. It can be done, but there are caveats. The biggest
challenge is you need to cache the entire GL state for each delayed primitive.
The implementation is effectively an "intermediate mode" layer unto itself. The
layer is a massive `todo` buffer with three phases: queue everything, analyze
(re-order) the queue, then execute the queue as a batch. If you don't choose the
batch size wisely, it's possible to lose any parallelism that you might have had
when GL calls were mixed in with scene graph calls. The second challenge is to
support transparency and other effects that depend on multiple passes in a
specific order, or that play games with the z-buffer (or other tests.)



On 04/15/2013 10:41 PM, Mason Wheeler wrote:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

I'm beating my own drum by saying this, but the SDL_RenderGeometry function I made may be a better compromise to enhance rendering speed, assuming the task at hand implies rendering multiple parts of the same texture. If you are rendering a low number of quads out of each texture, it'll probably give you the same performance as regular SDL_RenderCopy (it has no need for a hash table though).

Anyway, it'll probably come down to the same sort of arguments we saw before, and the "why don't you do it in OpenGL" will eventually pop up








2013/4/16 John




--
Gabriel.

Blimey, forgot about transparency. John's right, if you start including semitransparent objects into your queue, then you can't just throw them in the texture-centric batch and let the depth test sort them out; you'd have to run a separate pass afterwards in sequential painting order.



On 16 April 2013 11:36, John wrote:

Another thing is that scenes that complex will most likely have many
textures anyway which is bound to completely negate the advantage. And
yeah, considering the SDL renderer would be most likely used to render
sprites in 2D, proper transparency support is pretty much a must (even
if you don't draw "proper" translucent stuff you may be bound to be
doing it with antialiased borders).

Coming to think on it, this also means sprites *must* be rendered in
order, otherwise the depth buffer will completely screw up the
transparency. Given the order of the primitives is completely up to
the GPU, there isn't much that can be done short of multiple calls.

2013/4/16, Scott Percival:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Yeah. That's what the Z order is there for.




From: Sik the hedgehog
To: SDL Development List
Sent: Monday, April 15, 2013 9:48 PM
Subject: Re: [SDL] External dependencies in the renderer?


Another thing is that scenes that complex will most likely have many
textures anyway which is bound to completely negate the advantage. And
yeah, considering the SDL renderer would be most likely used to render
sprites in 2D, proper transparency support is pretty much a must (even
if you don't draw "proper" translucent stuff you may be bound to be
doing it with antialiased borders).

Coming to think on it, this also means sprites *must* be rendered in
order, otherwise the depth buffer will completely screw up the
transparency. Given the order of the primitives is completely up to
the GPU, there isn't much that can be done short of multiple calls.

2013/4/16, Scott Percival:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Not exactly. The optimization assumes that the principal rendering
bottleneck is the overhead involved in sending scene data to the
graphics card, which assumption is borne out by testing data. It
intends to minimize the number of *drawing calls* by delaying primitives
and sending them in batches, ordered by Z and texture.


You avoid having to cache "the entire GL state" by the simple expedient
of flushing the to-do buffer if a call comes in that changes the GL state.
All you need to keep cached is the map of textures to arrays of coordinates.
And transparency works fine as long as you have a Z parameter to order
by. Things get drawn on top of each other in the prescribed order. I've
been using this for a while now. The system works.



From: John
To:
Sent: Monday, April 15, 2013 8:36 PM
Subject: Re: [SDL] External dependencies in the renderer?


Ok, so the optimization assumes that a rendering bottleneck is the cost of
switching textures, and intends to minimize the number texture switches by
delaying primitives, then re-ordering them by texture and Z.

I've seen this before. It can be done, but there are caveats. The biggest
challenge is you need to cache the entire GL state for each delayed primitive.
The implementation is effectively an "intermediate mode" layer unto itself. The
layer is a massive `todo` buffer with three phases: queue everything, analyze
(re-order) the queue, then execute the queue as a batch. If you don't choose the
batch size wisely, it's possible to lose any parallelism that you might have had
when GL calls were mixed in with scene graph calls. The second challenge is to
support transparency and other effects that depend on multiple passes in a
specific order, or that play games with the z-buffer (or other tests.)



On 04/15/2013 10:41 PM, Mason Wheeler wrote:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Also, if having many textures "is bound to completely negate the advantage,"
why do I see a 3x performance improvement when rendering big, complex
scenes this way?


Don't assume, don't guess; measure. I've measured it, and this way works.



From: Sik the hedgehog
To: SDL Development List
Sent: Monday, April 15, 2013 9:48 PM
Subject: Re: [SDL] External dependencies in the renderer?


Another thing is that scenes that complex will most likely have many
textures anyway which is bound to completely negate the advantage. And
yeah, considering the SDL renderer would be most likely used to render
sprites in 2D, proper transparency support is pretty much a must (even
if you don't draw "proper" translucent stuff you may be bound to be
doing it with antialiased borders).

Coming to think on it, this also means sprites *must* be rendered in
order, otherwise the depth buffer will completely screw up the
transparency. Given the order of the primitives is completely up to
the GPU, there isn't much that can be done short of multiple calls.

Is there any guarantee in OpenGL at all that primitives are drawn in
the order they appear in the buffer (which would seem inefficient)?
Otherwise ordering by Z is pretty much eventually going to break in
the future.

2013/4/16, Mason Wheeler:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Somehow this turned into a scenegraph discussion, to which I recommend this reading material:
http://home.comcast.net/~tom_forsyth/blog.wiki.html#[[Scene%20Graphs%20-%20just%20say%20no]]

On a topic of correctness however, isn't it kind of implicit in a 2D graphics API that your draw order is sacred? You usually want things to overlap in a specific way.

An order-preserving technique has no need of hashes or any such thing, it only needs to skip issuing state calls that are the same, and some things that are not order-dependent can be combined
regardless (like using glBufferSubData to write multiple quads into the vertex buffer before drawing any of them, for a considerable savings in driver overhead).

On 04/15/2013 10:25 PM, Sik the hedgehog wrote:


--
LordHavoc
Author of DarkPlaces Quake1 engine - http://icculus.org/twilight/darkplaces
Co-designer of Nexuiz - http://alientrap.org/nexuiz
"War does not prove who is right, it proves who is left." - Unknown
"Any sufficiently advanced technology is indistinguishable from a rigged demo." - James Klass
"A game is a series of interesting choices." - Sid Meier

_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

If we want to be blunt, the real issue here isn't switching to a
scenegraph (besides the complexity it may bring - it's debatable
whether it's worth it or just tell users to use OpenGL directly for
those extreme cases) but bringing in an external dependency to SDL...

2013/4/16, Forest Hale:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

As long as you have access to uintptr_t, there should be few to zero
concerns about the range of anything that can be described as an id
number, and it's pretty easy to describe z-order as an id in this
case.



After double checking the header files to make certain I was
remembering correctly, it looks like a dirty-rect queue should work
fairly well. Algorithm:
1) Check the current render command against the dirty-rect(s) of the
current queue node, if
1a: They overlap, then create a new queue node and make this commend
the first entry in that node, else
1b: Add this command to the current node, and expand the node's
dirty-rect(s) to cover the new area.

You can use a new node every time you use a different texture, you can
combine multiple textures in a single node (after all, you know they
won't overlap), you can send point & line data either the same way, or
with custom nodes, you can provide hook functions to shoe-horn your
own rendering system into the queue, etc. This would also be a first
step towards the oft-requested (albeit somewhat bone-headed) feature
of issuing rendering calls from whichever thread you want.

The main issue is how the system would work. I think that what Mason's
suggesting would require that you look through nodes until you find a
dirty-rect collision (even a partial dirty-rect collision would count,
and the only thing that gets looked at is the actual coordinates,
whether e.g. the texture is or isn't the same doesn't matter). At that
point you go back to the most-recently-checked node that used the same
texture and add your command there, or add your command in a new node
if there wasn't a previous node.

That should (I think) provide the correct sequencing, while also
ensuring that you reuse textures as few times as you can get away
with.
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

If SDL Renderer is turning into a beast, it should be punted to its own library, much like SDL_mixer and so on.

As a matter of practicality however, I think it is fine being in the core, so long as it stays simple and direct.

My understanding of the problem that warranted this discussion is that it is abusive about Draw calls and texture switches or some such? That has nothing at all to do with draw order, and if the draw
order is less important than performance then the app should take care of sorting them first, it isn't the duty of SDL to fix an app performance issue.

As far as some underlying technical details of GL and D3D APIs, I would recommend implementing a draw queue (fully buffered API) that is flushed to real calls to the driver after enough vertex data
has accumulated to make it worthwhile, this also allows multiple consecutive draws to be merged if their state is the same, a lot of optimizations can be done once you have that "lookahead" capability
inherent in the flush routine.

On 04/16/2013 12:30 AM, Sik the hedgehog wrote:


--
LordHavoc
Author of DarkPlaces Quake1 engine - http://icculus.org/twilight/darkplaces
Co-designer of Nexuiz - http://alientrap.org/nexuiz
"War does not prove who is right, it proves who is left." - Unknown
"Any sufficiently advanced technology is indistinguishable from a rigged demo." - James Klass
"A game is a series of interesting choices." - Sid Meier

_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

The problem is that SDL issues calls for every thing you draw, i.e. it
does things the naive way rather than being 100% optimized for GPUs
(which really are more optimized towards rendering entire complex 3D
scenes than rendering generic 2D stuff). He wants to change the way
the renderer works so it fits that better, the problem being he wants
to pull in an external dependency (uthash).

2013/4/16, Forest Hale:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

If you buffer draws, you get higher performance.

If you additionally sort them, you get even higher performance but break the most basic assumption of a 2D graphics API - that things occur in the order specified.

I see no reason to use uthash here, I do see great reason to buffer things.

Why is uthash still the subject of this discussion? We're not going to reach a conclusion on the broad topic of outside dependencies, it's better to focus on the specific problem at hand.

On 04/16/2013 02:08 AM, Sik the hedgehog wrote:


--
LordHavoc
Author of DarkPlaces Quake1 engine - http://icculus.org/twilight/darkplaces
Co-designer of Nexuiz - http://alientrap.org/nexuiz
"War does not prove who is right, it proves who is left." - Unknown
"Any sufficiently advanced technology is indistinguishable from a rigged demo." - James Klass
"A game is a series of interesting choices." - Sid Meier

_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

to my mind came the following idea:

have a todo queue, but only for one texture. Flush it when it's full or when another texture should be rendered.
-> if speed is an issue for a specific program, the programmer can sort the calls by texture and get the speedup
-> we don't need a complicated system or an external dependency in SDL

_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Optimization is a task of the programmer, not the library.
That said, SDL's interface is too high-level to enable the programmer to optimize render performance.

I see a couple options here:
1) Add another function for rendering the same texture multiple times:

2) Add a "sprite batch" API:

GL likes to generate texture ids incrementing from 1. I don't recall whether
that's standard or reliable. If it is, you wouldn't want a general purpose hash
table to map texture ids.


On 04/15/2013 11:09 PM, Mason Wheeler wrote:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

It's not "ordering by Z and texture" but "grouping by Z and texture". Every render with a Z of 1 will get sent before every render with a Z of 2, and so on. That's why I said you end up with an array of multimaps.


Mason



From: Sik the hedgehog
To: Mason Wheeler; SDL Development List
Sent: Monday, April 15, 2013 10:25 PM
Subject: Re: [SDL] External dependencies in the renderer?


Is there any guarantee in OpenGL at all that primitives are drawn in
the order they appear in the buffer (which would seem inefficient)?
Otherwise ordering by Z is pretty much eventually going to break in
the future.

2013/4/16, Mason Wheeler:

That sounds like ordering by Z to me, no?

The GLES device vendors advise against implementing your own depth sorting
because the GPU depth test does it much faster, more efficiently, can correctly
handle overlaps, and runs in parallel with the CPU.

Also, z is floating point in transformed view coordinates which means there may
not be many duplicate z values to group by.

Have you measured the cost of switching the active texture unit? The number of
switches that will be saved by this optimization is easy to calculate, it's
roughly the number of primitives minus the number of textures.



On 04/16/2013 12:41 PM, Mason Wheeler wrote:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

The problem is that I think the idea is to use a single batch for
everything... Again, I'm not sure at all that this kind of Z ordering
is reliable in that case. The problem is that the safest way is
sending one thing at a time, i.e. one draw call per SDL function,
which is the very thing we're trying to avoid...

Also yeah, the Z range is why I said we could run out of them. On PCs
we have 24-bit depth buffer, OK (though somebody could still attempt
to set 16-bit, and I guess on 2D this could make sense), but on mobile
I wonder how the Z range is handled (especially on referred renderers
as opposed to standard rasterizer ones).

And yes, OpenGL numerates textures from 1 onwards (this is true for
all objects, really), but remember you can create gaps by deleting
textures, and OpenGL will attempt to fill those if I recall correctly
(I'm not sure about the details).

2013/4/16, John:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

OK, since it's apparently not clear from my original proposal, I wasn't
talking about sending Z coordinates to OpenGL or Direct3D in any way.
I was talking about using them on the SDL side. You'd end up with a
certain number of layers, (most 2D games draw 4 or 5 distinct layers
IME,) and each layer would have its own Z number.

Each Z layer would have its own texture-to-coordinates multimap.
When it's time to render everything, it looks like this (pseudocode):

for each multimap in layers:
for each texture in multimap:
CreateCoordArrays(multimap[texture])
SelectTexture(texture)
RenderArrays


It's really that simple, in concept. Everything draws on top of what
it's supposed to draw on top of. There's no need to send Z ordering
to the GPU. There's no atrociously slow one-API-render-per-call.
I've tested it. It works, and it's about 3x faster than the current system
on large, complicated scenes.


There are only two real downsides: 1) it requires a multimap to work
properly, which we need a library for because libc provides neither a
multimap implementation nor the fundamental primitives needed to
build one (a map and a dynamic array).
And 2) SDL_RenderCopy does not currently have a Z parameter on
it, which is needed to make layering work correctly.



Mason



From: Sik the hedgehog
To: SDL Development List
Sent: Tuesday, April 16, 2013 4:37 PM
Subject: Re: [SDL] External dependencies in the renderer?


The problem is that I think the idea is to use a single batch for
everything... Again, I'm not sure at all that this kind of Z ordering
is reliable in that case. The problem is that the safest way is
sending one thing at a time, i.e. one draw call per SDL function,
which is the very thing we're trying to avoid...

Also yeah, the Z range is why I said we could run out of them. On PCs
we have 24-bit depth buffer, OK (though somebody could still attempt
to set 16-bit, and I guess on 2D this could make sense), but on mobile
I wonder how the Z range is handled (especially on referred renderers
as opposed to standard rasterizer ones).

And yes, OpenGL numerates textures from 1 onwards (this is true for
all objects, really), but remember you can create gaps by deleting
textures, and OpenGL will attempt to fill those if I recall correctly
(I'm not sure about the details).

2013/4/16, John:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org

Not just SDL_RenderCopy, nothing in the rendering API has.

It looks like basically what you're doing is just telling the API that
the order doesn't matter as long as specific groups are, if I'm
understanding correctly (which isn't how the SDL API works). Indeed
that's a valid optimization but not one that would work with the
current API, if that's the case. Is that correct?

2013/4/16, Mason Wheeler:
_______________________________________________
SDL mailing list

http://lists.libsdl.org/listinfo.cgi/sdl-libsdl.org