Possible enhancement to vector?

Possible enhancement to vector?

Post by Be » Sun, 27 Jul 2003 19:53:18



Recently my friends and I are thinking about the std::vector class.
We feel that its object moving algorithm is not optimized.

when it comes to re-size the buffer, Here are the things it will do:
1. allocate a big enough buffer (no problem)
2. copy some of the old objects into the new buffer. (problem starts
here)
3. insert new value into the new buffer
4. copy the rest of the old objects into the new buffer.
5. destroy the old objects by calling dtor.
6. deallocate the old buffer. (no problem).

The problem we noted is that the copy+dtor is sometimes expensive and
not necessary.
Suppose I have a string class, which internally holds a pointer to a
char array.
When asked to copy, I'll need to allocate new storage, copy the entire
string.
But if I know it's just a move, I can simply copy the pointer of the
buffer. WAY faster!
Also, we believe that for many types, a memcpy would be sufficient for
the object move purpose.

Now, the question is: why doesn't stl delegate the object move to the
allocator object so that the programmer can customize the allocator
accordingly to achieve the optimal performance? It sounds like an
obvious thing to do.

I actually revised std::vector with the extended allocator concept.
and it worked. It does not require any language change or hacking, all
it does is to delegate the move to the extended allocator and let the
programmer do the optimal "move" instead of doing it all by itself.
Whether "memcpy" or any other user-defined move is all up to the
programmer.

I'm sure many people would have been wondering about the same thing,
but what puzzled me is that it seems possible to make vector both
generic and optimizable. Why vector is not doing this though?

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

 
 
 

Possible enhancement to vector?

Post by Dhru » Mon, 28 Jul 2003 19:31:45


 > Recently my friends and I are thinking about the std::vector class.
 > We feel that its object moving algorithm is not optimized.
 >

Have you heard of the moveable concept being proposed for C++. There is an
official report on this, and one by Andrei (Yes, he wrote Modern C++
design). What you are hunting at is strongly thi. I do not have the links
handy with me now. Someone will probably point them to you. They will make
a good read. And about using memcpy, it should be memmove, because
iterators are allowed to overlap (at least they were some time ago). See
some good STL implementation for the copy algorithm, or download this
file, and see the file algorithm.hpp. It should be correct FWIW.

http://www.geocities.com/dhruvbird/nstl/nstl0.2.zip

Regards,
-Dhruv.

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

 
 
 

Possible enhancement to vector?

Post by Dhru » Mon, 28 Jul 2003 19:32:36


[snip]......

 > Now, the question is: why doesn't stl delegate the object move to the
 > allocator object so that the programmer can customize the allocator
 > accordingly to achieve the optimal performance? It sounds like an
 > obvious thing to do.
 >
 > I actually revised std::vector with the extended allocator concept.
 > and it worked. It does not require any language change or hacking, all
 > it does is to delegate the move to the extended allocator and let the
 > programmer do the optimal "move" instead of doing it all by itself.
 > Whether "memcpy" or any other user-defined move is all up to the
 > programmer.
 >
 > I'm sure many people would have been wondering about the same thing,
 > but what puzzled me is that it seems possible to make vector both
 > generic and optimizable. Why vector is not doing this though?

The allocator is required to encapsulate the memory model, and not be
directly involved with the obejct copying. How would you implement an
allocator to move built-in types and userdefined types differently. Yes,
you could do a dispatch, but for types such as string, where a simple
memcpy would do. You would have to have some sort of typedef withing the
container, and use class_traits::moveable or something. That would be a
permmanent solution. I feel, but with the moveable concept being discussed
by people like Howard Hinnant, and the likes, this I feel is uncalled for.

Regards,
-Dhruv.

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

 
 
 

Possible enhancement to vector?

Post by Francis Glassboro » Tue, 29 Jul 2003 01:02:22




Quote:>Recently my friends and I are thinking about the std::vector class. We
>feel that its object moving algorithm is not optimized.

>when it comes to re-size the buffer, Here are the things it will do: 1.
>allocate a big enough buffer (no problem) 2. copy some of the old
>objects into the new buffer. (problem starts
>here)
>3. insert new value into the new buffer
>4. copy the rest of the old objects into the new buffer.
>5. destroy the old objects by calling dtor.
>6. deallocate the old buffer. (no problem).

>The problem we noted is that the copy+dtor is sometimes expensive and
>not necessary.

I guess library implementors could provide std::vector<std::string> as a

specialisation. However the problem is more extensive which is why a
group of us is actively looking at a core language change to support the

concept of move semantics for ctors and assignment operators.

--
ACCU Spring Conference 2003 April 2-5
The Conference you should not have missed
ACCU Spring Conference 2004 Late April
Francis Glassborow      ACCU

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

 
 
 

Possible enhancement to vector?

Post by Maciej Sobcza » Tue, 29 Jul 2003 02:18:33


Hi,


> The allocator is required to encapsulate the memory model, and not be
> directly involved with the obejct copying.

But they are close to each other, especially taking into account that
what is needed is *moving*, not copying.

I think that having "move" delegated to allocator is not a bad idea.
We would alternatively have a separate component to manage copy and move
(yes, breaking containers into policies), but this would make too much
havoc in the library.

Quote:> You would have to have some sort of typedef

Not necessarily.
The generic "move" in the allocator would be implemented in terms of
plain-vanilla copy followed by destruction of the original object. This
would work for primitive types and would not break the way containers
work now. The last time I've seen the internals of vector it was exactly
like that: copy followed by destruction. Why not make it a single,
delegated operation?

We would specialize allocator<> for types that would benefit from
special treatment. Standard library types (including std::string) would
have specializations already provided.

I like the idea and I am open to further discussion.

--
Maciej Sobczak
http://www.maciejsobczak.com/

Distributed programming lib for C, C++, Python & Tcl:
http://www.maciejsobczak.com/prog/yami/

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

 
 
 

Possible enhancement to vector?

Post by Ed Avi » Tue, 29 Jul 2003 08:51:04


Couldn't vector use std::swap() to shuffle things around - then there
would be an optimized implementation for strings.  And vectors of
vectors would become practical.

--

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

 
 
 

Possible enhancement to vector?

Post by Joe » Thu, 31 Jul 2003 07:46:31


Is all this copying required by the C++ standard or do you have a bad
implementation of the STL?

I thought that STLPort implementation went to great pains to use memmove
whenever possible.


Quote:> Recently my friends and I are thinking about the std::vector class.
> We feel that its object moving algorithm is not optimized.

> when it comes to re-size the buffer, Here are the things it will do:
> 1. allocate a big enough buffer (no problem)
> 2. copy some of the old objects into the new buffer. (problem starts
> here)
> 3. insert new value into the new buffer
> 4. copy the rest of the old objects into the new buffer.
> 5. destroy the old objects by calling dtor.
> 6. deallocate the old buffer. (no problem).

> The problem we noted is that the copy+dtor is sometimes expensive and
> not necessary.
> Suppose I have a string class, which internally holds a pointer to a
> char array.
> When asked to copy, I'll need to allocate new storage, copy the entire
> string.
> But if I know it's just a move, I can simply copy the pointer of the
> buffer. WAY faster!
> Also, we believe that for many types, a memcpy would be sufficient for
> the object move purpose.

> Now, the question is: why doesn't stl delegate the object move to the
> allocator object so that the programmer can customize the allocator
> accordingly to achieve the optimal performance? It sounds like an
> obvious thing to do.

> I actually revised std::vector with the extended allocator concept.
> and it worked. It does not require any language change or hacking, all
> it does is to delegate the move to the extended allocator and let the
> programmer do the optimal "move" instead of doing it all by itself.
> Whether "memcpy" or any other user-defined move is all up to the
> programmer.

> I'm sure many people would have been wondering about the same thing,
> but what puzzled me is that it seems possible to make vector both
> generic and optimizable. Why vector is not doing this though?

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

1. MFC 4: CScrollView: enhancement possible?

Any MFC / CScrollView experts around ??

I just wrote a dedicated source code editor using MFC 4.
I derived the view class from CScrollView.

Now I would like to implement a selection margin on the left
of the view area as implemented in MS Developer Studio 4.
To obtain this I tried to offset the viewport of the device
context attached to the view, but this does not prevent the
margin from being scrolled-away.

Does anyone know some trick to override this problem, or
is it necessary to write a special scroll view class derived
from CView?

Thanks to anybody who thinks a little about that !!

--
Roland Genske               Marxmeier Software Entwicklung GmbH

Voice : +49 202 2431440     42119 Wuppertal

2. RFC's...

3. Useful and small enhancement to std::vector -- opinions?

4. News Server problem

5. Is vector[1]==(&vector[0])[1] in a STL vector?

6. Verbatim blue vs gold

7. Vector of Vectors of Vectors

8. Cyborg Syllabus: The Evolution of Concepts

9. Vector of Array Type : vector<double[3]> and vector::push_back()

10. STL vector, direct access to array, possible?

11. Is ostream_iterator< vector<int> > possible?