From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/14811 Path: news.gmane.org!.POSTED.blaine.gmane.org!not-for-mail From: Micha Nelissen Newsgroups: gmane.linux.lib.musl.general Subject: Re: [PATCH] Use open_memstream(3) for more efficient asprintf Date: Mon, 14 Oct 2019 15:57:31 +0200 Message-ID: References: <20191014120727.GJ16318@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit Injection-Info: blaine.gmane.org; posting-host="blaine.gmane.org:195.159.176.226"; logging-data="171072"; mail-complaints-to="usenet@blaine.gmane.org" User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101 Thunderbird/60.9.0 To: musl@lists.openwall.com Original-X-From: musl-return-14827-gllmg-musl=m.gmane.org@lists.openwall.com Mon Oct 14 15:57:51 2019 Return-path: Envelope-to: gllmg-musl@m.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by blaine.gmane.org with smtp (Exim 4.89) (envelope-from ) id 1iK0r6-000iJz-6a for gllmg-musl@m.gmane.org; Mon, 14 Oct 2019 15:57:48 +0200 Original-Received: (qmail 15721 invoked by uid 550); 14 Oct 2019 13:57:45 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-ID: Original-Received: (qmail 15703 invoked from network); 14 Oct 2019 13:57:45 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=subject:to:references:from:message-id:date:user-agent:mime-version :in-reply-to:content-language:content-transfer-encoding; bh=ZDQrtvZmohcYW69f/M01f1TMOJ0uQV5RJLpUiQ2FYIw=; b=RGWY9f2Q/oRo9pMyHFVGKxmnTP6MQ9/DfX0BQah1MvBFPl/9dZUKziBZVu5xbfBJDi t9kLSP1ioZeb9RQaTJBhBoDmD3oCclFjZBYldYTn7fGYkAqQiF/NMxW/yfZHm+7dipJI U93Oc0gN24zKTdHU1HYh+V5IM650z3XIGaoc+p/8hd5+OOx0mX9KVLgHfE56ch2c3Vwz uM3qOZwQp0Ly8ry564wEBXvU03/MK0gYMbEuXSBIA64EG/lycAEgIOuMv2BJFu5PGqH8 MpDGMMHeN8XPmd5eEvfmsUyJuK6RW7R4EXkLPOTPPAJUrRfSZRA87k/HcAlLiDx2ATMq 40Lg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:subject:to:references:from:message-id:date :user-agent:mime-version:in-reply-to:content-language :content-transfer-encoding; bh=ZDQrtvZmohcYW69f/M01f1TMOJ0uQV5RJLpUiQ2FYIw=; b=S85POw9RGkqBaYGaIQKMIX40JmZwVQZgMD4sLaepRBWAn98UZZe3OS1xwgL/6fTdsk p6fPzU8ZAcZZhKmFir/fGzVTG3QvWRZk211nJvEoPfeaQJwpzsZ56Og9eHiRfavbqFOB ZWHX+xchpmTON5VSzrTtCIu0pEI42A9u927hsvL5CIOpwQHX9rF9UdvNE56EMrpvgpvo uEe1ND8WCul8sdA2UeB5ojfwUDC8q8iUTP9cnm1NRMVcWmTlfVuctZbrcfG9HTut3r1l auI+TwEPFErvoGDVZZC7t/e6EcSqavWLXXQFXmp+IJDU68ZZXBF0EZDyNdbrXnYqRSfT +ElQ== X-Gm-Message-State: APjAAAUL4QSoDeKSep1qNRguE4y+rzQGJJBb6P5JbMTpyjk+C71dEJZo 07KqbskeUxT2KScb7WtHLW2NYrDc X-Google-Smtp-Source: APXvYqxdwXr/Ahghrid5+54ZhXt/2oOThCgBfYCJ/37UaCcCfh4sThnN1HWxC8s/UTucT1AzAUEyvg== X-Received: by 2002:aa7:cb55:: with SMTP id w21mr28093460edt.163.1571061453697; Mon, 14 Oct 2019 06:57:33 -0700 (PDT) In-Reply-To: <20191014120727.GJ16318@brightrain.aerifal.cx> Content-Language: en-US Xref: news.gmane.org gmane.linux.lib.musl.general:14811 Archived-At: On 14-10-2019 14:07, Rich Felker wrote: > - avoiding quadratic-time worst-case (from the memcpy in realloc with > linear buffer size growth at each step) or internal fragmentation > (from geometric buffer growth at each step). Our current memstream > implementation uses linear growth I think so it would be the former > (quadratic time) This seems to imply linear buffer size growth doesn't cause fragmentation? In general it does I would assume. > - avoiding fragmentation produced by realloc I guess the idea behind the original malloc(GUESS) (and also this memstream implementation?) is that it allocates from end of heap, and therefore realloc is very cheap: just move end of heap pointer. Although in a multi-threaded world this becomes less likely depending on the intensity of malloc/realloc usage by other threads. Micha