From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/4452 Path: news.gmane.org!not-for-mail From: Rich Felker Newsgroups: gmane.linux.lib.musl.general Subject: Re: Re: Removing sbrk and brk Date: Fri, 3 Jan 2014 14:03:50 -0500 Message-ID: <20140103190350.GW24286@brightrain.aerifal.cx> References: <20131221234041.GA13204@brightrain.aerifal.cx> <20131222184855.GS1685@port70.net> <20131223044609.GZ24286@brightrain.aerifal.cx> <20140102220302.GR24286@brightrain.aerifal.cx> <20140103173301.GU24286@brightrain.aerifal.cx> <20140103181906.GV24286@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1388775836 10250 80.91.229.3 (3 Jan 2014 19:03:56 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 3 Jan 2014 19:03:56 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-4456-gllmg-musl=m.gmane.org@lists.openwall.com Fri Jan 03 20:04:04 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1VzA2N-000182-Ez for gllmg-musl@plane.gmane.org; Fri, 03 Jan 2014 20:04:03 +0100 Original-Received: (qmail 5184 invoked by uid 550); 3 Jan 2014 19:04:02 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 5174 invoked from network); 3 Jan 2014 19:04:02 -0000 Content-Disposition: inline In-Reply-To: <20140103181906.GV24286@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Xref: news.gmane.org gmane.linux.lib.musl.general:4452 Archived-At: On Fri, Jan 03, 2014 at 01:19:06PM -0500, Rich Felker wrote: > On Fri, Jan 03, 2014 at 12:33:01PM -0500, Rich Felker wrote: > > hodge-podge of copy-and-paste from various legacy code. I suspect > > omalloc is considerably higher quality than a lot of the things those > > two implementations copied, but from casual inspection, it doesn't > > look anywhere near as small or high-performance as musl's. > > > > > http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/stdlib/malloc.c > > Quick summary of omalloc: > > - Uses mmap directly for allocations of at least PAGE_SIZE (vs musl > which only uses mmap directly past 128k/256k limit). > > - Rounds all allocation sizes up to a power of 2 (vs musl which has > exact sizes for all mod-16-aligned sizes up to 512 bytes, or > mod-32-aligned up to 1024 bytes on 64-bit, and above that every 1/4 > unit between successive powers of 2). > > - Global lock (vs musl which uses local, per-bin locks, allowing > allocations of different sizes not to touch the same locks). > > - Allocations smaller than PAGE_SIZE are made by allocating a whole > page of same-size objects that cannot be merged or resized in-place > (vs musl which splits and combines free ranges as needed from a > large, growable heap). > > Overall my assessment is that omalloc is _simple_ (in some ways > simpler than musl's), but looks to have much worse fragmentation > properties, much worse performance properties (both syscall overhead > and locking come to mind), and no other clear advantages. And one more big one: - Allocations don't have headers locally, so free is not O(1), but has to perform a hash table lookup based on the address passed to it (vs musl which has O(1) free, modulo retry-on-contention issues). I'm not sure how bad the cost from the hash table is; in some ways, it's an interesting alternate solution that avoids overhead and allows tight packing of small allocations. It also provides greater protection against corruption of the internal malloc structures, in the sense of allowing the program to keep going after overflows, but less ability to catch overflows and less protection from corrupting other application data, unless you add back overhead just for that purpose. Rich