Around 10 o'clock on May 30, Keith Packard wrote:
> I think I'll convert the branches to a packed representation and take the
> performance hit when searching. That should reduce memory usage for
> the branches from 664320 to 32403 bytes. I'll take the performance hit
> for the 630K savings; the reduction in cache misses should more than
> compensate.
I've converted from btrees to a packed list of pages for each charset;
this has the advantage of dramatically simplifying the code to implement
the various algorithms as well as avoiding the previous situation where a
large amount of code couldn't be easily tested because I have no fonts
with codepoints outside the BMP. Now such fonts are treated with
the same datastructures, albiet with a possible performance impact. If
such fonts become common, I can revisit this and change the datastructures
yet again.
This new datastructure cannot support fonts with glyphs outside the 24-bit
Unicode range, although changing that would be very easy.
The changes have reduced memory to a much more modest level. With my 4803
font test case, I have the following usage:
total total mem unique unique mem
Leaves: 46572 1490304 1705 54560
Charsets: 4803 96060 526 10520
Tables: 46572 279432 6078 36468
Total: 1865796 101548 18x
The 'charsets' structures themselves are now shared, the 'tables' entry
here corresponds to the former 'branch' structure; these are simply two
parallel arrays, one with 16-bit Unicode page numbers and the other with
pointers to the underlying leaves. Searching these is done with a binary
search; slower than the former direct indexing, but the memory savings
seem worth the effort. Even with the more modest set of 383 fonts,
the savings are quite good:
total total mem unique unique mem
Leaves: 4962 158784 793 25376
Charsets: 383 7660 81 1620
Tables: 4962 29772 1917 11502
Total: 196216 38498 5x
This shows sub-linear growth in memory vs the number of fonts; I need to
try even larger sets to get a better sense of the actual function here.
Performance for Owen's test case of generating a packed list of faces for
the 'sans-serif' pattern has improved about 20% because this packed
representation is significantly better suited to that operation, and
probably because we're touching a lot less memory -- the former data
structures were spread across 600KB of memory, now we're touching only
40KB. On my 1133 MHz Athlon, with my 383 font sample, it takes about 3.8ms
per sort operation. With 4803 fonts, it takes about 42ms.
These changes have no effect on the ABI of the library; all of these
datastructures are opaque to applications.
Keith Packard XFree86 Core Team HP Cambridge Research Lab
_______________________________________________
Fonts mailing list
[EMAIL PROTECTED]
http://XFree86.Org/mailman/listinfo/fonts
