HomeWildfire Games

Cleanup CCmpRallyPointRenderer

Description

Cleanup CCmpRallyPointRenderer

Replace std::deque by std::vector
Replace some casts by cpp casts
Move the class and struct declaration to a separate file for clarity.
Fixes rP10704 by removing offending function
Refs #5288
Refs D1681

Reviewed by: @vladislavbelov

Differential Revision: https://code.wildfiregames.com/D1682

Event Timeline

elexis added a subscriber: elexis.Oct 2 2019, 7:52 PM

Replace std::deque by std::vector

Why chose a slower data structure if you could call pop_back?
https://en.cppreference.com/w/cpp/container/deque/pop_back

https://en.cppreference.com/w/cpp/container/deque

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end.
As opposed to std::vector, the elements of a deque are not stored contiguously:

https://en.cppreference.com/w/cpp/container/vector

Reallocations are usually costly operations in terms of performance.
This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted

It was asked by Vladislav too:

https://code.wildfiregames.com/D1682?id=7006#inline-32888
There is an erasing of elements from this container, and std::deque is faster by constant for such operation. So I think it'd be better to use std::deque here, some performance tests may help to decide.
Or as the article suggests: segments.pop_back();.

@vladislavbelov it seems std::deque was removed without a reason or performance consideration?
It's not trivial whether its preferable to have reallocations and contiguous memory or cheap insertion, it looks like it was changed from deque to vector to achieve Fixes rP10704 by removing offending function.

Stan added a comment.EditedOct 2 2019, 8:03 PM
In D1682#72623, @Stan wrote:

If you want more specific output https://pastebin.com/myEAnKEj

9000000 samples

cl.exe fine.cpp /EHsc

STD: Vector 'push_back' time:1.62
STD: Deque 'push_back' time: 2.193
STD: Vector 'emplace_back' time: 1.551
STD: Deque 'emplace_back' time: 2.222
STD: Vector 'erase' time: 1.236
STD: Deque 'erase' time: 10.948

cl.exe fine.cpp /EHsc /O1

STD: Vector 'push_back' time:0.428
STD: Deque 'push_back' time: 0.771
STD: Vector 'emplace_back' time: 0.468
STD: Deque 'emplace_back' time: 0.689
STD: Vector 'erase' time: 0.074
STD: Deque 'erase' time: 1.025

cl.exe fine.cpp /EHsc /O2

STD: Vector 'push_back' time:0.297
STD: Deque 'push_back' time: 0.647
STD: Vector 'emplace_back' time: 0.341
STD: Deque 'emplace_back' time: 0.64
STD: Vector 'erase' time: 0.029
STD: Deque 'erase' time: 0.62

cl.exe fine.cpp /EHsc /OX

STD: Vector 'push_back' time:0.299
STD: Deque 'push_back' time: 0.669
STD: Vector 'emplace_back' time: 0.345
STD: Deque 'emplace_back' time: 0.641
STD: Vector 'erase' time: 0.027
STD: Deque 'erase' time: 0.628

I guess that's one profiling comment ?

About the UB fix, the function was unused.

elexis added a comment.EditedOct 3 2019, 9:53 AM

Ah sorry, I didn't see that profiling comment.

Without reading the code the results are unexpected, because the vector insertion is described as slower in the specs and dequeue as faster as it uses the heap as mentioned above.
Also vector is only slow if reallocation happens, and that only happens if it didnt reserve memory yet.

So looking at your code, the first thing that happens in

int samples = 10000;
std::clock_t begin = clock();
for(int i = 0; i < samples ; ++i)
{
    segmentsVector.push_back(SVisibilitySegment(true, 0, 1000 - 1));
}

So it reserves a size of 1000 items.
So you get the memory of 1000 items and the vector wont lose that throughout its lifetime.

But thats not a representative test, because in the rallypoint renderer you dont preallocate 1000 items, but you reallocate them each time an item is added, no?

Edit: nope, it doesnt drop the added items, so why the heck is vector faster?

Stan added a comment.Oct 3 2019, 9:57 AM

Most of the time everything is reset, because you change the flag position completely. The only case where you don't reset the vector is when you shift click IIRC.

elexis added a comment.Oct 3 2019, 9:59 AM

It could be that the compiler optimizer recognizes that the vector will use 1000 items and adds a reserve(1000).
A test ruling that out would be to measure the numbers in the code modified itself.

elexis added inline comments.Oct 3 2019, 10:03 AM
/ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp
356

m_VisibilitySegments.emplace_back()

I've run this test:

Index: source/main.cpp
===================================================================
--- source/main.cpp	(revision 23032)
+++ source/main.cpp	(working copy)
@@ -679,6 +679,15 @@
 	}
 #endif // OS_UNIX
 
+	{
+	    std::vector<int> vec;
+	    for(int i = 0; i < 1000; ++i)
+	    {
+		    debug_printf("vec capacity %lu\n", vec.capacity());
+	        vec.push_back(i);
+	    }
+	}
+
 	EarlyInit();	// must come at beginning of main
 
 	RunGameOrAtlas(argc, const_cast<const char**>(argv));

while I can't confirm that the optimizer allocated all 1000 elements in the beginning,
it does allocate twice the size each time.

i.e. 1, 2, 4, 8, 16, 32, 64, ..., 1024.

So after the 512th element is added, it will reserve 512 more items.

vec capacity 0
vec capacity 1
vec capacity 2
vec capacity 4
vec capacity 4
vec capacity 8
vec capacity 8
vec capacity 8
vec capacity 8
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 16
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 32
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 64
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 128
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 256
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 512
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024
vec capacity 1024

The larger the sample size, the more performant std::vector will become.

So what are realistic numbers of vector / dequeue items? I haven't looked at the code, but if it's something like 5, then you'll get 4 reallocations (that would be expected to be slower than dequeue which doesnt reallocate). But reading from it again may be slower since for dequeue the memory isnt contiguous.

A more meaningful test would be to measure inside the game.
One can implement both vector and dequeue at the same time and measure how long each allocation consumes.

But thats also shady, since I sometimes noticed operation1(value); operation2(value) and operation2(value); operation1(value) sometimes end up with the first call being faster in both cases.
(That can be reduced by running operation1(value); operation2(value); operation2(value); operation1(value), but doesn't make it particularly more trustworthy)

Here another test with time measured per item:

Index: source/main.cpp
===================================================================
--- source/main.cpp	(revision 23032)
+++ source/main.cpp	(working copy)
@@ -679,6 +679,27 @@
 	}
 #endif // OS_UNIX
 
+	{
+		#include <chrono>
+
+		struct SVisibilitySegment {
+		    bool m_Visible;
+		    size_t m_StartIndex;
+		    size_t m_EndIndex; // Inclusive
+		};
+
+	    std::vector<SVisibilitySegment> vec;
+	    for(int i = 0; i < 80; ++i)
+	    {
+	        auto begin = std::chrono::high_resolution_clock::now();
+	        vec.emplace_back();
+	        debug_printf(
+	        	"vec capacity %lu, took %lu\n",
+				vec.capacity(),
+				std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - begin).count());
+	    }
+	}
+
 	EarlyInit();	// must come at beginning of main
 
 	RunGameOrAtlas(argc, const_cast<const char**>(argv));
vec capacity 1, took 201
vec capacity 2, took 2257
vec capacity 4, took 255
vec capacity 4, took 51
vec capacity 8, took 217
vec capacity 8, took 57
vec capacity 8, took 46
vec capacity 8, took 46
vec capacity 16, took 2494
vec capacity 16, took 51
vec capacity 16, took 50
vec capacity 16, took 46
vec capacity 16, took 51
vec capacity 16, took 46
vec capacity 16, took 52
vec capacity 16, took 47
vec capacity 32, took 339
vec capacity 32, took 51
vec capacity 32, took 48
vec capacity 32, took 45
vec capacity 32, took 59
vec capacity 32, took 45
vec capacity 32, took 60
vec capacity 32, took 52
vec capacity 32, took 48
vec capacity 32, took 57
vec capacity 32, took 46
vec capacity 32, took 45
vec capacity 32, took 59
vec capacity 32, took 51
vec capacity 32, took 58
vec capacity 32, took 51
vec capacity 64, took 489
vec capacity 64, took 45
vec capacity 64, took 47
vec capacity 64, took 46
vec capacity 64, took 46
vec capacity 64, took 46
vec capacity 64, took 65
vec capacity 64, took 45
vec capacity 64, took 45
vec capacity 64, took 47
vec capacity 64, took 46
vec capacity 64, took 52
vec capacity 64, took 48
vec capacity 64, took 48
vec capacity 64, took 59
vec capacity 64, took 49
vec capacity 64, took 56
vec capacity 64, took 45
vec capacity 64, took 45
vec capacity 64, took 59
vec capacity 64, took 46
vec capacity 64, took 45
vec capacity 64, took 59
vec capacity 64, took 50
vec capacity 64, took 56
vec capacity 64, took 45
vec capacity 64, took 45
vec capacity 64, took 59
vec capacity 64, took 45
vec capacity 64, took 45
vec capacity 64, took 46
vec capacity 64, took 47
vec capacity 128, took 2839
vec capacity 128, took 45
vec capacity 128, took 62
vec capacity 128, took 47
vec capacity 128, took 51
vec capacity 128, took 51
vec capacity 128, took 45
vec capacity 128, took 47
vec capacity 128, took 59
vec capacity 128, took 45
vec capacity 128, took 66
vec capacity 128, took 45
vec capacity 128, took 45
vec capacity 128, took 70
vec capacity 128, took 45
vec capacity 128, took 47

A comparison with deque:

Index: source/main.cpp
===================================================================
--- source/main.cpp	(revision 23032)
+++ source/main.cpp	(working copy)
@@ -679,6 +679,39 @@
 	}
 #endif // OS_UNIX
 
+	{
+		#include <chrono>
+
+		struct SVisibilitySegment {
+		    bool m_Visible;
+		    size_t m_StartIndex;
+		    size_t m_EndIndex; // Inclusive
+		};
+
+	    std::vector<SVisibilitySegment> vec;
+	    std::deque<SVisibilitySegment> deq;
+
+	    for(int i = 0; i < 80; ++i)
+	    {
+	        auto begin = std::chrono::high_resolution_clock::now();
+	        vec.emplace_back();
+	        debug_printf(
+	        	"vec capacity %lu, took %lu\n",
+				vec.capacity(),
+				std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - begin).count());
+	    }
+
+	    for(int i = 0; i < 80; ++i)
+	    {
+	        auto begin = std::chrono::high_resolution_clock::now();
+	        deq.emplace_back();
+	        debug_printf(
+	        	"deq %d took %lu\n",
+				i,
+				std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - begin).count());
+	    }
+	}
+
 	EarlyInit();	// must come at beginning of main
 
 	RunGameOrAtlas(argc, const_cast<const char**>(argv));
deq 0 took 155
deq 1 took 47
deq 2 took 42
deq 3 took 70
deq 4 took 40
deq 5 took 43
deq 6 took 43
deq 7 took 39
deq 8 took 40
deq 9 took 42
deq 10 took 56
deq 11 took 39
deq 12 took 41
deq 13 took 45
deq 14 took 41
deq 15 took 39
deq 16 took 43
deq 17 took 42
deq 18 took 42
deq 19 took 49
deq 20 took 758
deq 21 took 44
deq 22 took 44
deq 23 took 52
deq 24 took 46
deq 25 took 43
deq 26 took 39
deq 27 took 48
deq 28 took 40
deq 29 took 46
deq 30 took 100
deq 31 took 40
deq 32 took 39
deq 33 took 40
deq 34 took 39
deq 35 took 54
deq 36 took 44
deq 37 took 39
deq 38 took 46
deq 39 took 39
deq 40 took 40
deq 41 took 173
deq 42 took 40
deq 43 took 39
deq 44 took 43
deq 45 took 44
deq 46 took 39
deq 47 took 41
deq 48 took 40
deq 49 took 40
deq 50 took 41
deq 51 took 39
deq 52 took 40
deq 53 took 40
deq 54 took 40
deq 55 took 39
deq 56 took 73
deq 57 took 39
deq 58 took 40
deq 59 took 39
deq 60 took 40
deq 61 took 41
deq 62 took 206
deq 63 took 40
deq 64 took 39
deq 65 took 40
deq 66 took 40
deq 67 took 43
deq 68 took 45
deq 69 took 40
deq 70 took 85
deq 71 took 39
deq 72 took 40
deq 73 took 41
deq 74 took 40
deq 75 took 53
deq 76 took 39
deq 77 took 45
deq 78 took 40
deq 79 took 39

Notice that this doesn't tell us anything about the impact of memory layout, which may or may not be better with the vector.

vladislavbelov added a comment.EditedOct 3 2019, 2:33 PM

My result on macOS (clang-11.0.0) for https://code.wildfiregames.com/P184 (output doubles are in microseconds):

NUMBER_OF_ELEMENTS = 10
  deque.emplace_back:	0.225
  vector.emplace_back:	0.714
  deque.push_back:	0.237
  vector.push_back:	0.714
  deque.operator[]:	0.013
  vector.operator[]:	0.004
NUMBER_OF_ELEMENTS = 20
  deque.emplace_back:	0.272
  vector.emplace_back:	0.856
  deque.push_back:	0.286
  vector.push_back:	0.853
  deque.operator[]:	0.027
  vector.operator[]:	0.007
NUMBER_OF_ELEMENTS = 30
  deque.emplace_back:	0.300
  vector.emplace_back:	0.877
  deque.push_back:	0.323
  vector.push_back:	0.866
  deque.operator[]:	0.040
  vector.operator[]:	0.011
NUMBER_OF_ELEMENTS = 40
  deque.emplace_back:	0.348
  vector.emplace_back:	0.971
  deque.push_back:	0.364
  vector.push_back:	0.966
  deque.operator[]:	0.058
  vector.operator[]:	0.013
NUMBER_OF_ELEMENTS = 50
  deque.emplace_back:	0.378
  vector.emplace_back:	0.998
  deque.push_back:	0.403
  vector.push_back:	0.982
  deque.operator[]:	0.072
  vector.operator[]:	0.019
NUMBER_OF_ELEMENTS = 60
  deque.emplace_back:	0.407
  vector.emplace_back:	1.017
  deque.push_back:	0.442
  vector.push_back:	1.011
  deque.operator[]:	0.084
  vector.operator[]:	0.022
NUMBER_OF_ELEMENTS = 70
  deque.emplace_back:	0.439
  vector.emplace_back:	1.181
  deque.push_back:	0.472
  vector.push_back:	1.166
  deque.operator[]:	0.096
  vector.operator[]:	0.023
NUMBER_OF_ELEMENTS = 80
  deque.emplace_back:	0.472
  vector.emplace_back:	1.186
  deque.push_back:	0.499
  vector.push_back:	1.177
  deque.operator[]:	0.115
  vector.operator[]:	0.027
NUMBER_OF_ELEMENTS = 90
  deque.emplace_back:	0.504
  vector.emplace_back:	1.216
  deque.push_back:	0.541
  vector.push_back:	1.246
  deque.operator[]:	0.126
  vector.operator[]:	0.033
NUMBER_OF_ELEMENTS = 100
  deque.emplace_back:	0.556
  vector.emplace_back:	1.256
  deque.push_back:	0.574
  vector.push_back:	1.246
  deque.operator[]:	0.139
  vector.operator[]:	0.033
NUMBER_OF_ELEMENTS = 1000
  deque.emplace_back:	4.953
  vector.emplace_back:	5.255
  deque.push_back:	5.034
  vector.push_back:	5.252
  deque.operator[]:	1.353
  vector.operator[]:	0.370

Now the question is what's the ratio between number of real inserts and real calls by index.

/ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp
356

It'd be faster to make it like:

if (index >= m_VisibilitySegments.size())
{
    m_VisibilitySegments.resize(index - m_VisibilitySegments.size() + 1);
}

The same above and below.

vladislavbelov added inline comments.Oct 3 2019, 2:37 PM
/ps/trunk/source/simulation2/components/CCmpRallyPointRenderer.cpp
356

UPD. m_VisibilitySegments.resize(index + 1);.

Stan added a comment.Oct 3 2019, 3:21 PM

It doesn't like your testing code, only works properly on mingw32 https://code.wildfiregames.com/P185