[bind10-dev] new in-memory zone data design

[Michal 'vorner' Vaner]

Good morning

On Wed, Jun 20, 2012 at 02:53:31PM +0000, Francis Dupont wrote:
> > Well, that's the point. Dynamic performance means it is fast with updates.
> 
> => yes, in the case of the AFTR most connections had short lifetimes
> so it was critical to get fast insertions/deletions. And for long
> term connections I used a dynamically sized hash table as a cache
> (I can look at the code and the front comment: I don't believe there
> are many things which can be easily improved, in fact the AFTR code
> is clearly over-engineered but to use it for algo experiments was
> a part of the design...).

AVL ones are not slow. They are just constant-time slower on updates and
constant-time faster on lookups.

Did you have more updates than lookups?

> > What I fear is, somebody decided to use RB tree because it is
> >  generally the good choice (without really thinking about specific
> >  needs) and then everybody uses them because everybody uses them. We
> >  never had a discussion about what tree we want to use.
> 
> => yes, perhaps we are a bit RB addict but on the other hand we never
> got bad results with RB too. Perhaps we can agree to make it modular
> (in a real programming language it will be a functor) and to start
> with RB trees?

I agree with it making it modular (though I don't see how a functor would fit
in, I think some templates might be slightly better). But I'd still want to
start with AVL ones, because in nearly all practical scenarios, there are orders
of magnitude more lookups than updates. So if we can get 1.4-times faster on
lookups at the cost of being 10 times slower on updates, and we have (let's say)
1000 lookups per each update, we still get almost 1.4-times faster. But the 1000
is a wild guess (10 is a guess too, but it is really oversized one, it might be
something like 3 more likely). Do we have some numbers to compare?

With regards

-- 
Next sleep is scheduled after 1k lines of code

Michal 'vorner' Vaner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <https://lists.isc.org/pipermail/bind10-dev/attachments/20120620/0eeb5342/attachment.bin>