[bind10-dev] Ideas for memory backend

[Michal 'vorner' Vaner]

Good morning

I know that the memory backend is not yet started nor planned right now, but I
got few ideas when I couldn't sleep and I didn't want them to get lost, so I
post them anyway. Anyway, these are just guesses, it would need to be measured.


A b-tree with span-out like 8 or 16 could be faster than RB-tree, since all the
other comparisons inside should be inside one cache line (if the nodes are well
aligned), so they would be „for free“. If they were even larger, it could maybe
help too, because the reads would be sequential, which the prefetch predictors
usually like more than random jumps across memory.

If the nodes contained whole labels/strings, they would be pointers somewhere,
which would mean additional „random“ fetches from memory. So it would be nice if
it was possible to keep them inside somehow, possibly being able to choose a
character/position in the string and compare only that one (which is shorter to
compare and takes less memory, which is inlined into the node). I think this
could be done, but didn't try to find out how yet (how to find which is the best
character/position to distinguish them by).

I'm not sure how expensive it would be to put a read-write lock into each node,
but it could allow it to be multithreaded instead of multiprocess and have
updates live instead of batched, potentially faster updates. If what I heard is
correct (that the locks are really cheap when they are „green“), the penalty for
having them could be worth it.


Anyway, I'm going to write a thesis that is quite close to this problem of fast
in-memory data structures, so I would like to use this as one of the experiments
to measure in it. When the backend is written, I would like to try 2 or 3 other
different data structures to put in, tune and measure them (and bill that time
to the thesis instead of bind, but bind could faster as a result). I hope there
should be no problems like with copyrights and licencing (bind10 is opensource
and I didn't hear of any problems with releasing thesis code as opensource).

Any comments welcome, of course.

Sorry for such a long email.

With regards

-- 
2 keys should be enough for everyone

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: not available
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20100904/93cb75bd/attachment.bin>