Messages in this thread | | | From | Rusty Russell <> | Subject | Re: [PATCH 1/4] stringbuf: A string buffer implementation | Date | Sat, 27 Oct 2007 20:09:30 +1000 |
| |
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. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |