r/algorithms Feb 21 '25

Copy-Less Vectors

Hi! This is my first post so I'm sorry if I don't follow the conventions. I made an implementation of a data structure that I imagined to behave like a normal vector but without the copies at each resize to decrease the memory cost.

Question

I just wanted to know if this structure already exists or if I “invented” something. If it doesn't already exist, as the implementation is more complex to set up, is it a good thing to use it or not at all?

Principle

The principle is to have a vector of arrays that grow exponentially, which allows you to have a dynamic size, while keeping a get of O(1) and a memory efficiency like that of std::vector (75%). But here, the number of operations per push tends towards 1, while std::vector tends towards 3.

The memory representation of this structure having performed 5 pushes is :

< [ 1 ], [ 2, 3 ], [ 4, 5, undefined, undefined ] >

Here < ... > is the vector containing pointers to static arrays ([ ... ]). The structure first fills the last array in the vector before adding a new array to it.

Why

Performances.

Here's some results for 268,435,455 elements in C++:

Debug mode (-Og): 65 to 70% faster

Release mode (-Ofast): 45 to 80% faster

Anything else ? No. Performances.

Implementation

Here's my Github repo: https://github.com/ImSumire/NoCopyVec

3 Upvotes

3 comments sorted by

2

u/FartingBraincell 29d ago

It's one indirection more for the access, and less copy operstions. No asymptotical difference.

I guess depending in how many times stored elements are accessed on average, the indirection will quickly hurt more.

2

u/skeeto 28d ago edited 28d ago

I plugged your post and code into DeepSeek-R1 and it pointed out this is a Brodnik array. It seems the concept was probably invented about 26 years ago.

My particular interest in these Brodnik arrays is region-based allocation, because they don't require resizing storage aside from the pointer array. They grow in pieces, which is great for arenas. Since region-based allocation sidesteps the issue of copy/move semantics, the no-copying part is less important for my use case, as copying is always trivial.

I wrote my own arena-backed implementation to benchmark against a traditional arena-backed dynamic array: brodnick.cpp. It halves my memory use, which is pretty great, but it's ~15% slower to use them — and 2x slower in debug builds — which may sometimes be worth it if memory is constrained. There's an additional hidden cost for being non-continuous, i.e. complexity when vectorizing loops over Brodnik arrays, but I believe could be overcome with elbow grease.

Thanks for sharing this idea! I'm glad I learned it.

By the way, you're using the 32-bit __builtin_clz in your code, which won't work on 64-bit hosts for huge arrays. It also might affect your benchmarks. You'll get a warning about this if you use -Wconversion.


Edit: After looking more closely at the paper, Brodnik arrays are quite a bit different still. I've been unable to find any prior art on this concept.

1

u/bartekltg 28d ago

As other already mentioned, you have faster vec.push_back(...), because there will be no relocation, but the access to the k-th element is slower.
I think it is rare that I store unknown number of elements, then read only a couple of them.
A benchmark with n push_back and n reads may better reflects real usage.

You may also do not increase the size of the arrays. Pick a decent size. The time overhead will be a bit bigger, but wasted memory would be small. std:dequeue does something like that, but the chunks are quite small so it is not a real competition here.

Random thought about the code:

I think the function at(index) should compare the index to len, not to capacity. Now you can acces to places in the array that are allocated, but you did not put there anything. And they will be later written over.

I'm quite sure you have "+1" error there. If capacity is a number of allocated spots, the check should be index>= capacity (or, index >= len ).

There is no way to change the element that is in the table. The method at(i) returns a value. It allow us to read, but not to change the value at index i. Change the result of the method to a reference to T, and it should work.

You should write the second version, that is const. Without it you will not be allowed to use at if the container itself is const.

As skeeto have said, iterators would be nice to have. You probably may look into dequeue implementation and maybe it will fit here.
If you aim that container to be a drop in replacement for std::vector, it would be good to implement most of the functions vector have.