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