[Intel-gfx] [PATCH 1/3] drm/i915: BUG_ON() when cmd/reg tables are not sorted

[Volkin, Bradley D]

On Thu, Mar 27, 2014 at 02:47:03PM -0700, Kenneth Graunke wrote:
> Does any code actually rely on the tables being sorted?

Not today. The idea was to make it easier to move to an algorithm that does
in the future. For example, I thought binary search might be an easy win.

> 
> I didn't see any early breaks or returns once the parser has gone past a
> command...it seems to keep looking through the entire list.
> 
> As an aside:
> 
> It seems like find_cmd could be implemented a lot more efficiently.

Yes, it's definitely a naive implementation. I've been hesitant to do too
much in the way of optimizing the searches until we have some real perf
regressions to look at. I've received several suggested improvements that,
at least with quick implementations, didn't show gains in the benchmarks
I had available (e.g. binary search; using kmap_atomic instead of vmap). My
hope is that with the feature now generally available, we'll see some data
from benchmarks people care about and go from there.

I like your suggestion though and I'll add it to the list.

Thanks,
Brad

> Currently, most 3DSTATE commands are not in the tables - they only
> appear to contain commands that need special handling.  This means that
> find_cmd will walk through every command in every table before falling
> back to the default info struct.
> 
> As an example, my window manager (KWin) submitted a render ring batch
> with 700 commands in it.  Most of those commands need to walk through
> every command in every table, which is about 48 entries.  That's 33,600
> iterations through tables, which seems...kind of excessive.
> 
> For example, 3D commands all have the form 0x78xx or 0x79xx.  We could
> use the xx as an array index into a lookup table, and get O(1) access
> instead of O(n).  Or, at least something similar.
> 
> Thanks again for your work on this, Brad.
> 
> --Ken
>