STL queue technique

Discussion in 'C++' started by Shailesh Humbad, Jul 26, 2004.

  1. 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);
    }
    Shailesh Humbad, Jul 26, 2004
    #1
    1. Advertising

  2. Shailesh Humbad

    Siemel Naran Guest

    "Shailesh Humbad" <> 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);
    > }


    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, Jul 26, 2004
    #2
    1. Advertising

  3. Siemel Naran wrote:

    > "Shailesh Humbad" <> 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);
    >>}

    >
    >
    > 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?
    Shailesh Humbad, Jul 26, 2004
    #3
  4. On Sun, 25 Jul 2004 23:35:05 GMT, Shailesh Humbad <>
    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);
    > }


    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
    John Harrison, Jul 26, 2004
    #4
  5. >
    > 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
    John Harrison, Jul 26, 2004
    #5
  6. Shailesh Humbad

    Siemel Naran Guest

    "Shailesh Humbad" <> 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, Jul 26, 2004
    #6
  7. 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.
    Shailesh Humbad, Jul 26, 2004
    #7
  8. John Harrison wrote:

    > On Sun, 25 Jul 2004 23:35:05 GMT, Shailesh Humbad <>
    > 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
    Shailesh Humbad, Jul 26, 2004
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Paul L. Du Bois

    Queue.Queue-like class without the busy-wait

    Paul L. Du Bois, Mar 24, 2005, in forum: Python
    Replies:
    29
    Views:
    1,038
    Antoon Pardon
    Apr 4, 2005
  2. Russell Warren

    Is Queue.Queue.queue.clear() thread-safe?

    Russell Warren, Jun 22, 2006, in forum: Python
    Replies:
    4
    Views:
    666
    Russell Warren
    Jun 27, 2006
  3. Kceiw
    Replies:
    3
    Views:
    982
    Jim Langston
    Mar 14, 2006
  4. Gabriel Rossetti
    Replies:
    3
    Views:
    533
    Jerry Hill
    Apr 25, 2008
  5. Kris
    Replies:
    0
    Views:
    464
Loading...

Share This Page