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[i]);
} 7 4391
"Shailesh Humbad" <no*****@nowhere.com> wrote in message news:JsXMc.10800
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[i]); }
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.
Siemel Naran wrote: "Shailesh Humbad" <no*****@nowhere.com> wrote in message news:JsXMc.10800
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[i]); }
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?
On Sun, 25 Jul 2004 23:35:05 GMT, Shailesh Humbad <no*****@nowhere.com>
wrote: 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[i]); }
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
> 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
"Shailesh Humbad" <no*****@nowhere.com> wrote in message news:7P0Nc.6631 Siemel Naran wrote:
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).
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.
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?
You can try the above suggestion, but I still don't think the STL will be as
fast as your own one.
Siemel Naran wrote: 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.
John Harrison wrote: On Sun, 25 Jul 2004 23:35:05 GMT, Shailesh Humbad <no*****@nowhere.com> wrote:
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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: phil |
last post by:
And sorry I got ticked, frustrating week
>And I could help more, being fairly experienced with
>threading issues and race conditions and such, but
>as I tried to indicate in the first place,...
|
by: Brian Henry |
last post by:
If i inherite a queue class into my class, and do an override of the enqueue
member, how would i then go about actually doing an enqueue of an item? I am
a little confused on this one... does over...
|
by: Kceiw |
last post by:
Dear all,
When I use #include "queue.h", I can't link it.
The error message follows:
Linking...
G:\Projects\Datastructure\Queue\Debug\main.o(.text+0x136): In
function `main':...
|
by: lavender |
last post by:
When define a maxQueue is 10, means it able to store 10 items in circular queue,but when I key in the 10 items, it show "Queue Full" in items number 10.
Where is the wrong in my code? Why it cannot...
|
by: jrpfinch |
last post by:
I have a script which is based on the following code. Unfortunately,
it only works on Python 2.3 and not 2.5 because there is no esema or
fsema attribute in the 2.5 Queue. I am hunting through...
|
by: j_depp_99 |
last post by:
Thanks to those guys who helped me out yesterday. I have one more
problem; my print function for the queue program doesnt work and goes
into an endless loop. Also I am unable to calculate the...
|
by: ecestd |
last post by:
how do you implement a copy constructor for this pointer-based ADT
queue
#include <cassert // for assert
#include <new // for bad_alloc
using namespace std;
//private:{Queue::Queue(const...
|
by: ecestd |
last post by:
I did implement the copy constructor but still have a problem with
it. It is not working. What could be wrong?
#include "QueueP.h"
#include <cassert // for assert
#include <new // for...
|
by: Ralph Wiggum |
last post by:
I'm planning on pulling data from a webservice and push the data on to a buffer/queue for each response. This should happen in a thread, while another thread parses the data (heavy) and writes them...
|
by: taylorcarr |
last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
|
by: ryjfgjl |
last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
| |