Re: [PATCH 1/4] stringbuf: A string buffer implementation

Rusty Russell
2007-10-27T10:09:22Z

On Saturday 27 October 2007 06:57:14 Matt Mackall wrote:
> Well I expect once you start letting people easily build strings by
> concatenation, you'll very shortly afterwards have people using them
> in loops. And having hidden O(n^2) behavior in there is a little sad,
> even though n will tend to be small and well-bounded. If we can do
> something simple to avoid it, we should.

Hi Matt,

I avoid typing even a single character of optimization until it's
justified. This is partially a reaction against the machoptimization
tendencies of many kernel programmers, but it's mainly a concern at the
kernel's complexity creep.

Meanwhile, of course, I've now spent far too long analyzing this :)

Building a 1000 byte string 1 byte at a time involves 6 reallocs (SLAB) or 10
reallocs (SLUB). Frankly, that's good enough without an explicit alloc
length field (better in some ways).

As to keeping an explicit length vs strlen(): those 1000 calls on my test
machine take 1491ns per call with an explicit length vs 1496ns per call with
strlen(). That's not worth 4 bytes, let alone a single line of code, O(n^2)
or no.

As the nail in the coffin, callers only use ->buf, so are insulated from any
such optimizations if we decided to do them in future.

Hope that helps,
Rusty.
PS. I don't think we should switch this to a simple char ** tho, as
the "struct stringbuf" gives us some type safety and reminds people not to
simply kfree it.