Does the kernel page the CFS's red-black tree nodes?
in [Kernel]
|
Prev: [PATCH 1/1] module: initialize module dynamic debug later
Next: net: NET_SKB_PAD should depend on L1_CACHE_BYTES
From: Richard Yao on 15 Jun 2010 21:00 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Alan Cox on 16 Jun 2010 07:20 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Andi Kleen on 17 Jun 2010 04:10
Richard Yao <shiningarcanine(a)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(a)linux.intel.com -- Speaking for myself only. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |