Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #8966 > unrolled thread

Marshalling deques

Back to article view | Back to comp.lang.c++

Contents

  Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-16 19:13 -0700
    Re: Marshalling deques "Bo Persson" <bop@gmb.dk> - 2011-08-17 12:23 +0200
      Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-17 09:28 -0700
        Re: Marshalling deques Victor Bazarov <v.bazarov@comcast.invalid> - 2011-08-17 13:32 -0400
          Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 18:41 +0100
            Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 18:46 +0100
            Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-17 11:08 -0700
              Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 19:12 +0100
                Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 19:21 +0100
          Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-17 15:06 -0700
            Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 23:29 +0100
              Re: Marshalling deques Leigh Johnston <leigh@i42.co.uk> - 2011-08-17 23:34 +0100
                Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-18 08:59 -0700
            Re: Marshalling deques Jeff Flinn <TriumphSprint2000@hotmail.com> - 2011-08-17 21:10 -0400
            Re: Marshalling deques "Bo Persson" <bop@gmb.dk> - 2011-08-18 14:24 +0200
              Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-18 08:53 -0700
                Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-19 15:39 -0700
                  Re: Marshalling deques Ebenezer <woodbrian77@gmail.com> - 2011-08-22 12:39 -0700
        Re: Marshalling deques "Bo Persson" <bop@gmb.dk> - 2011-08-18 14:22 +0200
    Re: Marshalling deques ptyxs <kerloch@gmail.com> - 2011-08-17 09:43 -0700

#8966 — Marshalling deques

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.

[toc] | [next] | [standalone]

#8972

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.


Bo Persson

[toc] | [prev] | [next] | [standalone]

#8993

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.

[toc] | [prev] | [next] | [standalone]

#8998

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'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

[toc] | [prev] | [next] | [standalone]

#9000

On 17/08/2011 18:32, Victor Bazarov 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'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...

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

[toc] | [prev] | [next] | [standalone]

#9002

On 17/08/2011 18:41, Leigh Johnston wrote:
> On 17/08/2011 18:32, Victor Bazarov 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'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...
>
> 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.
>

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

[toc] | [prev] | [next] | [standalone]

#9004

On Aug 17, 12:41 pm, Leigh Johnston <le...@i42.co.uk> wrote:
> On 17/08/2011 18:32, Victor Bazarov 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'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...
>
> 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

I think he meant push_front.

[toc] | [prev] | [next] | [standalone]

#9005

On 17/08/2011 19:08, Ebenezer wrote:
> On Aug 17, 12:41 pm, Leigh Johnston<le...@i42.co.uk>  wrote:
>> On 17/08/2011 18:32, Victor Bazarov 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'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...
>>
>> 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
>
> I think he meant push_front.

std::vector does not have a push_front.

/Leigh

[toc] | [prev] | [next] | [standalone]

#9006

On 17/08/2011 19:12, Leigh Johnston wrote:
> On 17/08/2011 19:08, Ebenezer wrote:
>> On Aug 17, 12:41 pm, Leigh Johnston<le...@i42.co.uk> wrote:
>>> On 17/08/2011 18:32, Victor Bazarov 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'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...
>>>
>>> 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
>>
>> I think he meant push_front.
>
> std::vector does not have a push_front.

But yes inserting at the front is O(1) for deques and O(n) for vectors.

/Leigh

[toc] | [prev] | [next] | [standalone]

#9017

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.

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.

[toc] | [prev] | [next] | [standalone]

#9018

On 17/08/2011 23:06, Ebenezer wrote:
> 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.
>
> 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.

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

[toc] | [prev] | [next] | [standalone]

#9019

On 17/08/2011 23:29, Leigh Johnston wrote:
> On 17/08/2011 23:06, Ebenezer wrote:
>> 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.
>>
>> 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.
>
> 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.

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

[toc] | [prev] | [next] | [standalone]

#9050

On Aug 17, 5:34 pm, Leigh Johnston <le...@i42.co.uk> wrote:
> On 17/08/2011 23:29, Leigh Johnston wrote:
>
>
>
>
>
> > On 17/08/2011 23:06, Ebenezer wrote:
> >> 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.
>
> >> 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.
>
> > 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.
>
> 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.
>

I'm going to think about adding support for that
container to what I'm working on.

[toc] | [prev] | [next] | [standalone]

#9025

Ebenezer wrote:
> 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

[toc] | [prev] | [next] | [standalone]

#9038

Ebenezer wrote:
> 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.
>
> 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.

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


Bo Persson

[toc] | [prev] | [next] | [standalone]

#9048

On Aug 18, 7:24 am, "Bo Persson" <b...@gmb.dk> wrote:
> Ebenezer wrote:
> > 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.
>
> > 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.
>
> There are additional bookkeping involved because the first and last
> chunk may be only partially filled.
>

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.

[toc] | [prev] | [next] | [standalone]

#9106

On Aug 18, 10:53 am, Ebenezer <woodbria...@gmail.com> wrote:
> On Aug 18, 7:24 am, "Bo Persson" <b...@gmb.dk> wrote:
>
> > There are additional bookkeping involved because the first and last
> > chunk may be only partially filled.
>
> 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.

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

[toc] | [prev] | [next] | [standalone]

#9191

On Aug 19, 5:39 pm, Ebenezer <woodbria...@gmail.com> wrote:
>
> #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.

[toc] | [prev] | [next] | [standalone]

#9037

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.

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

[toc] | [prev] | [next] | [standalone]

#8995

On Aug 17, 4:13 am, Ebenezer <woodbria...@gmail.com> 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));
>

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c++

csiph-web