linux-kernel - Re: BFS cpu scheduler and skip list implementation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Fri, 30 Sep 2011 06:58:15 +0200
From:	Willy Tarreau <w@....eu>
To:	Con Kolivas <kernel@...ivas.org>
Cc:	Andi Kleen <andi@...stfloor.org>, linux-kernel@...r.kernel.org
Subject: Re: BFS cpu scheduler and skip list implementation

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

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/