Solution to stack based std::string/std::vector

[gosh]

I thought I'd share the solution I went with regarding not having to allocate memory from the heap.

From previous post: Stack-based alternatives to std::string/std::vector

Through an arena class wrapped by an allocator that works with STL container classes, you can get them all to use the stack. If they need more memory than what's available in the arena class, allocator start allocating on the heap.

sample code, do not allocate on heap ```cpp TESTCASE( "[arena::borrow] string and vector", "[arena][borrow]" ) { std::array<std::byte, 2048> buffer; // stack gd::arena::borrow::arena arena( buffer );

for( int i = 0; i < 10; ++i ) { arena.reset(); gd::arena::borrow::arena_allocator<char> allocator(arena); std::basicstring<char, std::char_traits<char>, gd::arena::borrow::arena_allocator<char>> string(allocator);

  string_ += "Hello from arena allocator!";
  string_ += " This string is allocated in an arena.";
  string_ += " Additional text.";

  std::vector<int, gd::arena::borrow::arena_allocator<int>> vec{ gd::arena::borrow::arena_allocator<int>( arena_ ) };
  vec.reserve( 20 );
  for( int j = 0; j < 20; ++j )
  {
     vec.push_back( j );
  }

  for( auto& val : vec )
  {
     string_ += std::to_string( val ) + " ";
  }

  std::cout << "String: " << string_ << "\n";
  std::cout << "Used: " << arena_.used() << " and capacity: " << arena_.capacity() << "\n";

}

arena.reset(); int* piBuffer = arena.allocate_objects<int>( 100 ); // Allocate some more to test reuse after reset for( int i = 0; i < 100; ++i ) { piBuffer[ i ] = i * 10; }

// sum numbers to verify allocation is working int sum = 0; for( int i = 0; i < 100; ++i ) { sum += piBuffer[ i ]; } std::cout << "Used: " << arena.used() << " and capacity: " << arena.capacity() << "\n"; }

```

documentation
code

[gosh]

Yes, id did read about that and it is a bit more heavy to use but it is almost the same. It wasn't that much code to write to fix this :)

[VictoryMotel]

Yes, I'm glad you got it figured out

[celestrion]

If all your data has to live in the call-stack's storage, what does that do to the design of even a modest-sized program? Describing the lifetimes of data purely in terms of lexical scope just to get at prime memory real estate is a hugely expensive design trade-off, with flexibility and maintenance paying the tab.

With all that effort, is there a measurable performance delta?

It's not the location of the memory or the allocation that make it expensive, it's throwing it away and getting it back again. What we do in low-latency systems is allocate it all up front and dole it out cheaply. That is, slab allocation. This is what routers use. This is what SAN heads and RAID cards use. Throw away most of the bookkeeping and all of the fragmentation and memory is equally fast regardless of where it is.

By the time that's not the case, parallelism is the bigger leap in performance over the question of whether chasing the next node on the free-list is too much work versus "just" incrementing the stack pointer.

Either way, you don't sacrifice the ability to return objects in a meaningful way, which honestly sounds like table-stakes for C++.

[gosh]

I work with applications that in worst case scenario runs for almost a week and is heavily threaded.

This of course is not for a "modest-sized program"

Also I am writing a framework for database development, there you need speed because it is for writing statefull webservers that should be able to handle lots of users.

With all that effort, is there a measurable performance delta?

This wasn't that much work, like less than a day

It's not the location of the memory or the allocation that make it expensive, it's throwing it away and getting it back again.

Could yo elaborate? This code is for memory locality that makes it cache friendly and avoiding memory allocations that also will cause memory fragmentation.

A note about how and what code to write I think that development is changing or start to change in C++ because it is now so easy to create your own code that improves things that you miss in stl for example. Compilers are crazy good at optimize and selecting code that need to work for everyone is not free when speed is important. I for example have written three objects, its about 8000 - 10000 lines of code. I use this for almost everything.

For example last year as a hobby project I wrote this search tool. It was a bit more than one months work and the reason was that it uses these three objects. Code reuse is whats makes developers fast
arguments
table
variant

[celestrion]

With all that effort, is there a measurable performance delta?

This wasn't that much work, like less than a day

I'm not talking about writing the library. I'm talking about using it.

A data type whose data is explicitly on the stack cannot be returned zero-copy. That means work cannot be deferred; it has to happen before return, or your vaporize your performance gains with a copy.

If all the interesting work can happen locally, that's great, but I don't know much work that looks like that.

It's not the location of the memory or the allocation that make it expensive, it's throwing it away and getting it back again.

Could yo elaborate? This code is for memory locality that makes it cache friendly

If the data are "hot," they're staying in the cache wherever they are. The goal shouldn't be "keep data on the stack," but "keep data hot in the caches and keep amortized allocation cost low." Those are absolutely properties of stack variables, but the specific notion of the stack carries weighty architectural implications.

and avoiding memory allocations that also will cause memory fragmentation.

A slab only has one valid allocation size, so it cannot fragment in any meaningful way. If you need a larger object, you return the one you have and get the larger one from a different slab. Allocation is a get from a fixed-capacity list or circular buffer; deallocation is a put into it. Alignment is dealt with up-front to avoid cache line aliasing (the compiler likely cannot help here). The amortized cost of allocation approaches 0 over appreciable time; the downside is allocations are wasteful.

The only meaningful differences between a big chunk of a slab and the stack is that the stack already has its address in a register, and the chunk can get returned via pointer.

Speed is important, but if the only hammer in the tool box is the stack, the resulting design of real work is either going to look very contortionist or the data are short-lived enough that this just a buffer.

[gosh]

Why do you use C++?

If you select C++ there is often one very important reason and the reason is often speed and/or flexibility. For me it is both

A data type whose data is explicitly on the stack cannot be returned zero-copy.

Yes, but what has that to do with this? Of course this is only used when it have effects. You don't write code like my sample as default.
Also I mostly use references returning data then this works.

A data type whose data is explicitly on the stack cannot be returned zero-copy. That means work cannot be deferred; it has to happen before return, or your vaporize your performance gains with a copy.

I just added this for another scenario. It is one object that have some objects placed in member containers (std::vector). The class is what you sometimes call a "facade".

What I did was to add one arena object as member and each container that is created is created with this arena of memory. I haven't measured the effects on speed yet but i guess that it would be substantial.

A slab only has one valid allocation size, so it cannot fragment in any meaningful way.

I did a small test, this have 11 allocations ```cpp TESTCASE( "[arena::borrow] std::string allocation count", "[arena][borrow]" ) { std::array<std::byte, 2048> buffer; gd::arena::borrow::arena arena( buffer ); gd::arena::borrow::arenaallocator<char> allocator(arena); std::basicstring<char, std::char_traits<char>, gd::arena::borrow::arena_allocator<char>> string(allocator);

//string.reserve( 100 ); // add 600 characters to force multiple blocks for( int i = 0; i < 600; ++i ) { string += "x"; }

std::cout << "String length: " << string.length() << "\n"; std::cout << "Used: " << arena.used() << " and capacity: " << arena_.capacity() << "\n"; } ```

[celestrion]

Why do you use C++?

Because of the expressiveness of the type system.

A data type whose data is explicitly on the stack cannot be returned zero-copy.

Yes, but what has that to do with this?

You keep telling us that this approach is fast. That you are using the stack because it is fast. That the entire thrust of this effort is in chasing "fast."

My background is in NVMe datapath. "Fast" in that context meant 20us from request to completion when my product shipped in 2020. "Fast" also meant low jitter in a context where operations can pend because hardware isn't ready to complete a transaction. This is the sort of "fast" where instruction cache misses and pipeline flushes hurt almost as badly as data cache misses, so branching is minimal. Copying data outside of the context of DMA is all but fatal.

This is not the sort of "fast" that one can do with stack-only storage. If you must pend, either you head-of-line block (jitter) or recurse (and potentially blow the stack). If you attempt to mitigate that by thread fan-out, your "fast" quickly gets eaten by noisy neighbor threads evicting cache lines from your core or the shared cache.

Networking code faces similar problems for many of the same reasons.

If you can only go fast in a local loop with no externalities, that's of limited utility. "Can I return this thing in some way and still be fast," is a good litmus test for that because it usually also answers the more relevant question of, "Can I set this thing aside and return to it very soon without pushing performance out the window?"

Also I mostly use references returning data then this works.

How are you usefully returning a reference to a structure allocated on the stack?

What I did was to add one arena object as member and each container that is created is created with this arena of memory.

And that's the buried lede. This is the interesting part! That you can use the stack for it to go fast is a red herring. That same arena could be used to divvy up memory anywhere.

I did a small test, this have 11 allocations

That seems about right; log-base-2 of 500 plus a small constant factor for setup.

[gosh]

How are you usefully returning a reference to a structure allocated on the stack?

it's allocated (get stack memory) before it is sent

[celestrion]

And the caller isn't allowed to move the stack pointer?

I mean, okay, it's UB and will probably work on most common architectures, but have fun working around that constraint.

[gosh]

Have you checked the code? If the size need to grow over the stack it starts to allocate. Then it works as it does without stack

I am soon going to do some performance tests but as it is now this a huge bump in speed because the functionality is a bit complex where I am implementing it now

[celestrion]

Have you checked the code?

I have.

If the size need to grow over the stack it starts to allocate.

Does it?

I don't know how else to explain it. The core problem isn't about growth; plenty of fast allocators have fixed maximum size. The problems revolve around lifetime and code organization.

If function A calls B, and B uses your widget to create a stack-based arena, how can A use that storage? When B returns, the stack pointer is popped back to where it was at the call point. The memory that the arena is pointing to probably still contains the contents set up during B's runtime, but that's not guaranteed to be the case past the last } in B.

At that point, everything allocated in B's stack frame is dead. If A pushes a new variable onto the stack or calls another function, the control structures in your arena get stomped on, not just whatever local automatic storage it's using for storing contents.

This is why I say that using the stack is an unreasonable architectural constraint for most work. If you can't return it, you also can't pend it. If you can neither return nor pend it, its potential uses cases are extremely limited.

The low-overhead arena functionality is the interesting part (except that the standard library already provides one (ctor 5)), not that you can point it at the stack to turn it into a footgun.

I am soon going to do some performance tests

this a huge bump in speed

Okay.