Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

3,326 views

Skip to first unread message

Nov 5, 2003, 5:03:39 AM11/5/03

to

I've been doing other stuff lately, so this may be old news (though I

wasn't able to find any mention of this via Google), but I just noticed

that the growth factor for vector in the MS7.1 implementation seems to be

1.5 instead of the more traditional 2 (as I believe it was in VC6). My

other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

a factor of 2 when a push_back exceeds capacity.

wasn't able to find any mention of this via Google), but I just noticed

that the growth factor for vector in the MS7.1 implementation seems to be

1.5 instead of the more traditional 2 (as I believe it was in VC6). My

other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

a factor of 2 when a push_back exceeds capacity.

I'd be intersted if any other vector implemenations uses a growth factor

other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

don't have that compiler here).

Thanks,

Scott

[ See http://www.gotw.ca/resources/clcm.htm for info about ]

[ comp.lang.c++.moderated. First time posters: Do this! ]

Nov 5, 2003, 3:19:54 PM11/5/03

to

"Scott Meyers" <Use...@aristeia.com> wrote in message

news:MPG.1a11d4f0a...@news.hevanet.com...

news:MPG.1a11d4f0a...@news.hevanet.com...

> I've been doing other stuff lately, so this may be old news (though I

> wasn't able to find any mention of this via Google), but I just noticed

> that the growth factor for vector in the MS7.1 implementation seems to be

> 1.5 instead of the more traditional 2 (as I believe it was in VC6). My

> other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

> a factor of 2 when a push_back exceeds capacity.

>

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

VC++ V7.0 also uses 1.5. We settled on that factor as a better balance

between memory utilization and expansion efficiency.

P.J. Plauger

Dinkumware, Ltd.

http://www.dinkumware.com

Nov 5, 2003, 3:30:50 PM11/5/03

to

Scott Meyers wrote:

> I've been doing other stuff lately, so this may be old news (though I

> wasn't able to find any mention of this via Google), but I just

> noticed that the growth factor for vector in the MS7.1 implementation

> seems to be 1.5 instead of the more traditional 2

> I've been doing other stuff lately, so this may be old news (though I

> wasn't able to find any mention of this via Google), but I just

> noticed that the growth factor for vector in the MS7.1 implementation

> seems to be 1.5 instead of the more traditional 2

See this thread:

<http://groups.google.com/groups?threadm=3b6805d7%241%40primark.com>

> (as I believe it was in VC6).

You remember correctly.

> My other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to

> grow by a factor of 2 when a push_back exceeds capacity.

>

> I'd be intersted if any other vector implemenations uses a growth

> factor other than 2, and I'd also like to know whether VC7 uses 1.5

> or 2 (since I don't have that compiler here).

VC++ 7 uses a factor of 1.5.

Nov 5, 2003, 3:32:30 PM11/5/03

to

Not directly related, I presume, but the Java library uses a factor of 1.5

in ArrayList.

in ArrayList.

In article MPG.1a11d4f0a...@news.hevanet.com, Scott Meyers at

Use...@aristeia.com wrote on 11/5/03 4:03 AM:

> I've been doing other stuff lately, so this may be old news (though I

> wasn't able to find any mention of this via Google), but I just noticed

> that the growth factor for vector in the MS7.1 implementation seems to be

> 1.5 instead of the more traditional 2 (as I believe it was in VC6). My

> other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

> a factor of 2 when a push_back exceeds capacity.

>

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

>

> Thanks,

>

> Scott

--

Glenn P. Downing

The University of Texas at Austin

Department of Computer Sciences

Taylor Hall 2.124

Austin, TX 78712

(512) 471-7316

http://www.cs.utexas.edu/users/downing/

Nov 5, 2003, 3:32:51 PM11/5/03

to

Scott Meyers schrieb:

> I've been doing other stuff lately, so this may be old news (though I

> wasn't able to find any mention of this via Google), but I just noticed

> that the growth factor for vector in the MS7.1 implementation seems to be

> 1.5 instead of the more traditional 2 (as I believe it was in VC6). My

> other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

> a factor of 2 when a push_back exceeds capacity.

>

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

As far as I remember, a factor near 1.5 results from an analysis from Andrew

Koenig (?), which takes several general aspects of allocation processes

into account. Regrettably I forgot the quote from the corresponding article,

but

surely there will remember another one.

Greetings from Bremen,

Daniel

Nov 5, 2003, 5:12:36 PM11/5/03

to

Scott Meyers <Use...@aristeia.com> wrote:

> [...] I just noticed

> that the growth factor for vector in the MS7.1 implementation seems to be

> 1.5 instead of the more traditional 2 (as I believe it was in VC6).

> [...] I just noticed

> that the growth factor for vector in the MS7.1 implementation seems to be

> 1.5 instead of the more traditional 2 (as I believe it was in VC6).

VC6 indeed seems to have a factor of 2.

> My

> other implementations (g++ 3.2 mingw and Comeau 4.3.3) continue to grow by

> a factor of 2 when a push_back exceeds capacity.

>

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

Besides VC 6/7.1 I have access to Metrowerks'

MSL (CW8) and STLport (4.5).

Both use a factor of 2.

> Thanks,

>

> Scott

Schobi

--

Spam...@gmx.de is never read

I'm Schobi at suespammers org

"And why should I know better by now/When I'm old enough not to?"

Beth Orton

Nov 5, 2003, 5:26:10 PM11/5/03

to

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

There is a technical reason to prefer 1.5 to 2 -- more specifically, to

prefer values less than 1+sqrt(5)/2.

Suppose you are using a first-fit memory allocator, and you're progressively

appending to a vector. Then each time you reallocate, you allocate new

memory, copy the elements, then free the old memory. That leaves a gap, and

it would be nice to be able to use that memory eventually. If the vector

grows too rapidly, it will always be too big for the available memory.

It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

will always be too big for the hole that has been left sofar; if it is

<1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to

allow the memory to be recycled.

Nov 5, 2003, 5:29:16 PM11/5/03

to

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

>

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

>

VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

probably the most common (and well-known) factor. It also changes the

performance characteristics of code written in older times.

It's hard to tell which factor is best in the absolute sense, so I'd

prefer that to be a parameter. Just changing a hard-coded number

doesn't seem a good solution to me.

- Vahan

Nov 6, 2003, 5:33:49 AM11/6/03

to

On 5 Nov 2003 17:26:10 -0500, "Andrew Koenig" <a...@acm.org> wrote:

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

Since 1+sqrt(5)/2 > 2, correcting that typo gives (1+sqrt(5))/2.

John

Nov 6, 2003, 8:42:36 AM11/6/03

to

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

> prefer values less than 1+sqrt(5)/2.

Sorry, I meant (1+sqrt(5))/2.

Nov 6, 2003, 9:09:13 AM11/6/03

to

On 5 Nov 2003 17:26:10 -0500, Andrew Koenig wrote:

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

Didn't you write an article on this one time? If so, can you please post a reference and, if

available, a URL?

Thanks,

Scott

Nov 6, 2003, 9:18:17 AM11/6/03

to

Vahan Margaryan wrote:

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor.

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor.

It's hard for me to see this as "reducing portability". There is nothing in the

Standard that requires or even implies that std::vectors should reallocate in

multiples of 2. If client code is relying on std::vector growing by multiples

of 2, then I would say that the client code is reducing portability, not VC.

Nov 6, 2003, 9:19:31 AM11/6/03

to

On 5 Nov 2003 17:26:10 -0500, Andrew Koenig <a...@acm.org> wrote:

>> I'd be intersted if any other vector implemenations uses a growth factor

>> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

>> I

>> don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

>

> Suppose you are using a first-fit memory allocator, and you're

> progressively

> appending to a vector. Then each time you reallocate, you allocate new

> memory, copy the elements, then free the old memory. That leaves a gap,

> and

> it would be nice to be able to use that memory eventually. If the vector

> grows too rapidly, it will always be too big for the available memory.

>

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough

> to

> allow the memory to be recycled.

Yes,small correction, less then (1+sqrt(5))/2 that is less then 1.6~1.7

--

grzegorz

Nov 6, 2003, 9:32:13 AM11/6/03

to

In article <44d2ad1a.03110...@posting.google.com>, Vahan

Margaryan <mar...@yahoo.com> writes

>Scott Meyers <Use...@aristeia.com> wrote in message

>news:<MPG.1a11d4f0a...@news.hevanet.com>...

>> I'd be intersted if any other vector implemenations uses a growth factor

>> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

>> don't have that compiler here).

>>

>

>VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

>probably the most common (and well-known) factor.

Margaryan <mar...@yahoo.com> writes

>Scott Meyers <Use...@aristeia.com> wrote in message

>news:<MPG.1a11d4f0a...@news.hevanet.com>...

>> I'd be intersted if any other vector implemenations uses a growth factor

>> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

>> don't have that compiler here).

>>

>

>VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

>probably the most common (and well-known) factor.

I fail to see how an implementation detail such as the growth factor can

possibly effect portability.

> It also changes the

>performance characteristics of code written in older times.

Yes, but that is not what we mean by portability. There are many aspects

of performance that change with new releases of compilers. Actually the

amount and types of available memory influences performance in a far

more dramatic way. The existence of large cache memory actually means

that vector<T> will often out perform list<T> for insertions even though

list<T> is theoretically much superior when uniform memory is used.

The innovative feature of the C++ Standard Library was the provision of

certain performance guarantees.

>

>It's hard to tell which factor is best in the absolute sense, so I'd

>prefer that to be a parameter. Just changing a hard-coded number

>doesn't seem a good solution to me.

Possibly, but hard coded values do allow certain optimisations and in

another post Andy Koenig points out the a growth factor of 1.5 allows a

memory usage optimisation that is not available to systems using a

factor of 2.0

--

Francis Glassborow ACCU

If you are not using up-to-date virus protection you should not be reading

this. Viruses do not just hurt the infected but the whole community.

Nov 6, 2003, 11:43:33 AM11/6/03

to

Andrew Koenig schrieb:

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

>

> Suppose you are using a first-fit memory allocator, and you're progressively

> appending to a vector. Then each time you reallocate, you allocate new

> memory, copy the elements, then free the old memory. That leaves a gap, and

> it would be nice to be able to use that memory eventually. If the vector

> grows too rapidly, it will always be too big for the available memory.

>

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to

> allow the memory to be recycled.

Hello Andrew Koenig,

so my remembrance took me right! Is it correct, that you wrote an article about

the

proof of this dependency? Can you please give me quote for it?

Thank you very much!

Greetings from Bremen,

Daniel Spangenberg

Nov 6, 2003, 11:49:06 AM11/6/03

to

"Andrew Koenig" <a...@acm.org> wrote in message news:FUbqb.206398

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

But 1+sqrt(5)/2 = 2.118... The OP's question is about 1.5 versus 2.0, and

both are less than 1+sqrt(5)/2.

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough

to

> allow the memory to be recycled.

Also, where did the sqrt(5) come from?

--

+++++++++++

Siemel Naran

Nov 6, 2003, 11:54:32 AM11/6/03

to

"Vahan Margaryan" <mar...@yahoo.com> wrote in message

> Scott Meyers <Use...@aristeia.com> wrote in message

> Scott Meyers <Use...@aristeia.com> wrote in message

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

I

> > don't have that compiler here).

>

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor. It also changes the

> performance characteristics of code written in older times.

The factor 1.5 or 2.0 is an implementation detail and should not affected

the portability of the code in the sense that the code should compile and

run as expected on all platforms. It may affect performance characteristics

as you mention. Members of this newsgroup say the 1.5 method leads to

better memory usage. Of course, use vector::reserve whenever you can.

> It's hard to tell which factor is best in the absolute sense, so I'd

> prefer that to be a parameter. Just changing a hard-coded number

> doesn't seem a good solution to me.

Implementations may add an additional template parameter to std::vector.

Here's an attempt

template <class T, class Allocator=std::allocator<T>, double mult=1.5>

class vector;

But non-template parameters must be integral constants. So how to do it?

Second, how do we multiply the size by 1.5? Do you divide by 2 then

multiply by 3, or what?

--

+++++++++++

Siemel Naran

Nov 6, 2003, 7:45:08 PM11/6/03

to

Vahan Margaryan wrote:

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor.

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor.

I cannot see how a groing factor could impact portability. I think that you

should give your definition of portability, because it doesn't seem to fit

its usual meaning in C++...

> It also changes the

> performance characteristics of code written in older times.

Well, if you got critical counter-performance by using the automatic

allocation scheme of vectors, i am not sure any growth factor is a correct

answer.

However, your second assertion is somehow in contradiction with your first

one. If you talk about portability, you cannot assume that the allocation

scheme is equally performing on different systems, even if the growth factor

is the same...

Chris

Nov 6, 2003, 7:48:49 PM11/6/03

to

Hi Scott.

You wrote:

> I'd be intersted if any other vector implemenations uses a growth factor

> other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> don't have that compiler here).

IBM's VisualAge C++ 5.0.2.2 on AIX also seems to use a growth

factor of 1.5. A small test program which push_back()s elements

onto an (initially empty) vector yields the following sequence

of capacities:

size capacity

1 1

2 2

3 3

4 4

5 6

7 9

10 13

14 19

20 28

29 42

43 63

64 94

95 141

142 211

212 316

317 474

475 711

712 1066

1067 1599

1600 2398

2399 3597

3598 5395

5396 8092

8093 12138

(size indicates which vector size caused a change in the

capacity).

Kind regards

Ingolf

--

Ingolf Steinbach Jena-Optronik GmbH

ingolf.s...@jena-optronik.de ++49 3641 200-147

PGP: 0x7B3B5661 213C 828E 0C92 16B5 05D0 4D5B A324 EC04

Nov 6, 2003, 7:52:53 PM11/6/03

to

mar...@yahoo.com (Vahan Margaryan) writes:

> Scott Meyers <Use...@aristeia.com> wrote in message

> news:<MPG.1a11d4f0a...@news.hevanet.com>...

>> I'd be intersted if any other vector implemenations uses a growth

>> factor other than 2, and I'd also like to know whether VC7 uses 1.5

>> or 2 (since I don't have that compiler here).

>>

>

> VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> probably the most common (and well-known) factor. It also changes

> the performance characteristics of code written in older times.

>

> It's hard to tell which factor is best in the absolute sense, so I'd

> prefer that to be a parameter. Just changing a hard-coded number

> doesn't seem a good solution to me.

Isn't that what the reserve() member function is for? Since the growth

factor is not specified by the standard, and probably not even

documented for your platform, relying on any particular growth factor

is inherently non-portable. Using reserve() you can guarantee (at

least) enough memory for a given number of elements in a fully

portable manner. Otherwise, you can just rely on a quality

implementation doing something reasonable.

--

Raoul Gough.

(setq dabbrev-case-fold-search nil)

Nov 6, 2003, 7:56:03 PM11/6/03

to

news:FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

>

> Suppose you are using a first-fit memory allocator, and you're

progressively

> appending to a vector. Then each time you reallocate, you allocate new

> memory, copy the elements, then free the old memory. That leaves a gap,

and

> it would be nice to be able to use that memory eventually. If the vector

> grows too rapidly, it will always be too big for the available memory.

>

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough

to

> allow the memory to be recycled.

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

>

> Suppose you are using a first-fit memory allocator, and you're

progressively

> appending to a vector. Then each time you reallocate, you allocate new

> memory, copy the elements, then free the old memory. That leaves a gap,

and

> it would be nice to be able to use that memory eventually. If the vector

> grows too rapidly, it will always be too big for the available memory.

>

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough

to

> allow the memory to be recycled.

Surely, if the growth factor is >= 2 the new memory will always

be too big for the hole that has been left sofar; if it is < 2,

the new memory will eventually fit.

Presumably the reason for (1+sqrt(5))/2 is...

Initial allocation is s.

The first resize is k*s.

The second resize is k*k*s, which'll fit the hole

iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

...the hole can be recycled asap.

It could, by storing its previous size, grow fibonaccily.

Louis.

Nov 6, 2003, 8:00:24 PM11/6/03

to

"Andrew Koenig" <a...@acm.org> wrote in message news:<FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net>...

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically,

> to prefer values less than 1+sqrt(5)/2.

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically,

> to prefer values less than 1+sqrt(5)/2.

I calculated 1+sqrt(5)/2 as 2.118

Did you mean (1+sqrt(5))/2 ?

(That's about 1.618)

Michael

Nov 7, 2003, 9:17:46 AM11/7/03

to

In article

<svnqb.207208$0v4.16...@bgtnsc04-news.ops.worldnet.att.net>,

"Siemel Naran" <Sieme...@REMOVE.att.net> wrote:

<svnqb.207208$0v4.16...@bgtnsc04-news.ops.worldnet.att.net>,

"Siemel Naran" <Sieme...@REMOVE.att.net> wrote:

> Also, where did the sqrt(5) come from?

From the relevant root of the equation k^2 - k - 1 = 0. ;-)

-Howard

Nov 7, 2003, 9:18:07 AM11/7/03

to

Hi,

> But 1+sqrt(5)/2 = 2.118... The OP's question is about 1.5 versus 2.0, and

> both are less than 1+sqrt(5)/2.

Actually, (1+sqrt(5))/2. The golden section.

> Also, where did the sqrt(5) come from?

From finding a ratio a:b such that

a:b = (a+b):a

This leads to a quadratic equation whose solution is the prominent

golden section. (That is also related to the fibunacci sequence, btw.)

Greetings,

Thomas

Nov 7, 2003, 9:23:34 AM11/7/03

to

Siemel Naran wrote:

> Second, how do we multiply the size by 1.5? Do you divide by 2 then

> multiply by 3, or what?

> Second, how do we multiply the size by 1.5? Do you divide by 2 then

> multiply by 3, or what?

Does it matter ?

(i don't think you are talking about some performance issue, because the

allocation and copy is most likely to consume more than 99% of the time that

the function will be running)

Chris

Nov 7, 2003, 9:24:39 AM11/7/03

to

> Also, where did the sqrt(5) come from?

Andrew Koenig means Phi, the Golden Ratio, the ratio of 2 successive terms

that the Fibonacchi series converges to 1,2,3,5,8,13,21,34,55,...

It is also the ratio of a long diagonal of a regular pentagon to its edge.

Phi is (sqrt(5.0)+1.0)/2.0

It has some almost magical properties

1/ Phi = 0.6180339887498948482045868343656...

Phi = 1.6180339887498948482045868343656...

Phi * Phi = 2.6180339887498948482045868343656...

and in general

pow(Phi, n+1) = pow(Phi, n) + pow(Phi, n-1)

Stephen Howe

Nov 7, 2003, 9:30:45 AM11/7/03

to

In article

<uvnqb.207209$0v4.16...@bgtnsc04-news.ops.worldnet.att.net>, Siemel

Naran <Sieme...@REMOVE.att.net> writes

>Second, how do we multiply the size by 1.5? Do you divide by 2 then

>multiply by 3, or what?

<uvnqb.207209$0v4.16...@bgtnsc04-news.ops.worldnet.att.net>, Siemel

Naran <Sieme...@REMOVE.att.net> writes

>Second, how do we multiply the size by 1.5? Do you divide by 2 then

>multiply by 3, or what?

i += i>>1;

--

Francis Glassborow ACCU

If you are not using up-to-date virus protection you should not be reading

this. Viruses do not just hurt the infected but the whole community.

Nov 7, 2003, 9:33:45 AM11/7/03

to

On 6 Nov 2003 11:49:06 -0500, "Siemel Naran"

<Sieme...@REMOVE.att.net> wrote:

<Sieme...@REMOVE.att.net> wrote:

> Also, where did the sqrt(5) come from?

It is (1 + sqrt(5))/2 which is the golgen ratio that answers

all questions. :)

The solution to x^2 - x - 1 = 0 which is the equation that you

get when you ask for the memory freed by prior increases to sum

to the amount needed for the next one.

John

Nov 7, 2003, 4:54:53 PM11/7/03

to

On 6 Nov 2003 19:56:03 -0500, "Louis Lavery" <Lo...@devilsChimney.co.uk>

wrote:

wrote:

> Surely, if the growth factor is >= 2 the new memory will always

> be too big for the hole that has been left sofar;

Yes.

> if it is < 2, the new memory will eventually fit.

No.

Try 1.8.

size free

0 0

1 0

2 0

3 1

5 3

9 6

16 11

Please continue the exercise until your "eventually" happens.

John

Nov 7, 2003, 5:05:24 PM11/7/03

to

Siemel Naran schrieb:

> "Andrew Koenig" <a...@acm.org> wrote in message news:FUbqb.206398

>

> > > I'd be intersted if any other vector implemenations uses a growth factor

> > > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

> I

> > > don't have that compiler here).

> >

> > There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> > prefer values less than 1+sqrt(5)/2.

>

> But 1+sqrt(5)/2 = 2.118... The OP's question is about 1.5 versus 2.0, and

> both are less than 1+sqrt(5)/2.

>

> > It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> > will always be too big for the hole that has been left sofar; if it is

> > <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough

> to

> > allow the memory to be recycled.

>

> Also, where did the sqrt(5) come from?

I am quite sure, he meant (1+sqrt(5))/2, which is also known as the Golden

ratio.

This number often occurs during analysis of repeated divisions...

Daniel

Nov 7, 2003, 5:06:50 PM11/7/03

to

Louis Lavery <Lo...@devilsChimney.co.uk> wrote in message

news:bode8v$fis$1$8300...@news.demon.co.uk...

>

> Andrew Koenig <a...@acm.org> wrote in message

> news:FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

[snip

> > It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> > will always be too big for the hole that has been left sofar; if it is

> > <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small

enough

> to

> > allow the memory to be recycled.

>

> Surely, if the growth factor is >= 2 the new memory will always

> be too big for the hole that has been left sofar; if it is < 2,

> the new memory will eventually fit.

>

> Presumably the reason for (1+sqrt(5))/2 is...

>

> Initial allocation is s.

> The first resize is k*s.

> The second resize is k*k*s, which'll fit the hole

> iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

>

> ...the hole can be recycled asap.

Ah! The hole still contains the current data :-(

So it's as you say, k must be < (1+sqrt(5))/2 for

an eventual fit.

Louis.

P.S. Little point in k < (0.5+sqrt(69)/18)^1/3+(0.5-sqrt(69)/18)^1/3

(which is its recylce asap value).

Nov 7, 2003, 5:07:12 PM11/7/03

to

"Siemel Naran" <Sieme...@REMOVE.att.net> wrote in message

news:svnqb.207208$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

> > There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> > prefer values less than 1+sqrt(5)/2.

>

> > prefer values less than 1+sqrt(5)/2.

>

> Also, where did the sqrt(5) come from?

The calculation involves a bit of somewhat non-trivial math,

but the theory seems to be the following (and I'm just

guessing since I haven't seen the article):

Let the increment ratio be 'x'. Subsequent allocations

are therefore x, x^2, x^3, x^4, ... (times the size of the

initial allocation, but that doesn't affect the ratios).

When the block of size 'x^n' becomes full, a new one

of size 'x^(n+1)' needs to be allocated. It would be good

if this block fit into the size of already de-allocated blocks.

Because block 'x^n' must be present for copying stuff into

the new block, the sum of the sizes of the previous blocks

(x, x^2, x^3, ..., x^(n-1) ) should be less than or equal to

the size of the next block. x^(n+1) . This leads to a formula

x^= x+1, to which (1+sqrt(5))/2 is the positive solution.

This is a nice theory, but it neglects a number of factors:

- Administrative data of the memory allocator is a constant

added to every allocation

- Filling the vector may need to allocate memory, ruining the

idea that the "next" block always fits to what is left from

the previous allocations

- This scheme pays off only once. It is based on the idea

that *all* of the past deallocations accumulate a memory

block that is enough to contain a "next" allocation. When

this has been done once, the past deallocations block

can never again contain *all* of the past deallocations.

To fight some of the drawbacks, the ratio is lowered from

(1+sqrt(5))/2 ~1.618 to, say - like in the topical case - 1.5 .

Some drawbacks still remain.

Cheers!

- Risto -

Nov 7, 2003, 7:20:54 PM11/7/03

to

"Louis Lavery" <Lo...@devilsChimney.co.uk> wrote in message

news:bode8v$fis$1

news:bode8v$fis$1

> Presumably the reason for (1+sqrt(5))/2 is...

>

> Initial allocation is s.

> The first resize is k*s.

> The second resize is k*k*s, which'll fit the hole

> iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

Dumb question. What hole?

--

+++++++++++

Siemel Naran

Nov 7, 2003, 7:25:25 PM11/7/03

to

Hi,

Louis Lavery wrote:

> Presumably the reason for (1+sqrt(5))/2 is...

>

> Initial allocation is s.

> The first resize is k*s.

> The second resize is k*k*s, which'll fit the hole

> iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

>

> ...the hole can be recycled asap.

It's not that easy.

Note that in order to grow the vector, you need to *first* allocate the

new memory, copy the elements and *after that* you can free the old block.

This means that the condition for recycling is not what you wrote,

because in order to allocate k*k*s you still need the k*s still in

place, so you cannot count it in the gap.

The gap will accumulate and after few reallocations the gap will be big

enough to accommodate the new vector, but it is not the second

allocation, no matter what is the growing factor.

The condition for memory reuse is this:

(k^n)*s <= Sum(i=0, n-2, (k^i)*s)

For example, in order to reuse the gap in fourth growing step, we have:

k*k*k*k*s <= s + k*s + k*k*s

because the k*k*k*s is still needed while k*k*k*k*s is being allocated.

It is too early in the morning for me to bite the above as a

mathematician, but as a programmer I was able to write this:

#include <iostream>

using namespace std;

int main()

{

double k;

cout << "enter the growing factor: ";

cin >> k;

double size = 1.0;

double newsize;

double gap = 0.0;

int steps = 1;

while ((newsize = k * size) > gap)

{

gap += size;

size = newsize;

++steps;

}

cout << "the gap is reused after " << steps

<< " steps, with size " << newsize

<< " bigger than initially\n";

}

The growing factor 1.5 guarantees that the gap will be reused in 5th

step, growing the vector ~7.6 times (the accumulated gap will be ~8*s).

The factor 1.6 reuses the gap in 8th step, growing vector 42.9 times.

The factor 1.7 overflows, meaning that the value between 1.6 and 1.7

(presumably (1+sqrt(2))/2) is indeed the critical one, but in the

asymptotic way, not as the guarantee of instant reuse.

> It could, by storing its previous size, grow fibonaccily.

Interesting, but it would not be able to meet the "amortized constant

cost of unit grow" requirement. This requirement boils down to constant

factors.

--

Maciej Sobczak : http://www.msobczak.com/

Programming : http://www.msobczak.com/prog/

Nov 7, 2003, 7:32:25 PM11/7/03

to

Francis Glassborow <fra...@robinton.demon.co.uk> wrote in message news:<XlJkfEFoeYq$Ew...@robinton.demon.co.uk>...

> I fail to see how an implementation detail such as the growth factor can

> possibly effect portability.

> I fail to see how an implementation detail such as the growth factor can

> possibly effect portability.

My definition of portability (admittedly not necessarily universally

accepted) is the inverse of the effort it takes to take the code to

another platform and make it work. This includes the performance: if

the code compiles on a different platform but performs noticeably

worse, we usually don't consider porting complete.

> Yes, but that is not what we mean by portability. There are many aspects

> of performance that change with new releases of compilers. Actually the

> amount and types of available memory influences performance in a far

> more dramatic way. The existence of large cache memory actually means

> that vector<T> will often out perform list<T> for insertions even though

> list<T> is theoretically much superior when uniform memory is used.

I agree that there are many factors beyond our control that affect

portability of performance of our code. File system operations may

have different complexities under different OS's, compilers are

different, etc. In some casese those things force rewrites (as in the

case you've mentioned). That's the inevitable evil. However, in this

case:

a) This is something under our control, so why introduce an additional

problem? I for one was unpleasantly surprised when I found out that

the factor changes from platform to platform.

Why not use a common default and use an extra integer template

parameter that specifies the reallocation factor (in percents, for

instance)?

b) Containers and algorithms are very important determinants of

performance, if not the most important ones. I don't really care if

mkdir works slower or faster than CreateDirectory, that won't affect

the performance of my program. But I would like to be certain about

the characteristics of the containers, because the performance of

programs crucially depends on them.

Then of course I can write my own containers and not use STL. Yet, it

has been serving me well mostly, and I'd like to think of it as a

serious and usable library.

Some portability (my definition) issues that I've encountered in STL:

1. The std::list::size/splice performance. One has to be careful not

to use std::list's size() thoughtlessly, or write a wrapper, or

something. IOW, perform additional effort.

2. Hash tables. Unlike std::set, which, in my experience, behaves

pretty uniformly, hash performance differs significanly. There are

many implementation strategies, policies involved. I prefer to drag a

single implementation from platform to platform, rather than rely on

the platform-specific implementation. Btw, last I checked, the

proposal for hash-tables doesn't eliminate some of the choices (but I

may be outdated on this), and that's, in my view, a defect.

> The innovative feature of the C++ Standard Library was the provision of

> certain performance guarantees.

What I suggest is that perhaps the guarantees should be even stricter.

> >It's hard to tell which factor is best in the absolute sense, so I'd

> >prefer that to be a parameter. Just changing a hard-coded number

> >doesn't seem a good solution to me.

>

> Possibly, but hard coded values do allow certain optimisations and in

> another post Andy Koenig points out the a growth factor of 1.5 allows a

> memory usage optimisation that is not available to systems using a

> factor of 2.0

It's not the specific factor that concerns me, it's my unawareness of

the factor when I move to another platform.

- Vahan

Nov 7, 2003, 7:38:56 PM11/7/03

to

Hi!

"Andrew Koenig" <a...@acm.org> wrote in message

news:FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

> > I'd be intersted if any other vector implemenations uses a growth factor

> > other than 2, and I'd also like to know whether VC7 uses 1.5 or 2 (since

I

> > don't have that compiler here).

>

> There is a technical reason to prefer 1.5 to 2 -- more specifically, to

> prefer values less than 1+sqrt(5)/2.

>

> Suppose you are using a first-fit memory allocator, and you're

progressively

> appending to a vector. Then each time you reallocate, you allocate new

> memory, copy the elements, then free the old memory. That leaves a gap,

and

> it would be nice to be able to use that memory eventually. If the vector

> grows too rapidly, it will always be too big for the available memory.

>

> It turns out that if the growth factor is >= (1+sqrt(5))/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <(1+sqrt(5))/2, the new memory will eventually fit. So 1.5 is small

enough to

> allow the memory to be recycled.

[Fixed the obvious but crucial typos in the quoted material]

This is a novel idea, and I understand the underlying theory.

However, according to my calculations, using growth factor

of 1.5 generates almost exactly twice as much copying than

using the growth factor 2 in the long run.

However, the difference in the amount of copying taking

place would allow a modification to the growth factor 2

algorithm which, after copying stuff from the old block to

the new block, would free the old block and allocate yet

another block the size of the new block, which will now

fit in the space vacated by the *old* block as well. This

algorithm would perform as many copies as the algorithm

that uses growth factor 1.5 (despite the fact that it does

a redundant round of copying to compact the free store)

so it would still be at least as good, but it would have an

additional performance benefit of being able to postpone

the redundant copying until the space actually becomes

a concern.

I've said it in another article, but again... there are more

factors involved than a simplistic model can handle:

- Constant allocation overhead in every block

- Populating the grown vector may pollute free store with

allocations that the straightforward calculation doesn't

take into account (typically in a rate that grows at the

same speed with the size of the vector).

- Attempts to reuse too large of a portion of the already

deallocated memory will render the algorithm useless

after the first application of this optimization, because

the algorithm *itself* will then have polluted the ideal

free store.

I don't know... somebody should probably make a more

rigorous study of this topic - if not for anything else, it is

an interesting question. Unfortunately I don't have time

for it myself right now. (Or rigor, for that matter :-) ).

My bottom line is that it's debatable whether the growth

factor 1.5 yields any benefit against 2 .

Cheers!

- Risto -

Nov 7, 2003, 7:53:40 PM11/7/03

to

Louis Lavery wrote:

> Andrew Koenig <a...@acm.org> wrote in message

> news:FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

<snip>> Andrew Koenig <a...@acm.org> wrote in message

> news:FUbqb.206398$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

>> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new

>> memory will always be too big for the hole that has been left sofar;

>> if it is <1+sqrt(5)/2, the new memory will eventually fit. So 1.5

>> is small enough to allow the memory to be recycled.

>

> Surely, if the growth factor is >= 2 the new memory will always

> be too big for the hole that has been left sofar; if it is < 2,

> the new memory will eventually fit.

>

> Presumably the reason for (1+sqrt(5))/2 is...

>

> Initial allocation is s.

> The first resize is k*s.

> The second resize is k*k*s, which'll fit the hole

> iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

>

> ...the hole can be recycled asap.

That doesn't work because it can't free the memory for the k*s

elements before allocating the memory for the k*k*s elements.

However, at the (n+2)th allocation, all the memory for the 1st

to nth allocations is available.

I tried this out with a spreadsheet. If k = sqrt(2) then a

"hole" of freed memory preceding the current allocation can be

used every 4 allocations (after some initial variability); if

k = 1.5 then every 5 allocations; if k = 1.618 then every 21

allocations; if k = (1+sqrt(5))/2 then never except for a few

initial successes due to rounding errors.

Nov 8, 2003, 6:50:10 AM11/8/03

to

> Surely, if the growth factor is >= 2 the new memory will always

> be too big for the hole that has been left sofar; if it is < 2,

> the new memory will eventually fit.

> be too big for the hole that has been left sofar; if it is < 2,

> the new memory will eventually fit.

Nope. The problem is that the new memory has to be allocated before the old

memory is deallocated, which means that even if the hole is big enough after

deallocation, it won't be before deallocation.

Here's an example. Suppose, optimistically, that there is no overhead

associated with memory allocation. Suppose also that you start with a

1-element vector and grow it by a factor of two each time.

Then you start out with 1 element. The first time you want to grow, you

must allocate 2 elements, then free the 1, leaving a 1-element hole followed

by 2 elements. Next time, you allocate 4, then free 2, leaving a 3-element

hole followed by 4 elements. In general, after each allocation, you will

have an (n-1)-element hole followed by n elements.

So the question about whether the hole is ever large enough to reuse is not

whether (n-1)>=n, which is almost true, but whether (n-1)>=2n, which isn't

close to true.

Nov 8, 2003, 6:55:32 AM11/8/03

to

On Thu, 06 Nov 2003 19:56:03 -0500, Louis Lavery wrote:

[snip]...

> Presumably the reason for (1+sqrt(5))/2 is...

>

> Initial allocation is s.

> The first resize is k*s.

> The second resize is k*k*s, which'll fit the hole

> iff k*k*s <= k*s+s I.e. iff k <= (1+sqrt(5))/2

>

> ...the hole can be recycled asap.

>

If you take the upper bounds of the product, then every 6th allocation

starting form 1 as the initial size would recycle the previous memory

usinf a first fit allocation starategy, but most good allocators use some

sort of hybrid of all the allocation strategies, like dmalloc, which is

pretty effective!!!, and even I've written allocator policy, which is not

that straight forward. I guess that if the current vector is not the only

vector, or even the only container in the current program that's using the

heap, then the factor of 2 should do fine. There is no concrete proof I

guess to choose 1.5 over 2 apart form the fact that if (1). vector is the only

container around, and (2). the allocation starategy is first fit, then the

performance will get better. But the probability of 1 and 2 happening at

the same time is very small, so 2 seems to be fine, and so does 1.5 to me.

(Others might disagree). dmalloc and the default malloc on linux is pretty

efficient, and I guess it is VMM aware, so no matter how much you allocate

without reserve, the memory usage is only what is being used (capacity),

and not size. On the other hand dmalloc uses mmap, which is again a

directly VMM mapped memory access, so the virtual memory manager can

handle that. However, if I use the same driver program with my pool

allocator, then the memory usage shoots up by at least 50%. Not that the

allocator is inefficient, but the allocation starategy is such that this

kind of memory usage is not supported. What I use is a compination of

first fit, next fit, and previous fit algorithms + checks on what the size

of the last deallocated block was, depending on the current state of the

allocator, 1.5 will perform better on such an allocation scheme given that

the grow size of the pool is suitably adjusted. Also, after some threshold

has been reached, then this will tend to calling malloc for huge sizes.

> It could, by storing its previous size, grow fibonaccily.

That is one good solution!!!, but memory usage would be again a problem of

concern.

Regards,

-Dhruv.

Nov 8, 2003, 6:58:37 AM11/8/03

to

In article <3faa855e$0$252$ed9e...@reading.news.pipex.net>, Stephen

Howe <NOSPAM...@dial.pipex.com> writes

> > Also, where did the sqrt(5) come from?

>

>Andrew Koenig means Phi, the Golden Ratio, the ratio of 2 successive terms

>that the Fibonacchi series converges to 1,2,3,5,8,13,21,34,55,...

Howe <NOSPAM...@dial.pipex.com> writes

> > Also, where did the sqrt(5) come from?

>

>Andrew Koenig means Phi, the Golden Ratio, the ratio of 2 successive terms

>that the Fibonacchi series converges to 1,2,3,5,8,13,21,34,55,...

Which leads me to wonder if using a Fibonacci series growth would

satisfy the amortised constant time requirement of the C++ Standard for

vector.

--

Francis Glassborow ACCU

If you are not using up-to-date virus protection you should not be reading

this. Viruses do not just hurt the infected but the whole community.

Nov 8, 2003, 8:20:49 AM11/8/03

to

Matt Seitz <meta...@sbcglobal.net> wrote in message news:<lHhqb.4998$Np2...@newssvr25.news.prodigy.com>...

> Vahan Margaryan wrote:

> > VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> > probably the most common (and well-known) factor.

>

> It's hard for me to see this as "reducing portability". There is nothing in the

> Standard that requires or even implies that std::vectors should reallocate in

> multiples of 2. If client code is relying on std::vector growing by multiples

> of 2, then I would say that the client code is reducing portability, not VC.

>

> Vahan Margaryan wrote:

> > VC7 uses 1.5. I wonder why. This reduces portability, since 2 is

> > probably the most common (and well-known) factor.

>

> Standard that requires or even implies that std::vectors should reallocate in

> multiples of 2. If client code is relying on std::vector growing by multiples

> of 2, then I would say that the client code is reducing portability, not VC.

>

In my code, nothing explicitly relies on the growing factor, it's just

ordinary vector manipulation. And neither does the performance

precalculation rely on it. But if and when I take the code to a

different platform and run benchmarks and some fail, I don't want it

to be because of a change of vector's factor. If something can be

equivalent across platforms, then I'd prefer it to be such, so that we

could concentrate porting efforts on real issues.

And it's a flaw of the Standard IMO that it doesn't mandate the

growing factor.

- Vahan

Nov 8, 2003, 8:28:49 AM11/8/03

to

"Vahan Margaryan" <mar...@yahoo.com> wrote in message

news:44d2ad1a.03110...@posting.google.com...> Francis Glassborow <fra...@robinton.demon.co.uk> wrote in message

news:<XlJkfEFoeYq$Ew...@robinton.demon.co.uk>...

> > I fail to see how an implementation detail such as the growth factor can

> > possibly effect portability.

>

> My definition of portability (admittedly not necessarily universally

> accepted) is the inverse of the effort it takes to take the code to

> another platform and make it work. This includes the performance: if

> the code compiles on a different platform but performs noticeably

> worse, we usually don't consider porting complete.

I basically agree. I've long maintained that portability is a measure

of the cost of moving code vs. rewriting it. So have you *noticed* that

1.5 is unacceptably worse than 2 for a growth factor?

> > Yes, but that is not what we mean by portability. There are many aspects

> > of performance that change with new releases of compilers. Actually the

> > amount and types of available memory influences performance in a far

> > more dramatic way. The existence of large cache memory actually means

> > that vector<T> will often out perform list<T> for insertions even though

> > list<T> is theoretically much superior when uniform memory is used.

>

> I agree that there are many factors beyond our control that affect

> portability of performance of our code. File system operations may

> have different complexities under different OS's, compilers are

> different, etc. In some casese those things force rewrites (as in the

> case you've mentioned). That's the inevitable evil. However, in this

> case:

>

> a) This is something under our control, so why introduce an additional

> problem? I for one was unpleasantly surprised when I found out that

> the factor changes from platform to platform.

Maybe the problem also provides one or more *solutions*. Again, was your

unpleasant surprise the result of a performance measurement or just an

idle conjecture?

> Why not use a common default and use an extra integer template

> parameter that specifies the reallocation factor (in percents, for

> instance)?

The C++ Standard doesn't let you add template parameters.

> b) Containers and algorithms are very important determinants of

> performance, if not the most important ones. I don't really care if

> mkdir works slower or faster than CreateDirectory, that won't affect

> the performance of my program. But I would like to be certain about

> the characteristics of the containers, because the performance of

> programs crucially depends on them.

And containers have tightly constrained *complexity* requirements.

Implementation details can often yield linear factors of two or more,

which swamp any difference between 1.5 and 2 growth rates.

> Then of course I can write my own containers and not use STL. Yet, it

> has been serving me well mostly, and I'd like to think of it as a

> serious and usable library.

It is. Do you have any performance data that indicates you'd be better

off writing your own?

> Some portability (my definition) issues that I've encountered in STL:

>

> 1. The std::list::size/splice performance. One has to be careful not

> to use std::list's size() thoughtlessly, or write a wrapper, or

> something. IOW, perform additional effort.

Or measure to see if the difference amounts to a hill of beans before

you go to all that work.

> 2. Hash tables. Unlike std::set, which, in my experience, behaves

> pretty uniformly, hash performance differs significanly. There are

> many implementation strategies, policies involved. I prefer to drag a

> single implementation from platform to platform, rather than rely on

> the platform-specific implementation. Btw, last I checked, the

> proposal for hash-tables doesn't eliminate some of the choices (but I

> may be outdated on this), and that's, in my view, a defect.

Then submit a proposal to fix it.

> > The innovative feature of the C++ Standard Library was the provision of

> > certain performance guarantees.

>

> What I suggest is that perhaps the guarantees should be even stricter.

Be interesting to see how you'd write guarantees of linear performance

factors.

> > >It's hard to tell which factor is best in the absolute sense, so I'd

> > >prefer that to be a parameter. Just changing a hard-coded number

> > >doesn't seem a good solution to me.

> >

> > Possibly, but hard coded values do allow certain optimisations and in

> > another post Andy Koenig points out the a growth factor of 1.5 allows a

> > memory usage optimisation that is not available to systems using a

> > factor of 2.0

>

> It's not the specific factor that concerns me, it's my unawareness of

> the factor when I move to another platform.

And 99 per cent of the factors that change between platforms are unimportant.

It's only when you *measure* performance and find that it fails to meet

objective specifications that you should begin to care. You'll then typically

find that the things you have to tweak are nowhere near where you first to

look.

P.J. Plauger

Dinkumware, Ltd.

http://www.dinkumware.com

Nov 8, 2003, 8:54:47 AM11/8/03

to

"Andrew Koenig" <a...@acm.org> wrote:

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory

> will always be too big for the hole that has been left sofar; if it is

> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to

> allow the memory to be recycled.

> allow the memory to be recycled.

[With a typo correction of the factor being (1+sqrt(5))/2.]

Yes, but shouldn't we ask also the guy providing the allocator, what

kind of allocating and pooling strategy he uses? And does the scheme

remain optimal, if we do other allocations or grow two vectors, for

instance?

I'm not arguing that 1.5 is wrong number, but I'm pondering whether

there are any right numbers.

--

Jouko

Nov 8, 2003, 8:55:17 AM11/8/03