[cairo-bugs] [Bug 17399] _cairo_hash_table_lookup_internal is O(n) slower than it should be

[bugzilla-daemon at freedesktop.org]

http://bugs.freedesktop.org/show_bug.cgi?id=17399


Karl Tomlinson <bugs.freedesktop at karlt.net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Depends on|                            |18165, 18166
                URL|                            |https://bugzilla.mozilla.org
                   |                            |/show_bug.cgi?id=453200
            Summary|hash table improvements     |_cairo_hash_table_lookup_int
                   |                            |ernal is O(n) slower than it
                   |                            |should be




--- Comment #1 from Karl Tomlinson <bugs.freedesktop at karlt.net>  2008-10-21 22:52:27 PST ---
There is no evacuation of dead entries in cairo_hash_tables if the size of the
table never changes, so, when entries are regularly added and removed,
eventually the hash table has no free entries.

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, calling
cairo_hash_keys_equal_func_t on every live entry, so the lookup is O(n).

Bug 18165 or bug 18166 will reduce that speed at which hash_tables fill,
but, because entries are well distributed throughout the table (and
_cairo_hash_table_random_entry removes entries randomly), the tables
eventually fill.

The scaled glyph caches are a common case where the table size remains
constant but entries are regularly added and removed.


--- Comment #2 from Karl Tomlinson <bugs.freedesktop at karlt.net>  2008-10-21 23:05:17 PST ---
Created an attachment (id=19802)
 --> (http://bugs.freedesktop.org/attachment.cgi?id=19802)
reshuffle to remove dead entries

Ensure that at least 25% of the entries in the table are free (search
terminations).

When the number of free entries becomes small, the table is reshuffled.
This reshuffling avoids the need to reallocate, but means an extra pass through
the table entries.  Tests indicate that this method works well, but I don't
know whether or not a memory allocation would be preferable to the extra pass. 
I guess it depends on the size of the table, but let me know if you think a
memory allocation would be better.

One iteration of reshuffling doesn't necessarily clear out all dead entries,
but does clear out most of them, so the number of reshuffles remains small. 
The number of add and remove cycles between reshuffles should be O(n), where n
is the table size, so the average lookup time remains O(1).


-- 
Configure bugmail: http://bugs.freedesktop.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the QA contact for the bug.