STL queue technique

S

Shailesh Humbad

I wrote a simple, but proprietary queue class that efficiently
enqueues and dequeues arbitrary length byte arrays. I would like to
replace it with an STL container if the performance overhead is not
too high. Currently, I am thinking of replacing it like shown below,
but it is not efficient due to repeated function calls to "push". Can
anyone with more STL experience show a better way to use it, if there
is one?

// CUSTOM QUEUE
// receive data from network into byte array
iBytesReceived = recv(destinationBuffer)
// store it in the queue in a single pass
myCustomQueue.Enqueue(destinationBuffer, iBytesReceived)

// STL QUEUE (slower)
// receive data from network into byte array
iBytesReceived = recv(destinationBuffer)
// store it in the queue using push
for(int i = 0; i < iBytesReceived; i++) {
my_STL_Queue.push(destinationBuffer);
}
 
S

Siemel Naran

What if you create your own STL queue class? The easiest way is to derive
from std::queue. Then add a new function push taking two arguments, a range
to the start and end of a range. In this function call c.insert(c.begin(),
begin, end).

Replace
for(int i = 0; i < iBytesReceived; i++) {
my_STL_Queue.push(destinationBuffer);
}


with

my_STL_Queue.push(destinationBuffer, destinationBuffer + iBytesReceived);

Also, if you have access to a profiler, use it to determine where the
bottleneck is.

Also, in your own home-made queue, how is the speed of removing elements
from the queue? It is possible to make insertions faster at the cost of
making removals slower. So it might be hard to come up with a definitive
answer for all problems.
 
S

Shailesh Humbad

Siemel said:
What if you create your own STL queue class? The easiest way is to derive
from std::queue. Then add a new function push taking two arguments, a range
to the start and end of a range. In this function call c.insert(c.begin(),
begin, end).

Replace

for(int i = 0; i < iBytesReceived; i++) {
my_STL_Queue.push(destinationBuffer);
}



with

my_STL_Queue.push(destinationBuffer, destinationBuffer + iBytesReceived);

Also, if you have access to a profiler, use it to determine where the
bottleneck is.



I can't derive another queue because I think I would still have to
rely on the internal queue push function. Also, if I derive a queue,
then I am using a proprietary data structure again.

The STL way above is slower than my home-made queue because it must
perform a function call, do bounds checks, and (possibly) do
reallocation/copying at each step. I have stepped through the push
function source code. To enqueue 500 bytes, my queue takes 30K clock
ticks, whereas the STL queue takes 380K clock ticks. Even if I switch
to deque, and use the resize prior to enqueueing, it takes 300K ticks.
Also, in your own home-made queue, how is the speed of removing elements
from the queue? It is possible to make insertions faster at the cost of
making removals slower. So it might be hard to come up with a definitive
answer for all problems.

My queue can dequeue into an array just as fast as it can enqueue.
After doing some bounds check, it is simply doing a memcpy from the
internal array to the external one, which is very fast. Is there a
way to get the same speed with STL?
 
J

John Harrison

I wrote a simple, but proprietary queue class that efficiently enqueues
and dequeues arbitrary length byte arrays. I would like to replace it
with an STL container if the performance overhead is not too high.
Currently, I am thinking of replacing it like shown below, but it is not
efficient due to repeated function calls to "push". Can anyone with
more STL experience show a better way to use it, if there is one?

// CUSTOM QUEUE
// receive data from network into byte array
iBytesReceived = recv(destinationBuffer)
// store it in the queue in a single pass
myCustomQueue.Enqueue(destinationBuffer, iBytesReceived)

// STL QUEUE (slower)
// receive data from network into byte array
iBytesReceived = recv(destinationBuffer)
// store it in the queue using push
for(int i = 0; i < iBytesReceived; i++) {
my_STL_Queue.push(destinationBuffer);
}


Your problem is that you are pushing bytes. Maybe you can create a bigger
object to push onto the queue (it hard to know since its not clear whow
you are using this data structore). You could consider using the
shared_array class from boost for instance.
http://www.boost.org/libs/smart_ptr/shared_array.htm

But maybe the best way is to use a deque instead of a queue, then you can
write

my_STL_deque.insert(my_STL_deque.end(), destinationBuffer,
destinationBuffer + i);

By why are you replacing your custom written class after you've gone to
the trouble of writing it? Isn't that the wrong way round? Normally you
would start with STL classes (since they are easy to use) and only replace
with customised classes if you need to.

john
 
J

John Harrison

But maybe the best way is to use a deque instead of a queue, then you
can write

my_STL_deque.insert(my_STL_deque.end(), destinationBuffer,
destinationBuffer + i);

I meant.

my_STL_deque.insert(my_STL_deque.end(), destinationBuffer,
destinationBuffer + iBytesReceived);

john
 
S

Siemel Naran

Shailesh Humbad said:
Siemel Naran wrote:
I can't derive another queue because I think I would still have to
rely on the internal queue push function. Also, if I derive a queue,
then I am using a proprietary data structure again.

No, you don't have to rely on the queue's push function. In the standard,
std::queue is defined as a container adapter. The queue contains a member
variable c which by default is a a std::deque. The function queue::push
just calls c.push_back to add one element to the array.

So if the container has a special push_back function to add multiple
elements, you could use it. Presumably it would be more efficient than
calling the normal push_back many times. Turns out that for std::deque
there is no push_back function taking two arguments, but there is an insert
function.

In my previous email I said call c.insert(c.begin(), begin, end). This
would insert the elements in the range [begin, end) at the start of the
array. But I think you need to insert at the end, so the call should really
be c.insert(c.end(), begin, end).
The STL way above is slower than my home-made queue because it must
perform a function call, do bounds checks, and (possibly) do
reallocation/copying at each step. I have stepped through the push
function source code. To enqueue 500 bytes, my queue takes 30K clock
ticks, whereas the STL queue takes 380K clock ticks. Even if I switch
to deque, and use the resize prior to enqueueing, it takes 300K ticks.


My queue can dequeue into an array just as fast as it can enqueue.
After doing some bounds check, it is simply doing a memcpy from the
internal array to the external one, which is very fast. Is there a
way to get the same speed with STL?

You can try the above suggestion, but I still don't think the STL will be as
fast as your own one.
 
S

Shailesh Humbad

Siemel said:
No, you don't have to rely on the queue's push function. In the standard,
std::queue is defined as a container adapter. The queue contains a member
variable c which by default is a a std::deque. The function queue::push
just calls c.push_back to add one element to the array.

So if the container has a special push_back function to add multiple
elements, you could use it. Presumably it would be more efficient than
calling the normal push_back many times. Turns out that for std::deque
there is no push_back function taking two arguments, but there is an insert
function.

In my previous email I said call c.insert(c.begin(), begin, end). This
would insert the elements in the range [begin, end) at the start of the
array. But I think you need to insert at the end, so the call should really
be c.insert(c.end(), begin, end).

Okay, I missed that. I tried insert with deque, but internally, it
also uses the push_back function. So there is still a function call
for each byte. I think you're right that my own queue will be best.
Thanks for your suggestions.
 
S

Shailesh Humbad

John said:
Your problem is that you are pushing bytes. Maybe you can create a
bigger object to push onto the queue (it hard to know since its not
clear whow you are using this data structore). You could consider using
the shared_array class from boost for instance.
http://www.boost.org/libs/smart_ptr/shared_array.htm

But maybe the best way is to use a deque instead of a queue, then you
can write

my_STL_deque.insert(my_STL_deque.end(), destinationBuffer,
destinationBuffer + i);

By why are you replacing your custom written class after you've gone to
the trouble of writing it? Isn't that the wrong way round? Normally you
would start with STL classes (since they are easy to use) and only
replace with customised classes if you need to.

john

Well, the reason I'm considering replacing it is that someday I hope
to share my code with other people. Using standard classes saves the
communication effort of explaining/learning a custom class, so my code
becomes team-friendly.

Please see my other post regarding the insert method. I'd like to
avoid boost for a number of reasons that are not relevant to this
discussion, which I'd be happy to share only if you're interested.

The way I'm using this queue is that in one thread, I enqueue TCP
network data into the queue. Then, in another thread, I dequeue the
data and process it like this:

lReceivedDataLength = myCustomQueue.DequeueCopy(recvBuffer, 10000);

The queue is protected by a mutex. After getting a copy of the bytes
into a local recvBuffer array, the thread releases the mutex and
continues processing the data byte by byte.

So, I don't technically _need_ to use my own custom queue class,
because the STL queue provides enough functionality. But since I
can't find a way to do enqueueing and dequeueing directly into or out
of the internal queue array, the performance will be low. STL's
implementation is designed to hold objects which may need copy
constructing, and this may be a reason why it doesn't have push_back
or pop_front functions that take an array of objects.

I think I will keep my own class in this case. Thanks for all your help.

Regards,
Shailesh
 

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

Members online

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top