Re: BFS cpu scheduler and skip list implementation

[Willy Tarreau <w@1wt.eu>]

On Fri, Sep 30, 2011 at 08:58:28AM +1000, Con Kolivas wrote:
> 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 :-)

> 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
> 
> http://ck-hack.blogspot.com/

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 :-)

> 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