Bug 1250 - Keep index by family name
Summary: Keep index by family name
Alias: None
Product: fontconfig
Classification: Unclassified
Component: library (show other bugs)
Version: 2_1
Hardware: x86 (IA32) Linux (All)
: high normal
Assignee: fontconfig-bugs
QA Contact: Behdad Esfahbod
Depends on:
Reported: 2004-08-31 07:02 UTC by Owen Taylor
Modified: 2015-05-01 21:20 UTC (History)
6 users (show)

See Also:
i915 platform:
i915 features:


Description Owen Taylor 2004-08-31 07:02:29 UTC
Currently, the way to walk over all fonts in the system with Pango is

 for family in fontmap.list_families():
    for face in family.list_faces():
        description = face.describe()

What Pango stores for a family is the family name, and to get to the
list of faces for that family, it calls FcFontList()

What Pango stores for the face is the family and style, and to get to
the details of the face, it calls FcFontMatch().

Since FcFontList() and FcFontMatch() are O(n_fonts_on_system), the
above algorithm is O(n_fonts_on_system^3) !

Now, I can optimize this somewhat in Pango by storing a reference
to the full pattern with the face object,  but I dont' think it's
unreasonable to expect that a call to FcFontList or FcFontMatch that
includes a family name should be O(1) not O(n_fonts_on_system).
The memory usage for a hash table from family=>fonts with that family
should be minimal compared to the total memory usage for fontconfig.
Comment 1 Owen Taylor 2004-11-15 09:18:40 UTC
has a patch from Brian Ryner.
Comment 2 Keith Packard 2004-12-04 21:56:17 UTC
I think this ties rather tightly into my hoped-for redesign of the cache files
into something suitable for shared mmaping.  Let's work on this for fontconfig
2.4, and also restructure the matching algorithm to better support CSS2.
Comment 3 Patrick Lam 2006-02-22 16:17:27 UTC
Couldn't find the patch.  FcFontSetMatch is, alas, still O(n), but the constant
should be much smaller now...
Comment 4 Behdad Esfahbod 2008-08-12 16:34:07 UTC
Keith, now with mmap there, do you have any idea how to fasten things up?
Comment 5 Keith Packard 2008-08-12 19:31:36 UTC
Mapped cache files don't really affect this issue. What is needed is a new pattern matching design which performs some CSS-ish match algorithm instead of the current global scoring.

I know most fontconfig users now cache match results; would it still be useful to come up with a more efficient basic font matching system? Would the abilty to do more CSS-compatible matching make this worthwhile even if performance is no longer a significant concern?
Comment 6 Behdad Esfahbod 2015-05-01 21:20:33 UTC
Anything like that would be fontconfig3, so we can close this right now.

Use of freedesktop.org services, including Bugzilla, is subject to our Code of Conduct. How we collect and use information is described in our Privacy Policy.