3
\$\begingroup\$

so I wrote a queue implementation in c++ and even though I know the code probably isn't as robust as it should be and probably doesn't perform all the checks it should, I'd like to know mostly if there is any functionality difference between my implementation and the one in STL.

My implementation idea is to use a circular queue, when I reach the end of the queue I start using the elements at the beginning of the range (that were removed through the pop method).

When I don't have any more space to allocate a new element I reallocate a new buffer and move everything to the new buffer in order (this could probably be done faster using 2 memmoves).

The reason I post this here is because this queue implementation seems to be aproximately 50% faster than the one in std. Here is my code:

template<typename T>
class Queue
{
private:
    int m_capacity;
    int m_size;
    int m_startIndex;
    int m_endIndex;
    T* m_buffer;

    void expand_queue() {
        int newCapacity = m_capacity * 2;
        T* newBuffer = new T[newCapacity];
        if (m_endIndex <= m_startIndex) {
            int cnt = 0;
            for (int i = m_startIndex; i < m_capacity; i++) {
                newBuffer[cnt++] = m_buffer[i];
            }

            for (int i = 0; i < m_endIndex; i++) {
                newBuffer[cnt++] = m_buffer[i];
            }
        } else {
            int cnt = 0;
            for (int i = m_startIndex; i < m_endIndex; i++) {
                newBuffer[cnt++] = m_buffer[i];
            }            
        }

        delete[] m_buffer;
        m_buffer = newBuffer;
        m_startIndex = 0;
        m_endIndex = m_size;
        m_capacity = newCapacity;
    }

    void init_queue(int capacity) {
        m_capacity = capacity;
        m_size = 0;
        m_startIndex = 0;
        m_endIndex = 0;

        m_buffer = new T[capacity];
    }

public:
    Queue() {
        init_queue(32);
    }

    Queue(int capacity) {
        init_queue(capacity);
    }

    void push(T element) {
        if (m_endIndex == m_startIndex && m_size > 0) {
            // expand queue
            expand_queue();
        }

        m_buffer[m_endIndex] = element;
        m_endIndex = (m_endIndex + 1) % m_capacity;
        m_size++;
    }

    void pop() {
        if (m_size == 0) {
            return;
        }

        m_startIndex = (m_startIndex + 1) % m_capacity;
        m_size--;
    }

    T front() {
        if (m_size == 0) {
            throw;
        }

        return m_buffer[m_startIndex];
    }

    T back() {
        if (m_size == 0) {
            throw;
        }

        if (m_endIndex == 0) {
            return m_buffer[m_capacity - 1];
        } else {
            return m_buffer[m_endIndex - 1];
        }
    }

    int size() {
        return m_size;
    }
};

And here is the code I used to test this:

#include <queue>
#include "queue.h"
#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>

using namespace std;

Queue<int> q;
// queue<int> q;

int main() {
    srand(time(0));
    for (int i = 0; i < 100000000; i++) {
        if (q.size() > 10000000) {
            q.pop();
        } else if (q.size() == 0) {
            q.push(i);
        } else if (random() % 2 == 0) {
            q.push(i);
        } else {
            q.pop();
        }
    }

    while (q.size() > 0) {
        q.pop();
    }

    return 0;
}

You can see that in the test code I have both queue types in there (just comment one line and uncomment the other). This program perform 100 milion operation of push/pop on the queue while making sure the queue doesn't go over 10 million in size.

Using the queue implementation above I get this time:

real    0m3.859s
user    0m3.827s
sys     0m0.015s

And these are times using the std queue:

real    0m6.077s
user    0m6.055s
sys     0m0.011s

(Benchmarks done on a mid-2012 Macbook Air).

After studying the std queue implementation I managed to note these differences:

  • std::queue uses std::deque as a container by default (using std::list gives even worse results). The std::queue only calls the pop_front and the push_back methods of the deque. All the logic is in the deque.
  • std::deque creates chunks of fixed size which he uses to allocate the data and manages them accordingly (first chunk expands in reverse and the last chunk expands normally).
  • Given that std::deque creates these chunks memory fragmentation could also become an issue.
  • std::queue doesn't do any memory movements, just allocations of new chunks, while my queue will move the memory around when it needs to expand the queue (log(N) times where N is the maximum size of the queue).
\$\endgroup\$
2
\$\begingroup\$

Please use std::vector instead of T* because you clearly don't know what you are doing (missing operator=, copy-constructor, etc). Better, make the underlying container a template parameter.

The std::queue is probably slower because it may free some memory when doing all these pop() while yours doest release anything.

About this:

    if (m_size == 0) {
        throw;
    }

what do you think you are throwing ? Please throw a proper exception (see http://en.cppreference.com/w/cpp/header/stdexcept for example).

\$\endgroup\$
  • \$\begingroup\$ I didn't write this as a proper replacement for the entire functionality of the queue (a proper container). I was only interested in the performance part, I probably didn't post this in the right place though. I know i'm missing a lot of stuff (copy constructors, operators etc). \$\endgroup\$ – Tiberiu Savin Jul 23 '16 at 12:13
  • \$\begingroup\$ @TiberiuSavin, it is quite right place. But the thing is, you shouldn't expect everyone to write about performance :) People generally prefer to get worst things out of the way first. \$\endgroup\$ – Incomputable Jul 23 '16 at 12:16
0
\$\begingroup\$

Yes, your class is functionally different from the queue provided by the stl. This line:

m_buffer = new T[capacity];

Means that the type T has to provide a default constructor. This limitation is not imposed on you if you use the STL queue.

As an aside, when you're comparing performance of two different systems and you want to use random numbers as part of it, you're better off not seeding the random number generator. This:

srand(time(0));

seeds the random number generator using the current time. In a lot of cases this is what you want. However when you're comparing the performance of the two queues you want pseudo random numbers, but you don't want them to be different every time. That way you know you're comparing like with like. You don't want to end up testing your queue with a maximum length of 100 and the stl queue with a maximum length of 10000.

\$\endgroup\$
  • \$\begingroup\$ 1. Yeah I actually meant to use malloc instead of new, but I was too lazy to check the malloc syntax, I just wanted to make it work to compare performance. I will change that to malloc because I don't actually want to call the constructor. 2. Good point, I didn't think about the fact that I was testing the queues on different operations. I don't think it's any big difference but it's a valid point. \$\endgroup\$ – Tiberiu Savin Jul 23 '16 at 17:18
0
\$\begingroup\$

I have only a couple of minor comments:

1

void push(T element) {
    if (m_endIndex == m_startIndex && m_size > 0) {
        // expand queue
        expand_queue();
    }

    m_buffer[m_endIndex] = element;
    m_endIndex = (m_endIndex + 1) % m_capacity;
    m_size++;
}

Why not write simply if (m_size == m_capacity) ... ?

2

if (m_endIndex <= m_startIndex) {
    int cnt = 0;
    for (int i = m_startIndex; i < m_capacity; i++) {
        newBuffer[cnt++] = m_buffer[i];
    }

    for (int i = 0; i < m_endIndex; i++) {
        newBuffer[cnt++] = m_buffer[i];
    }
} else {
    int cnt = 0;
    for (int i = m_startIndex; i < m_endIndex; i++) {
        newBuffer[cnt++] = m_buffer[i];
    }            

}

The above could be written more succintly as

for (int i = m_startIndex, cnt = 0; cnt < m_size; ++i, ++cnt) {
    newBuffer[cnt] = m_buffer[i % m_capacity];
}

3

Finally, if you could guarantee that the internal storage array has capacity that is always a power of two, you could substitute:

index % m_capacity --> index & m_mask, 

where m_mask == m_capacity - 1.

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ 1. Yeah when I wrote that code the m_size didn't exist yet. Only later I realized I actually needed that. 2. Yep, good point. 3. That's not actually a guarantee because the initial capacity of the queue is not necessarily a power of 2. Thanks for the comments. \$\endgroup\$ – Tiberiu Savin Jul 23 '16 at 17:14
  • \$\begingroup\$ @TiberiuSavin For the sake of maintainability I strongly encourage you to keep the m_size around. \$\endgroup\$ – coderodde Jul 23 '16 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.