linux-kernel - Re: pthread_create() slow for many threads; also time to revisit 64b context switch optimization?

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20080813214650.GS1366@one.firstfloor.org>
Date:	Wed, 13 Aug 2008 23:46:50 +0200
From:	Andi Kleen <andi@...stfloor.org>
To:	Andrew Morton <akpm@...ux-foundation.org>
Cc:	Andi Kleen <andi@...stfloor.org>, mingo@...e.hu,
	drepper@...hat.com, arjan@...radead.org, hugh@...itas.com,
	linux-mm@...ck.org, linux-kernel@...r.kernel.org,
	briangrant@...gle.com, cgd@...gle.com, mbligh@...gle.com,
	torvalds@...ux-foundation.org, tglx@...utronix.de, hpa@...or.com
Subject: Re: 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
--
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/