[Intel-gfx] [PATCH 20/41] drm/i915: Replace priolist rbtree with a skiplist

[Chris Wilson]

Quoting Tvrtko Ursulin (2021-01-27 15:10:43)
> 
> On 25/01/2021 14:01, Chris Wilson wrote:
> > Replace the priolist rbtree with a skiplist. The crucial difference is
> > that walking and removing the first element of a skiplist is O(1), but
> 
> I wasn't (and am not) familiar with them, but wikipedia page says 
> removal is O(logN) average case to O(N) worst case.
> 
> If I understand correctly O(1) could be ignoring the need to traverse 
> from top to bottom level and removing the element from all. But since 
> I915_PRIOLIST_HEIGHT is fixed maybe it is okay to call it O(1).

Correct, since we removing the first element, we do not need to do the
lgN search and can just move the next[I915_PRIOLIST_HEIGHT] forwards.
(Although, I did starting doing the lgN removal for timeslicing as
traversing the empty levels were showing up in worst case lock hold
times.) But the primary means of removing from the skiplist is as we
consume the first request during the dequeue.

> I wonder though why this wouldn't mean skip list would be worse for both 
> lightly loaded and highly-loaded scenarios? Presumably height would need 
> to be balanced to compensate for that.

I think the answer is yes. skiplists uses probablistic balancing so they
are only from a bird's eye view as good as a rbtree. If you look at the
perf tests, the skiplists are generally faster, but it's close overall.

What sold me was lock_stat and that I could remove a few hacky patches
trying to hide some of the worst case behaviour of rbtree and how we had
frees within the critical submit path.
 
> In summary I have no idea for what number of in-flight requests would 
> they be better.
> 
> How about putting this patch aside for now since it doesn't sound it is 
> critical for deadline scheduling per se?

Oh no, we are not going back to the hacky patches like
https://patchwork.freedesktop.org/patch/407913/?series=84900&rev=1
https://patchwork.freedesktop.org/patch/407903/?series=84900&rev=1
-Chris