Quoting Tvrtko Ursulin (2021-01-27 15:58:12) > 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. In the following patches, we introduce a new sort key to the scheduler, a virtual deadline. This imposes a different structure to the tree. Using a priority sort, we have very few priority levels active at any time, most likely just the default priority and so the rbtree degenerates to a single elements containing the list of all ready requests. The deadlines in contrast are very sparse, and typically each request has a unique deadline. Instead of being able to simply walk the list during dequeue, with the deadline scheduler we have to iterate through the bst on the critical submission path. Skiplists are vastly superior in this instance due to the O(1) iteration during dequeue, with very similar characteristics [on average] to the rbtree for insertion. This means that by using skiplists we can introduce a sparse sort key without degrading latency on the critical submission path. As an example, one simple case where we try to do lots of semi-independent work without any priority management (gem_exec_parallel), the lock hold times were [worst] [total] [avg] 973.05 6301584.84 0.35 # plain rbtree 559.82 5424915.25 0.33 # best rbtree with pruning 208.21 3898784.09 0.24 # skiplist 34.05 5784106.01 0.32 # rbtree without deadlines 23.35 4152999.80 0.24 # skiplist without deadlines -Chris _______________________________________________ Intel-gfx mailing list Intel-gfx@xxxxxxxxxxxxxxxxxxxxx https://lists.freedesktop.org/mailman/listinfo/intel-gfx
