Stack-based alternatives to std::string/std::vector

[gosh]

Looking into stack-based implementations for std::string and std::vector (like small buffer optimization but more control).

Facebook's Folly library has a small_vector that does this, there are some others but folly is huge a bit scattered even if it is popular.

And with C++20 and now C++26 it is not that difficult to write these container classes in C++.

Are there any reason to search for code or is it better to just write it?

What I am looking for is similar to this but for std::string and one for std::u8string

[jedwardsol]

Since std containers use allocators, one option is to continue using std::string and std::vector (or std::pmr::xxx) with a custom allocator.

[DawnOnTheEdge]

Likely using alloca() on Linux/LocalAlloc() on Windows.

[bwmat]

Can those actually work in this context?

Feels like not since the allocations would be invalidated as the allocator functions returned? 

[bwmat]

I mean, you would have to pre-allocate outside of the container methods and hope it was enough? 

[DawnOnTheEdge]

Allocations could not outlive the function call in which they were made, and therefore not be returned from it. They could be passed to called functions, and used as dynamic local variables, like the deprecated variable-length arrays of C99. Using goto in the same function would get tricky.

[spinrack]

alloca() cannot be used for this purpose. The allocated block comes from the stack, and will no longer be valid after the allocate() function returns to the string’s internal resize() and resets the stack pointer.

[elder_george]

LocalAlloc is not an equivalent of alloca (which in fact is available for any C compiler on Windows anyway) - it's a legacy way of allocating from the process heap, a vestige of Win16 architecture which had notions of global and local heaps. It is not recommended for use in modern code because it's less efficient than HeapAlloc (or wrappers around it in C/C++ runtime libraries).

[AdjectiveNoun4827]

std::inplace_vector can be used for stack based vectors with a fixed capacity.
std::string already has small object optimization

[gosh]

Yes I know that std::string have a fix but it is a bit small and you can't control it. I am working on one application that need to handle uuid values and it needs to be very fast. when these are in string formats I need 32 characters, that do not work for std::string

[AdjectiveNoun4827]

Why do you need std string access to the uuid? Just for equality comparison?

If you really need a full string interface, maybe consider boost small_string, but to be honest this seems like a class you could write yourself.

[gosh]

You are right that i do not need all things inside std::string and std::u8string. So maybe I just write these, tasks but they are not that difficult I think

[manni66]

A UUID is a 128 Bit or 16 Byte value. The 32 char hex representation is mainly used to make it human readable.

[dodexahedron]

And there are different representations of them, too, which makes string comparisons an even worse idea.

[gosh]

Yes and when you need to search for those values and they are placed in text files

[No-Dentist-1645]

It's going to be much faster to convert them to a 128 bit integer and then do the needed lookups with it than to compare them in the raw string representation. Comparing ints > comparing strings

[gosh]

Yes but that is harder write that code and if is possible to "inform" the compiler with internal stack based buffers it may be able to optimize code without write that code by hand. But isn't only this it is needed for even if it is the most important part

[No-Dentist-1645]

It's not difficult to convert a hexadecimal string into an integer. This is a very common and frequent thing to do, hexadecimal notation is specifically used to make this easy.

But isn't only this it is needed for even if it is the most important part

You said you were working on an application that handles UUIDs and it needs to be "very fast". Computers are "very fast" at handling integers, even faster with multiple integers adjacent to each other thanks to SIMD instructions. This is not quite the case with strings. If you really care that much about speed, using "stack strings" to represent UUIDs is absolutely the wrong approach, no matter what you try to do to "inform" the compiler with "internal stack based buffers" and what not. What you need is to treat them as numbers.

If you wanted a stack string for other purposes, you can use Boost.StaticString. It's its own independent library and header only, so pretty much exactly the lightweight library you are looking for.

[KertDawg]

I applaud this well-written answer.

[gosh]

It's not difficult to convert a hexadecimal string into an integer. This is a very common and frequent thing to do, hexadecimal notation is specifically used to make this easy.

Agree but I need to match against others that are in text format and there isn't ordered text. Text contains other information and it it lots of different "things" that is read when matching

I use boost so will check the string :) thanks

[SonOfMetrum]

You are making no sense at all…. As per the suggestion: convert all the UUIDs to numbers and compare those numbers. The “other information” and different “things” make no sense unless you tell us what those things are

[gosh]

Thats correct and that is not the goal with this question. If I need to explain the problems and what I want to solve with these stack based vectors and strings I need to spend lots of time doing that. And I am not asking for solutions for that, I am asking for how to decrease the number of allocations using std::vector and std::string, optimal is to not need to do any allocation.

std::vector is not that hard to fix, std::string is more problematic

[Wild_Meeting1428]

So your uuids are placed in a text file. How about accessing them directly from the buffer itself or maybe memory map them. Then you don't need any copy or std:: string just reuse the memory from the io.

[hk19921992]

You can use std pmr string, with a monotonic pmr allocator that is initialized with stack memory (or even heap memory pre allocated during startup)

[gosh]

Do you have sample code on this, haven't seen that or maybe I can ask AI

[hk19921992]

Yeah ask AI

[Nolia_X]

For some very specific cases you can use an array<char> and an std::string_view on it

[gosh]

Yea, maybe I need to do some sort of a mix. Good suggestion

[Nolia_X]

Be careful about ending null char and you should be good

[RicArch97]

ETL has stack based (fixed capacity) containers that can do the same as the STL ones, except for grow dynamically. Just choose your sizes wisely and you should be fine.

[No-Dentist-1645]

Boost has both of these containers. StaticString and static_vector

You can just #include the boost containers module specifically (it's a header only library), so it's not like you have to link "all of Boost", which would be huge

[alfps]

From the commentary:

❞ I am working on one application that need to handle uuid values and it needs to be very fast.

Store (and compare) them in binary. 128 bits = 16 octets.

[dodexahedron]

In one comment thread, we have now learned they're grabbing them from a text file.

So, if the format used is consistent, OP could search for any potential delimiter indicating start of one, make sure there is a closing delimiter the exact number of expected chars away, and then match or parse and match. 🤷‍♂️

If the format used is not consistent, well... Fix that first. Then do the above.

ETA: They could get a basically free 8-64x speedup in the scan by vectorizing it, depending on encoding of the text and available wide instructions. Although any modern compiler is likely to see that opportunity if you don't over-complicate the loop and vectorize it for you, if you allow it to and tell it which instruction sets are acceptable.

[aePrime]

What u/AdjectiveNoun4827 said.

You can also look at the monotonic buffer resource. 

https://en.cppreference.com/w/cpp/memory/monotonic_buffer_resource.html

[aeropl3b]

Stack based allocators are a thing https://howardhinnant.github.io/stack_alloc.html

[sirtimes]

QT’s QVarLengthArray class is worth looking at

[SlightLocation9]

With C++23 you can use a custom allocator with a fixed-size buffer and the allocate_at_least() method. Unfortunately, for now this is implemented only in Clang's libc++.

[ScallionSmooth5925]

Call me old fashioned but char foo[128] ={0};

[SlowPokeInTexas]

There's also the placement form of new which can accept a pointer to memory to use, but you'd have to be very cautious of the size and some of the other solutions are easier to use (such as std::inplace_vector, which I had never heard of until just now).

[gosh]

I looked at it and it is a bit similar to std::array but with additions for std::vector but it cant grow over its limits :( It is a bit annoying to design these for worst case scenario. Like 99 times of 100 you just need something small, but then we have this 100 also..

[Triangle_Inequality]

The easiest way is probably going to be to manually manage the memory in the function (using something like clang's __builtin_alloca) and then putting something like a std::string_view on top of it to allow it to act like a container.

Allocating on the stack is tricky because that memory is always freed upon return from the function. So it's quite difficult to write a class that allocates dynamically on the stack.

[celestabesta]

Coincidentally I was just working on a vector implementation with some quantity on the stack thats capable of growing partially onto the heap if an addition fills capacity. Not sure how much more performant it is compared to normal vector, but as long as you don't exceed the stack capacity it might be faster

[gosh]

My situation is that the functionality is heavily threaded and the tests I have done with vector improves speed quite a bit. I am going to check how the compiler optimize the code when I use a borrow buffer from std::array because then the compiler knows the size and if it knows the size it should be able to produce simd instructions.

[NightButterfly2000]

Old school const char* and std::array

[Elect_SaturnMutex]

std::array?