X-Spam-Check-By: sourceware.org
Message-ID: <450464da0611290257i50116402m4b2d97fc303ec374@mail.gmail.com>
Date: Wed, 29 Nov 2006 21:57:05 +1100
From: "Robbie Gates" <robbie AT m8s DOT org>
To: cygwin AT cygwin DOT com
Subject: Re: FYI - bash crash due to asprintf bug
In-Reply-To: <456CF7D9.3090801@byu.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
References: <456CF7D9 DOT 3090801 AT byu DOT net>
X-Google-Sender-Auth: c67b159e366b0e85
X-IsSubscribed: yes
Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
Precedence: bulk
List-Id: <cygwin.cygwin.com>
List-Unsubscribe: <mailto:cygwin-unsubscribe-archive-cygwin=delorie DOT com AT cygwin DOT com>
List-Subscribe: <mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive: <http://sourceware.org/ml/cygwin/>
List-Post: <mailto:cygwin AT cygwin DOT com>
List-Help: <mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Delivered-To: mailing list cygwin AT cygwin DOT com

> reduces asprintf's use of realloc from quadratic
> to log-linear performance (ie. calling realloc every time you add a byte
> is bad, compared to doubling the buffer size every time you call realloc).

Just out of interest, note that a size increase of 50% (i.e. new size
= (3*oldsize)/2) has better properties for certain memory managers, as
opposed to doubling. It has the same asymptotic complexity improvement
as doubling. Roughly speaking, any factor less than the golden ratio
(1+sqrt(5))/2 is good, but 1.5 is (a) cheaply obtanied on most cpu
architectures, and (b) leaves a little space in case the memory
manager adds some overhead. See http://tinyurl.com/yd5669 for details.

 - robbie

--
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple
Problem reports:       http://cygwin.com/problems.html
Documentation:         http://cygwin.com/docs.html
FAQ:                   http://cygwin.com/faq/