Re: Does the kernel page the CFS's red-black tree nodes?

Re: Does the kernel page the CFS's red-black tree nodes?

[Richard Yao]

Dear Linus Torvalds et all:

I read a recently published article on the ACM website, which
discusses the effect virtual memory pressure has on certain algorithms
and explains that data structures need to be designed in such a way
that they minimize such effects:

http://queue.acm.org/detail.cfm?id=1814327

The author observed slow-downs in an algorithm that ignored virtual
memory upon the incidence of page faults. The basic idea I took from
it is that people should use B-Heaps instead of Binary Heaps and
B-Trees instead of Binary Trees for optimal performance on modern
systems that use virtual memory. Today, it occurred to me that the
kernel's completely fair scheduler could be susceptible this sort of
slow-down, provided that the kernel pages its red-black tree nodes to
swap, so I thought I would ask here if this is the case.

With that said, does the kernel page the CFS's red-black tree nodes to
swap? If it does, it might be a good idea to reimplement the CFS'
Red-Black trees in B-Trees, which would minimize slow-downs from
vm-pressure and also have the additional benefit of minimizing cache
misses caused by tree traversal.

This is my first post to the kernel mailing list. The FAQ says that I
should indicate that I "wish to be personally CC'ed the
answers/comments posted to the list in response" to my posting, so
this sentence is my indication that I "wish to be personally CC'ed the
answers/comments posted to the list".

Yours truly,
Richard Yao

Re: Does the kernel page the CFS's red-black tree nodes?

[Alan Cox]

The kernel doesn't page its own data structures (there a couple of
exceptional cases). That avoids the entire nightmare of trying to have
partly paged kernels, the resulting priority inversions and all the other
horrors you can get plus the big overheads from it.

Alan

Re: Does the kernel page the CFS's red-black tree nodes?

[Andi Kleen]

Richard Yao <shiningarcanine@gmail.com> writes:
>
> With that said, does the kernel page the CFS's red-black tree nodes to
> swap? If it does, it might be a good idea to reimplement the CFS'
> Red-Black trees in B-Trees, which would minimize slow-downs from
> vm-pressure and also have the additional benefit of minimizing cache
> misses caused by tree traversal.

The kernel does not swap itself, but yes in theory btrees might help to 
improve CPU cache locality.

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.