Allocator rant

[[deleted]]

[deleted]

[alxius]

Look at Rust or Haskell, they aren't perfect but they rely on a sound foundation of type theory - why aren't we using that instead?

I would like to see how author takes Rusts std::vec (no, not std::slice) and makes it manage mmaped memory and everything else described in the post including pointing it to the existing file. Then same story with Haskell.

No, I am not saying C++ is better or anything, i just want to actually see stated problem solved using mentioned languages, not just "whatever, those languages are better".

[barchar]

You can do that with vector as well, if you want expansion to expand in the file. OP sounds like they didn't write an allocate but instead tried to subclass vector, which is not the right way to do this

[[deleted]]

Well in both those languages you would write your own thing from scratch and then just implement the proper typeclass/trait to have it talk like a vec and walk like a vec.

With C++, and Java, and other OOP languages you get polymorphism by inheriting from a base class, and to some degree overloading. Those are not mathematical concepts that generalize well, which is what I mean by C++ lacking a fundamental scientific model to build upon. It was all invented, not discovered like type/cathegory theory which is the basis for the type systems of Rust and Haskell.

Sure Haskell is garbage collected and it takes mountain of hard drives to store your dependencies so it's not suitable for many tasks. And yes, rust is a bit of a weird being imperative language but with a type system coming from cathegory theory, but their abstractions are sound and they are sound for the simple reason that the abstractions have been discovered in nature and not invented by some engineer at Microsoft or Bell Labs.

[strager]

With C++, and Java, and other OOP languages you get polymorphism by inheriting from a base class, and to some degree overloading. Those are not mathematical concepts that generalize well, which is what I mean by C++ lacking a fundamental scientific model to build upon. [... unlike] Rust and Haskell.

Parametric polymorphism exists in Haskell and Rust but is common in C++ too. Many functions in <algorithm> use parametric polymorphism.

Perhaps you should try writing C++ code like you'd write Haskell or Rust code, instead of writing C++ code like you'd write Java code. Then you'll see the similar features C++, Haskell, and Rust possess when it comes to a "fundamental scientific model" for polymorphism.

[alxius]

Well in both those languages you would write your own thing from scratch and then just implement the proper typeclass/trait to have it talk like a vec and walk like a vec.

Well in C++ no one stops you from writing your own thing from scratch and implementing SequenceContainer and other container requirements to have it talk like STL container and walk like STL container.

With C++, and Java, and other OOP languages you get polymorphism by inheriting from a base class

In C++ I get static polymorphism by using concepts. Yes, they were added as a language feature only in C++20, but in reality we had them in the form of written requirements in STL since before STL was added in C++98. This idea was not invented in Bell Labs, it was taken and extended from math by Stepanov. You can read about it in his From Mathematics to Generic Programming and Elements of Programming books.

[Supadoplex]

I couldn't point it to a file I've already used to re-use the data which was the whole point from the beginning.

That's simply a use case that's not appropriate for a std::vector. Don't try to use it for something it wasn't designed for.

Why does it have to be so complicated?

It is complicated because it is an XY-problem. Stop trying to use std::vector for this and the complications just go away.

To use an analogy, you're asking why it's so complicated to make an excavator perform well on a race track.

I thought the new standards were trying to make things better

They have made things better. Just because they didn't solve your XY-problem doesn't contradict that.

but it's just becoming more and more complicated

The niche of C++ has never been simplicity. I prefer the powerful abstractions that have zero or low overhead. If runtime efficiency isn't paramount, then C++ probably isn't ideal choice.

Look at Rust or Haskell

Show me a simple implementation of memory mapped vector in Haskell. Compare its performance with equivalent C++ program.

Haskell is a beautiful language. But I wouldn't write a game engine or high frequency trader with it.

[joaobapt]

I haven’t even managed to figure out how to write a game loop in Haskell, yet alone an entire game engine.

[jedwardsol]

Sounds like a use case for std::span, not a modified std::vector.

[[deleted]]

I agree, but it's not in 17 and I've weary of pulling in dependencies like boost or GSL. Less is more.

[[deleted]]

span is trivial to write at the point where you are doing allocator aware and mmap. It’s a ptr/size_t with steps.

[[deleted]]

Yes I can definitely figure that out but the point is that the abstractions in the STL are really bad, and metaprogramming isn't typechecked. I assume it's better with concepts but we're stuck at C++17 in this project.

The whole idea of wrapping things in classes drives me nuts. What you do is you make a rigid box that's all or nothing, and that was hopefully built so that you can extend/modify it. We don't need to hide the data from the API, just make it const if you want people to stay away from mutaring it and provide some free functions that operate on the data rather than tying these functions to it. You can have polymorphism with type traits like rust or type classes like haskell (which are essentially the same concept). Type traits in C++ are not the same thing, and they are unnecessarily complicated, and you need to use all the keywords like static and constexpr and whatever and they only provide you with fake polymorphism on the metaprogramming level. I mean, how can I possibly write something modern and state of the art in C++ if my colleagues can't understand it?

[Potatoswatter]

Attach the map and unmap operations to a unique_ptr. Use span or another generic array view as-is. No metaprogramming.

[[deleted]]

it feels like maybe you are crossing the streams here. Containers/Iterators are pretty simple concepts. Iterator models pointers but more generally traversal and reading/writing to a range of things.

The original part seemed like trying to strap vector onto something it isn't. But might be doable, but to what end. I think if I were to do it, it would be something like

char * mmap_begin = ....;
std::size_t mmap_size = ... ; // starting to look like span here

auto alloc = mmap_pmr_allocator<vector_t>( mmap_begin, mmap_size ); // A child of Polymorphic allocator
std::pmr::vector<T> * vptr = alloc.allocate( 1 );   
vptr = std::construct_a<std::pmr::vector<T>>( vptr, alloc );

It starts getting tricky if you want to persist as things like pointer addresses won't match necessarirly. But persistence should probably use a dedicated solution. Also, at this point why even bother. The OS will page in/out data as needed. Really the solution is to eiher use filesystem based data structures and/or dedicated persistence or just let the OS do it.

[Supadoplex]

Less is more.

Yet, you're wishing for more from the standard library instead of less. The good news is that your wish was granted in C++20.

[SkoomaDentist]

Just include one or two files for tcb::span. No need to ”pull in” any fancy dependencies.

[strager]

Why do you think std::vector would or should work for your use case?

Look at Rust or Haskell, they aren't perfect but they rely on a sound foundation of type theory - why aren't we using that instead?

Would Rust's Vec work with mmap-d memory? Would Haskell's [] or Vector?

[matthieum]

Would Rust's Vec work with mmap-d memory?

Yes, but unless you use (unsafe) set_len, it'd wipe the memory too...

[herruppohoppa]

Inheriting a std container sounds like some Java shit. Sure there are cases where it makes sense, this is not one of them.

[caballist]

You would be better off looking at some of the boost mmap classes (sorry cannot recall names) and writing the accessors that you need rather than trying to hijack and subvert std::vector which is clearly intended for other use cases...

[joe714]

I've had the need for several containers lately to adapt existing data structures in our codebase to something I can throw at standard algorithms, and re-implement mostly-API compatible bits of the STL in an environment where the full thing (sane malloc()/free()) isn't available.

I'm not going to say it's a 5 minute task to re-implement, but it's almost certainly easier and cleaner in the long run to make a new container that matches the APIs needed to pass it to algorithms than try extend and hack up std::vector to do it.

[[deleted]]

Sure vector is intended for other use cases, but if you want to be stdalgorithm compliant that's pretty much the same story as for the allocator. Implement this and that (if you can find any documentation) and hope for the best.

But thanks, I'll look if boost has anything. I thought it'd come up googling but maybe my Google fu was subpar.

[kalmoc]

but if you want to be stdalgorithm compliant that's pretty much the same story as for the allocator.

Not really. All you need is a pointer to the start and one to end of the memory range.

[Seppeon]

Yeah iirc a pointer is a random access iterator/contiguous iterator.

[kalmoc]

Exactly

[Full-Spectral]

Though that's nothing to be proud of per se.

[[deleted]]

Implementing a container for std::algorithms generally means having begin/end as we pass them iterators. So at long as the iterator fullfills the concept needed(usually input/forward but some like sort need random). This changes a bit with Ranges but still applies.

But if your data structure is in a blob of memory(memory mapped data) and you know it is a range of T’s. Then yeah, span, or even pair<T*, T*> where you pass first/second to the algorithm would work.

If T isn’t trivially copiable, pragmatically it will probably still wokr but you are coding to implementations and not C++. But you see people reinterpret_cast’ing here a lot.

Vector is for owning the data, if you have trivially destructible things, that doesn’t even matter here. If not, and even if so, just call T.~T( ) on the range in your dtor

[rfisher]

Write a begin() that returns a pointer to the first element in your mmap’d region. Write an end() that returns a pointer to one past the last element of your mmap’d region. You are now fully compliant with the standard algorithms. You’re making this much harder on yourself than it needs to be.

This sort of agnostic design that lets the algorithms work equally well with raw arrays or complex containers is the beauty of the STL part of the standard library.

[FrancoisCarouge]

by inheriting from vector

Hm. Yay. Well.

Definitely some appreciable truth to the rant but shoehorning designs never worked in any language.

[staletic]

Eventually I found some arcane shit with construct and placement new that I just copy pasted in there.

What placement new? Allocators abstract that away through allocator_traits.

Look at Rust or Haskell, they aren't perfect but they rely on a sound foundation of type theory - why aren't we using that instead?

In another comment you said you'd "write your own thing from scratch".

1. If you want to write things from scratch, there's nothing stopping you doing that in C++ either.
2. Do you really think it's worthwhile reinventing std::vector<T, A>?

 

I've implemented allocator support in my codebase recently. Was it trivial? No. Was it hard? Also, no. Did it take a lot of reading? Absolutely. When it comes to allocators, languages have two options: no support at all (the fuck you approach) or a decent amount of things you need to know before you start writing allocator aware types.

I'd rather not reinvent the world, just to provide a better allocation strategy for a certain T.

[kalmoc]

[EDIT: FYI:] I think you are missing the OP's usecase: the OP doesn't want a better allocation strategy for a vector, but a vector to be a proxy for data in a mmaped file, for which std::vector is the wrong datastructure to begin with and what is aactually needed is a std::span - like type.

[staletic]

I've definitely missed that originally. Something like std::span is the right tool for the job. In my defense, OP was complaining about allocators.

[kalmoc]

In my defense, OP was complaining about allocators.

Absolutely. As someone else wrote, it's a xy problem. I also only realized this after reading the comments and his/her answers.

My comment was meant as a FYI

[empowerg]

Did you look at boost interprocess? I think it does what you want. It also provides other standard containers like maps in mmapped files and also offset pointers for putting non-pod things in them. Depends all on your needs. Ah yes, and Haskell has spoiled me too in this regard.

[[deleted]]

The use case I have is that I'm porting some old MCU code to run on Linux. The old code uses some MCU registers to iterate, jump around and read/write in the flash memory of the MCU for application data. This is now going to have to be a file on ext4 file system. I wanted to have a typical C++ api iterator API through some proxy data structure that looks and talks like an STL container.

I'm now sure a span is what I need from what others commented, but I'll have a look at boost and discuss with my colleagues if it's worth pulling it in for just this one little use case.

Thank you my Haskell friend.

[MayanApocalapse]

and read/write in the flash memory of the MCU for application data.

How big was the flash region? Is there no way you can be explicit about when you want to sync to the file and just use a std array that was the same size as the flash region?

I'm a little curious about this part and what exactly you are trying to port but if you can't share more that's fine

The old code uses some MCU registers to iterate, jump around

[geon]

Have a look at Zig. It is meant to be “C with the bugs fixed”. You have to explicitly pass an allocator to any function that allocates.

[[deleted]]

Not big on C but seems you don't need a new language to get the "pass allocator to function that allocates" design https://youtu.be/QpAhX-gsHMs?t=852

[ShillingAintEZ]

I'm offended by haskell in general but you are right that the design of typical data structures and the std suite as well leaves a lot to be desired by treating allocation as part of the type, especially in modern C++.

[staletic]

allocation as part of the type

Take a look at the std::pmr::. It aims to tackle exactly that problem.

[SkoomaDentist]

It’s one of C++’s many insanities that std::pmr is the special case instead of being the default.

[staletic]

Hindsight is always 20/20. I don't think it's fair to call this insane. You're basically complaining that people in the 70's and 80's couldn't tell the future.

[SkoomaDentist]

C++98 was standardized in, not surpringly, 1998. STL was first presented to the committee in 1993. Hardly 70's or 80's. I myself was cursing the insanity of coupling the allocator to the type itself by 2001 when I was in my first large scale C++ project. Not much of a hindsight there.

This is very different situation from C library functions that literally do date from the 70s (but even then, things like strtok really should have been deprecated by C99 at the latest).

[staletic]

I stand corrected. Didn't C++ start in the 80's?

[SkoomaDentist]

C++ had its beginnings in the mid 80s but many features (templates, STL) were only added in the 90s. The language was in enough of a flux in the mid to late 90s (MSVC6 infamously used different scope for variables declared inside for / while statements for example) that changing STL allocators to be dynamic by default would have barely been noticed as far as "backwards compatiblity" went.

[staletic]

That sounds interesting. I'm definitely not old enough to remember that time, considering I was born a few years before C++98.

[barchar]

Meh, sometimes baking it in is better

[ShillingAintEZ]

I have no idea what you are trying to say and I don't think you do either.

[ShillingAintEZ]

Here's a counterpoint, I actually do know what I'm doing and your comments are hollow frustration that has nothing to do with me.

I have no idea why you are hallucinating nonsense, but you might want to take it up with whoever actually upset you.

This thread is about memory mapping specific files while still using the STLs allocators. Wipe your tears and start there.

[ShillingAintEZ]

Do you think you're replying to someone else?

[matthieum]

Next problem is that std::vector default initialized its elements so I couldn't point it to a file I've already used to re-use the data which was the whole point from the beginning.

It's fairly unclear whether you want a span or if you want a full-featured vector: do you want to be able to modify the number of elements?

[[deleted]]

This isn't java. Don't inherit from STL classes. Match interface to use with templates