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

[Chris Wilson]

Quoting Tvrtko Ursulin (2021-01-29 09:37:27)
> 
> On 28/01/2021 16:26, Chris Wilson wrote:
> > Quoting Tvrtko Ursulin (2021-01-28 15:56:19)
> 
> >>> -static void assert_priolists(struct i915_sched_engine * const se)
> >>> -{
> >>> -     struct rb_node *rb;
> >>> -     long last_prio;
> >>> -
> >>> -     if (!IS_ENABLED(CONFIG_DRM_I915_DEBUG_GEM))
> >>> -             return;
> >>> -
> >>> -     GEM_BUG_ON(rb_first_cached(&se->queue) !=
> >>> -                rb_first(&se->queue.rb_root));
> >>> -
> >>> -     last_prio = INT_MAX;
> >>> -     for (rb = rb_first_cached(&se->queue); rb; rb = rb_next(rb)) {
> >>> -             const struct i915_priolist *p = to_priolist(rb);
> >>> -
> >>> -             GEM_BUG_ON(p->priority > last_prio);
> >>> -             last_prio = p->priority;
> >>> -     }
> >>> +     root->prng = next_pseudo_random32(root->prng);
> >>> +     return  __ffs(root->prng) / 2;
> >>
> >> Where is the relationship to I915_PRIOLIST_HEIGHT? Feels root->prng %
> >> I915_PRIOLIST_HEIGHT would be more obvious here unless I am terribly
> >> mistaken. Or at least put a comment saying why the hack.
> > 
> > HEIGHT is the maximum possible for our struct. skiplists only want to
> > increment the height of the tree one step at a time. So we choose a level
> > with decreasing probability, and then limit that to the maximum height of
> > the current tree + 1, clamped to HEIGHT.
> > 
> > You might notice that unlike traditional skiplists, this uses a
> > probability of 0.25 for each additional level. A neat trick discovered by
> > Con Kolivas (I haven't found it mentioned elsewhere) as the cost of the
> > extra level (using P=.5) is the same as the extra chain length with
> > P=.25. So you can scale to higher number of requests by packing more
> > requests into each level.
> > 
> > So that is split between randomly choosing a level and then working out
> > the height of the node.
> 
> Choosing levels with decreasing probability by the virtue of using ffs 
> on a random number? Or because (BITS_PER_TYPE(u32) / 2) is greater than 
> I915_PRIOLIST_HEIGHT?

        /*
         * Given a uniform distribution of random numbers over the u32, then
         * the probability each bit is unset is P=0.5. The probability of a
         * successive sequence of bits being unset is P(n) = 0.5^n [n > 0].
         *   P(level:1) = 0.5
         *   P(level:2) = 0.25
         *   P(level:3) = 0.125
         *   P(level:4) = 0.0625
         *   ...
         * So we can use ffs() on a good random number generator to pick our
         * level. We divide by two to reduce the probability of choosing a
         * level to .25, as the cost of descending a level is the same as
         * following an extra link in the chain at that level (so we can
         * pack more nodes into fewer levels without incurring extra cost,
         * and allow scaling to higher volumes of requests without expanding
         * the height of the skiplist).
         */

-Chris