1. 17 Sep, 2018 8 commits
    • Hans Petter Jansson's avatar
      tests: Fix bad node ordering assumption · 51b05623
      Hans Petter Jansson authored
      The tests were making assumptions about the order of the returned D-Bus
      introspection nodes. However, these are semantically unordered and
      changes to e.g. GHashTable would break the tests.
      
      Fix this by applying a sort prior to validation.
      51b05623
    • Hans Petter Jansson's avatar
      tests: Remove assertion that unused buckets should have NULL key/value · 4937b6cb
      Hans Petter Jansson authored
      We still clear the key/value on removal, but since we're growing the
      arrays with realloc() now, we can't guarantee that incoming memory is
      cleared. There's no reason it should be either, since we check the
      hashes array (which is always in a defined state) before accessing the
      other arrays.
      4937b6cb
    • Hans Petter Jansson's avatar
      ghash: Use realloc in place of alloc for key/value · 45328b94
      Hans Petter Jansson authored
      Minor simplification resulting in the removal of redundant alloc wrappers.
      45328b94
    • Hans Petter Jansson's avatar
      ghash: Be less eager to opportunistically grow the table on cleanup · 443b4285
      Hans Petter Jansson authored
      When g_hash_table_resize() gets called, we clear out tombstones and grow
      the table at the same time if needed. However, the threshold was set too
      low, so we'd grow if the load was greater than .5 after subtracting
      tombstones. Increase this threshold to ~.75.
      443b4285
    • Hans Petter Jansson's avatar
      ghash: Significantly reduce peak memory use · 57e2aebf
      Hans Petter Jansson authored
      When resizing, we were keeping both the old and new hash, key and value
      arrays around while we reinserted entries, resulting in a peak memory
      overhead of 50%. Using a temporary bookkeeping array with one bit per
      entry we can now grow and shrink the main arrays using realloc() and an
      eviction scheme, reducing the overhead to .625% (assuming 64-bit keys and
      values). Tests show the CPU overhead is negligible.
      57e2aebf
    • Hans Petter Jansson's avatar
      ghash: Use less memory when storing ints on 64-bit platforms · c2edf795
      Hans Petter Jansson authored
      If int is smaller than void * on our arch, we start out with
      int-sized keys and values and resize to pointer-sized entries as
      needed. This saves a good amount of memory when the HT is being
      used with e.g. GUINT_TO_POINTER().
      c2edf795
    • Hans Petter Jansson's avatar
      ghash: Simplify g_hash_table_set_shift() · 171f698e
      Hans Petter Jansson authored
      Even if we're using a prime modulo for the initial probe, our table is
      power-of-two-sized, meaning we can set the mask simply by subtracting one
      from the size.
      171f698e
    • Hans Petter Jansson's avatar
      ghash: Fix poor performance with densely populated keyspaces · 0dee6297
      Hans Petter Jansson authored
      Sequential integers would be densely packed in the table, leaving the
      high-index buckets unused and causing abnormally long probes for many
      operations. This was especially noticeable with failed lookups and
      when "aging" the table by repeatedly inserting and removing integers
      from a narrow range using g_direct_hash() as the hashing function.
      
      The solution is to multiply the hash by a small prime before applying
      the modulo. The compiler optimizes this to a few left shifts and adds, so
      the constant overhead is small, and the entries will be spread out,
      yielding a lower average probe count.
      0dee6297
  2. 31 Aug, 2018 8 commits
  3. 30 Aug, 2018 7 commits
  4. 29 Aug, 2018 3 commits
  5. 28 Aug, 2018 3 commits
  6. 27 Aug, 2018 11 commits