> It has the gross disadvantage that it requires a random number
> generator source which can keep up with the rate at which we can form
> new vma's. This is why we won't be using this, I like skip lists too
> for some of their beautiful properties, but the random number source
> requirement completely annuls all the benefits.
I've not had much experience with skip lists (beyond looking at the paper
and marvelling). How much randomness is actually needed? I'd (naievely)
assume that one of the faster PRNGs would be sufficient, as long as it
didn't have a cycles likely to mesh up with allocation patterns.
(BTW, uClinux has a need for something along these lines, as it needs to
keep track of kmalloc'd blocks owned by processes, in a manner virtually
identical to the vma system. Thus, I'm keeping an eye on the kmalloc and
vma changes, with an eye towards making a true verify_area() feasible
without an MMU.)
> Solaris uses skip lists, let them lose. (they in fact lose even
> moreso because they dynamically switch from single-list+one-behind-cache
> to skip lists depending upon the number of mmaps an address space has,
> as Ingo has mentioned that has a lot of problems).
Ouch, that doesn't sound crisp at all.
> I did a lot of research into this, and the fuzzy hash scheme was
> superior to anything else I have ever seen on the planet. It is the
> only hash scheme (to my knowledge) which is cheap to implement _and_
> works when the search involves comparing two keys against an input key
> for each object in the hash chains (ie. a range, no other hash scheme
> can deal with ranges, traditional hashes can deal with only exact
> single key 'equal' comparisons per object).
Color me interested.
-- Kenneth Albanowski (kjahds@kjahds.com, CIS: 70705,126)
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.altern.org/andrebalsa/doc/lkml-faq.html