string-class

Oliver S.

I've developed a string-class that holds the string in an array which
is a member-variable of the class and that has maximum-size which is con-
figurable through a template-parameter. If any operation would grow the
string beyond its maximum size, an exeception would be thrown. This kind
of string obviously has superior performance over a std::string because
there's never any additional memory-allocation. But before I'm going to
re-invent the wheel, I'd like to ask if someone here alreay encountered
a fully-fledged implementation of such a string-class on the web.

Jul 19 '05 #1

Oliver S.

> You allocate the maximum chunk of memory for *every* string object,[color=blue]
> even for a null string? What an idea! I bet no one ever tried such
> a thing.[/color]

Millions of developers tried this because it's exactly the
C-way except that I'm doing a bounds-check here.

Jul 19 '05 #2

Karl Heinz Buchegger

"Oliver S." wrote:[color=blue]
>[color=green]
> > You allocate the maximum chunk of memory for *every* string object,
> > even for a null string? What an idea! I bet no one ever tried such
> > a thing.[/color]
>
> Millions of developers tried this[/color]

Might be. They tried this because
* it is a good exercise
* they need to practice dynamic memory management
[color=blue]
> because it's exactly the
> C-way except that I'm doing a bounds-check here.[/color]

If you want it the C way, then do it the C way. In C++
this is not a good idea. And btw: you expect a *huge*
speed increase, do you? I tell you a secret: it will
not happen. The guys writing std::string aren't that
dumb. They don't reallocate every time a string gets
larger. There are good and very effective strategies to
avoid this.

--
Karl Heinz Buchegger
kbuchegg@gascad.at

Jul 19 '05 #3

John Dibling

On 28 Jul 2003 23:11:41 GMT, "Oliver S." <Follow.Me@gmx.net> wrote:
[color=blue]
> I've developed a string-class that holds the string in an array which
>is a member-variable of the class and that has maximum-size which is con-
>figurable through a template-parameter. If any operation would grow the
>string beyond its maximum size, an exeception would be thrown. This kind
>of string obviously has superior performance over a std::string because
>there's never any additional memory-allocation. But before I'm going to
>re-invent the wheel, I'd like to ask if someone here alreay encountered
>a fully-fledged implementation of such a string-class on the web.[/color]

Why not just use a fixed-size char array, and not make out-of-bounds
errors?

</dib>
John Dibling
Witty banter omitted for your protection

Jul 19 '05 #4

Oliver S.

> If you want it the C way, then do it the C way.

In most cases you can estimate the maximum string-length a string will
have. So my suggested approach is suitable for all this cases. With the
lib I started you simply give the maximum lentgh as a template-parame-
ter and the calls would throw an exception if the bounds would be excee-
ded (a solution that does a fallback to heap-based strings in this case
would be most elegant, although I doubt that this is really needed).
[color=blue]
> In C++ this is not a good idea.[/color]

That's your opinion that bases on your personal preferences; nothing
more. If you don't need the performance, you can stick with std::strings
but otherwise the approach I suggested is very handy compared to a simple
char[].
[color=blue]
> And btw: you expect a *huge* speed increase, do you?[/color]

Yes, because there's no need for at least the single allocation/deallo-
cation-pair the std::string-approach takes. This call is either very slow
(compared to the fixed-buffer-approach) or does a lot of memory-fragmen-
tation.
[color=blue]
> I tell you a secret: it will not happen. The guys writing
> std::string aren't that dumb.[/color]

That's nothing to do with the fact that even they can't avoid some
general allocation-overhead.
[color=blue]
> They don't reallocate every time a string gets larger.[/color]

Of course not; but the fixed-buffer-approach is *much* faster than a
single allocation on construction and a deallocation on destruction of
the string anyway.
[color=blue]
> There are good and very effective strategies to avoid this.[/color]

Of course; and they're trivial as well (assuming that' you're not
writing the allocator yourself). But even this strategies take per-
formance.

Jul 19 '05 #5

Oliver S.

> Why obviously?[color=blue]
> You underestimate the intelligence of the guys who hoave written
> your standard library.[/color]

No, I don't.
[color=blue]
> In practice you seldom will find much differences in execution speed
> between your implementation and the one already provided to you.[/color]

Of course you can generally find a difference; please test your std::
string-implementation before you issue such false unfounded statements.

Jul 19 '05 #6

Oliver S.

> Why not just use a fixed-size char array, and not make out-of-bounds[color=blue]
> errors?[/color]

Because that's by far not that handy.

Jul 19 '05 #7

John Dibling

On 29 Jul 2003 16:06:37 GMT, "Oliver S." <Follow.Me@gmx.net> wrote:
[color=blue][color=green]
>> Why not just use a fixed-size char array, and not make out-of-bounds
>> errors?[/color]
>
> Because that's by far not that handy.[/color]

In that case, why not use a reserve()'d string? Or a vector<char>?

What is not handy? Writing solid code? (Not a jab) Or are there
additional methods in your class (like formatting methods) that add
handiness to the char buffer? I agree that writing solid code isn't
easy; but that's why we get paid pretty well, and that's the glamorous
life of a C/C++ programmer.

It seems to me that you are essentially using a fixed-size char[] with
extra stuff plunked on top. That extra stuff can only be useful while
still developing code, in helping find the code that causes buffer
overruns etc. That is, once you have found and eliminated the bugs in
the code that uses the strings, the extra code youv'e added to your
char[] buffer has lost its usefullness. At that point, it is less
efficient than just using the raw buffer (in terms of memory, speed
and maintainability), so why do it?

Maybe I'm missing something. You have said that in most cases the
programmer will "know" how big the buffer will need to be in advance.
But suppose they don't. Suppose they want to use your string class in
a function that takes a variable number of paramaters, like in a
specialized version of sprintf. Then you throw an exception when the
buffer gets too big, essentially telling the calling code, "You
screwed up in calling me, now deal with this." Pretty rude,
especially if the fault isn't on the caller, but the fact that a
fixed-length buffer is of very limited usefullness. Furthermore, in
order to write robust, industrial code, everybody who uses your string
class will need to wrap all thier calls in try{}catch{} blocks,
greatly degrading performance. What a hassle.

Again I ask you, why not just use a fixed-length char buffer and avoid
all this mess?

</dib>
John Dibling
Witty banter omitted for your protection

Jul 19 '05 #8

John Dibling

On 29 Jul 2003 21:56:36 GMT, "Oliver S." <Follow.Me@gmx.net> wrote:
[color=blue][color=green]
>> In that case, why not use a reserve()'d string?[/color]
>
> Because even this needs an allocation/deallocation-pair.
>[/color]

Even a raw buffer needs to be allocated and deallocated. A
reserve()'s string can be reserve()'s by a ctor call, ensuring that
there aren't uneeded allocations. So this point is a wash.
[color=blue]
> A class like the one I suggested should have methods for string-typical
>operations like the formatting-operations you mentioned.[/color]

[snip]
[color=blue]
> Most of the usefulness comes from the formatting-options (which are easy
>to implement somewhat faster than formatting with the stupid stream-modi-
>fiers of the iostream-lib). The bounds-checking is just one tiny feature.[/color]

Ok, now I think we are getting to the root of the issue. Suffer my
predictions of your reasoning, and please correct me as needed.

You feel that std::string is inadequate for 2 main reasons: 1) you
don't like the alloc/dealloc scheme it employs, and 2) it doesn't
provide comprehensive string support functions, like sprintf().
[color=blue]
> I didn't suggest the depicted string-class for general purpose ! But
>I claim that a lot of std::string-uses could be replaced by such string
>-objects and thereby significantly lowering the CPU-time string-opera-
>tions take.[/color]

Much of industrial code consists of formatting short strings. I agree
that std::string's is often too inefficient as compared to using a raw
buffer for such formatting. But very often these formatted strings
need to then be saved in memory for a while, and a raw buffer isn't
the right tool for that job either. But combining the use of raw
buffers for formatting with std::strings for the occasional retention
of string data provides what I think is a very effective solution to
both problems. Maybe Iv'e just gotten used to this model of
programming, but I also find it to be an elegant and completely
general-purpose solution.

</dib>
John Dibling
Witty banter omitted for your protection

Jul 19 '05 #9

Oliver S.

> Even a raw buffer needs to be allocated and deallocated.

No, there's no *extra* allocation; either it is inline with its enclo-
sing object or its on the stack.
[color=blue]
> You feel that std::string is inadequate for 2 main reasons: 1) you
> don't like the alloc/dealloc scheme it employs, and 2) it doesn't
> provide comprehensive string support functions, like sprintf().[/color]

For me, only the performance is relevant; if I'd develop a fully-fledged
string-class for public use, there'd be much functionality in the class I
need.
[color=blue]
> Much of industrial code consists of formatting short strings. I agree
> that std::string's is often too inefficient as compared to using a raw
> buffer for such formatting. But very often these formatted strings
> need to then be saved in memory for a while, and a raw buffer isn't
> the right tool for that job either.[/color]

Of course not, but in most cases the string could be inline with an en-
closing object so there'd no extra-allocation. Pure std::strings with no
additional context are rather rare. And of course the over-allocation has
to be balanced against the more compact "just-fits-allocation" (although
memory-fragmentation and allocation-granularity are relevant here also).

Jul 19 '05 #10

Karl Heinz Buchegger

"Oliver S." wrote:[color=blue]
>[color=green]
> > If you want it the C way, then do it the C way.[/color]
>
> In most cases you can estimate the maximum string-length a string will
> have. So my suggested approach is suitable for all this cases. With the
> lib I started you simply give the maximum lentgh as a template-parame-
> ter and the calls would throw an exception if the bounds would be excee-
> ded (a solution that does a fallback to heap-based strings in this case
> would be most elegant, although I doubt that this is really needed).
>[color=green]
> > In C++ this is not a good idea.[/color]
>
> That's your opinion that bases on your personal preferences; nothing
> more.[/color]

Oh. I already tested std::string compared to fixed length character
buffers. I found that in my applications it doesn't make a difference
in terms of speed. But the safety and ease that std::string brings
is more then worth that small spees penalty. And yes: The penalty
has always been small in real world programs.


--
Karl Heinz Buchegger
kbuchegg@gascad.at

Jul 19 '05 #11