![]() ![]() The random access results are shown in Figure 5b.įigure 5b. ![]() You can see that there is no much difference in the results of up to 100,000 elements, but than the access to the deque elements slows down in contrast to all other structures. Visual C++ 2022. Random access of double float-point values (nanoseconds per element). The random access results are shown in Figure 5a.įigure 5a. There is some diffrence, but it is not as dramatic as in Visual C++: for the number of elements 5 million and more, deque takes over twice as much time as DeVector. Random insert of double floating-point values (microseconds per element). In Figure 4b, the random insertion results are shown.įigure 4b. and Boost devector, it takes about 0.85s įor random insertion, the advantage double-ended vector over std::deque is obvious.for std::vector and Boost devector, it takes 1 hour and 5 minutes.What it means in practice for creating a structure of 5 million elements: At the same time, insertion into a deque is on average 7 times slower than into a DeVector, which increases to 14 times for 5 million elements. It shows that random insertion into a vector or Boost devector is about twice as slow as into a DeVector, which uses balanced insertion. In Figure 4a, the random insertion results are shown.įigure 4a. In GCC 11.2, the following command line was used: When compiled in Visual C++ 2022, the following options were used: The code was executed on a PC with Intel i7-4790, 3.6GHz processor, 16GB RAM. I am presenting results for both compilers. Then I tested in GCC 11.2 with C++17 and the results were not so pronounced. General ObservationĪt first, I tested devector in Visual C++ 2022 and saw major advantage in using devector. I have included my own implementation, which I call DeVector, where both insertion and deletion are balanced. Unfortunately, in the Boost implementation ( Boost devector), the insertion is not balanced and the benchmarks show it. By using balanced devector, the insertion time into a flat map can be cut by half in comparison with time used by vector. By using balanced insertion, we will cut the time by half! If a devector used to create a flat map, which contains "key-value" pairs as elements and binary search is used to find the right element. Imagine if a devector is build using random insertion of elements. In Figure 3, the basic idea of balanced insertion is illustrated.įigure 3. If it is in the middle, either option will do. If it is closer to the beginning, then option 2 (backwards). If it is closer to the end of the data, then option 1 (forward). Which option should be chosen? it depends on the position of the element. to move the elements in front backwards.When an element is inserted into a vector, there is only one option - to move the rest of the elements forward, by increasing their addresses in memory. One issue that should be considered is insertion. Special Consideration: Balanced Insertion The headroom is used for push_front and the tail capacity for push_back if there is not enough room for either of them, usually a new memory slot can be reserved, which can be, for instance, three times the size of the required data, which will be positioned in the middle of the reserved slot. The data can grow in both directions, so that push_front as well as push_back can be easily performed. If data is positioned roughly in the middle of the reserved space, so that it can grow in both directions, we end up with double-ended vector or devector, which is shown in Figure 2.įigure 2. The issue with the vector is that it is easy to append data to the end of a vector ( push_back operation), but not to the beginning. That allows not to allocate memory too often, as the data increases. The newly allocated space is usually greater than required (by a factor between 1.5 or 2.0). If the data needs more space than the capacity, the new space with increased capacity should be allocated. As the data grows, the capacity should increase. The data space always starts with the start of the reserved memory, the size of which is called capacity. In Figure 1, the std::vector memory reservation is shown.įigure 1. The double-ended vector idea is rather simple: if in a vector the data starts with the beginning of the pre-allocated space, in a double-ended vector the data is positioned relatively in the middle, which means that for a while new items can be pushed at both ends without re-allocating space or moving the elements. Some implementations are done by Lars Greger Nordland Hagen , Valasiadis Fotios and there is also a Boost implementation. Double-ended vector (devector) has been discussed a few times. ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |