Nick Piggin posted an efficient algorithm for converting a data structure, "this is my 'data structure switch' algorithm that can convert one data structure into another, with just a single unlikely branch in fastpaths and no locking or atomic operations (the branch is only triggered when the data structure is in the process of being converted). A pointer indirection is generally also needed when converting a global data structure." He provided an example of using it to resize a hash then noted:

"the algorithm need not only convert between two different sized hashes, but that's just the most obvious and useful thing to do. It _could_ convert between a hash and a tree or something crazy like that too :)"

Nick added that while the conversion algorithm was efficiently implemented, converting it into an API was proving difficult, "the algorithm implementation is basically optimal, but the API means that it requires and extra function call and indirect function call to work, which probably makes it unusable for important implementations. (C preprocessor magic to avoid the indirect function calls and allow some level of templating while retaining the types might be the way to do it)."

From: Nick Piggin [email blocked]
Subject: [rfc][patch] dynamic data structure switching
Date:	Sun, 2 Sep 2007 20:27:38 +0200

Hi,

This is my "data structure switch" algorithm that can convert one data
structure into another, with just a single unlikely branch in fastpaths
and no locking or atomic operations (the branch is only triggered when
the data structure is in the process of being converted). A pointer
indirection is generally also needed when converting a global data
structure.

I posted this algorithm a while back and converted the dcache hash to
be dynamically resized at runtime[*], and David Miller started on a
patch to make one of the networking hashes dynamic too.

[*] The algorithm need not only convert between two different sized
    hashes, but that's just the most obvious and useful thing to do.
    It _could_ convert between a hash and a tree or something crazy
    like that too :)

Anyway, the problem with this is that I hadn't found a really nice
way to abstract this functionality and package it in a nice API. It
is almost small enough that open-coding it would be reasonable...
but it would be much nicer to be able to abstract it.

Anyway, here is the algorithm nicely packaged behind a really crappy
API :P I think the idea might be useful enough not to lose it, so
I'm posting this WIP just as a request for comments. 

The algorithm implementation is basically optimal, but the API means
that it requires and extra function call and indirect function call
to work, which probably makes it unusable for important implementations.
(C preprocessor magic to avoid the indirect function calls and allow
some level of templating while retaining the types might be the way
to do it).

Dumb pidhash conversion also provided to help people tinker.


Index: linux-2.6/lib/dyndata.c
[patch]



From: Nick Piggin [email blocked]
Subject: Re: [rfc][patch] dynamic data structure switching
Date:	Sun, 2 Sep 2007 20:36:19 +0200

Dumb, slightly incomplete, dynamic pidhash resizing. I'm just sending this
as a reference and testing tool. While the pid-hash might be the least
problematic one we have, RAM saving / collision minimisation aren't the
only reasons to size a hash optimally: in a really lookup intensive
workload, a small dense hash table will have between 4-32x better cache
efficiency than a very sparse one, depending on line size and pointer
size. So it is possible that resizing even reasonably small hashes can
be a good idea.

Index: linux-2.6/kernel/pid.c
[patch]

• Archive of above thread
• KernelTrap interview with Nick Piggin