This is the mail archive of the
`libstdc++@gcc.gnu.org`
mailing list for the libstdc++ project.

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |

*To*: libstdc++ at gcc dot gnu dot org*Subject*: Re: [Fwd: basic_string<> - useless because of its poor performance]*From*: Nathan Myers <ncm at nospam dot cantrip dot org>*Date*: Fri, 6 Jul 2001 12:40:17 -0700*References*: <200107061228.f66CSUh79620@latour.rsch.comm.mot.com> <200107061237.f66Cb7u79651@latour.rsch.comm.mot.com>*Reply-To*: libstdc++ at gcc dot gnu dot org

On Fri, Jul 06, 2001 at 07:37:07AM -0500, Loren James Rittle wrote: > >> Only if you fail to use reserve() wisely as suggested by Stroustrup... ;-) > > > No. The standard says that string growth is "amortized linear". > > >> I do basically agree that we should do something better than > >> per-character growth given what we generally know about malloc > >> implementations. However, it is unclear that an exponential growth > >> policy is wise. > > > An exponential growth policy is the only way to get the performance > > required by the standard. In fact, exponential growth with base 2 > > is required by the wording, although there have been suggestions that > > 1.5 should be allowed in future amendments. > > Could you explain how the standard can say ``that string growth is > "amortized linear"'' yet ``[a]n exponential growth policy is the only > way to get the performance required by the standard''? This seems > quite contradictory to me. > > To me, ``amortized linear'' implies growing by a fixed block size not > doubling in size each growth. But, I know you are much better read on > the actual standard in most areas than me... The "amortized linear" requirement means that adding <N> characters <M> times should take o(NM) time. (<X> is a random variable with expectation X.) With a linear allocation strategy, allocation time dominates the runtime, and you get much slower performance than NM, as measured. With an exponential allocation strategy, allocation time drops out and the copying time dominates, as required. Or something like that. Anyway, every other implementation uses exponential allocation, although some fudge by using a 1.5 multiplier. Nathan Myers ncm at cantrip dot org

**Follow-Ups**:**Amortized Analysis***From:*David Sankel

Index Nav: | [Date Index] [Subject Index] [Author Index] [Thread Index] | |
---|---|---|

Message Nav: | [Date Prev] [Date Next] | [Thread Prev] [Thread Next] |