From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from elaine.keithp.com (home.keithp.com [63.227.221.253]) by sourceware.org (Postfix) with ESMTPS id 20BF03985822 for ; Sat, 22 Aug 2020 22:57:58 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.3.2 sourceware.org 20BF03985822 Received: from localhost (localhost [127.0.0.1]) by elaine.keithp.com (Postfix) with ESMTP id C9E3F3F2D5C8; Sat, 22 Aug 2020 15:57:55 -0700 (PDT) X-Virus-Scanned: Debian amavisd-new at keithp.com Received: from elaine.keithp.com ([127.0.0.1]) by localhost (elaine.keithp.com [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 2dxrW4q2CLsh; Sat, 22 Aug 2020 15:57:54 -0700 (PDT) Received: from keithp.com (koto.keithp.com [10.0.0.2]) by elaine.keithp.com (Postfix) with ESMTPSA id 8B19D3F2D53F; Sat, 22 Aug 2020 15:57:54 -0700 (PDT) Received: by keithp.com (Postfix, from userid 1000) id 1D8FC1582201; Sat, 22 Aug 2020 15:57:55 -0700 (PDT) From: "Keith Packard" To: Maarten van der Schrieck | Things Connected , newlib@sourceware.org Subject: Re: [PATCH] nano malloc allocator algorithm improvement In-Reply-To: References: Date: Sat, 22 Aug 2020 15:57:54 -0700 Message-ID: <87tuwugufh.fsf@keithp.com> MIME-Version: 1.0 Content-Type: multipart/signed; boundary="=-=-="; micalg=pgp-sha256; protocol="application/pgp-signature" X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: newlib@sourceware.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Newlib mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 22 Aug 2020 22:58:00 -0000 --=-=-= Content-Type: text/plain Content-Transfer-Encoding: quoted-printable Maarten van der Schrieck | Things Connected writes: > The current nano malloc implementation has two issues reducing the amount= of memory available and increasing fragmentation. > > The first issue is that sbrk() will be called to allocate a space with > the size of the entire requested alloc_size, even if the last free > chunk borders the edge of currently allocated memory. This means that > in a system with 20 kb of RAM, you will get ENOMEM when performing > this: Oh, that's a great idea. I did the same for realloc when the block was at the end of the heap; doing the same for malloc is a nice addition. > The second issue is that a free chunk that is oversized will be cut up > in two pieces, where the *second* piece is used for allocation and the > first one is kept as a free chunk. Although this is easier/shorter in > code (because the free list remains unaffected apart from the size of > the free chunk) it leads to an inefficient pattern of memory > allocation, and ultimately in fragmentation and slower malloc/free > calls. I re-worked the list management to use a different pattern that makes this change much less invasive. https://github.com/picolibc/picolibc/commit/fd2d18bb5ab442f16789c243648d07b= 4ec8e2b29 =2D-=20 =2Dkeith --=-=-= Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEw4O3eCVWE9/bQJ2R2yIaaQAAABEFAl9BovIACgkQ2yIaaQAA ABFQwxAAqeHQyDUw73A7H7oijfaJqdl+nNsyLieYGblqaCvTb06MbGs3kWJcvkdS UKKsGnlwkWdhx0skriD+VUPFZWwBliJLkuXrvnvSLw8jJisgfyU2j+Kcv/eISCZm /H61bY8x4SzXKb0tyvlbOwfbbfpAsb+ScHn0BLhCDRRUAXL2Z1D0jqOreIHlOGY1 WpK3AgzyZjY8FeOW/YPFkpff+egOhcShc7qgvP45WX8V9ok0ULZxdql6l4PML1ok Wq/ARB4/TGkjxVb12TbQj10ED9mUQ1Us9EduaGaiugx42AEmxfLmjWxIjJt0wF3m N4FMX1gpBQPdJ9qhZcd8QHs21PYZVuOOhuJmnBffFLGSz0+b/abXYWN8QUmGf9SW Vx8DXFlmlZezB5ha/bjrokjlZnzcr/3jzVqjhAjg2RxhJ3UvsDDaYrKTUSPZ8jDF n80tl1T8xfAhBzTOGKMJFf/80IQGdYOV97Jvv4sEAaQiAjjtm8HWrXdPbYIC58OZ DiTmcSoVNSXXRDdVmkrnzLXBgNRRwKQ7Pp6M6DIVUJPn1+QjVFnmjXPn7Zw7WLP4 JCKg3fzlFabdb0tsR652B6bNO/J4+V+DEqcVYG3adcgYeY8fgP7K3MPdog8Gg3vY 1Lj50HgDP6cahhcWdPrB3SMYkAEDX8zzoc/Ran7IdASt996GFI0= =XPKd -----END PGP SIGNATURE----- --=-=-=--