[Fontconfig] Excessive short-lived allocations during FcFontSet

[Chris Wilson]

As everyone who has profiled the memory allocation behaviour of a Pango
using app knows (hi Behdad!) FcCharSetFindLeafCreate dominates the
profile during initialisation. And then every time Pango has to load a
new fontset.

For a very simple GTK+ application just opening a window:
Allocator		nAllocs		nBytes
FcCharSetFindLeafCreate 62886		2012352
FcCharSetPutLeaf        9361		11441108

For gedit loading a UTF-8 demo:
FcCharSetFindLeafCreate 124872		3995904
FcCharSetPutLeaf        18656		22372816

AIUI, the current behaviour of FcSortWalk() is to create a new FcCharSet
on each iteration that is the union of the previous iteration with the
next FcCharSet in the font set. This causes the existing FcCharSet to be
duplicated in its entirety and then allocates fresh leaves for the new
FcCharSet. In essence the number of allocations is quadratic wrt the
number of fonts required.

By introducing a new FcCharSet operator to merge a new FcCharSet into an
existing FcCharset, we can reduce the allocations to cover the leaves in
all the fonts in the set and no more.

For gedit loading the UTF-8 demo, after the patch:
FcCharSetFindLeafCreate 1940		62080
FcCharSetPutLeaf        281		190336

Please review, thanks.
--
Chris Wilson
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Reduce-number-of-allocations-during-FcSortWalk.patch
Type: application/mbox
Size: 0 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/fontconfig/attachments/20080423/9ae8cfce/attachment.bin