[concurrency-interest] Benchmark to demonstrate improvement in thread management over the years.

Vitaly Davidovich vitalyd at gmail.com
Tue Aug 13 09:47:35 EDT 2013


CFS is an O(logN) scheduler since it represents the runqueue as a red-black
tree (previous scheduler was O(1)).  It keeps a reference to the leftmost
leaf (next runnable task) so that removing from the tree is O(1) but after
running it, it reinserts into the tree which gives logN.

Sent from my phone
On Aug 13, 2013 6:37 AM, "Kimo Crossman" <kimo at webnetic.net> wrote:

> I thought current Linux scheduler CFS was O(1)
>
> http://en.wikipedia.org/wiki/O(1)_scheduler
>
>
> On Tue, Aug 13, 2013 at 1:49 AM, Kirk Pepperdine <kirk at kodewerk.com>wrote:
>
>>
>> On 2013-08-13, at 8:38 AM, James Roper <james.roper at typesafe.com> wrote:
>>
>> On Tue, Aug 13, 2013 at 2:59 PM, Unmesh Joshi <unmeshjoshi at gmail.com>wrote:
>>
>>> Hi James,
>>>
>>> At what number of threads JVM or OS performance starts degrading? Or
>>> number of threads start becoming the main bottleneck in the system?
>>>
>>
>> Really, you just need to do your own load testing specific to your own
>> application, hardware and OS requirements.  The current Linux scheduler
>> runs in O(log N),
>>
>>
>> Really? I thought it was using an O(N) heap sort. Anyways, IME, the
>> bigger problem is that getting the thread scheduler scheduled so that you
>> can get threads scheduled... (there might be a Dr. Seuss thing going on
>> here).
>>
>>
>>
>> so technically, that means performance starts degrading at 2 threads,
>> since every thread added increases the amount of time the scheduler takes.
>>  But of course, that degradation is negligible compared to the amount of
>> time your app spends waiting for IO.  So it all depends on your app, what
>> it's doing, and what its requirements are.
>>
>> It's not just scheduling that gets impacted, another obvious one that I
>> already I pointed out was memory consumption, so once the thread stacks
>> have consumed all available RAM, then they won't just be the bottleneck,
>> your application will slow to a crawl or even crash.
>>
>>
>> Slow is something due to something else. No more stack space leads to
>> OOME Stack space exhausted. Is this what you mean?
>>
>> Regards,
>> Kirk
>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>>
>>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20130813/75010771/attachment.html>


More information about the Concurrency-interest mailing list