About :: TODO :: Blog :: RSS :: Old blog :: Projects :: GIT :: Gallery :: Notes

Tue, 28 Nov 2006

Multidimensional trie implementation has been completed.


It is a first and the most significant step in netchannels wildcard implementation. I tested it with different number of dimensions (1-5) and different number of added/searched/removed rules (upto several millions in each dimension).
Algorithm is simple and fast - my previous estimation was incorrect - currently 1 million 5-dimensional insertions take about 6 seconds, 1 million 1-dimension insertions take about 1.1 seconds on my test machine.
When I add search/remove operation (one-by-one, i.e. add one, search for it and remove it), the whole tuple takes about 15 and 3.2 seconds for 5-dimensional and 1-dimensional case accordingly.

I will (probably) create some graphs describing algorithm and how it will be used with netchannels tomorrow, but if algorithm itself is implemented correctly, it is the most significant part of wildcards support fot netchannels.

I have started following testing case for 5-dimensional case for the night: 10 rules are added, then 10 various values (actually inserted values, but with 0xffffffff mask) are searched for, and then all they are removed, let's see how this will end up tomorrow.

/devel/networking :: Link / Comments ()