From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43)
	id 1N1Ptg-0001Jn-Ph
	for qemu-devel@nongnu.org; Fri, 23 Oct 2009 15:34:00 -0400
Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43)
	id 1N1Ptc-0001JH-9W
	for qemu-devel@nongnu.org; Fri, 23 Oct 2009 15:34:00 -0400
Received: from [199.232.76.173] (port=52533 helo=monty-python.gnu.org)
	by lists.gnu.org with esmtp (Exim 4.43) id 1N1Ptc-0001JB-2F
	for qemu-devel@nongnu.org; Fri, 23 Oct 2009 15:33:56 -0400
Received: from mail2.shareable.org ([80.68.89.115]:51526)
	by monty-python.gnu.org with esmtps (TLS-1.0:RSA_AES_256_CBC_SHA1:32)
	(Exim 4.60) (envelope-from <jamie@shareable.org>) id 1N1Ptb-0004WE-JA
	for qemu-devel@nongnu.org; Fri, 23 Oct 2009 15:33:55 -0400
Date: Fri, 23 Oct 2009 20:33:43 +0100
From: Jamie Lokier <jamie@shareable.org>
Subject: Re: [Qemu-devel] [PATCH 01/11] Add append method to qstring and empty
	constructor
Message-ID: <20091023193343.GD12559@shareable.org>
References: <1255786571-3528-1-git-send-email-aliguori@us.ibm.com>
	<1255786571-3528-2-git-send-email-aliguori@us.ibm.com>
	<20091018193652.3d1eb6f1@doriath>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20091018193652.3d1eb6f1@doriath>
List-Id: qemu-devel.nongnu.org
List-Unsubscribe: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=unsubscribe>
List-Archive: <http://lists.gnu.org/pipermail/qemu-devel>
List-Post: <mailto:qemu-devel@nongnu.org>
List-Help: <mailto:qemu-devel-request@nongnu.org?subject=help>
List-Subscribe: <http://lists.nongnu.org/mailman/listinfo/qemu-devel>,
	<mailto:qemu-devel-request@nongnu.org?subject=subscribe>
To: Luiz Capitulino <lcapitulino@redhat.com>
Cc: Anthony Liguori <aliguori@us.ibm.com>, qemu-devel@nongnu.org

Luiz Capitulino wrote:
> >      qstring = qemu_malloc(sizeof(*qstring));
> > -    qstring->string = qemu_strdup(str);
> > +
> > +    qstring->length = strlen(str);
> > +    qstring->capacity = qstring->length;
> > +
> > +    qstring->string = qemu_malloc(qstring->capacity + 1);
> > +    memcpy(qstring->string, str, qstring->length);
> > +    qstring->string[qstring->length] = 0;
> 
>  Couldn't this be:
> 
> qstring->string = qemu_strdup(str);
> qstring->length = qstring->capacity = strlen(str);

Probably to have one call to strlen() instead of two (one inside
qemu_strdup()).

> > +void qstring_append(QString *qstring, const char *str)
> > +{
> > +    size_t len = strlen(str);
> > +
> > +    if (qstring->capacity < (qstring->length + len)) {
> > +        qstring->capacity += len;
> > +        qstring->capacity *= 2; /* use exponential growth */
> > +
> > +        qstring->string = qemu_realloc(qstring->string, qstring->capacity + 1);
> > +    }
> 
>  Why do we need to double it? Wouldn't be enough to only keep track
> of the current string length and add 'len' to it? We could drop
> 'capacity' then.

You need exponential growth if large stringes are to be grown in O(n)
time where n is the number of characters, appended in small pieces.

Think about the time spent copying bytes every time qemu_realloc() is called.

If you just add 'len' each time, think about appending 1 byte 10^4
times.  It will copy approximately 10^8/2 bytes, which is a lot just to
make a string 10^4 bytes long.

But += len; *= 2 is not necessary.  *= 2 is enough, provided the
result is large enough.

> > +    memcpy(qstring->string + qstring->length, str, len);
> > +    qstring->length += len;
> > +    qstring->string[qstring->length] = 0;
> 
>  I would use strcat().

Again, that's an extra call to strlen(), traversing the string twice instead of once.
Doesn't make much different for small strings, only large ones.

-- Jamie