Testing modern hash table designs in OVN and OVS

During my Red Hat internship on the Open Virtual Network (OVN) team, I was assigned a task I found especially interesting: Investigate whether OVN and Open vSwitch (OVS) hashmap performance could be improved by using a different hashmap design. This work turned into a deeper look at modern hash table algorithms, OVS's existing hashmap implementation, OVN's large-scale workloads, and performance profiling in C.

My goal with this article is to make the work useful to anyone interested in hashmap design and performance, while also giving OVN and OVS developers enough context to understand what was tested and what the results mean for the codebase.

Starting point: Rosemarie's hmap experiment

The work started by picking up where my OVN team member Rosemarie O'Riorden left off. Rosemarie had been experimenting with replacing OVS's hmap implementation with a design inspired by Valkey's A new hash table article. The Valkey design keeps collisions inside compact cache-line-sized buckets, stores small hash metadata next to the entries, and only allocates child buckets when a bucket overflows. Rosemarie presented this work at the 2025 OVS and OVN conference, and my goal was to see whether the idea would still work well in OVN's real workloads and OVS's existing hmap API.

Rosemarie created the diagram in figure 1 for her conference talk, which shows top-level buckets pointing to embedded nodes, with a child bucket used for overflow.

In Rosemarie's conference talk, she presented the following benchmark comparisons of her hashmap code vs baseline:

Iterate and destroy were close to baseline, but search was slower and insert was much slower. That wasn't too surprising: Insert is where OVS's current hmap is hardest to beat, because inserting into a chained intrusive table is usually just linking one node into a bucket.

That also changed how I read the Valkey article. The article does mention possible latency and CPU improvements, but it presents them as workload-dependent, and usually small. The main benefit it emphasizes is reduced memory usage, not CPU performance. The same article also mentioned another hashmap design, the Swiss table, which is known for strong lookup performance and compact metadata. This gave me a new direction to investigate.

OVS hmap

OVS's current hmap is an intrusive chained hash table. Callers embed a struct hmap_node inside their own objects, and the table stores buckets of linked nodes rather than owning the objects itself. This keeps the API simple and avoids extra allocations inside the hashmap, but lookups can involve pointer chasing through bucket chains. It also means that replacing hmap isn't just a matter of choosing a faster hashmap algorithm; the replacement has to fit the intrusive API that OVS and OVN already use throughout the codebase. Changing the hmap API would require a very large refactor across much of OVN and OVS.

Swiss tables

I decided to look more into Swiss tables, because it would be great to improve both CPU performance and memory usage. Swiss tables are open-addressed hash tables. Entries live in an array, and collisions are handled by probing nearby slots instead of following linked lists. Each slot also has a small metadata byte that says whether the slot is empty, deleted, or occupied. For occupied slots, that byte stores a small fingerprint from the hash. During lookup, the table scans a group of metadata bytes at once to find possible matches, then only compares the full key for those candidates. That keeps lookups cache-friendly and avoids a lot of unnecessary pointer chasing.

The diagram in figure 2 shows the main layout difference. OVS hmap uses a bucket array that points to caller-owned objects linked through embedded hmap_node fields. The Swiss table used in these experiments keeps hash fingerprints and node pointers in aligned arrays, allowing it to scan metadata before following a pointer to a possible match. The hexadecimal values in the control-byte row are the small hash fingerprints stored for occupied slots.

Swiss tables are not an obscure idea. Rust's standard HashMap and Go's built-in map implementations are both based on Swiss tables. That made Swiss tables feel like a reasonable direction to investigate.

The dshmap library

I thought it could be a good idea to create a generic C Swiss table library that could be dropped into OVS. The best existing C Swiss table library I found was Google's cwisstable. The cwisstable library looked useful, but it was not a good fit for OVS. It required C11 and generated type-specific APIs, while OVS's hmap is an intrusive C container used through widely included headers. It's also a large and complicated library, and I thought I could make something simpler.

I created a free and open source library named dshmap, a header-only C99 hashmap library with configurable algorithms. As I profiled and researched different cases, I found that simple chaining could perform better for small tables, while Swiss tables were stronger for large tables. The short version is that dshmap was designed to keep the small-map path cheap without giving up the cache-friendly large-map behavior that made Swiss tables interesting in the first place. Full information and benchmarks are available in the repository README file.

Experiment repository

To keep the OVS and OVN hashmap work reproducible, I organized the integration branches, benchmark scripts, and results into an ovn-hmap-experiments repository so future hashmap experiments could pick up from the same setup. Each approach I discuss has its own branch, and I link to those branches in the relevant sections below.

The benchmark tables below come from separate runs, so each table compares an experiment against the baseline from the same run.

Wrapping dshmap with OVS hmap

I designed the dshmap API to look similar to OVS's hmap API because I knew the library would eventually need to be integrated with OVS. The first integration approach was a compatibility layer that kept the existing OVS hmap API but used dshmap underneath (that code is available on the dshmap-wrapper branch). The OVS hmap struct became a simple wrapper over a dshmap:

struct hmap {
    dshmap map;
};

OVS code expects hmap to be an intrusive container built around struct hmap_node, with support for patterns like reserved insertion, iteration, and removing entries while iterating. dshmap is a standalone pointer table with different ownership and lookup assumptions, so the question was not just whether dshmap was fast, but whether it could preserve the exact behavior existing OVS code already relied on.

The wrapper approach did not perform well in OVN's built-in 200x200 scale benchmark (described in Benchmark setup):

The lflow timings were the important signal here. The compatibility layer avoided a large source code edit, but it made the main OVN workload substantially slower, so wrapping dshmap underneath the existing hmap API was not a promising direction.

Integrating dshmap directly into hmap

The next approach was to remove the extra wrapper layer and integrate the dshmap ideas and code directly into OVS's hmap (that code is available on the experiment repository's dshmap-integrated branch). Instead of storing a dshmap inside struct hmap, this version kept hmap as the real container and added both a chained mode and a Swiss table mode:

enum hmap_mode {    HMAP_MODE_CHAINED,    HMAP_MODE_SWISS,};struct hmap {    struct hmap_node **buckets;    struct hmap_node *one;    int8_t *ctrl;    size_t mask;    size_t n;    size_t n_occupied;    uint8_t mode;};

This was a better fit for OVS than the wrapper because it preserved the intrusive hmap_node model directly, which is very important for the overall hmap performance. It also allowed small maps to stay in the original chained representation and larger maps to promote into a Swiss table layout. However, the benchmark still showed a clear regression:

This ruled out the wrapper as the only problem. Small maps still used the original chained representation, but the implementation was no longer identical to baseline: struct hmap was larger, and the code had extra overhead in having to check which mode the table was in, and large maps still promoted into the Swiss table layout. Those costs were enough that the code remained slower than baseline.

Targeted Swiss table usage

At that point, I thought the correct next step was to stop treating Swiss tables as a global hmap replacement, and instead look for specific maps whose workload actually matched the algorithm. To do that, I added hmap instrumentation on the hmap-metrics branch. The instrumentation produced one record per hmap lifetime, including many empty, temporary, and internal maps, so the raw record count was not very useful by itself. The useful data was the operation mix and the callsites with large table sizes.

The most useful view was the largest callsite groups by peak table size, grouped across recorded hmap lifetimes:

Callsite size and lifetime records

Mutation counts by callsite

Lookup and iteration counts by callsite

Those numbers made lflow-mgr look like an obvious targeted candidate. It had a very large map, many lookups, and a huge amount of iteration. Another good candidate was ovsdb-idl, because it maintains large row indexes and does a lot of lookup and iteration over database rows. These were much better tests for a plain Swiss table library than replacing every hmap in OVS, because they focused on the places where cache-friendly lookup and iteration had a realistic chance to matter. The results for these experiments are listed below. Overall, targeted Swiss tables were the most promising part of the experiment, but the improvements were small and not stable enough to justify the complexity and cost of bringing a new and separate hash table library into OVS.

ovsdb-idl

The swtab-ovsdb-idl branch changes the OVSDB IDL row table from hmap to swtab. This was the more promising targeted result:

This result was promising, but not enough by itself to justify adding a separate hash table implementation to OVS.

lflow-mgr

The swtab-lflow-mgr branch changes the logical-flow table in lflow-mgr to use sharded swtab tables. This result was weaker than ovsdb-idl, but still better than baseline in the lflow timings from this run:

This made lflow-mgr less convincing as a targeted Swiss-table candidate. The build result improved, but the recompute result was close enough to baseline that I would treat it as roughly neutral without more benchmark runs.

Parallelism was also a concern here. lflow-mgr uses OVN's ovn-parallel-hmap, which wraps the regular hmap, so this was not replacing a plain single-threaded hmap. A single flat Swiss table is not a natural fit for parallel mutation unless it is sharded or otherwise given finer-grained synchronization. Gregory Popovitch's Parallel Hashmap article explains this tradeoff well: His design keeps Swiss-table-style performance, but splits the table into submaps so different threads can work with less contention. That is why the lflow-mgr experiment used sharded swtab tables instead of one shared table. That means parallelism was a real design concern, but not the only explanation for the result.

Why the experiments did not produce a clear win

The experiments mostly failed because real OVS and OVN workloads are already well matched to the existing hmap. OVS hmap is an intrusive chained table that normally grows at about two nodes per bucket, keeping average chains short even though individual chains can still be long. This removes much of the lookup-miss problem where Swiss-table metadata scanning usually helps.

Swiss tables tend to shine when lookup misses or dense cache-friendly iteration dominate. In the 200x200 benchmark, the expensive work was not concentrated there. The hmap stats showed heavy mutation: Vell over 100 million inserts and well over 100 million removes.

That operation mix favors OVS hmap. When the table is already sized, inserting an intrusive node is just an O(1) link into a bucket. A Swiss-table-style design has more bookkeeping: Slot metadata, probing, deletion handling, and a less natural fit for objects that already contain struct hmap_node.

So the final result was not that Swiss tables are bad. Real OVN workloads do not have enough expensive hashmap lookup work to pay for replacing OVS's simple intrusive chained table.

Benchmark setup

Benchmarks were run against OVN 26.03.2, using the vendored OVS copy included in the experiment repository. All variants were built with OVN's default configure/build settings unless otherwise noted.

Benchmark runs used the experiment repository's bench/run-check-perf-200x200.sh script, which records the current git revision and status, runs make check-perf TESTSUITEFLAGS="--rebuild 1" and stores the copied result logs under results/<branch>-check-perf-200x200/.

• Hardware: Dell PowerEdge R760 bare-metal server
• CPU: 2 x Intel Xeon Gold 6438N
• Cores/threads: 64 physical cores, 128 hardware threads
• Topology: 2 sockets, 32 cores per socket, 2 threads per core
• NUMA nodes: 2
• Memory: 250 GiB RAM, 31 GiB swap
• Architecture: x86_64, little-endian
• OS: Red Hat Enterprise Linux 10.3 Beta (Coughlan)
• Kernel: Linux 6.12.0-225.el10.x86_64