Chris Wilson
2008-Apr-23 08:07 UTC
[PATCH] 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 | 62 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
src/fcint.h | 3 ++
src/fcmatch.c | 13 ++--------
3 files changed, 68 insertions(+), 10 deletions(-)
diff --git a/src/fccharset.c b/src/fccharset.c
index 5da1312..87f7945 100644
--- a/src/fccharset.c
+++ b/src/fccharset.c
@@ -452,6 +452,68 @@ FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
}
+FcCharSet *
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b)
+{
+ FcCharSet *fcs;
+ FcCharSetIter ai, bi;
+
+ if (a == NULL) {
+ return FcCharSetCopy ((FcCharSet *) b);
+ } else if (a->ref == FC_REF_CONSTANT) {
+ fcs = FcCharSetCreate ();
+ if (fcs == NULL)
+ return NULL;
+ } else
+ fcs = a;
+
+ FcCharSetIterStart (a, &ai);
+ FcCharSetIterStart (b, &bi);
+ while (ai.leaf || bi.leaf)
+ {
+ if (ai.ucs4 < bi.ucs4)
+ {
+ if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
+ goto bail;
+
+ FcCharSetIterNext (a, &ai);
+ }
+ else if (bi.ucs4 < ai.ucs4)
+ {
+ if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
+ goto bail;
+
+ FcCharSetIterNext (b, &bi);
+ }
+ else
+ {
+ FcCharLeaf leaf;
+
+ if (FcCharSetUnionLeaf (&leaf, ai.leaf, bi.leaf))
+ {
+ if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
+ goto bail;
+ }
+
+ FcCharSetIterNext (a, &ai);
+ FcCharSetIterNext (b, &bi);
+ }
+ }
+
+ if (fcs != a)
+ FcCharSetDestroy (a);
+
+ return fcs;
+
+bail:
+ FcCharSetDestroy (fcs);
+
+ if (fcs != a)
+ FcCharSetDestroy (a);
+
+ return NULL;
+}
+
static FcBool
FcCharSetSubtractLeaf (FcCharLeaf *result,
const FcCharLeaf *al,
diff --git a/src/fcint.h b/src/fcint.h
index ddeb745..599f3cf 100644
--- a/src/fcint.h
+++ b/src/fcint.h
@@ -639,6 +639,9 @@ FcNameParseCharSet (FcChar8 *string);
FcPrivate FcCharLeaf *
FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4);
+FcPrivate FcCharSet *
+FcCharSetMerge (FcCharSet *a, const FcCharSet *b);
+
FcPrivate FcBool
FcCharSetSerializeAlloc(FcSerialize *serialize, const FcCharSet *cs);
diff --git a/src/fcmatch.c b/src/fcmatch.c
index f041052..dc08655 100644
--- a/src/fcmatch.c
+++ b/src/fcmatch.c
@@ -602,16 +602,9 @@ FcSortWalk (FcSortNode **n, int nnode, FcFontSet *fs,
FcCharSet **cs, FcBool tri
{
if (trim || build_cs)
{
- if (*cs)
- {
- ncs = FcCharSetUnion (ncs, *cs);
- if (!ncs)
- return FcFalse;
- FcCharSetDestroy (*cs);
- }
- else
- ncs = FcCharSetCopy (ncs);
- *cs = ncs;
+ *cs = FcCharSetMerge (*cs, ncs);
+ if (*cs == NULL)
+ return FcFalse;
}
FcPatternReference (node->pattern);
--
1.5.4.3
--=-5WIYBf96v6lfQwDBC8An--