Re: Pointer To A Vector Elements While Still Adding

From: John Carson (jcarson_n_o_sp_am__at_netspace.net.au)
Date: 03/27/05 

Date: Sun, 27 Mar 2005 22:09:20 +1000

"Ioannis Vranos" <ivr@remove.this.grad.com> wrote in message
news:1111913379.341766@athnrd02
> John Carson wrote:
>
>
> Your code tweaked and improved:

By making start and finish of type clock_t, you make this line:

> cout << (finish - start)/CLOCKS_PER_SEC << endl;

perform integer division, so you get an integer result. This is anything but
an improvement. Cast one of those terms to a double in order to get a
non-zero result for vector.

>
> C:\c>temp
> List elapsed time is 2
> Vector elapsed time is 0
>
> C:\c>
>
>
> Of course if I had reserved enough space for vector before, they
> would have the same performance.

What? Your figures show vector with superior performance (infinitely
superior, actually, but I won't claim that) and you think that reserving
enough space for the vector would even things up?

> Check the table in 17.1.2 on page 464 of TC++PL3.
>
>>
>> Vectors have an advantage with large sizes.
>
> Vectors have no additional time-cost advantage than lists for back
> operations, list has O(1) while vector has O(1)+ (the + is when
> reallocations take place). You have O(1) for back operations with
> vector while its size() is smaller its capacity() (which can be
> adjusted with reserve()).

You seem to be under the impression that O properties say all that is
relevant. All O results tell you is how time varies with n. They tell you
nothing about the base time when n==1. Two operations can both be O(1) yet
one operation can take a million times as long as the other.

As I understand it, when you add an element to the end of a list, memory is
allocated for that final element with a call to new. Calls to new are
expensive.

When you add an element to the end of a vector, there is no call to new if
there is sufficient capacity. This makes the vector operation quicker than
the list operation. If there is insufficient capacity in the vector, then
new memory is allocated and all elements need to be copied over from the old
memory to the new. This makes the vector operation slower than the list
operation.

You seem to be misunderstanding the meaning of O(1)+. This does not mean
"more than O(1)". It means, to quote Stroustrup, that "occasionally a
significant extra cost is incurred" --- extra relative to what normally
happens, not extra relative to what is required for O(1) performance.

To further explain: capacity is added to vectors by multiplying pre-existing
capacity by some constant factor. This means that the number of calls to new
diminishes relative to n as n increases, e.g., if you start with a capacity
of 1 and double each time, then you need 3 calls to get 8 elements, and 6
calls to get 64 elements. Thus with 8 elements, each element requires 3/8 of
a call to new, whereas with 64 elements each element requires 6/64 of a call
to new. With 1 million elements, each element requires roughly 1/50,000 of a
call to new. Thus this aspect of insertion is *less* than O(1). (This
argument assumes that calls to new cost the same regardless of the amount of
memory allocated which probably isn't true, especially when the vector gets
large; this qualification, however, doesn't seem sufficiently important to
overturn the conclusion in most cases.) The total amount of copying from old
memory to new is proportionate to n, so this aspect is O(1).

On two computers (a slow Pentium II and a fast laptop), I get a consistent
result that adding to the back of list takes around the same amount of time
regardless of whether it is 1 million elements to a single list or 100
elements to 10,000 lists.

With a vector, by contrast, adding 1 million elements to a single vector
takes about half the time it takes to add 100 elements to 10,000 vectors.
This is consistent with my "less than O(1)" argument above.

When the number of elements gets larger, the story becomes more complicated
(the peculiarities of the memory manager come into play and stack memory
becomes an issue, given that I declared the arrays on the stack, so it is
better to allocate them statically). Neither container seems to have O(1)
performance. However, it remains the case that

1. the vector is faster than the list.
2. the vector is 2-6 times faster when using a single large container than
when using multiple small containers for the same total capacity.

Of course, vector memory must be contiguous, so vectors may have problems if
memory becomes fragmented. 

-- 
John Carson

Relevant Pages

  • Re: Pointer To A Vector Elements While Still Adding
    ... that deque has equal or better Big-O performance in equivalent operations, ... > there is sufficient capacity. ... > memory to the new. ... > elements to 10,000 lists. ...
    (comp.lang.cpp)
  • Re: SImple question about structure and linked list
    ... let's allocate a big chunk of memory. ... strings, lists, vectors, and in fact any other sort of container you ... but instead gets evaluated by the compiler at compile time. ...
    (comp.lang.cpp)
  • Re: Process arbitrary #lists (continued)
    ... Subject: Process arbitrary #lists (continued) ... allocate ) ... so simple to manipulate the indexable data structure with averages, ... Probably not, but why bother, todays CPU comes with HUMONGUOUS memory ...
    (comp.lang.pl1)
  • Re: Linked list allocation
    ... and delete_item frees that memory. ... An alternative I thought of was that add_item should allocate a block, ... for inserting and deleting nodes from linked lists. ...
    (comp.lang.c)
  • Re: Breaking numbers
    ... >> one would exceed the capacity of a 32-bit machine to store the ... >> resulting list in memory somewhere before ... > This is only if you store the results as a flat lists. ...
    (comp.lang.lisp)