Messages in this thread | | | Date | Tue, 15 Jun 2010 20:55:20 -0400 | Subject | Re: Does the kernel page the CFS's red-black tree nodes? | From | 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |