[cairo] Reworking text handling

[Keith Packard]

We discovered a significant performance problem in cairo text handling
several weeks ago and I'm now trying to rectify it, along with fixing
some missing functionality in the text implementation.

I thought I'd write down what I'm doing and see if anyone has 'issues'
with the work before I finish up the remaining pieces.

First off, the major performance problem was actually in measuring text
extents, not so much in drawing the glyphs.

Text is measured in user space and draw in device space. The problem was
that the only metrics available were device space metrics, so every time
text was measured, the device space metrics were carefully converted
back to user space metrics. This computation was actualy very expensive
and dominated the simplistic profiling done.

The obvious fix here is to cache metrics up in user space. A simple
prototype was tested quite a while ago and performance improved
dramatically. However, the prototype used huge piles of memory and so
wasn't a practical solution.

The current code also stores all glyphs in one giant cache. This makes
it reasonably easy to pick a glyph at random for replacement, but makes
it very expensive to locate glyphs for other things as the cache key
must contain the face, index, scaling and rendering options. All but the
index are constant for the face, so just making a cache-per-face leaves
you indexing with the glyph index (a rather cheap operation). It also
saves piles of memory because the cache entries don't have to duplicate
all of this key data.

Inside this new per cairo_scaled_font_t object, the cache holds objects
of type cairo_scaled_glyph_t. These glyphs now hold our user-space
metrics, a device space bounding box (used to compute the bounds on a
set of glyphs) and two optional representations of the glyph, an image
surface to hold pixels for the glyph and a path to hold the outline of
the glyph.

The other change is to shrink the scaled_font_backend API down to six
functions from 10. We now have:

struct _cairo_scaled_font_backend {
    cairo_status_t
    (*create_toy)  (cairo_toy_font_face_t       *toy_face,
                    const cairo_matrix_t        *font_matrix,
                    const cairo_matrix_t        *ctm,
                    const cairo_font_options_t  *options,
                    cairo_scaled_font_t        **scaled_font);

Create a scaled font from a toy face

    void
    (*fini)             (void                   *scaled_font);

Clean up a scaled font

    cairo_status_t
    (*scaled_glyph_init)        (void                        *scaled_font,
                                 cairo_scaled_glyph_t        *scaled_glyph,
                                 cairo_scaled_glyph_shape_t   shapes);

Initialize a scaled glyph structure by computing and saving user-space
metrics and (optionally) the surface and/or path. There are helper
functions _cairo_scaled_glyph_set_* to make this easier.

    cairo_status_t
    (*scaled_glyph_ensure_shape)(void                        *scaled_font,
                                 cairo_scaled_glyph_t        *scaled_glyph,
                                 cairo_scaled_glyph_shape_t   shapes);

Ammend an existing glyph to add either a surface and/or a path.

    unsigned long
    (*ucs4_to_index)            (void                        *scaled_font,
                                 uint32_t                     ucs4);

Convert unicode to glyph indices. Should this be in the cairo_face_t
backend instead?

    cairo_int_status_t
    (*show_glyphs)      (void                   *scaled_font,
                         cairo_operator_t        operator,
                         cairo_pattern_t        *pattern,
                         cairo_surface_t        *surface,
                         int                     source_x,
                         int                     source_y,
                         int                     dest_x,
                         int                     dest_y,
                         unsigned int            width,
                         unsigned int            height,
                         const cairo_glyph_t    *glyphs,
                         int                     num_glyphs);

An optional API to show glyphs in some font-system accelerated fashion.
FreeType doesn't use this, but Windows will.

I've also restructured the drawing code so that the gstate asks the surface
to draw text, and failing that, asks the font to draw it. This
makes it a bit simpler looking to me.

I've got this mostly working with no surface backend code yet (everything
goes through the slowest possible path). Adding surface backend code will
happen soon.

Oh, the other big change is that this patch includes cworth's new cache
code. That entailed removing all other uses of the old cache, those were
only related to the baroque glyph caching scheme described above.

TODO:
	1)	Fix bugs. Things are kinda working, but lots of
		stuff remains busted.

	2)	Add Xlib backend support. Should be reasonably
		straightforward

	3)	Connect surface backend to font cache management
		so that Render glyphs are freed when the local
		cache entry is destroyed.

	4)	Fix Windows backend.

So far, performance at least appears to be solved; it is measuring text
about 5 times faster than the old code, and most of the time is now
spent in the cache lookup code, which we may want to bypass for a simple
linear array -- the number of glyphs is reasonably small and they're
packed densely together numerically.

Patch:	http://freedesktop.org/~keithp/cairo-scaled-glyph.diff

-keith

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : http://lists.freedesktop.org/archives/cairo/attachments/20050822/641bcefa/attachment-0001.pgp