lkml.org 
[lkml]   [2008]   [Aug]   [13]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: pthread_create() slow for many threads; also time to revisit 64b context switch optimization?
    > Yes, the free_area_cache is always going to have failure modes - I
    > think we've been kind of waiting for it to explode.
    >
    > I do think that we need an O(log(n)) search in there. It could still
    > be on the fallback path, so we retain the mostly-O(1) benefits of
    > free_area_cache.

    The standard dumb way to do that would be to have two parallel trees, one to
    index free space (similar to e.g. the free space btrees in XFS) and the
    other to index the objects (like today). That would increase the constant
    factor somewhat by bloating the VMAs, increasing cache overhead etc, and
    also would be more brute force than elegant. But it would be simple
    and straight forward.

    Perhaps the combined data structure experience of linux-kernel can come
    up with something better and some data structure that allows to look
    up both efficiently?

    This would be also an opportunity to reevaluate rbtrees for the object
    index. One drawback of them is that they are not really optimized to be
    cache friendly because their nodes are too small.

    -Andi


    \
     
     \ /
      Last update: 2008-08-13 23:49    [W:4.343 / U:0.000 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site