Re: arca-vm-26

Re: arca-vm-26

[Zlatko Calusic]

Andrea Arcangeli <andrea@e-mind.com> writes:

> Sure, I _am_ interested. Please give me pointers (on the web, I don't have
> money for books ;).
> 

I found something at http://www.csihq.com/CSI/pubs/skiplist.html but
never had time to investigate it.

Enjoy!
-- 
Zlatko

-
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.tux.org/lkml/

Re: arca-vm-26

[Nimrod Zimerman]

On Thu, Jan 21, 1999 at 08:56:12PM +0100, Andrea Arcangeli wrote:

> > I do not wish to start a religious war about data structures.  Have you considered
> > the relatively new data structure called a 'skip list'?  I have replaced several
> 
> Never heard about them.

Pretty nice beasts. When I learned about them, I didn't quite consider them
a better alternative to various trees, but I guess smarter people (smarter
people with more time) have studied them extensively enough to show that
they are indeed a better choice at times.

The implementation is indeed simple. Far simpler than any self-balancing
tree (tough one has to admit that writing a B+ tree implementation is an
endless source of fun). Analyzing the complexity, at least in the variant
I've learned, isn't all that straight forward, as the algorithm is
probabilistic.

Anyway, a reference 'on the web' is http://wannabe.guru.org/alg/node35.html
(it is a very extensive reference of various algorithms. A must keep in your
bookmark file if your bank account doesn't look all that good...). I just
saw that it has a reference to the original paper presenting the data
structure, and this might make an interesting reading.

                                                   Nimrod

-
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.tux.org/lkml/

arca-vm-26

[Andrea Arcangeli]

I've put out an arca-vm-26. The differences between arca-vm-25 and -26 are
that I don't do aging on the swap cache anymore (this should allow
shrink_mmap to decrease the size of the cache at least more easily also on
low memory systems), and a modifyed mem trashing heuristic. It fix also a
potential swap deadlock (triggerable only by the shm memory I think).

The patch can be downloaded from:

ftp://e-mind.com/pub/linux/kernel-patches/2.2.0-pre8testing-arca-VM-26.gz

If you try it please feedback as usual ;). thanks.

Andrea Arcangeli

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: arca-vm-26

[Andrea Arcangeli]

On Wed, 20 Jan 1999, Andrea Arcangeli wrote:

> I've put out an arca-vm-26. The differences between arca-vm-25 and -26 are

I've released now arca-vm-27. I would like to know if you see
some difference between arca-vm-26 and -27. The main difference is that I
removed again the swapout smart code (that I inserted at PG_dirty time
trying to decrease the stalls caused by the swap code that was running
too much).

ftp://e-mind.com/pub/linux/kernel-patches/2.2.0-pre8testing-arca-VM-27.gz

Thanks.

Andrea Arcangeli

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org