From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,64b29dfa2220a59f X-Google-Attributes: gid103376,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news2.google.com!news3.google.com!proxad.net!feeder1-2.proxad.net!fdn.fr!club-internet.fr!feedme-small.clubint.net!nuzba.szn.dk!news.jacob-sparre.dk!pnx.dk!not-for-mail From: "Randy Brukardt" Newsgroups: comp.lang.ada Subject: Re: Reserve_Capacity for Unbounded_String? Date: Wed, 25 Jul 2007 14:08:43 -0500 Organization: Jacob's private Usenet server Message-ID: References: <1185134043.892012.217560@n2g2000hse.googlegroups.com> <1185203238.701948.307410@m37g2000prh.googlegroups.com> NNTP-Posting-Host: static-69-95-181-76.mad.choiceone.net X-Trace: jacob-sparre.dk 1185390384 16974 69.95.181.76 (25 Jul 2007 19:06:24 GMT) X-Complaints-To: news@jacob-sparre.dk NNTP-Posting-Date: Wed, 25 Jul 2007 19:06:24 +0000 (UTC) X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2800.1807 X-MIMEOLE: Produced By Microsoft MimeOLE V6.00.2800.1896 Xref: g2news2.google.com comp.lang.ada:1182 Date: 2007-07-25T14:08:43-05:00 List-Id: "Robert A Duff" wrote in message news:wcctzrtrzhz.fsf@shell01.TheWorld.com... > "Randy Brukardt" 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.