| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
Simplify arrangements by keeping only table sizes, remove some useless
code and fix make check.
|
|
When there are no free entries to terminate a search, checking that a
key is not in the table requires probing every entry in the table,
i.e. it degenerates in an O(n) operation.
Rehashing when the number of free entries is less than 25% makes the
expected lookup time O(1).
The hash-table micro benchmark become 4-6x faster.
Fixes https://bugs.freedesktop.org/show_bug.cgi?id=17399
|
|
If the hash value is different, the keys cannot be equal. Testing this
beforehand can avoid a few function calls and shares this optimization
across all cairo-hash uses.
|
|
Instead of artificially introducing collisions in the step value by
replacing 0 with 1 (which causes the value 1 to have twice the
frequency of any other value), the step value can simply be computed
as an uniformly distributed value in the range [1, rehash], extremes
included.
This is safe because any step value smaller than the hash modulus is
co-prime with it, hence induces an orbit which includes every integer
in [0, table_size - 1].
|
|
I updated the Free Software Foundation address using the following script.
for i in $(git grep Temple | cut -d: -f1 )
do
sed -e 's/59 Temple Place[, -]* Suite 330, Boston, MA *02111-1307[, ]* USA/51 Franklin Street, Suite 500, Boston, MA 02110-1335, USA/' -i "$i"
done
Fixes http://bugs.freedesktop.org/show_bug.cgi?id=21356
|
|
A pending commit will want to include some utility code from cairo and
so we need to extricate the error handling from the PLT symbol hiding.
|
|
We refactor the surface fallbacks to convert full strokes and fills to the
intermediate polygon representation (as opposed to before where we
returned the trapezoidal representation). This allow greater flexibility
to choose how then to rasterize the polygon. Where possible we use the
local spans rasteriser for its increased performance, but still have the
option to use the tessellator instead (for example, with the current
Render protocol which does not yet have a polygon image).
In order to accommodate this, the spans interface is tweaked to accept
whole polygons instead of a path and the tessellator is tweaked for speed.
Performance Impact
==================
...
Still measuring, expecting some severe regressions.
...
|
|
Jeff Muizelaar pointed out that the severe overallocation implicit in the
current version of the glyph cache is obnoxious and prevents him from
accepting the trunk into Mozilla. Jeff captured a trace of scaled font
and glyph usage during a tp run and presented his analysis in
http://lists.cairographics.org/archives/cairo/2009-March/016706.html
Using that data, the design was changed to allocate pages of glyphs from a
capped global pool but with per-font hash tables. This should allow the
glyph cache to have tight memory bounds with fair allocation according to
usage. Note that both the old design and the 1.8 glyph cache had
essentially unbounded memory constraints, since each scaled font could
cache up to 256 glyphs (1.8) or had a reserved page (old), with no limit
on the number of active fonts. Currently the eviction policy is a simple
random strategy, this gives a 'fair' allotment of the cache, but a LRU
variant might perform better.
On a sample run of firefox-3.0.7 perusing BBC news in 32 languages:
1.8: cache allocation 8190x, ~1.2 MiB; elapsed 88.2s
old: cache allocation 771x, ~13.8 MiB; elapsed 81.7s
lean: cache allocation 433x, ~1.8 MiB; elapsed 82.4s
|
|
Currently glyphs are cached independently in each font i.e. each font
maintains a cache of up to 256 glyphs, and there can be as many scaled fonts
in use as the application needs and references (we maintain a holdover
cache of 512 scaled fonts as well).
Alternatively, as in this patch, we can maintain a global pool of glyphs
split between all open fonts. This allows a heavily used individual font
to cache more glyphs than we could allow if we used per-font glyph caches,
but at the same time maintains fairness across all fonts (by using random
replacement) and provides a cap on the maximum number of global glyphs.
The glyphs are allocated in pages, which are cached in the global pool.
Using pages means we can exploit spatial locality within the font
(nearby indices are typically used in clusters) to reduce frequency of small
allocations and allow the scaled font to reserve a single MRU page of
glyphs. This caching dramatically reduces the cairo overhead during the
cairo-perf benchmarks, and drastically reduces the number of allocations
made by the application (for example browsing multi-lingual site with
firefox).
|
|
Use the gcc likelihood annotation to indicate that allocation failures are
extremely unlikely.
|
|
Behdad prefers these to be upper-case to be consistent with G_UNLIKELY and
friends. However, as I intend to use these for nearly all instances of
if(status), I suggest that we keep to the short and not so loud:
if (unlikely (status))
return status;
|
|
Avoid unnecessary conditionals for the hotpaths by separating out the
iteration over the elements into their distinct modes.
|
|
Use the return value to return the result from _cairo_hash_table_lookup()
(as opposed to filling an output parameter on the stack) as this (a)
results in cleaner code (no strict-alias breaking pointer casts), (b)
produces a smaller binary and (c) is measurably faster.
|
|
As we obey the rule in Cairo that we only insert if we know that there is
no existing entry in the hash table, we can therefore perform a much quicker
search knowing that the key is unique.
|
|
|
|
|
|
|
|
Every time we assign or return a hard-coded error status wrap that value
with a call to _cairo_error(). So the idiom becomes:
status = _cairo_error (CAIRO_STATUS_NO_MEMORY);
or
return _cairo_error (CAIRO_STATUS_INVALID_DASH);
This ensures that a breakpoint placed on _cairo_error() will trigger
immediately cairo detects the error.
|
|
At some point during the blitz, I accidentally wrote
_cairo_error (CAIRO_STATUS_SUCCESS) and then proceeded to paste it into
the next 30 error sites! s/CAIRO_STATUS_SUCCESS/CAIRO_STATUS_NO_MEMORY/
|
|
Blitz all allocations to ensure that they raise a
_cairo_error(CAIRO_STATUS_NO_MEMORY) on failure.
|
|
Yet another victim in my hunt against abbreviations within cairo's implementation.
|
|
Previously if we detected an error during resize we would report a
failure to insert the entry into the hash table having already done so.
|
|
|
|
|
|
This patch was produced with the following (GNU) sed script:
sed -i -r -e 's/[ \t]+$//'
run on all *.[ch] files within cairo.
Note that the above script would have also created all the changes
from the previous commits to remove trailing whitespace.
|
|
This patch was produced with the following (GNU) sed script:
sed -i -r -e '/^[ \t]*[{}][ \t]*/ s/[ \t]+$//'
run on all *.[ch] files within cairo.
|
|
This patch was produced with the following (GNU) sed script:
sed -i -r -e '/^[ \t]*\/?\*/ s/[ \t]+$//'
run on all *.[ch] files within cairo, (though I manually excluded
src/cairo-atsui-font.c which has a code line that appears as a comment
to this script).
|
|
This patch was produced with the following (GNU) sed script:
sed -i -r -e 's/^[ \t]+$//'
run on all *.[ch] files within cairo.
|
|
I discovered that _cairo_hash_table_foreach walks over the hash table
without preventing it from being resized as a result of deletions
occuring from the callback.
Kinda nasty when you're trying to free everything from a hash table.
It was also easy to fix; just prevent the table from being resized while
iterating and clean it up after the iteration is completed.
|
|
anticipated use of cairo_hash_table_t in cairo needs the destroy notifier. Most uses will be hash-backed object create/destroy functions.
(_cairo_hash_table_destroy): Document that it is now a fatal error to call _cairo_hash_table_destroy on a non-empty hash table.
(_cairo_hash_table_insert): Document that it is now a fatal error to insert an entry with a key that matches an existing entry.
(_cairo_hash_table_random_entry): Add predicate function so that the user can select a random entry satisying the given predicate.
(_cairo_hash_table_remove): Change return type to void since failure is really not possible here.
|
|
|
|
Fix to update live_entries.
style changes.
Add code to shrink table as well as to grow it.
Call new version of resize so that table will grow or shrink as needed on insert and remove.
|
|
and void *value. This is slightly more painful to use, but lends itself to a more memory-efficient implementation. Add documentation.
|
|
object derviation is required to use it).
Remove extraneous prototype for non-existent _cairo_cache_reference.
|
|
Add _cairo_cache_shrink_to which reduces cache memory usage to a specified level.
Change global glyph and xlib glyphset caches behaviour to only shrink cache on unlock. This is done by telling the cache code to never shrink (max_memory == 0), and then manually shrinking using _cairo_cache_shrink_to from the unlock function.
Fix Carl's variable renaming mixing (cache = cache).
reviewed by: cworth
|
|
Remove gratuitous nesting as recommended in CODING_STYLE.
|
|
Standardize brace handling around all else clauses according to new CODING_STYLE guidelines.
|
|
Track #ifdef -> #if changes.
Add support to automatically change all #ifdef CAIRO_HAS to #if CAIRO_HAS.
|
|
|
|
Fix problem when no entry could be found.
|
|
resolution.
src/cairoint.h src/cairo_font.c src/cairo_ft_font.c src/cairo_xlib_surface.c src/cairo_pdf_surface.c src/cairo_gstate.c src/cairo.c: Switch many internal methods from handling cairo_unscaled_font_t and cairo_font_scale_t pairs to handling cairo_font_t.
src/cairo-ft-private.h src/cairo_ft_fontc: Add some internal interfaces for use by the FreeType backend.
Clear the gstate's current font when the transform or target surface changes.
src/cairo.h src/cairo_ft_font.c: Rename cairo_ft_font_pattern to cairo_ft_font_get_pattern().
src/cairo.h src/cairo_ft_font.c: Make cairo_ft_font_create() and cairo_ft_font_create_for_ft_face() take a font scale; make the latter take load_flags for FT_Load_Glyph() as well. Change cairo_ft_font_face() to Xft-style cairo_ft_font_lock_face, cairo_ft_font_unlock_face.
Remove the name/slant/weight=>unscaled font cache, it didn't work with the new cairo_font_t setup. If it turns out to be needed, it can be added back in some other form.
src/cairoint.h src/cairo_font.c: Add a 'flags' field to cairo_glyph_cache_key_t, we use it for load flags with freetype backend.
Switch the caching to be from resolved fontconfig pattern => file; keep only a fixed number of FT_Face objects open at once, similar to FreeType.
src/cairo_gstate.c src/cairoint.h: Add public cairo_font_glyph_extents, use it to implement _cairo_gstate_glyph_extents().
Add refcounting for glyph cache elements; there was an bug where elements got ejected from the cache and freed before they could be used.
src/cairoint.h src/cairo_cache.c (_cairo_cache_random_entry()) New function to return a random entry in the cache matching a predicate; reuse the internals for the previous _random_live_entry().
src/cairoint.h src/cairo_cache.c (_cairo_cache_lookup()): Add an optional created_entry return value.
src/cairo_ft_font.c src/cairo_xlib_surface.c: Adapt to _cairo_cache_lookup() change.
Support max_memory == 0 to indicate an unbounded cache.
src/cairoint.h src/cairo_cache.c (_cairo_cache_remove()): Add a function to manually remove entries from the cache.
Update for changes, document cairo_matrix_t, cairo_glyph_t, etc.
src/cairo.h src/cairo-atsui.h src/cairo-ft.h src/cairo-glitz.h src/cairo-pdf.h src/cairo-png.h src/cairo-ps.h src/cairo-quartz.h src/cairo-xcb.h src/cairo-xlib.h: Add CAIRO_BEGIN/END_DECLS for extern "C", use it on all public headers. Move header guards outermost.
Fix encoding.
|
|
Remove cache memory usage assertions as single objects can be larger than the cache size
Decompose font matrix transformations into a couple of helper routines. Return all metrics in font space.
Eliminate compiler warning
Expect glyph metrics to be in font space. Compute text extents by fetching one glyph metric at a time, transforming to user space and computing the overall bounding box.
use 'sincos' where available. Scale factors now ensure the non-scale transform is area preserving. Scale factors requires another parameter to mark the fixed axis.
Change license to LGPL Mark int32x32_64_mul as broken (which it still is)
Ensure each glyph is located as close to the specified position as possible
interface change to _cairo_matrix_compute_scale_factors
|
|
_cairo_fixed_integer_ceil.
Call _cairo_gstate_restore_external_state on restore.
Fix cache-misses.
Implement floor and ceil
Restore surface clip region on restroe.
(_calculate_region_for_intermediate_clip_surface), (_cairo_gstate_clip_and_composite_trapezoids), (_cairo_gstate_show_surface), (_cairo_gstate_show_glyphs): Create intermediate clip surfaces of the minimal required size.
|
|
Add test to demonstrate bug when item is too big for cache.
Really remove that refcount assertion this time.
|
|
cache destruction.
Support tests that produce no output, (don't check image if (width,height) == (0,0)).
Add #include <assert.h> here rather than in multiple .c files.
Add const qualifier to static cache_arrangements table. (_cache_sane_state): Remove refcount assertion as it it false during the cairo_cache_destroy. (_cache_sane_state): #include <assert.h> moved up to cairoint.h (_entry_destroy): Fix bug in assertion (used_memory >= entry->memory), not >. (_cairo_cache_destroy): Fix timing of refcount decrement so that the destroy function actually works.
|
|
|
|
Rewrite using temporary glyph arrays
New file.
Remove old glyph cache code. (_cairo_font_scale) (_cairo_font_transform): Remove font-transforming code. (_cairo_font_text_extents) (_cairo_font_text_bbox) (_cairo_font_show_text) (_cairo_font_text_path): Remove text-API code. (_cairo_font_cache_key_t): New structure type. (_font_cache_hash) (_font_cache_keys_equal) (_font_cache_create_entry) (_font_cache_destroy_entry) (_font_cache_destroy_cache): New font cache code. (_global_font_cache) (_lock_global_font_cache) (_unlock_global_font_cache) (_get_global_font_cache): New global font cache. (_cairo_font_text_to_glyphs) (_cairo_glyph_cache_hash) (_cairo_glyph_cache_keys_equal) (_image_glyph_cache_create_entry) (_image_glyph_cache_destroy_entry) (_image_glyph_cache_destroy_cache): New glyph cache code. (_global_image_glyph_cache) (_cairo_lock_global_image_glyph_cache) (_cairo_unlock_global_image_glyph_cache) (_cairo_get_global_image_glyph_cache): New global glyph cache. (_cairo_font_cache_backend): New structure. (_cairo_image_cache_backend): Likewise. (_cairo_font_create): Reimplement in terms of font cache. (_cairo_font_init): Remove matrix and glyph cache related code. (_cairo_font_copy): Likewise. (_cairo_font_show_glyphs): Delegate to surface when possible. (_cairo_font_glyph_extents) (_cairo_font_glyph_bbox) (_cairo_font_glyph_path) (_cairo_font_font_extents) (_cairo_font_show_glyphs): Rename to as cairo_unscaled_font_XXX, and add scale parameter.
New structure types. (_create_from_face) (_reference_font_val) (_destroy_font_val) (_create_from_library_and_pattern): New functions. (_ft_font_cache_hash) (_ft_font_cache_keys_equal) (_ft_font_cache_create_entry) (_ft_font_cache_destroy_entry) (_ft_font_cache_destroy_cache): New ft font cache code. (_global_ft_cache) (_lock_global_ft_cache) (_unlock_global_ft_cache) (_get_global_ft_cache): New global ft font cache. (_ft_font_cache_backend): New structure. (_cairo_ft_font_create): Rewrite to use cache. (_cairo_ft_font_destroy): Likewise. (_cairo_ft_font_copy): Remove. (_install_font_matrix): Rename as _install_font_scale. (_utf8_to_glyphs): Rename as _cairo_ft_font_text_to_glyphs. (_cairo_ft_font_text_to_glyphs): Use cache for metrics. (_cairo_ft_font_extents): Accept size, use scaled metrics. (_cairo_ft_font_glyph_extents) (_cairo_ft_font_glyph_bbox) (_cairo_ft_font_show_glyphs) (_cairo_ft_font_glyph_path): Modify to use size, cache. (_cairo_ft_font_text_extents) (_cairo_ft_font_text_bbox) (_cairo_ft_font_show_text) (_cairo_ft_font_text_path): Remove text-API code. (cairo_ft_font_create) (cairo_ft_font_create_for_ft_face) (cairo_ft_font_face) (cairo_ft_font_pattern): Rewrite using ft_font_val_t.
Just reference font. (_cairo_gstate_fini): Finalize font matrix. (_cairo_gstate_default_matrix): Initialize font matrix. (_cairo_gstate_clip): Re-enable clipping rectangle. (_cairo_gstate_select_font) (_cairo_gstate_set_font): Set font matrix to identity. (_cairo_gstate_scale_font): Scale font matrix, not font. (_cairo_gstate_transform_font): Transform font matrix, not font. (_cairo_gstate_set_font_transform): Install as font matrix, not in font. (_build_font_scale): New helper function. (_cairo_gstate_text_to_glyphs): New function. (_cairo_gstate_current_font_extents) (_cairo_gstate_glyph_extents) (_cairo_gstate_show_glyphs) (_cairo_gstate_glyph_path): Rewrite using font matrix and size. (_cairo_gstate_text_path (_cairo_gstate_text_extents) (_cairo_gstate_show_text): Remove text-API code.
Minor bug fix. (_cairo_xlib_surface_show_glyphs): New function. (_cairo_xlib_surface_backend): Add reference to new function. (glyphset_cache_t) (glyphset_cache_entry_t): New structure types. (_next_xlib_glyph): New helper function. (_xlib_glyphset_cache_create_value) (_xlib_glyphset_cache_destroy_cache) (_xlib_glyphset_cache_destroy_value) (_xlib_glyphset_cache_backend): New glyphset cache code. (_xlib_glyphset_caches) (_lock_xlib_glyphset_caches) (_unlock_xlib_glyphset_caches) (_get_glyphset_cache): New global glyphset cache.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
Add NULL entry for show_glyphs.
New structure type. (cairo_cache_entry_base_t) (cairo_cache_arrangement_t) (cairo_cache_t): New structure types. (_cairo_cache_init) (_cairo_cache_reference) (_cairo_cache_destroy) (_cairo_cache_lookup) (_cairo_hash_string): New cache functions. (CAIRO_IMAGE_GLYPH_CACHE_MEMORY_DEFAULT) (CAIRO_XLIB_GLYPH_CACHE_MEMORY_DEFAULT) (CAIRO_FONT_CACHE_NUM_FONTS_DEFAULT) (CAIRO_FT_CACHE_NUM_FONTS_DEFAULT): New constants. (cairo_font_scale_t) (cairo_glyph_cache_key_t) (cairo_image_glyph_cache_entry_t): New structure types. (_cairo_lock_global_image_glyph_cache) (_cairo_unlock_global_image_glyph_cache) (_cairo_get_global_image_glyph_cache) (_cairo_glyph_cache_hash) (_cairo_glyph_cache_keys_equal): New functions for glyph caches. (cairo_font_backend_t): Remove text-API calls, add scale params, remove copy call. (cairo_surface_backend_t): Add show_glyphs entry. (cairo_glyph_surface_t) (cairo_glyph_surface_node_t): Remove old glyph cache structures. (cairo_unscaled_font_t): New structure type. (cairo_font): Remove glyph cache member, add pointer to unscaled. (cairo_gstate): Add font_matrix member, change to hold unscaled. (_cairo_gstate_set_font_transform) (_cairo_gstate_current_font_transform) (_cairo_gstate_text_to_glyphs): New functions. (_cairo_gstate_text_path (_cairo_gstate_text_extents) (_cairo_gstate_show_text) (_cairo_font_text_extents) (_cairo_font_text_bbox) (_cairo_font_show_text) (_cairo_font_text_path): Remove text-API code. (_cairo_font_glyph_extents) (_cairo_font_glyph_bbox) (_cairo_font_glyph_path) (_cairo_font_font_extents) (_cairo_font_show_glyphs): Add scale parameter.
|
