BFS cpu scheduler and skip list implementation
Hi all
Many of you may know about Skip lists as an alternative to balanced binary search trees. They feature O(log n) insertion, lookup and removal of table entries. Anyway I've been looking for some time at the O(n) lookup of BFS (which is O(1) insertion and removal) to try and find a solution that didn't cost us at the desktop level since O(n) of small numbers of n is very fast. The problem is of course at higher numbers of n (or server type loads), where it gets linearly slower, and the cache trashing aspect of scanning linked lists becomes expensive.
http://en.wikipedia.org/wiki/Skip_list
So to cut a long story short, I've implemented the first draft of a custom version of skip lists for BFS in place of the O(n) lookup. The insertion remains O(log n), but by sorting all tasks realtime, iso, normal, batch and idleprio in a way they all end up on the same table, I was able to do away with the regular linked lists and the bitmap priority lookup. Then I was able to utilise one of the features of the skip lists in that the first task on the "bottom" list is always sorted to be the highest priority. This means the lookup is O(1). Then I put an extra pointer into each entry to the previous entry (the original design normally only points to the next entry). Finally I placed a pointer to the entry in the task struct as a way of reverse looking up the entry without any search.
So what I'm left with is an O(log n) insertion, O(1) lookup, and O(k) removal (k is the "height" of the node in question, up to 16, but usually only 1-4).
I've implemented the sticky task used for CPU affinity by simply comparing the last sticky task to the first entry returned from the skip list. Alas I have not yet provided a good version of the sticky task being used to improve scaling governor behaviour. This means that this will likely perform worse with the ondemand governor at this stage. On the other hand, the performance governor seems to be working very nicely in my preliminary tests.
Here's some code (for a BFS patched 3.0.x kernel):
http://ck.kolivas.org/patches/bfs/test/bfs406-skiplists.patch
Try it out, see what you think. It seems to be running safely here but as always, there are no guarantees. All going well, you should notice pretty much no difference on a desktop. If you do any throughput benchmarks comparing before/after, I'd love to hear about them.
Patch inserted here as well:
--- include/linux/init_task.h | 2 include/linux/sched.h | 3 include/linux/skip_lists.h | 26 ++++++ kernel/Makefile | 2 kernel/sched_bfs.c | 175 ++++++++++++++++++++------------------------- kernel/skip_lists.c | 159 ++++++++++++++++++++++++++++++++++++++++ 6 files changed, 268 insertions(+), 99 deletions(-)
include/linux/sched.h +2 -1
@@ -97,6 +97,7 @@ struct sched_param {#include <linux/task_io_accounting.h> #include <linux/latencytop.h> #include <linux/cred.h> +#include <linux/skip_lists.h> #include <asm/processor.h>
@@ -1243,7 +1244,7 @@ struct task_struct {#ifdef CONFIG_SCHED_BFS int time_slice;u64 deadline; -struct list_head run_list; +skiplist_node *node;/* Skip list node id */ u64 last_ran;u64 sched_time;/* sched_clock time spent running */ #ifdef CONFIG_SMP
kernel/Makefile +2 -0
@@ -117,6 +117,8 @@ ifneq ($(CONFIG_SCHED_OMIT_FRAME_POINTER CFLAGS_sched.o := $(PROFILING) -fno-omit-frame-pointer endif +obj-$(CONFIG_SCHED_BFS) += skip_lists.o + $(obj)/configs.o: $(obj)/config_data.h # config_data.h contains the same information as ikconfig.h but gzipped.
kernel/sched_bfs.c +78 -97
273 lines not on this page · raw message
kernel/skip_lists.c new file +159 -0
159 lines not on this page · raw message
include/linux/init_task.h +1 -1
@@ -145,7 +145,7 @@ extern struct cred init_cred; .cpus_allowed = CPU_MASK_ALL, \ .mm = NULL, \ .active_mm = &init_mm, \ - .run_list = LIST_HEAD_INIT(tsk.run_list), \ + .node = NULL, \ .time_slice = HZ, \ .tasks =LIST_HEAD_INIT (tsk.tasks), \INIT_PUSHABLE_TASKS (tsk) \
include/linux/skip_lists.h new file +26 -0
@@ -0,0 +1,26 @@ +#ifndef _LINUX_SKIP_LISTS_H +#define _LINUX_SKIP_LISTS_H +typedef u64 keyType ; +typedef struct task_struct *valueType ; + +typedef struct nodeStructure skiplist_node ; + +struct nodeStructure { +int level;/* Levels in this structure */ +keyType key; +valueType value; +skiplist_node *next[16 ]; +skiplist_node *prev[16 ]; +}; + +typedef struct listStructure { +int level;/* Maximum level of the list +(1 more than the number of levels in the list) */ +struct nodeStructure * header;/* pointer to header */ +}skiplist ; + +skiplist_node *skiplist_init (void ); +skiplist *new_skiplist (skiplist_node *slnode); +skiplist_node *skiplist_insert (skiplist_node *slnode,skiplist *l,keyType key,valueType value,u64 randseed); +void skiplist_delnode (skiplist_node *slnode,skiplist *l,skiplist_node *node); +#endif /* _LINUX_SKIP_LISTS_H */
Signature · 1 line
-ck
Quoted 8 lines · Con Kolivas
Many of you may know about Skip lists as an alternative to balanced binary search trees. They feature O(log n) insertion, lookup and removal of table entries. Anyway I've been looking for some time at the O(n) lookup of BFS (which is O(1) insertion and removal) to try and find a solution that didn't cost us at the desktop level since O(n) of small numbers of n is very fast. The problem is of course at higher numbers of n (or server type loads), where it gets linearly slower, and the cache trashing aspect of scanning linked lists becomes expensive.
The big problem with skiplists is that it is hard to resize the pointer
arrays: so you either waste a lot of memory/cache or you have a highest limit after which they start performing poorly.
I investigated them some time ago to replace the non scalable rbtrees we have currently, but got discouraged by these problems.
include/linux/skip_lists.h line 14
Quoted 7 lines
include/linux/skip_lists.h new file +7
-0+struct nodeStructure { +int level;/* Levels in this structure */ +keyType key; +valueType value; +skiplist_node *next[16 ]; +skiplist_node *prev[16 ]; +};
That's 128 byte / 2 cache lines, not too bad, but it limits the maximum number of tasks that can be efficiently handled (my guess to around 64k with maxlevel == 16, but someone may correct me on that)
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Quoted 13 lines · On Sat, 24 Sep 2011 11:21:06 Andi Kleen wrote:
include/linux/skip_lists.h line 14
Quoted 7 lines · Con Kolivas
include/linux/skip_lists.h new file +7
-0+struct nodeStructure { +int level;/* Levels in this structure */ +keyType key; +valueType value; +skiplist_node *next[16 ]; +skiplist_node *prev[16 ]; +};That's 128 byte / 2 cache lines, not too bad, but it limits the maximum number of tasks that can be efficiently handled (my guess to around 64k with maxlevel == 16, but someone may correct me on that)
Thanks very much for your informed comments. Do you mean once 64k of tasks are queued concurrently, or after 64k of entries have gone in +/- been removed?
Con
Signature · 1 line
-ck
Quoted 15 lines · Con Kolivas
Quoted 13 lines · On Sat, 24 Sep 2011 11:21:06 Andi Kleen wrote:
include/linux/skip_lists.h line 14
Quoted 7 lines · Con Kolivas
include/linux/skip_lists.h new file +7
-0+struct nodeStructure { +int level;/* Levels in this structure */ +keyType key; +valueType value; +skiplist_node *next[16 ]; +skiplist_node *prev[16 ]; +};That's 128 byte / 2 cache lines, not too bad, but it limits the maximum number of tasks that can be efficiently handled (my guess to around 64k with maxlevel == 16, but someone may correct me on that)
Quoted 2 lines
Thanks very much for your informed comments. Do you mean once 64k of tasks are queued concurrently, or after 64k of entries have gone in +/- been removed?
queued concurrently I believe.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only.
Quoted 16 lines · On Sat, 24 Sep 2011 17:35:22 Andi Kleen wrote:
Quoted 15 lines · Con Kolivas
Quoted 13 lines · On Sat, 24 Sep 2011 11:21:06 Andi Kleen wrote:
include/linux/skip_lists.h line 14
Quoted 7 lines · Con Kolivas
include/linux/skip_lists.h new file +7
-0+struct nodeStructure { +int level;/* Levels in this structure */ +keyType key; +valueType value; +skiplist_node *next[16 ]; +skiplist_node *prev[16 ]; +};That's 128 byte / 2 cache lines, not too bad, but it limits the maximum number of tasks that can be efficiently handled (my guess to around 64k with maxlevel == 16, but someone may correct me on that)
Quoted 5 lines
Quoted 3 lines
Thanks very much for your informed comments. Do you mean once 64k of tasks are queued concurrently, or after 64k of entries have gone in +/- been removed?
queued concurrently I believe.
That's great then. I'm sure we'd explode in other weird and wonderful ways before the CPU load ever got to 64k. Plus all that would happen is that it would start degenerating from O(log n) insertion to O(n) as the number way surpassed 64k. The number 16 for levels was simply chosen as the one originally used by William Pugh in his sample code, but seems to be ample for this application.
Being very unimaginative with my benchmarking, a quick benchmark showed a significant improvement in the make -j (allnoconfig kbuild) case on my quad core from the previous BFS code (all with performance governor).
3.0.0:
Elapsed Time 28.7
3.0.0-bfs406:
Elapsed Time 28.5
3.0.0-bfs406-sl:
Elapsed Time 27.0
For convenience of those interested in testing:
Here's the original 3.0 -bfs 406 patch:
http://ck.kolivas.org/patches/bfs/3.0.0/3.0-sched-bfs-406.patch
And here's a combined bfs406 + skiplists patch:
http://ck.kolivas.org/patches/bfs/test/3.0-sched-bfs-406-skiplists.patch
Signature · 1 line
-ck
Hi Con,
Quoted 6 lines · Con Kolivas
That's great then. I'm sure we'd explode in other weird and wonderful ways before the CPU load ever got to 64k. Plus all that would happen is that it would start degenerating from O(log n) insertion to O(n) as the number way surpassed 64k. The number 16 for levels was simply chosen as the one originally used by William Pugh in his sample code, but seems to be ample for this application.
If you're interested, during the early CFS benchmarks a few years ago, I reworked my old binary tree code to make it kernel-compatible. By this, I mean that it never needs to allocate memory, it's used just like rbtrees or kernel lists, by having a node in your structure and inserting it from the root of a tree. It offers the following features :
- O(log(N)) insertion/lookup
- O(1) removal
- O(1) next/prev walk
- 20 bytes per node on 32-bit pointers, 36-bytes on 64-bit pointers, plus the key
- supports unique or multiple occurrences of the same key (walked in insertion order and classed in trees)
- supports 32/64 bit signed/unsigned integers, strings and memory blocks
- supports prefixes (eg. to insert IP addresses with masks)
- supports lookup of greater than or equal to, less than or equal to.
I replaced the rbtree that was used in haproxy's scheduler with this new code and measured a noticeable performance improvement, since haproxy does insert/next/remove a lot of times a second, and not having to balance a tree saves a huge number of cycles.
I remember having conducted some tests on CFS a log time ago with it, but the only cases where I observed a gain was when running insane amounts of tasks at insane context switching rates, which was biased and irrealistic. So I stopped trying to put it into the kernel at that time.
Maybe for your usage it might bring some value. Take a look at the code here if you want, it's not too much documented but still enough to start with it. There are a few examples that can help get it right. I know that a few people use it for their own projects and they did not ask for help :-)
http://git.1wt.eu/web?p=ebtree.git;a=summary
Cheers,
Willy
Quoted 36 lines · On Fri, 30 Sep 2011 06:45:05 Willy Tarreau wrote:
Hi Con,
Quoted 6 lines · Con Kolivas
That's great then. I'm sure we'd explode in other weird and wonderful ways before the CPU load ever got to 64k. Plus all that would happen is that it would start degenerating from O(log n) insertion to O(n) as the number way surpassed 64k. The number 16 for levels was simply chosen as the one originally used by William Pugh in his sample code, but seems to be ample for this application.
If you're interested, during the early CFS benchmarks a few years ago, I reworked my old binary tree code to make it kernel-compatible. By this, I mean that it never needs to allocate memory, it's used just like rbtrees or kernel lists, by having a node in your structure and inserting it from the root of a tree. It offers the following features :
- O(log(N)) insertion/lookup
- O(1) removal
- O(1) next/prev walk
- 20 bytes per node on 32-bit pointers, 36-bytes on 64-bit pointers, plus the key
- supports unique or multiple occurrences of the same key (walked in insertion order and classed in trees)
- supports 32/64 bit signed/unsigned integers, strings and memory blocks
- supports prefixes (eg. to insert IP addresses with masks)
- supports lookup of greater than or equal to, less than or equal to.I replaced the rbtree that was used in haproxy's scheduler with this new code and measured a noticeable performance improvement, since haproxy does insert/next/remove a lot of times a second, and not having to balance a tree saves a huge number of cycles.
I remember having conducted some tests on CFS a log time ago with it, but the only cases where I observed a gain was when running insane amounts of tasks at insane context switching rates, which was biased and irrealistic. So I stopped trying to put it into the kernel at that time.
Quoted 7 lines
Maybe for your usage it might bring some value. Take a look at the code here if you want, it's not too much documented but still enough to start with it. There are a few examples that can help get it right. I know that a few people use it for their own projects and they did not ask for help :-)
http://git.1wt.eu/web?p=ebtree.git;a=summary
Thanks Willy that's most interesting.
In fact after I fixed a few bugs in the original implementation I posted here,
and cleaned up the code to not do dynamic memory allocation in the hot scheduler path and so on... I found it (my skip list implementation) to be universally slower than the existing BFS approach of simple linked lists and walking the list for lookup. Any performance advantage in the original version was coincidence due to the way it performed on one workload and was bad in others. Rather disappointing but you can read my thoughts here
Anyway I'll make sure to read your code and see if it has anything to offer me. Thanks for the pointer.
Regards,
Con
Signature · 1 line
-ck
Quoted 5 lines · Con Kolivas
In fact after I fixed a few bugs in the original implementation I posted here, and cleaned up the code to not do dynamic memory allocation in the hot scheduler path and so on... I found it (my skip list implementation) to be universally slower than the existing BFS approach of simple linked lists and walking the list for lookup.
People often underestimate how fast simple lists can be on small to medium data sets :-)
Quoted 5 lines
Any performance advantage in the original version
was coincidence due to the way it performed on one workload and was bad in others. Rather disappointing but you can read my thoughts here
Well, this coincidence at least shows something : by avoiding some work and by possibly being unfair to some non-critical tasks, you managed to reduce the time it takes to run a given workload. That's what many scientists call an accidental experimentation. Now you need to find how to get close to those numbers without the downsides you've explained on the link above :-)
Quoted 2 lines
Anyway I'll make sure to read your code and see if it has anything to offer me. Thanks for the pointer.
OK. Do not hesitate to ping me if you need some help when playing with the code. I might even still have a backup of the wikipedia article I wrote at that time when some users asked me, and that was deleted by some bastards^Wmoderators, who considered it was just self promotion! There were a few diagrams there which explain how that works.
Best regards,
Willy
Quoted 1 line · Con Kolivas
Try it out, see what you think.
Your patch applies cleanly to 3.0.4 vanilla, but compilation fails:
[....]/usr/src/linux-3.0.4/usr/include/linux/sched.h:1504: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1505: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1507: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1508: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1511: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1513: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1514: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1516: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1517: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1521: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1567: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/sched.h:1568: userspace cannot reference function or variable defined in the kernel /usr/src/linux-3.0.4/usr/include/linux/soundcard.h:1054: userspace cannot reference function or variable defined in the kernel make[3]: *** [/usr/src/linux-3.0.4/usr/include/linux/.check] Error 123
make[2]: *** [linux] Error 2
make[1]: *** [headers_check] Error 2
make: *** [vmlinux] Error 2
Quoted 7 lines · On Sun, 25 Sep 2011 19:04:17 Heinz Diehl wrote:
Quoted 1 line · Con Kolivas
Try it out, see what you think.
Your patch applies cleanly to 3.0.4 vanilla, but compilation fails:
[....]
/usr/src/linux-3.0.4/usr/include/linux/sched.h:1504: userspace cannot
I'm guessing you did not configure in the BFS CPU scheduler, which is pretty much mandatory with this patch.
Regards,
Con
Signature · 1 line
-ck
Quoted 2 lines · Con Kolivas
I'm guessing you did not configure in the BFS CPU scheduler, which is pretty much mandatory with this patch.
Of course, I did:
[root@wildsau ~]# cat /usr/src/linux/.config | grep BFS CONFIG_SCHED_BFS=yCONFIG_HUGETLBFS=yCONFIG_BFS_FS=m
Quoted 10 lines · On Sun, 25 Sep 2011 21:16:41 Heinz Diehl wrote:
Quoted 2 lines · Con Kolivas
I'm guessing you did not configure in the BFS CPU scheduler, which is pretty much mandatory with this patch.
Of course, I did:
[root@wildsau ~]# cat
/usr/src/linux/.config| grep BFSCONFIG_SCHED_BFS=yCONFIG_HUGETLBFS=yCONFIG_BFS_FS=m
Can you send me your config then please? Offlist is fine.
Signature · 1 line
-ck