Fontconfig - Apr 2008 - Excessive short-lived allocations during FcFontSet

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

On Wed, 2008-04-23 at 09:38 +0100, Chris Wilson wrote:
> Please review, thanks.
Looks like a good bit of savings. A couple of comments:

 * I don''t think we need to publish new API here.

 * It would be more efficient (and less confusing) if FcCharSetMerge
   just did the union in-line -- it need only walk the new charset and
   not look at each page of the existing one. Plus, that leaves all of
   the other charset functions unchanged.

-- 
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url :
http://lists.freedesktop.org/archives/fontconfig/attachments/20080423/5f61d8d3/attachment.pgp

Thanks Chris!  Finally...

I suggest keeping the FcCharSetOperate name and call the new one
FcCharSetOperateInPlace().  Other than that, looks good to me.  Keith,
this single change is worth a release on itself.


Cheers,

behdad

PS.  Chris, given that you have some familiarity with the fontconfig
code now, if you feel like hacking, there''s some useful and easy bugs
to
close for 2.6:

  https://bugs.freedesktop.org/show_bug.cgi?id=14062

On Wed, 2008-04-23 at 09:38 +0100, Chris Wilson wrote:
> 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
-- 
behdad
http://behdad.org/

"Those who would give up Essential Liberty to purchase a little
 Temporary Safety, deserve neither Liberty nor Safety."
        -- Benjamin Franklin, 1759

On Wed, 2008-04-23 at 15:51 -0400, Behdad Esfahbod
wrote:
> Thanks Chris!  Finally...
> 
> I suggest keeping the FcCharSetOperate name and call the new one
> FcCharSetOperateInPlace().  Other than that, looks good to me.  Keith,
> this single change is worth a release on itself.
Yup, I''ve been meaning to do a release for a while now; having an
actual
performance improvement like this would make it quite a bit more
compelling.

-- 
keith.packard at intel.com
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url :
http://lists.freedesktop.org/archives/fontconfig/attachments/20080424/8e004e91/attachment.pgp

On Wed, 2008-04-23 at 09:20 -0700, Keith Packard wrote:
> On Wed, 2008-04-23 at 09:38 +0100, Chris Wilson wrote:
> 
> > Please review, thanks.
> 
> Looks like a good bit of savings. A couple of comments:
> 
>  * I don''t think we need to publish new API here.
> 
>  * It would be more efficient (and less confusing) if FcCharSetMerge
>    just did the union in-line -- it need only walk the new charset and
>    not look at each page of the existing one. Plus, that leaves all of
>    the other charset functions unchanged.
Thanks guys for your feedback. I''ve attached an updated patch.
-- 
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/20080425/2e70abd0/attachment.bin