On 27/01/2021 15:44, Chris Wilson wrote:
Quoting Chris Wilson (2021-01-27 15:33:05)
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
To be extra clear, the biggest drawback in using deadlines as the sort
key is that they are very, very sparse in comparison to priorities.
Where we would typically have only a single priority level for every
request, with deadlines we typically have a new deadline with every
request (and it's not until we get into priority bumping or timeslice
deferring do we start to see the deadlines coalesce). In this situation,
the lgN list traversal of rbtree during execlists_dequeue() was
abyssmal, and so as the skiplists give similar lgN insertion but O(1)
list traversal, the difference is enough to completely negate the
overhead of having more levels to process. It is a dramatic improvement.
Okay makes sense. The change in key drives the requirement so just
please mention in the commit message and I'll tackle the skip list
mechanics in the meantime.
Regards,
Tvrtko
_______________________________________________
Intel-gfx mailing list
Intel-gfx@xxxxxxxxxxxxxxxxxxxxx
https://lists.freedesktop.org/mailman/listinfo/intel-gfx
