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

[bugzilla-daemon at freedesktop.org]

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

Andrea Canciani <ranma42 at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED

--- Comment #3 from Andrea Canciani <ranma42 at gmail.com> 2011-08-03 03:52:38 PDT ---
This should be fixed by:

commit aaa10fbf125a80e5379172b8564384a945728cba
Author: Andrea Canciani <ranma42 at gmail.com>
Date:   Tue Aug 2 10:50:00 2011 +0200

    hash: Improve handling of dead 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,
    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

The committed patch does not perform in-place reshuffling and simply rehashes
to a separate table.
Even if this implies an additional memory allocation, it greatly simplifies the
code, because it can directly reuse the rehash code used for changing size.

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