Re: Stale entries in dnscache's cache structure

> I've never looked at the cache code in detail, but presumably an
> alternative solution would be to do an O(n) traversal through the cache
> when there is cache pressure and expire anything stale or perhaps even
> close to stale. That would presumably free up several entries in one
> traversal, and you wouldn't need to traverse again until you filled up
> all of the available slots.

 Well, I thought about a garbage-collected cache. The problem is that
garbage-collecting the cache.c structure really is a lot of work, with
serious rewriting, copying and index linking all over the place, in at
least two passes. The garbage collector by itself would probably be more
code than the current cache.c file. Also, even if O(n) is not bad, the
factor would be high (lots and lots of byte_copy(), among others), so
I'm a bit afraid the garbage collection time would be non-negligible on
big caches (think 1 GB...)
 If I'm going to have that much more code and a performance impact, I'd
rather go binary trees and O(log n) operations, to smoothe the
performance impact instead of having a nonresponsive process for one
second when it performs a serious collection.


> But that is vague and handwaving. I would need a real analysis or some
> experimental evidence to be convinced.

 Yes, some real profiling would be needed; but unfortunately, I don't have
the resources (in time or in CPU) to implement several strategies and
test them.

(And Mark, don't you quote DJB on me. I'm the one who quotes DJB here, k?
 ;) )

-- 
 Laurent