From: "Randy Brukardt" <randy@rrsoftware.com>
Subject: Re: Reserve_Capacity for Unbounded_String?
Date: Wed, 25 Jul 2007 14:08:43 -0500
Date: 2007-07-25T14:08:43-05:00 [thread overview]
Message-ID: <f886vf$gie$1@jacob-sparre.dk> (raw)
In-Reply-To: wcctzrtrzhz.fsf@shell01.TheWorld.com
"Robert A Duff" <bobduff@shell01.TheWorld.com> wrote in message
news:wcctzrtrzhz.fsf@shell01.TheWorld.com...
> "Randy Brukardt" <randy@rrsoftware.com> writes:
...
> > Yup; I just checked the code to make sure. Moreover, I have yet to see
an
> > real example where the performance difference would matter that much
(Free
> > and new aren't that expensive relative to the alternatives).
>
> It's the copy I'm wondering about, not the new and free so much.
> To append N characters to an unb string requires quadratic copying
> (copying a char N**2 / 2 times).
True enough, but copying is extremely cheap relative to other operations. It
could only matter if N is extremely large, and that won't work in Janus/Ada
anyway (because Ada.Strings.Unbounded is broken in that it depends on type
Integer, which is 16-bit in Janus/Ada for historical reasons; if you want
really big strings in Janus/Ada you have to declare them yourself. I don't
much like this situation, but it is not practically fixable.)
> If you double the allocation every time, it's amortized linear.
> Yes, you waste some space that way.
Quadratic allocation maximizes heap fragmentation (a major issue for small
heaps, and a performance trap for all), and I no longer use it anywhere for
that reason. It also wastes huge amounts of space for long strings. I could
see using a scheme where you rounded up to the nearest 16 (or some similar
number) bytes (as the storage pool is likely to do something like that
anyway); that would catch the long-hanging fruit (i.e. appending lots of
single characters) without too much impact in terms of memory. But anything
further would have nasty memory use effects on programs with a lot of
unbounded strings. And doing that would cost extra overhead on every string
operation; most of them for which there would be no gain.
I still don't think it is worth it, but obviously a customer example could
change my mind.
Randy.
next prev parent reply other threads:[~2007-07-25 19:08 UTC|newest]
Thread overview: 35+ messages / expand[flat|nested] mbox.gz Atom feed top
2007-07-22 19:54 Reserve_Capacity for Unbounded_String? Maciej Sobczak
2007-07-22 21:32 ` Robert A Duff
2007-07-23 19:29 ` Maciej Sobczak
2007-07-23 20:30 ` Robert A Duff
2007-07-23 4:28 ` Jeffrey R. Carter
2007-07-23 15:07 ` Adam Beneschan
2007-07-24 1:01 ` Randy Brukardt
2007-07-24 7:57 ` Pascal Obry
2007-07-24 18:58 ` Randy Brukardt
2007-07-24 23:50 ` Robert A Duff
2007-07-25 0:00 ` Randy Brukardt
2007-07-24 23:54 ` Pascal Obry
2007-07-25 0:52 ` Randy Brukardt
2007-07-25 1:28 ` Randy Brukardt
2007-07-25 7:48 ` Pascal Obry
2007-07-25 9:55 ` Georg Bauhaus
2007-07-25 10:02 ` Georg Bauhaus
2007-07-25 18:58 ` Randy Brukardt
2007-07-25 8:50 ` Martin Krischik
2007-07-25 9:26 ` AW: " Grein, Christoph (Fa. ESG)
2007-07-25 15:32 ` Martin Krischik
2007-07-25 15:39 ` Martin Krischik
2007-07-24 23:41 ` Robert A Duff
2007-07-25 0:16 ` Randy Brukardt
2007-07-25 2:25 ` Robert A Duff
2007-07-25 6:07 ` Simon Wright
2007-07-25 19:08 ` Randy Brukardt [this message]
2007-07-25 20:37 ` Maciej Sobczak
2007-07-25 22:06 ` Georg Bauhaus
2007-07-26 6:24 ` Maciej Sobczak
2007-07-26 8:09 ` Dmitry A. Kazakov
2007-07-26 8:20 ` Pascal Obry
2007-07-26 9:59 ` Dmitry A. Kazakov
2007-07-26 8:35 ` Georg Bauhaus
2007-07-26 22:11 ` Randy Brukardt
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox