]> git.wh0rd.org - fontconfig.git/commit
Reduce number of allocations during FcSortWalk().
authorChris Wilson <chris@chris-wilson.co.uk>
Wed, 23 Apr 2008 08:07:28 +0000 (09:07 +0100)
committerBehdad Esfahbod <behdad@behdad.org>
Sat, 14 Feb 2009 00:54:00 +0000 (16:54 -0800)
commit311da2316f5d40d9b8c72c9965f7d70330f3c498
tree834083347339d6932c5bc34b8a03f75cc9429259
parent8072f4b1304efc59fee5e61efc4c4b0fc05bb8fb
Reduce number of allocations during FcSortWalk().

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
reproduced 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 method for merging a new FcCharSet with an existing
one we can change the behaviour to be effectively linear with the number
of fonts - allocating no more leaves than necessary to cover all the
fonts in the set.

For example, profiling 'gedit UTF-8-demo.txt'
    Allocator     nAllocs     nBytes
Before:
    FcCharSetFindLeafCreate 62886     2012352
    FcCharSetPutLeaf        9361     11441108
After:
    FcCharSetFindLeafCreate 1940     62080
    FcCharSetPutLeaf        281     190336

The savings are even more significant for applications like firefox-3.0b5
which need to switch between large number of fonts.
Before:
    FcCharSetFindLeafCreate 4461192     142758144
    FcCharSetPutLeaf     1124536     451574172
After:
    FcCharSetFindLeafCreate 80359     2571488
    FcCharSetPutLeaf     18940     9720522

Out of interest, the next most frequent allocations are
    FcPatternObjectAddWithBinding 526029    10520580
    tt_face_load_eblc     42103     2529892
src/fccharset.c
src/fcint.h
src/fcmatch.c