Marshalling deques
Ebenezer
When you have a vector of a primitive type, rather than
iterating through each element, you can marshal the vector
with the address of the first element and multiply the size
of the vector with the size of each element like this:
buf.Receive(&*vec.begin(), vec.size() * sizeof(T));
I'd like to do something similar with deques, but they are
implemented in chunks rather than a single chunk. How
to get the address and size of each chunk, though? Tia.
http://www.gotw.ca/gotw/054.htm
Brian Wood
Ebenezer Enterprises
www.webEbenezer.net
O n e
b i g -
a s s
m i s t a k e,
A m e r i c a.
Bo Persson
> When you have a vector of a primitive type, rather than
> iterating through each element, you can marshal the vector
> with the address of the first element and multiply the size
> of the vector with the size of each element like this:
>
> buf.Receive(&*vec.begin(), vec.size() * sizeof(T));
>
> I'd like to do something similar with deques, but they are
> implemented in chunks rather than a single chunk. How
> to get the address and size of each chunk, though? Tia.
>
> http://www.gotw.ca/gotw/054.htm
>
You cannot.
Deque has to use a two level addressing, probably involving an array
of pointers to the chunks, but the details are not specified by the
standard. There is no interface to this internal structure.
Bo Persson
Ebenezer
In that case, how about changing the standard? I believe iterating
through a deque is more involved than iterating through a vector.
ptyxs
> When you have a vector of a primitive type, rather than
> iterating through each element, you can marshal the vector
> with the address of the first element and multiply the size
> of the vector with the size of each element like this:
>
> buf.Receive(&*vec.begin(), vec.size() * sizeof(T));
>
Much surprising to choose to work that way. Vectors were designed
precisely NOT to have to do that. (If you really feel you need to work
that way, why not use an array, anyway !)
Victor Bazarov
So? It's not designed/designated to be "less involved" than vector.
It's designed to have a faster push_back than vector, and comparable
lookup, and have more relaxed memory requirements (no need to have a
contiguous block). Try iterating through a set...
V
--
I do not respond to top-posted replies, please don't ask
Leigh Johnston
I am of the opinion that you are incorrect to say that deque push_back
is designed to be faster than vector push_back. If you pre-allocate a
vector with reserve() then its push_back would easily out-perform deque
push_back. Even if you don't call reserve() I am still unconvinced that
deque's push_back out-performs vector's on average.
/Leigh
Leigh Johnston
To confirm this I did some quick timings on VC++:
struct timer
{
timer(const char* message)
{
std::cout << message;
QueryPerformanceCounter(&iStartTime);
}
~timer()
{
LARGE_INTEGER endTime;
QueryPerformanceCounter(&endTime);
LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
std::cout.precision(4);
std::cout << std::fixed << (float)(endTime.QuadPart -
iStartTime.QuadPart)/(float)freq.QuadPart << " seconds" << std::endl;
}
LARGE_INTEGER iStartTime;
};
int main()
{
std::vector<int> v;
{
timer t("vector :");
for (int i = 0; i != 10000000; ++i)
v.push_back(i);
}
std::deque<int> d;
{
timer t("deque :");
for (int i = 0; i != 10000000; ++i)
d.push_back(i);
}
}
outputs:
vector :0.0636 seconds
deque :0.2866 seconds
HTH.
/Leigh
Ebenezer
I think he meant push_front.
Leigh Johnston
std::vector does not have a push_front.
/Leigh
Leigh Johnston
But yes inserting at the front is O(1) for deques and O(n) for vectors.
/Leigh
Ebenezer
> On 8/17/2011 12:28 PM, Ebenezer wrote:
>
>
>
>
>
>
>
>
>
> > On Aug 17, 5:23 am, "Bo Persson"<b...@gmb.dk> wrote:
> >> Ebenezer wrote:
> >>> When you have a vector of a primitive type, rather than
> >>> iterating through each element, you can marshal the vector
> >>> with the address of the first element and multiply the size
> >>> of the vector with the size of each element like this:
>
> >>> buf.Receive(&*vec.begin(), vec.size() * sizeof(T));
>
> >>> I'd like to do something similar with deques, but they are
> >>> implemented in chunks rather than a single chunk. How
> >>> to get the address and size of each chunk, though? Tia.
>
> >>>http://www.gotw.ca/gotw/054.htm
>
> >> You cannot.
>
> >> Deque has to use a two level addressing, probably involving an array
> >> of pointers to the chunks, but the details are not specified by the
> >> standard. There is no interface to this internal structure.
>
> > In that case, how about changing the standard? I believe iterating
> > through a deque is more involved than iterating through a vector.
>
> So?
It seems that being able to bypass the relatively slower deque
iterators would be helpful.
What I need to know from a deque is what is the first element
of each of it's chunks. Say for example, a deque has 3 chunks
and 500 elements. The interface would give me indices something
like: 0, 200, 400. The indices could be served up in a vector
so I don't have to deal with deque iteration.
Leigh Johnston
Basically "You are doing it wrong! (tm)" std::deque does not provide
what you want (and likely never will) so the solution therefore is to
either use iterators properly or stick to std::vector as you mention in
your OP.
HTH.
/Leigh
Leigh Johnston
If you want something similar to deque that does do what you want you
may be interested in my segmented_array container the "segments" of
which you can access directly; details:
http://i42.co.uk/stuff/segmented_array.htm
HTH.
/Leigh
Jeff Flinn
> On Aug 17, 12:32 pm, Victor Bazarov <v.baza...@comcast.invalid> wrote:
>> On 8/17/2011 12:28 PM, Ebenezer wrote:
>>
>>> On Aug 17, 5:23 am, "Bo Persson"<b...@gmb.dk> wrote:
>>>> Ebenezer wrote:
>>>>> When you have a vector of a primitive type, rather than
>>>>> iterating through each element, you can marshal the vector
>>>>> with the address of the first element and multiply the size
>>>>> of the vector with the size of each element like this:
>>>>> buf.Receive(&*vec.begin(), vec.size() * sizeof(T));
>>>>> I'd like to do something similar with deques, but they are
>>>>> implemented in chunks rather than a single chunk. How
>>>>> to get the address and size of each chunk, though? Tia.
>>>>> http://www.gotw.ca/gotw/054.htm
>>>> You cannot.
>>>> Deque has to use a two level addressing, probably involving an array
>>>> of pointers to the chunks, but the details are not specified by the
>>>> standard. There is no interface to this internal structure.
>>> In that case, how about changing the standard? I believe iterating
>>> through a deque is more involved than iterating through a vector.
>> So?
>
> It seems that being able to bypass the relatively slower deque
> iterators would be helpful.
google the segmented iterator paper by Matt Austern, IIRC.
Jeff
Bo Persson
Iterating through a deque is encoded in the iterators. It does take
about twice as long as iterating a vector.
The advantage is that you can insert and delete at both ends without
moving the member objects and that the memory is allocated in chunks
instead of in one large block. That's a trade off!
Bo Persson
Bo Persson
There are additional bookkeping involved because the first and last
chunk may be only partially filled.
Bo Persson
Ebenezer
My example only indicates that as the last chunk, but, yes,
I agree. Not sure if your point is I'm assuming too much
about the implementation or what.
Ebenezer
I'm going to think about adding support for that
container to what I'm working on.
Ebenezer
#include <sys/time.h>
#include <deque>
#include <vector>
#include <iostream>
#include <SendBuffer.hh>
#include <Msgs.cg.hh>
void
Msgs::Marshal (SendBuffer& buf
, ::std::deque<int> const& abt1
)
{
buf.Receive32(abt1.size());
::std::deque<int >::const_iterator mediator3 = abt1.begin();
::std::deque<int >::const_iterator omega3 = abt1.end();
for (; mediator3 != omega3; ++mediator3) {
buf.Receive(&(*mediator3), sizeof(int));
}
}
void
optimizedMarshalling(SendBuffer& sendbuf
, ::std::deque<int> dq
, ::std::vector<int> indices
)
{
sendbuf.Receive32(dq.size());
::std::vector<int>::iterator vprev = indices.begin();
::std::vector<int>::iterator vit = vprev + 1;
for (; vit != indices.end(); ++vit) {
sendbuf.Receive(&dq[*vprev], (*vit - *vprev) * sizeof(int));
vprev = vit;
}
sendbuf.Receive(&dq[*vprev], (dq.size() - *vprev) * sizeof(int));
}
int
main()
{
::std::deque<int> adeque;
for (int j = 1; j <= 5000; ++j) {
adeque.push_back(j);
}
int index = 1;
::std::vector<int> indices;
indices.push_back(0);
::std::deque<int>::iterator prev = adeque.begin();
::std::deque<int>::iterator it = prev + 1;
for (; it != adeque.end(); ++it) {
if (&*it != (&*prev + 1)) {
indices.push_back(index);
}
prev = it;
++index;
}
{
SendBuffer sendbuf;
Msgs msgs(400000);
struct timezone tz;
timeval before, after;
gettimeofday(&before, &tz);
msgs.Marshal(sendbuf, adeque);
gettimeofday(&after, &tz);
if (before.tv_sec != after.tv_sec) {
after.tv_usec += 1000000;
}
::std::cout << "Using deque iterators: " << after.tv_usec -
before.tv_usec << ::std::endl;
::std::cout << "Buf size is " << sendbuf.getBufsize()
<< ::std::endl;
}
{
SendBuffer sendbuf;
struct timezone tz;
timeval before, after;
gettimeofday(&before, &tz);
optimizedMarshalling(sendbuf, adeque, indices);
gettimeofday(&after, &tz);
if (before.tv_sec != after.tv_sec) {
after.tv_usec += 1000000;
}
::std::cout << "Optimized approach:" << after.tv_usec -
before.tv_usec << ::std::endl;
::std::cout << "Buf size is " << sendbuf.getBufsize()
<< ::std::endl;
}
return 1;
}
[gs]# ./dq_test
Using deque iterators: 487
Buf size is 20004
Optimized approach:280
Buf size is 20004
[gs]# ./dq_test
Using deque iterators: 500
Buf size is 20004
Optimized approach:278
Buf size is 20004
[gs]# ./dq_test
Using deque iterators: 478
Buf size is 20004
Optimized approach:277
Buf size is 20004
[gs]# ./dq_test
Using deque iterators: 472
Buf size is 20004
Optimized approach:299
Buf size is 20004
[gs]# ./dq_test
Using deque iterators: 476
Buf size is 20004
Optimized approach:275
Buf size is 20004
[gs]# ./dq_test
Using deque iterators: 473
Buf size is 20004
Optimized approach:301
Buf size is 20004
The approach that uses deque iterators takes between
1.5 and 1.8 times longer than the optimized approach.
The optimized approach is given the indices that it
needs and no time is added for that. I'm not sure how
long it would take for deque to provide the information,
but believe this optimization could be helpful.
Ebenezer
>
> #include <sys/time.h>
>
> #include <deque>
> #include <vector>
> #include <iostream>
> #include <SendBuffer.hh>
> #include <Msgs.cg.hh>
>
> void
> Msgs::Marshal (SendBuffer& buf
> , ::std::deque<int> const& abt1
> )
> {
>
> buf.Receive32(abt1.size());
> ::std::deque<int >::const_iterator mediator3 = abt1.begin();
> ::std::deque<int >::const_iterator omega3 = abt1.end();
> for (; mediator3 != omega3; ++mediator3) {
> buf.Receive(&(*mediator3), sizeof(int));
> }
>
> }
>
> void
> optimizedMarshalling(SendBuffer& sendbuf
> , ::std::deque<int> dq
Thanks to "Roy Rogers" for pointing out that I wasn't
using a reference here. I've separated the tests now
into two separate mains and also remembered to turn on
-O3 optimization when building.
First, here's the implementation that uses deque iterators:
#include <sys/time.h>
#include <deque>
#include <iostream>
#include <SendBuffer.hh>
#include <Msgs.cg.hh>
int
main()
{
::std::deque<int> adeque;
for (int j = 1; j <= 50000; ++j) {
adeque.push_back(j);
}
SendBuffer sendbuf;
Msgs msgs(400000);
struct timezone tz;
timeval before, after;
gettimeofday(&before, &tz);
msgs.Marshal(sendbuf, adeque);
gettimeofday(&after, &tz);
if (before.tv_sec != after.tv_sec) {
after.tv_usec += 1000000;
}
::std::cout << "Using deque iterators: " << after.tv_usec -
before.tv_usec << ::std::endl;
::std::cout << "Buf size is " << sendbuf.getBufsize()
<< ::std::endl;
return 1;
}
The Marshal function hasn't changed and can be found in my
previous post.
And here's the implementation using the insider information:
#include <sys/time.h>
#include <deque>
#include <vector>
#include <iostream>
#include <SendBuffer.hh>
void
optimizedMarshalling(SendBuffer& sendbuf
, ::std::deque<int> const& dq
, ::std::vector<int> indices
)
{
sendbuf.Receive32(dq.size());
::std::vector<int>::const_iterator vprev = indices.begin();
::std::vector<int>::const_iterator vit = vprev + 1;
for (; vit != indices.end(); ++vit) {
sendbuf.Receive(&dq[*vprev], (*vit - *vprev) * sizeof(int));
vprev = vit;
}
sendbuf.Receive(&dq[*vprev], (dq.size() - *vprev) * sizeof(int));
}
int
main()
{
::std::deque<int> adeque;
for (int j = 1; j <= 50000; ++j) {
adeque.push_back(j);
}
int index = 1;
::std::vector<int> indices;
indices.push_back(0);
::std::deque<int>::iterator prev = adeque.begin();
::std::deque<int>::iterator it = prev + 1;
for (; it != adeque.end(); ++it) {
if (&*it != (&*prev + 1)) {
indices.push_back(index);
}
prev = it;
++index;
}
SendBuffer sendbuf;
struct timezone tz;
timeval before, after;
gettimeofday(&before, &tz);
optimizedMarshalling(sendbuf, adeque, indices);
gettimeofday(&after, &tz);
if (before.tv_sec != after.tv_sec) {
after.tv_usec += 1000000;
}
::std::cout << "Optimized approach: " << after.tv_usec -
before.tv_usec << ::std::endl;
::std::cout << "Buf size is " << sendbuf.getBufsize()
<< ::std::endl;
return 1;
}
[gs]# ./dq_iterators ; ./dq_iterators ; ./dq_iterators
Using deque iterators: 315
Buf size is 20004
Using deque iterators: 295
Buf size is 20004
Using deque iterators: 298
Buf size is 20004
[gs]# ./dq_iterators ; ./dq_iterators ; ./dq_iterators
Using deque iterators: 320
Buf size is 20004
Using deque iterators: 338
Buf size is 20004
Using deque iterators: 307
Buf size is 20004
[gs]# ./dq_iterators ; ./dq_iterators ; ./dq_iterators
Using deque iterators: 310
Buf size is 20004
Using deque iterators: 305
Buf size is 20004
Using deque iterators: 304
Buf size is 20004
[gs]# ./insider_info ; ./insider_info ; ./insider_info
Optimized approach: 96
Buf size is 20004
Optimized approach: 88
Buf size is 20004
Optimized approach: 103
Buf size is 20004
[gs]# ./insider_info ; ./insider_info ; ./insider_info
Optimized approach: 87
Buf size is 20004
Optimized approach: 94
Buf size is 20004
Optimized approach: 84
Buf size is 20004
[gs]# ./insider_info ; ./insider_info ; ./insider_info
Optimized approach: 100
Buf size is 20004
Optimized approach: 96
Buf size is 20004
Optimized approach: 101
Buf size is 20004
The deque iterator approach is over 3 times slower than
the approach that gets help from the deque. I believe
there's good reason to add a function to deque's interface
to assist in marshalling.