TL;DR: Test release for fastest BFS ever.
The skiplists patch has proven to be quite stable, but a couple of minor issues have shown up. First, as I knew, the ondemand behaviour would not quite match the current release, and second, SCHED_IDLEPRIO tasks weren't scheduled properly (they acted like normal tasks). However the code itself seemed quite safe otherwise. So I've tentatively put out a test release of the next version of BFS. The two main changes to the skiplist code are to bring the ondemand governor performance up to par with current BFS, and to fix the behaviour of SCHED_IDLEPRIO tasks.
Make -j4: 26.6s
Make -j : 27.8s
Make -j4: 26.4s
Make -j : 27.1s
Changelog in patch:
Implement skip lists as described here: http://en.wikipedia.org/wiki/Skip_list for the main priority queue. The old queue had: O(1) insertion, O(1) removal, but a lookup involving both a binary search of a bitmap and O(n) search through a linked list which is very cache unfriendly as the list gets larger. This queue is now: O(log n) insertion, O(1) lookup and O(k) lookup in a much more cache friendly manner. This should not compromise performance at all at very low loads, but improve both throughput and latency as loads get higher, as confirmed by benchmarks. Other changes: Cleanups of variable choices and micro-optimisations.
Full bfs410 patch for 3.0.x:
Incremental bfs410 for those on 3.0.x-bfs406:
Incremental bfs410 for those on 3.0.x-ck1:
Note that make headers check will report errors, so you may have to disable this option in kernel hacking if it is enabled. I'm investigating why this is, but it's a harmless warning.
EDIT: Uniprocessor builds will need the following fix on top:
EDIT2: The following fix is required for interactivity issues with the patch