Summary
I have just developed a growable array class as part of the OOTL, which outperforms std::vector on calls to push_back() by a factor of 2.5 on my installation of GCC.
Advertisement
The std::vector class from the STL is an example of a very useful data type: the growable array. The problem with most implementations of std::vector when used as indexable stacks is that when they reach the reserved memory capacity, a new block is allocated, and all of the data is copied. Or something like that. Correct me if I've made mistakes, I promise not to bite.
An alternate implementation is to create a reversed linked list of buffers which have exponentially increasing size. This allows you to grow the array without reallocation, and can save you an enormous amount of time. The results from my tests, which you can download at OOTL.org, using GCC 3.4 are as follows:
I found that iteration over the list was just as fast as for a std::vector, by using the for_each member function (the growable_array is a model of the Iterable concept).
This implementation also retains the characteristics of average O(1) individual element access. Half of the elements are in the first list node, one quarter are in the next, and so on. In the worst case -- which is accessing the first element ironically enough -- the complexity is O(Log N). That entails a traversal of the linked list of buffers.
Anyway the code is public domain, so have fun with it!
> >> This implementation also retains the characteristics of > average O(1) individual element access. > > Mode average maybe, but not mean.
No it is in fact the mean. Ignoring constants, half of all element take one operation to access, one quarter of all items take two operations, one eigth take three operations, etc.
n + n/2 + n/4 + n/8 + ... + n/2^i ------------------------------ i
converges at 2. Which is O(1).
> If C++ new[] = malloc, would a new[] equivalent of > realloc() solve the vector performance problem?
The problem with using realloc is that it moves the binary representations of the object, and not all objects support that (e.g. objects which contain pointers).
> Why isn't there a realloc new[]?
Good question. May be because it wouldn't be type-safe, but that hasn't stopped them from putting in other non-type-safe features (like placement new).
I think what you recreated is the equivalent of a std::deque. What differences, if any, does your implementation offer from a deque. I would be interested in seeing a performance test between your implementation and std::deque. As you know, the std::vector is implemented as a contiguous array in order to satisfy the standard, so besting it by ignoring that rule is almost unfair :-) Regardless, I think a deque more closely models what you describe and look forward to seeing those results.
> I think what you recreated is the equivalent of a > std::deque. What differences, if any, does your > implementation offer from a deque.
It's really a stack, there is no front end insertion at all.
> I would be interested > in seeing a performance test between your implementation > and std::deque.
See below:
> As you know, the std::vector is > implemented as a contiguous array in order to satisfy the > standard,
I was not aware that a std::vector had to be implemented in contiguous memory according to the standard. That seems counter to much of the standard which seems designed specifically to support non-contiguous memory models, but it is too late for me to go and look it up right now.
> so besting it by ignoring that rule is almost > unfair :-) Regardless, I think a deque more closely > models what you describe and look forward to seeing those > results.
In the below benchmarks v is a std::vector and d is a std::deque. I am using GCC 3.4 and STLPort 4.6.2 on windows.
So the STLPort 4.6.2 deque implementation, apart from providing front-end insertion, provides slightly slower iteration and back-end insertion (<10%), but much much slower indexing (over 5x).
Yes a std::vector has to be contigous. Much like the c_str method in std::string this is for c interop. Allowing you to write stuff like &(v[0]) to get the start of the array to pass to a c function. I believe this is mentioned in Stroustrup's book.
> So vector uses the amortization trick on "push_back()" > (assumming it doubles each time), while you use it on > "operator[]". Neat trick.
Thanks. I want to point out though that the worst case for an indexing operation in growable array is O(Log(N)) whereas the worst case for a push_back operation is O(N).
> Is there a situation/algorithm appends elements as many > times (or more times) as it indexes into an array?
One very common example is string concatenation.
By far, the most common scenario for indexing is iterating over each element in sequence, which is handled just as fast as a vector by the growable array. So the question would be more meaningful if you added the clause: "and out of sequence" to your question.
Wow, those speed results for deque are really painful! Did that include optimizations turned on? If so, Ouch!
The standard specifies that &v[0] for a vector must give a contiguous array that can be used by a function expecting a C-style array. While theoretically that doesn't necessarily require a contiguous implementation, practically it does.
> Yes a std::vector has to be contigous. Much like the c_str > method in std::string this is for c interop. Allowing you > to write stuff like &(v[0]) to get the start of the array > to pass to a c function. I believe this is mentioned in > Stroustrup's book.
That is ture for std::valarray, but there is no mention of that requirement for std::vector in either TCPL or the Standard. Here is, what I believe to be, the relevant section of the standard:
23.2.4 Template class vector ... A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in 23.1) and of a sequence, including most of the optional sequence requirements (23.1.1). The exceptions are the push_front and pop_front member functions, which are not provided. Descriptions are provided here only for operations on vector that are not described in one of these tables or for operations where there is additional semantic information. ...
There are no mentions here of special requirements on operator[] or on internal memory
Code using &vector[index] is accepted happily by any compiler. The problem is that most vectors use pointers as their iterators, so the compiler can't recognize the incorrect usage of the sequence. This idiom you describe is most likely widespread despite being technically incorrect.
Ironically this is a case where the tail wags the dog: if someone were to make the growable_array conformant to the STL requirements for std::vector, it would break so much preexisting code as it to render it unusable.
> Wow, those speed results for deque are really painful! > Did that include optimizations turned on?
Yes.
> If so, Ouch!
To be fair that is just the comparison against the STLPort implementation. I've posted the code in the public domain for anyone to play with at http://www.ootl.org
Deque implementations vary widely from what I can see (at least between Visual C++ and GCC STLPort). However, the reverse exponential list approach I propose, may very well be completely novel, but such a boisterous claim is hard to verify. I just don't have the patience to pour through journals. Perhaps I should just make the claim, and let someone prove me wrong. ;-)
> The standard specifies that &v[0] for a vector must give a > contiguous array that can be used by a function expecting > a C-style array.
Where in the standard? As I mentioned I've searched and I can't find it.
> While theoretically that doesn't > necessarily require a contiguous implementation, > practically it does.
If the requirement you mention is true, then this conclusion is inescapable.
> > The standard specifies that &v[0] for a vector must give > a > > contiguous array that can be used by a function > expecting > > a C-style array. > > Where in the standard? As I mentioned I've searched and I > can't find it.
I learned something about the standard today (from this discussion), so the draft response I was working on last night was incorrect.
However, I recognize that while random access in this Growable Array is O(1), it does steps similar to std::vector's at() method (which is O(1), but expected to be slower than operator[] O(1)). I'm kind of curious how this container compares to std::vector's random access methods.
Flat View: This topic has 18 replies
on 2 pages
[
12
|
»
]
Previous Topic
