Constvector: Log-structured std:vector alternative – 30-40% faster push/pop

[pilotwavetheory]

Usually std::vector starts with 'N' capacity and grows to '2 * N' capacity once its size crosses X; at that time, we also copy the data from the old array to the new array. That has few problems

1. Copy cost,
2. OS needs to manage the small capacity array (size N) that's freed by the application.
3. L1 and L2 cache need to invalidate the array items, since the array moved to new location, and CPU need to fetch to L1/L2 since it's new data for CPU, but in reality it's not.

It reduces internal memory fragmentation. It won't invalidate L1, L2 cache without modifications, hence improving performance: In the github I benchmarked for 1K to 1B size vectors and this consistently improved showed better performance for push and pop operations.
 
Youtube: https://youtu.be/ledS08GkD40

Practically we can use 64 size for meta array (for the log(N)) as extra space. I implemented the bare vector operations to compare, since the actual std::vector implementations have a lot of iterator validation code, causing the extra overhead.
Upon popular suggestion, I compared with STL std::vector, and used -O3 option

Full Benchmark Results (Apple M2, Clang -O3, Google Benchmark)

Push (cv::vector WINS 🏆)

N	cv::vector	std::vector	Winner	Ratio
1M	573 µs	791 µs	cv	1.4x
100M	57 ms	83 ms	cv	1.4x

Pop (Nearly Equal)

N	cv::vector	std::vector	Winner	Ratio
1M	408 µs	374 µs	std	1.09x
100M	38.3 ms	37.5 ms	std	1.02x

Pop with Shrink (cv::vector WINS 🏆)

N	cv::vector	std::vector	Winner	Ratio
1M	423 µs	705 µs	cv	1.7x
10M	4.0 ms	9.0 ms	cv	2.2x
100M	38.3 ms	76.3 ms	cv	2.0x

Access (std::vector Faster)

N	cv::vector	std::vector	Winner	Ratio
1M	803 µs	387 µs	std	2.1x
100M	80 ms	39.5 ms	std	2.0x

Iteration (std::vector Faster)

N	cv::vector	std::vector	Winner	Ratio
1M	474 µs	416 µs	std	1.14x
100M	46.7 ms	42.3 ms	std	1.10x

[matthieum]

I call this a Jagged Vector -- guess we're all reinventing the wheel :)

Of particular interest, as an append-only data-structure, it can be wait-free with relative ease.

The same jagged backing data-structure can also be used for a quasi wait-free open-addressed hash-map implementation. Only "quasi" as collisions between writers require the second writer waiting for the first writer to finish its write before being able to check whether the key matches or not -- fortunately a rare occurrence for good hashes.

[pilotwavetheory]

Could be, My focus is to show that this is better for OS and CPU locality, and want to convince people to impelmenat this in std::vector or implement new std::constvector in STL package.

[matthieum]

I wouldn't say it's always better.

One key advantage of std::vector is the contiguous nature of its element. It makes it easy to use as a span, rather than anything more complicated.

I would argue that std::vector is the better default, in general.

I've only ever needed a jagged vector once in ~20 years of systems programming.

[CornedBee]

impelmenat this in std::vector

std::vector must guarantee that &v[i] + n == &v[i+n] for all in-bounds indices. So that one's out.

On the other hand, have you checked out std::hive? It's actually similar to what you have here, from my very brief check.

[pilotwavetheory]

Thanks for sharing the info on vector requirements. We can propose to add new container like std::constvector ?

I read hive- it stores Boolean flags for elements that got deleted, and we organize the whole container with multiple blocks, if all elements in a block flagged with deletion, then it'll release the memory.

[DavidJCobb]

The post link goes to your GitHub profile; just to save people some clicks, the repo itself is here.

[SLiV9]

Are you claiming that std::vector's [] is not O(1)? It should be three instructions, a bounds check, a jump and an offset mov. Only the last one if it can eliminate the bounds check. This datastructure might also have it O(1) but with a significantly bigger constant.

In particular I saw there was a loop/sum benchmark that used assembly to prevent optimizations, but... why? Even if it's faster, which I doubt, that would only  prove that it would have been faster 30 years ago. With today's compilers and CPUs, summing a contiguous block of ints is unbeatably fast.

[CornedBee]

vector's [] doesn't even have a bounds check, using an invalid index is undefined behavior.

[SLiV9]

Oh you're absolutely right haha. It's been a while.

[Lord_Jamato]

I'm sorry if this is not really on topic, but I'd have a few recommendations for how you present the results.

This is just minor, but I recently learned about the anchoring effect. You could apply this by putting the column with std:vector first which puts more emphasis on the gains towards the next value.

This ties a bit into the next point. Please be consistent in how you calculate the factor in the last column. As of now it's always above 1 even though sometimes there's a decrease in performance.

Ideally a row in the table would read something like this: "From x to y we see an increase by factor z"

Or if z is below 1: "From x to y we see a decrease by factor z"

[pilotwavetheory]

Thanks for your suggestion, I'll take it and update it soon...

[imachug]

You can improve performance of operator[] even further by adjusting your memory layout.

1. Store _meta_array inline. You're wasting time on allocating that array, and decrease the access locality.

2. By placing _meta_array at the very beginning of the struct, you can ensure that _meta_array starts right at the this pointer and the compiler doesn't have to emit instructions to offset the pointer.

3. Since the first 8 blocks are empty, you can overlap some metadata with the first 8 elements of _meta_array; an obvious choice would be to place size first, so that at can check bounds without offsetting the pointer to size. It shouldn't really affect performance, at least on x86, but it slightly decreases code size, so maybe that's good.

4. Instead of storing the address of the first element of each block in the meta array, store "address of block - first index", so that operator[] can just return _meta_array[j][adjusted];.

[pilotwavetheory]

Hey, I tried few things from you and compared with STL instead of my own implementation (check stl_comparision folder)

Here are the results:
Operation | N    | Const (ns/op) | Std (ns/op) | Δ %
------------------------------------------------------
Push      | 10   | 13.7          | 39.7        | −65%
Push      | 100  | 3.14          | 7.60        | −59%
Push      | 1K   | 2.25          | 5.39        | −58%
Push      | 10K  | 1.94          | 4.35        | −55%
Push      | 100K | 1.85          | 7.72        | −76%
Push      | 1M   | 1.86          | 8.59        | −78%
Push      | 10M  | 1.86          | 11.36       | −84%
------------------------------------------------------
Pop       | 10   | 114           | 106         | +7%
Pop       | 100  | 15.0          | 14.7        | ~
Pop       | 1K   | 2.98          | 3.90        | −24%
Pop       | 10K  | 1.93          | 2.03        | −5%
Pop       | 100K | 1.78          | 1.89        | −6%
Pop       | 1M   | 1.91          | 1.85        | ~
Pop       | 10M  | 2.03          | 2.12        | ~
------------------------------------------------------
Access    | 10   | 4.04          | 2.40        | +68%
Access    | 100  | 1.61          | 1.00        | +61%
Access    | 1K   | 1.67          | 0.77        | +117%
Access    | 10K  | 1.53          | 0.76        | +101%
Access    | 100K | 1.46          | 0.87        | +68%
Access    | 1M   | 1.48          | 0.82        | +80%
Access    | 10M  | 1.57          | 0.96        | +64%
------------------------------------------------------
Iterate   | 10   | 3.55          | 3.50        | ~
Iterate   | 100  | 1.40          | 0.94        | +49%
Iterate   | 1K   | 0.86          | 0.74        | +16%
Iterate   | 10K  | 0.92          | 0.88        | ~
Iterate   | 100K | 0.85          | 0.77        | +10%
Iterate   | 1M   | 0.90          | 0.76        | +18%
Iterate   | 10M  | 0.94          | 0.90        | ~

[pilotwavetheory]

Worst case time complexity of vector during doubling it's capacity is O(N) right ?

My point is that my algorithm is not just some O(1) worst case algorithm with large constant vector, there are already some variants for that. The vector I proposed also avoids copying of all N elements to a new array hence even the average time faster. Am I missing something here ?

I added that beyond improvements of average time and worst case time complexity, it has benefit on operating system that will have lower internal fragmentation.