911590 - profile and optimize region code

Status: RESOLVED DUPLICATE of bug 845874

(Core :: Graphics, defect)

Description

[Andreas Gal :gal]

In bug 911471 questions came up regarding the optimality of our region code. I have heard anecdotal testimony before that the current code is slow. Lets do some profiling and see if there is something to fix here.

Comment 1

[Andreas Gal :gal]

I annotated the region destructor to print the number of rects in the region when its destructed. Empty regions and simple regions (single rect) dominate by far. Regions with a few rects (2..6) occur. Regions with more than 6 rects are really rare, statistically speaking.

Looking at our region code, its obvious that a few things are off:
1. Since regions are predominantly empty, we should optimize for a small size of the region object. Having mBoundRect for example is questionable. Most regions have so few rects, walking them might be overall faster because of better cache behavior.
2. Having a custom allocator for regions that uses chunks seems bad. Most regions would do fine with a few builtin rects and beyond that we can use malloc since many rects in a region are so rare. We have to balance this with empty rects, so we should probably have an indirection in between to optimize for empty rects in particular.

820613 0
562418 1
29370 2
30356 3
13161 4
5172 5
3911 6
1692 7
3090 8
1120 9
2423 10
 892 11
 577 12
 735 13
1040 14
1701 15
1244 16
 808 17
1199 18
 247 19
 442 20
 227 21
 115 22
  58 23
  89 24
   8 25
  19 26
  11 27
   6 28
  34 29
  38 30
  11 31
 150 32
   9 33
  16 34
  19 35
 106 36
  10 37
 105 38
 140 39
  74 40
  75 41
   6 42
  23 43
   1 44
   3 45
   7 46
   4 47
   4 48
   6 49
   1 50
   5 51
   4 52
   2 53
   2 54
   1 59
  11 60

Comment 2

[Boris Zbarsky [:bzbarsky]]

The actual concern I had in bug 911471 is that OptimizeInward() just drops all the rects if we're over the # of rects boundary.  It might be better to do something like drop half the rects, maybe the smaller ones... or something.

Comment 3

[Andreas Gal :gal]

Looking at the histogram I would say that case is so astronomically rare, I don't think we care.

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Jeff has a bug on replacing our regions implementation with pixman regions, which behave better, but I can't find the bug right now.

Comment 5

[Jeff Muizelaar [:jrmuizel]]

Pixman's regions seem to have much better behaviour and bug 845874 has patches to use them.