Marshalling deques

E

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

Bo Persson

Ebenezer said:
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
Click to expand...

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
 
E

Ebenezer

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.
Click to expand...

In that case, how about changing the standard? I believe iterating
through a deque is more involved than iterating through a vector.
 
P

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));
Click to expand...

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

Victor Bazarov

In that case, how about changing the standard? I believe iterating
through a deque is more involved than iterating through a vector.
Click to expand...

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
 
E

Ebenezer

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
Click to expand...

I think he meant push_front.
 
E

Ebenezer

So?  
Click to expand...

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

Jeff Flinn

Ebenezer said:
It seems that being able to bypass the relatively slower deque
iterators would be helpful.
Click to expand...

google the segmented iterator paper by Matt Austern, IIRC.

Jeff
 
B

Bo Persson

Ebenezer said:
In that case, how about changing the standard? I believe iterating
through a deque is more involved than iterating through a vector.
Click to expand...

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
 
B

Bo Persson

Ebenezer said:
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.
Click to expand...

There are additional bookkeping involved because the first and last
chunk may be only partially filled.


Bo Persson
 
E

Ebenezer

There are additional bookkeping involved because the first and last
chunk may be only partially filled.
Click to expand...

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

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.
Click to expand...

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

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
Click to expand...


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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Marshalling asymmetry 8
Container functionality and marshalling 11
segmented_array question 2
Is const_cast ok in marshalling code? 12
Blue J Ciphertext Program 2
Copying part of a vector element to a string variable 3
New version of C++ Middleware Writer available 1
Weird Behavior with Rays in C and OpenGL 4

Members online

Total: 30 (members: 1, guests: 29)
Robots: 376

Forum statistics

Threads
473,770
Messages
2,569,584
Members
45,077
Latest member
SangMoor21

Latest Threads

Top