From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-3.3 required=5.0 tests=MAILING_LIST_MULTI, RCVD_IN_DNSWL_MED,RCVD_IN_MSPIKE_H3,RCVD_IN_MSPIKE_WL autolearn=ham autolearn_force=no version=3.4.4 Received: (qmail 16435 invoked from network); 18 May 2020 18:36:01 -0000 Received: from mother.openwall.net (195.42.179.200) by inbox.vuxu.org with ESMTPUTF8; 18 May 2020 18:36:01 -0000 Received: (qmail 13559 invoked by uid 550); 18 May 2020 18:35:57 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Reply-To: musl@lists.openwall.com Received: (qmail 13538 invoked from network); 18 May 2020 18:35:57 -0000 Date: Mon, 18 May 2020 14:35:44 -0400 From: Rich Felker To: musl@lists.openwall.com Message-ID: <20200518183543.GE21576@brightrain.aerifal.cx> References: <20200510180934.GV21576@brightrain.aerifal.cx> <20200516002912.GN21576@brightrain.aerifal.cx> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20200516002912.GN21576@brightrain.aerifal.cx> User-Agent: Mutt/1.5.21 (2010-09-15) Subject: Re: [musl] mallocng progress and growth chart On Fri, May 15, 2020 at 08:29:13PM -0400, Rich Felker wrote: > On Sun, May 10, 2020 at 02:09:34PM -0400, Rich Felker wrote: > > 4668: 2x5440 2x5440 2x5440 2x5440 2x5440 5x4672 5x4672 5x4672 5x4672 5x4672 5x4672 7x4672 ... > > This turns out to be just about the worst edge case we have, and in a > sense one that's fundamental. Sadly there are a number of > applications, including bash, that do a lot of malloc(4096). The ones > that just allocate and don't have any complex malloc/free patterns > will see somewhat higher usage with mallocng, and I don't think > there's any way around that. (Note: oldmalloc also has problems here > under certain patterns of alloc/free, due to bin_index vs bin_index_up > discrepancy!) Actually oldmalloc "cheats" for the exact case mentioned here, 4096, because it's an exact size class boundary where bin_index(4096)==bin_index_up(4096). For any other size (e.g. 4080 or 4097) the catastrophic non-reusable-chunk thing will happen. This actually suggests that, if trying to improve/salvage a dlmalloc type design, it would be useful to round up to size classes before allocating, and to avoid trimming down to exact size. Of course this would use considerably more memory initially (just like mallocng uses more than oldmalloc) for straight bump allocation with no free, but it should give less fragmentation and more-stable usage over time. Of course there might be new failure modes too when doing that, especially since split/merge won't preserve the property of being exact size classes. An interesting experiment would be to hack up oldmalloc to round up to size classes, then compare memory usage with mallocng. I suspect we'd then find mallocng almost always uses less memory.