vector growth factor of 1.5

2342 просмотра
Перейти к первому непрочитанному сообщению

Scott Meyers

не прочитано,
5 нояб. 2003 г., 05:03:3905.11.2003
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


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

P.J. Plauger

не прочитано,
5 нояб. 2003 г., 15:19:5405.11.2003
"Scott Meyers" <Use...@aristeia.com> wrote in message
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

Ben Hutchings

не прочитано,
5 нояб. 2003 г., 15:30:5005.11.2003
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

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.

Glenn Downing

не прочитано,
5 нояб. 2003 г., 15:32:3005.11.2003
Not directly related, I presume, but the Java library uses a factor of 1.5
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/

Daniel Spangenberg

не прочитано,
5 нояб. 2003 г., 15:32:5105.11.2003

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

Hendrik Schober

не прочитано,
5 нояб. 2003 г., 17:12:3605.11.2003
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).

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

Andrew Koenig

не прочитано,
5 нояб. 2003 г., 17:26:1005.11.2003
> 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.

Vahan Margaryan

не прочитано,
5 нояб. 2003 г., 17:29:1605.11.2003
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.

- Vahan

John Potter

не прочитано,
6 нояб. 2003 г., 05:33:4906.11.2003
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

Andrew Koenig

не прочитано,
6 нояб. 2003 г., 08:42:3606.11.2003
> There is a technical reason to prefer 1.5 to 2 -- more specifically, to
> prefer values less than 1+sqrt(5)/2.

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

Scott Meyers

не прочитано,
6 нояб. 2003 г., 09:09:1306.11.2003
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.

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

Matt Seitz

не прочитано,
6 нояб. 2003 г., 09:18:1706.11.2003
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.

Grzegorz Sakrejda

не прочитано,
6 нояб. 2003 г., 09:19:3106.11.2003
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

Francis Glassborow

не прочитано,
6 нояб. 2003 г., 09:32:1306.11.2003
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.

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.

Daniel Spangenberg

не прочитано,
6 нояб. 2003 г., 11:43:3306.11.2003

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

Siemel Naran

не прочитано,
6 нояб. 2003 г., 11:49:0606.11.2003
"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

Siemel Naran

не прочитано,
6 нояб. 2003 г., 11:54:3206.11.2003
"Vahan Margaryan" <mar...@yahoo.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

Christophe Lephay

не прочитано,
6 нояб. 2003 г., 19:45:0806.11.2003
Vahan Margaryan wrote:
> 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

Ingolf Steinbach

не прочитано,
6 нояб. 2003 г., 19:48:4906.11.2003
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

Raoul Gough

не прочитано,
6 нояб. 2003 г., 19:52:5306.11.2003
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)

Louis Lavery

не прочитано,
6 нояб. 2003 г., 19:56:0306.11.2003

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.

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.

MJ

не прочитано,
6 нояб. 2003 г., 20:00:2406.11.2003
"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.

I calculated 1+sqrt(5)/2 as 2.118
Did you mean (1+sqrt(5))/2 ?
(That's about 1.618)


Michael

Howard Hinnant

не прочитано,
7 нояб. 2003 г., 09:17:4607.11.2003
In article
<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

Thomas Richter

не прочитано,
7 нояб. 2003 г., 09:18:0707.11.2003
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

Christophe Lephay

не прочитано,
7 нояб. 2003 г., 09:23:3407.11.2003
Siemel Naran wrote:
> 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

Stephen Howe

не прочитано,
7 нояб. 2003 г., 09:24:3907.11.2003
> 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

Francis Glassborow

не прочитано,
7 нояб. 2003 г., 09:30:4507.11.2003
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?

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.

John Potter

не прочитано,
7 нояб. 2003 г., 09:33:4507.11.2003
On 6 Nov 2003 11:49:06 -0500, "Siemel Naran"
<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

John Potter

не прочитано,
7 нояб. 2003 г., 16:54:5307.11.2003
On 6 Nov 2003 19:56:03 -0500, "Louis Lavery" <Lo...@devilsChimney.co.uk>
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

Daniel Spangenberg

не прочитано,
7 нояб. 2003 г., 17:05:2407.11.2003

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

Louis Lavery

не прочитано,
7 нояб. 2003 г., 17:06:5007.11.2003

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).

Risto Lankinen

не прочитано,
7 нояб. 2003 г., 17:07:1207.11.2003

"Siemel Naran" <Sieme...@REMOVE.att.net> wrote in message
news:svnqb.207208$0v4.16...@bgtnsc04-news.ops.worldnet.att.net...

> "Andrew Koenig" <a...@acm.org> wrote in message news:FUbqb.206398
>
> >
> > There is a technical reason to prefer 1.5 to 2 -- more specifically, to
> > 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 -

Siemel Naran

не прочитано,
7 нояб. 2003 г., 19:20:5407.11.2003
"Louis Lavery" <Lo...@devilsChimney.co.uk> wrote in message
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

Maciej Sobczak

не прочитано,
7 нояб. 2003 г., 19:25:2507.11.2003
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/

Vahan Margaryan

не прочитано,
7 нояб. 2003 г., 19:32:2507.11.2003
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.


> 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

Risto Lankinen

не прочитано,
7 нояб. 2003 г., 19:38:5607.11.2003
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 -

Ben Hutchings

не прочитано,
7 нояб. 2003 г., 19:53:4007.11.2003
Louis Lavery wrote:
> 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.
<snip>

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.

Andrew Koenig

не прочитано,
8 нояб. 2003 г., 06:50:1008.11.2003
> 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.

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.

Dhruv

не прочитано,
8 нояб. 2003 г., 06:55:3208.11.2003
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.

Francis Glassborow

не прочитано,
8 нояб. 2003 г., 06:58:3708.11.2003
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,...

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.

Vahan Margaryan

не прочитано,
8 нояб. 2003 г., 08:20:4908.11.2003
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.
>

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

P.J. Plauger

не прочитано,
8 нояб. 2003 г., 08:28:4908.11.2003
"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

Jouko Koski

не прочитано,
8 нояб. 2003 г., 08:54:4708.11.2003
"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
> <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to
> 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

Siemel Naran

не прочитано,
8 нояб. 2003 г., 08:55:1708.11.2003
"Christophe Lephay" <christop...@wanadoo.fr> wrote in message
> Siemel Naran wrote:

> > 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)

I meant in terms of avoiding overflow. Multiplying by 3 first might put us
over the maximum. Converting to double for multiplying by 1.5 could
introduce roundoff error. I like Francis' solution in the other post.

--
+++++++++++
Siemel Naran

Andrea Griffini

не прочитано,
8 нояб. 2003 г., 08:56:0508.11.2003
On 7 Nov 2003 19:32:25 -0500, mar...@yahoo.com (Vahan Margaryan)
wrote:

>Why not use a common default and use an extra integer template
>parameter that specifies the reallocation factor (in percents, for
>instance)?

I've seen *big* differences between implementations even
at other levels so if you really wanna write efficient
portable code I think the only solution is to actually
write it and analyze it on the platforms you want to
support. Sometimes the best solution for a compiler is
the worst for another; if you need to squeeze the CPU
in both I can't see anything portable you can do except
the good old #ifdef.
Even on the same compiler and on compatible hardware the
best methods may vary with the exact processor and
architecture, so I've even seen performance test about
different strategies done at runtime.
The difference may be *huge* ... I remember once I
timed a 1000% difference in execution speed by just
changing array size (with implications NOT on the
number of elements being used, but just their address).

Also I've no computer science university level education,
but what does it mean saying O(n) considering that n has
an upper limit ?

Andrea

John Potter

не прочитано,
9 нояб. 2003 г., 06:24:1109.11.2003
On 8 Nov 2003 06:58:37 -0500, Francis Glassborow
<fra...@robinton.demon.co.uk> wrote:

> 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,...

> Which leads me to wonder if using a Fibonacci series growth would
> satisfy the amortised constant time requirement of the C++ Standard for
> vector.

Yes. The number of copies performed to reach any size is less than 4 *
size. Linear as required to give amortized constant time.

John

Andrew Koenig

не прочитано,
9 нояб. 2003 г., 06:26:5409.11.2003
> Which leads me to wonder if using a Fibonacci series growth would
> satisfy the amortised constant time requirement of the C++ Standard for
> vector.

Yes -- exponential growth will satisfy the anortized constant time
requirement
regardless of the exponent, and Fibonacci growth is exponential growth with
an exponent of (1+sqrt(5))/2, at least asymptotically.

R.F. Pels

не прочитано,
9 нояб. 2003 г., 06:30:1609.11.2003
Andrea Griffini wrote:

> Also I've no computer science university level education,
> but what does it mean saying O(n) considering that n has
> an upper limit ?

O is a measure of complexity and expresses the cost of performing a certain
operation, for example in terms of time or resource usage. O(n) means that
the cost of an operation is linear with the number of times you execute the
operation, meaning for example that if:

n == 1, executing the operation has a total cost of 1
n == 2, executing the operation has a total cost of 2
n == 3, executing the operation has a total cost of 3

etcetera, while O(n^2) means:

n == 1, executing the operation has a total cost of 1
n == 2, executing the operation has a total cost of 4
n == 3, executing the operation has a total cost of 9

etcetera.

--
Ruurd
.o.
..o
ooo

R.F. Pels

не прочитано,
9 нояб. 2003 г., 06:31:0109.11.2003
Vahan Margaryan wrote:

> And it's a flaw of the Standard IMO that it doesn't mandate the
> growing factor.

It does not do that because mandating the growing factor might have
different consequences on one platform than on another platform. Maybe not
in this case, but certainly in other cases. Plus the standard deals with
the language and its interpretation, not how compiler makers implement it.

--
Ruurd
.o.
..o
ooo

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

R.F. Pels

не прочитано,
9 нояб. 2003 г., 06:31:5209.11.2003
Andrew Koenig wrote:

> 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.

Meaning that ~1.5 is optimal if there is no in-between allocation of some
other sort, right? Tell me please, did someone benchmark this in a 'real
world' situation and what were the conclusions?

--
Ruurd
.o.
..o
ooo

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

Joshua Lehrer

не прочитано,
9 нояб. 2003 г., 06:42:5909.11.2003
Andrea Griffini <agr...@tin.it> wrote in message news:<km4pqvgo6n3afnq2p...@4ax.com>...

> Also I've no computer science university level education,
> but what does it mean saying O(n) considering that n has
> an upper limit ?
>


That is an interesting question. Sorting algorithms are, generally
speaking, O(NLogN). LogN on modern day machines is 32 or 64, so the
algorithm is really O(64*N), or just O(N). In other words, a linear
algorithm can easily be worse than an NLogN algorithm as the constants
in the linear algorithm begin to creep up, and the constants in the
NLogN algorithm creep down.

joshua lehrer
factset research systems
NYSE:FDS

Daniel James

не прочитано,
9 нояб. 2003 г., 09:10:3609.11.2003
"Andrew Koenig" <a...@acm.org> wrote in message
> 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.

But doesn't this mean that sometimes you're wasting more memory,
because the hole has to be larger, so that it can contain the next
allocation?

With a factor of 1.5, before an allocation which reuses the hole, the
hole has to be more than 1.5 times the size of the currently allocated
memory. But if you're using a factor of 2 the hole will be about the
same size as the currently allocated memory.

Daniel

Ed Avis

не прочитано,
9 нояб. 2003 г., 17:35:0209.11.2003