In this project, I was requested to build an application to manage Queues (something like the ones you find when you want to view the latest Blockbuster movie). OK, It sounds simple, use a STL queue.
Unfortunately, this is not the whole requirement. Being a graphical application, it requested to refresh the screen from time to time showing all the items in the queue.
After some research I was not able to find a way to access elements inside the queue, only the Front and Back elements were accessible [if this is possible, let me know]. So, I had to take a look at other containers in STL in order to be able to get the functionality with good performance.
I have selected 4 containers to accomplish this task : Queue (Only to measure it's performance), Lists, Vectors and Deques.
All of them included members to work like Queues:
- Queue: push(int), front(), pop()
- List: push_back(int), front() and pop_front()
- Vector: push_back(int), front() and erase(vector::begin())
- Deque: push_back(int), front() and pop_front()
I performed 2 tests as follows:
1. Pop and Push elements
This test consisted of adding 50'000,000 integer elements to the end of the container, performing a sum of all elements starting from the first one and removing the First element (As a queue works).
Compiling the application to allow profiling with gprof, I get the following results (Please note I resumed them):
i %Time self Child name
[1] 98.2 0.00 16.76 main [1]
0.81 5.27 1/1 testList() [2]
0.78 5.04 1/1 testVector() [3]
0.88 1.75 1/1 testQueue() [6]
0.73 1.50 1/1 testDeque() [7]
[2] 35.6 0.81 5.27 1 testList() [2]
[3] 34.1 0.78 5.04 1 testVector() [3]
[6] 15.4 0.88 1.75 1 testQueue() [6]
[7] 13.1 0.73 1.50 1 testDeque() [7]
As we can see from this results, the best performance was accomplished surprisingly by the Deque (honestly, I thought queues were better) followed by Queues and finally Lists and Vectors, which doubles the execution percent time of the other two.
Why causes Lists and Vectors be that slow? Deeper analysis of the profile results shown that for Lists, most overhead is caused by adding elements to the end of the list (15.5%) and removing elements (12.6%). Getting the first element was really quick, only 2.7% of the whole execution time. Checking Vectors, overhead is caused by the function erase(), about (24.3%) of the total execution time. It looks like vectors don't like to remove their elements. Accessing first element and adding was quick also (3.3%) and (2.8%) respectively.
There's no much to say about Queues and Deques; their performance was similar, but deques outperform queues when removing elements (1.2%) vs (2.0%)
2. Go through the elements
For this test, I will get rid of the insertion/removal of elements in the container as this will happen about 3-4 seconds. I will focus on iteration through the container to display all queue elements. 100 Elements will be added to the queue and system will iterate 500.000 times the whole list.
Performing the application profiling the following results are obtained:
i %Time self Child name
[1] 98.2 0.00 8.28 main [1]
0.71 2.38 1/1 testVectorIterate() [2]
0.51 2.57 1/1 testDequeIterate() [3]
0.66 1.39 1/1 testListIterate() [4]
0.00 0.06 1/1 populate() [33]
[2] 36.7 0.71 2.38 1 testVectorIterate() [2]
[3] 36.5 0.51 2.57 1 testDequeIterate() [3]
[4] 24.4 0.66 1.39 1 testListIterate() [4]
From above results we can see that Iterating linearly the contained was performed faster by the List (24.4%) of the total execution time, followed by Deque (36.5%) and Vector(36.5%).
As you can see in previous example, although we were supposed to implement a Queue, the best option was not the Queue but the List, because, subtle in the requirements, the behavior we wanted was like a list and the bottelneck was not to pop or push elements but to go through them.
From this analysis I can conclude that we can't guide only by the obvious (There's needed something like a Queue, ok, let's use a Queue). Critical areas of an application must be profiled carefully and memory checking tools must be used to ensured that not only the application runs faster but also manage properly resources.
Unfortunately, this is not the whole requirement. Being a graphical application, it requested to refresh the screen from time to time showing all the items in the queue.
After some research I was not able to find a way to access elements inside the queue, only the Front and Back elements were accessible [if this is possible, let me know]. So, I had to take a look at other containers in STL in order to be able to get the functionality with good performance.
I have selected 4 containers to accomplish this task : Queue (Only to measure it's performance), Lists, Vectors and Deques.
All of them included members to work like Queues:
- Queue: push(int), front(), pop()
- List: push_back(int), front() and pop_front()
- Vector: push_back(int), front() and erase(vector::begin())
- Deque: push_back(int), front() and pop_front()
I performed 2 tests as follows:
1. Pop and Push elements
This test consisted of adding 50'000,000 integer elements to the end of the container, performing a sum of all elements starting from the first one and removing the First element (As a queue works).
Compiling the application to allow profiling with gprof, I get the following results (Please note I resumed them):
i %Time self Child name
[1] 98.2 0.00 16.76 main [1]
0.81 5.27 1/1 testList() [2]
0.78 5.04 1/1 testVector() [3]
0.88 1.75 1/1 testQueue() [6]
0.73 1.50 1/1 testDeque() [7]
[2] 35.6 0.81 5.27 1 testList() [2]
[3] 34.1 0.78 5.04 1 testVector() [3]
[6] 15.4 0.88 1.75 1 testQueue() [6]
[7] 13.1 0.73 1.50 1 testDeque() [7]
As we can see from this results, the best performance was accomplished surprisingly by the Deque (honestly, I thought queues were better) followed by Queues and finally Lists and Vectors, which doubles the execution percent time of the other two.
Why causes Lists and Vectors be that slow? Deeper analysis of the profile results shown that for Lists, most overhead is caused by adding elements to the end of the list (15.5%) and removing elements (12.6%). Getting the first element was really quick, only 2.7% of the whole execution time. Checking Vectors, overhead is caused by the function erase(), about (24.3%) of the total execution time. It looks like vectors don't like to remove their elements. Accessing first element and adding was quick also (3.3%) and (2.8%) respectively.
There's no much to say about Queues and Deques; their performance was similar, but deques outperform queues when removing elements (1.2%) vs (2.0%)
2. Go through the elements
For this test, I will get rid of the insertion/removal of elements in the container as this will happen about 3-4 seconds. I will focus on iteration through the container to display all queue elements. 100 Elements will be added to the queue and system will iterate 500.000 times the whole list.
Performing the application profiling the following results are obtained:
i %Time self Child name
[1] 98.2 0.00 8.28 main [1]
0.71 2.38 1/1 testVectorIterate() [2]
0.51 2.57 1/1 testDequeIterate() [3]
0.66 1.39 1/1 testListIterate() [4]
0.00 0.06 1/1 populate() [33]
[2] 36.7 0.71 2.38 1 testVectorIterate() [2]
[3] 36.5 0.51 2.57 1 testDequeIterate() [3]
[4] 24.4 0.66 1.39 1 testListIterate() [4]
From above results we can see that Iterating linearly the contained was performed faster by the List (24.4%) of the total execution time, followed by Deque (36.5%) and Vector(36.5%).
As you can see in previous example, although we were supposed to implement a Queue, the best option was not the Queue but the List, because, subtle in the requirements, the behavior we wanted was like a list and the bottelneck was not to pop or push elements but to go through them.
From this analysis I can conclude that we can't guide only by the obvious (There's needed something like a Queue, ok, let's use a Queue). Critical areas of an application must be profiled carefully and memory checking tools must be used to ensured that not only the application runs faster but also manage properly resources.
Comments
just registered and put on my todo list
hopefully this is just what im looking for looks like i have a lot to read.
just signed up and wanted to say hello while I read through the posts
hopefully this is just what im looking for looks like i have a lot to read.