Skip to content
GitLab
Projects Groups Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Sign in / Register
  • G GLib
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
  • Issues 859
    • Issues 859
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 39
    • Merge requests 39
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Releases
  • Packages and registries
    • Packages and registries
    • Container Registry
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • GNOMEGNOME
  • GLib
  • Issues
  • #1198
Closed
Open
Issue created Aug 30, 2016 by Bugzilla@bugzilla-migration💬Reporter

GHashTable: Robin Hood hashing

Submitted by Hans Petter Jansson @hansp

Link to original bug (#770616)

Description

Created attachment 334488 0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch

Alex' prodding in bug 526456 motivated me to patch GHashTable to use Robin Hood hashing. The patch passes the tests and works when linked with Evolution, but I'm still skeptical of its performance benefits.

One nice thing about it is that I was able to eliminate the use of tombstones entirely.

It still needs proper benchmarking of insertions, removals and lookups in an appropriate mix alongside the current implementation.

There may also be some microoptimization/cleanup left to do.

Patch 334488, "0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch":
0001-GHashTable-Change-from-quadratic-probing-to-Robin-Ho.patch

Version: 2.49.x

Assignee
Assign to
Time tracking