[cairo] [patch] caching, glyph, font, and glyphset patch
keithp at keithp.com
Tue Sep 28 13:08:31 PDT 2004
Around 12 o'clock on Sep 28, "graydon hoare" wrote:
> most of this work is internal plumbing; the only changes to the
> user-visible API are that you can't scale or transform fonts directly
> anymore, you have to "set" them into a cairo_t and then
> scale/transform the "current font" (you're actually just adjusting the
> gstate now, since fonts are sizeless).
This is different from how PostScript works. For discussion purposes,
let's also consider what it would look like with an intermediate data
structure which held a pointer to the sizeless font along with size
Aside from this, the design seems like a great step forward. Thanks
Graydon. I particularily like the use of a generic cache mechanism to
handle both glyphs and fonts.
Now some nits about the specific implementation...
I'd like to see the cairo_cache_bucket structure reduced in size; open
addressed hash tables are best if left nearly empty, so large caches will
necessitate large amounts of wasted space here. I suggest that the cache
entries themselves be simply pointers to objects and that each object have
a required set of members on the front of its storage. Mark 'NIL' buckets
with NULL pointers, and 'DEAD' buckets with a pointer to a fixed object.
With this change, we can leave the hash table less than 50% empty without
I also generally save the hash value in the object so that collisions in
the size of the hash table can be mitigated by comparing the full hash
value, but that's a less significant optimization when you can leave the
hash table nearly empty.
Also, I generally use a single hash function for each object and then use
two different modulus values instead, I pick a pair of prime numbers and
use the larger for a primary modulus and the smaller for the secondary.
I got this from Knuth years ago and it has the advantage of needing only a
single hash function for each data type while spreading values evenly in
the prime-sized hash table.
I don't have any suggestions for the remaining bits of the implementation;
a lot of that will need the experience of use before we know if it is right.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Size: 228 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20040928/eb1f6d41/attachment.pgp
More information about the cairo