-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 According to Robbie Gates on 11/29/2006 3:57 AM: >> 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.
This message on the cygwin list has a good point, and it made me wonder: should we update the semantics of x2nrealloc in lib/xalloc.h to prefer a ratio smaller than 2x growth? - -- Life is short - so eat dessert first! Eric Blake [EMAIL PROTECTED] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.5 (Cygwin) Comment: Public key at home.comcast.net/~ericblake/eblake.gpg Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org iD8DBQFFbZLK84KuGfSFAYARAutAAKCa/T/QsGDW/amEp2UQ3l2T5I6jmgCff4hS VkwRcKoHgkXTpXfheElNb1U= =FlE/ -----END PGP SIGNATURE-----
