_- Faster C++

Remember... In your youngly years... You're sitting in your classroom listening carefully to your computer science teacher. Standing there, all smiling, he explains that you can calculate its performance, even without having to implement and run it. Pseudo-code will do. Amazed by such a wonder, you take good note of this information, and keep it preciously in the back of your mind. Time has passed. You graduated and developped many pieces of software with this belief that reduced time complexity means increased performance. Prepare to get shaken! The following paragraphs will shatter everything you tought you knew. I will compare the speed of a [key, value] pair retrieval in two arrays versus a binary tree. An array is the simplest data structure. While a binary tree is quite a smart data structure, with various implementation variations. In the GCC STL, the Standard Template Library, the binary tree is used within the map container implementation. To be precise, the red-black tree variation is implemented. The data access complexity in an array is linear, while it is just logarithmic in the red-black tree. Now to give you an idea, it means that if 1,000 elements are stored in these data structures :   - In an array, it could take up to 1,000 operations to retrieve a single element.   - In a map, it could only take up to log₂(1,000) = 10 operations to retrieve a single element! So one would logically expect the map to be way faster than the arrays in all pratical use cases. But the truth is that the arrays outperform the map! This stands true even in the worst case scenatio, where the last elements of the array are to be retrieved! So much that developers who need performance actually never use the STL map, and prefer two side-by-side arrays. This is demonstrated in the vector_map class from the EASTL library, from the Electronics Arts game editor. Researchers scratch their head targeting better algorithmic complexities. But a better complexity is just a factor among others. It is not a predictor for better performance. I always recommend to actually measure the performance rather than trying to predict it. Because hardware nowadays is so complex that predicting performance is near-impossible. This all has to do with the hardware. Algorithmic complexity might be right asymptotically. But in practice, the naive implementation takes better advantage of the hardware capabilities. In fact, the array has the very best memory access pattern: a linear traversal. Now keep this in mind when you will code your own algorithms ;)