[cairo] [patch] caching, glyph, font, and glyphset patch

[Keith Packard]

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 
information.

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 
penalty.

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.

-keith


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 228 bytes
Desc: not available
Url : http://lists.freedesktop.org/archives/cairo/attachments/20040928/eb1f6d41/attachment.pgp