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

[Chris Wilson]

Quoting Tvrtko Ursulin (2021-01-28 16:42:44)
> 
> On 28/01/2021 16:26, Chris Wilson wrote:
> > Quoting Tvrtko Ursulin (2021-01-28 15:56:19)
> >> On 25/01/2021 14:01, Chris Wilson wrote:
> >>>    struct i915_priolist {
> >>>        struct list_head requests;
> >>
> >> What would be on this list? Request can only be on one at a time, so I
> >> was thinking these nodes would have pointers to list of that priority,
> >> rather than lists themselves. Assuming there can be multiple nodes of
> >> the same priority in the 2d hierarcy. Possibly I don't understand the
> >> layout.
> > 
> > A request is only on one list (queue, active, hold). But we may still
> > have more than one request at the same deadline, though that will likely
> > be limited to priority-inheritance and timeslice deferrals.
> > 
> > Since we would need pointer to the request, we could only reclaim a
> > single pointer here, which is not enough to warrant reducing the overall
> > node size. And while there is at least one user of request->sched.link,
> > the list maintenance will still be incurred. Using request->sched.link
> > remains a convenient interface.
> 
> Lost you.
> 
> Is the data structure like this and I will limit to priorities for 
> simplicity:
> 
>     Level1:     [-1]------------->[1]
>     Level0:     [-1]---->[0]----->[1]
> [SENTINEL]
> 
> Each of the boxes is struct i915_priolist?

Although each level is circular.

1: SENTINEL -> [-1] --------> [1] -> SENTINEL
0: SENTINEL -> [-1] -> [0] -> [1] -> SENTINEL

Ah. I think I see the cause of confusion here. Each column, not each
box, is a i915_priolist.

So the skiplist is really a set of [HEIGHT] singly linked lists, with
each list containing a sorted subset of the whole. And each descending
level includes every member from the level above, until we reach a
linked list of all i915_priolist in [0].

[skip, hopefully I caught the central point]

SENTINEL[2] is a list of all i915_priolist of level >= 2
SENTINEL[1] is a list of all i915_priolist of level >= 1
SENTINEL[0] is a list of all i915_priolist.

As we randomly assign i915_priolist.level, SENTINEL[1] should have half
the elements of SENTINEL[0], and SENTINEL[2] should have half again the
elements of SENTINEL[1] (hence its ability to do a binary/lgN search for
a key, each level is a bisection of the last).
-Chris