[PATCH xserver 0/3] Fix O(n*m) performance cliff in miarc

Adam Jackson ajax at redhat.com
Wed Mar 1 21:13:56 UTC 2017

So, way back in 946f664b, I removed a cache from the miarc code, with the
justification that arcs were rare and the performance improvement wasn't
worth it. I'd have been more right if the miarc code wasn't, what's the
word, garbage.

Turns out that for dashed arcs we end up computing an 'miArcSpanData' for
_every dash_ of the arc. This state is modestly expensive to compute, on
the order of a few milliseconds for arcs about 10000 pixels wide/high.
With the default 2/2 dash pattern that means you can take seconds to
grind your way through. This state is only sensitive to the arc width
and height, so the cache effectively hid this cost.

Rather than reintroduce the cache, this series holds on to the span data
for the duration of a single pass through the arc. So we'll still compute
things twice for double-dashed arcs, but that's still down in the "small
numbers of milliseconds per arc in the worst case" regime.

- ajax

More information about the xorg-devel mailing list