5 ms·

A not-so-quick introduction to the C++ allocator model

141 points by jandeboevrie 3y ago

rwmj 3y ago
How do you update pointers when relocating the object? I assume this must be combined with some rust-ish assertions about the number of references to the object? Or I suppose it's C++ so you just have to do it right or you get to keep the pieces.
- elteto 3y ago
  Raw C or C++ pointers you can’t, at least not trivially. You either have a double pointer masquerading as a single pointer, or some other fanciness. Come to think of it, std::shared_ptr has a control block that points to the actual data. I think implementations allocate the control block and the data contiguously for performance reasons, but you don’t really have to.
  - ksherlock 3y ago
    There is a std::make_shared( constructor arguments... ) function which will do one allocation for the control block + item data. I don't think compilers will do it automatically (it has other implications over a normal std::shared_ptr) so you need to opt into it.
  - maccard 3y ago
    std::make_shared exists to allocate the control block at the same time as the memory itself. This has a pretty major disadvantage, the memory for the shared pointer won't be deallocated until the last std::weak_ptr has been destroyed, even if the object has been destroyed.
    - pjmlp 3y ago
      And the major advantage that object data by being coupled with control block reduces fragmentation, and avoids the error of wrongly handling memory leaks when new obj() fails as parameter to shared pointer construction.
      - maccard 3y ago
        Yep, I realise I only talked about the negatives, not the advantages. In general I prefer to use make_shared and be careful with uses of weak pointers.
    - elteto 3y ago
      Ah good point. But in exchange you get cache locality of control block + data and single instruction deref.
      - maccard 3y ago
        Indeed. It's a tradeoff, and I personally prefer std::make_shared.
  - Conscat 3y ago
    `boost::intrusive_ptr` or the proposed `std::retained_ptr` is required to guarantee that.
- monocasa 3y ago
  > Or I suppose it's C++ so you just have to do it right or you get to keep the pieces. Yep. One reason why giving out pointers/references all willynilly to items in something like a std::vector can be fraught with peril. If you push to that vector, it could trigger a realloc of all of the previous items, leaving you with dangling pointers to everything you previously took references of.
  - CyberDildonics 3y ago
    By the time someone gets to the point where they are keeping pointers while reallocating the data structure that contains the objects, they have made a bunch of wrong turns already. It is much better to use indices or keys instead of pointers since that is the interface to the data structure.
  - CoastalCoder 3y ago
    An occurrence of this bug caused a lot of pain for one of my previous employers. One way we tried to isolate the bug was creating a replacement for std::vector. This vector used an array for the elements, but capitalized on the x86 page-protection system: - Between every pair of adjacent elements, this vector allocated a dummy page, marked as un-readable and un-writeable. Any attempt to access it would immediately trigger a segfault. This was to detect erroneous attempts to access some vector element; e.g. punning it to a type larger than the element's actual type. - Any time the vector needed to replace (or just retire) its internal array, it would not return the array to the free pool. Instead, it would leave it allocated, but mark all of its elements as un-readable and un-writeable. This was to detect usage of stale pointers into the vector. I think the team discovered the bug by other means, but I still think this approach has some merit. TL;DR: - The basic idea was inspired by Electric Fence. - This vector wasn't exactly a drop-in replacement for std::vector, because (at the time) it seemed like that would require a lot of additional code. - Obviously this wastes a lot of memory. It's only something one would use in certain debugging situations.
    - yakubin 3y ago
      At that point you might as well use a dynamic array which doesn't invalidate old pointers, when growing the internal buffer: <https://yakubin.com/notes/comp/reserve-and-commit.html https://yakubin.com/notes/comp/reserve-and-commit.html>. It also exhibits much better space utilisation than std::vector, not worse. (Sorry about the suboptimal formatting. It appears that web technologies aren't up-to-par when it comes to this type of content. I intend to rewrite this post in TeX and add some graphs in TikZ when I find a spare moment.)
- dundarious 3y ago
  Indices, regular or generational.
- barbariangrunge 3y ago
  In game dev, you sometimes avoid holding on to pointers for more than a single frame or operation because of this. Especially since many things get created or destroyed over time, and we want to keep our arrays densely packed to reduce cache misses. We are trying a database like approach for retrieving references to things in our current project. It adds a small performance penalty, but it’s far from a bottleneck and it’s been nice to work with
  - doctorpangloss 3y ago
    Did you ever work on a game development project where you would have rather done what you did versus using Unity? Would you want to work in a way where performance didn't matter? How could you tell the difference between the following two scenarios: - A specific kind of higher performance was important. - Higher performance wasn't important: you'd get the same reviews, sell the same copies, whatever graphics improvements you got didn't matter, and maybe you even finish your game 2x sooner because you weren't writing an engine, all else being equal. But because it was intellectually stimulating to you to deal with performance, you committed code every day, which is better than nothing.
    - sillysaurusx 3y ago
      Yes. Sorry for the low brow comment, but fuck unity. I really dislike the fact that if someone wants to become a gamedev in 2023, their only practical options are to write everything themselves, learn unity, or learn unreal engine. I’ve been putting together an alternative. https://github.com/shawwn/noh https://github.com/shawwn/noh It’s frankly amazing to work with a production grade engine that compiles in three minutes. I wouldn’t trade it for all the complexity in unity, regardless of how many extra copies I’d sell. But I realize I’m in the minority. I think it matters to love the tech stack you use, and gamedev has gone out of fashion mostly because no one loves any of the stacks. They deal with them, which is different.
MathMonkeyMan 3y ago
> You must go far out of your way, at Bloomberg, to encounter a container that works the same way as in the ordinary C++ STL. You need only disable the "bsl overrides std" build option. Whether you can do that is another question.
- frutiger 3y ago
  -DBSL_OVERRIDES_STD has been gone for a while now.
cmrdporcupine 3y ago
Have to admit to skimming -- this is complicated, but neat! -- but I also have to say lack of pluggable per-container allocators in Rust is perhaps my chief complaints at this point; really miss this from the C++ STL, even if this article does point out how it can get snakey and foot-gunny. I don't pay attention much the process or politics, but allocator_api feels like it is stuck in permanent limbo. https://github.com/rust-lang/rust/issues/32838 https://github.com/rust-lang/rust/issues/32838 -- opened 6 years ago, still pending.
gavinray 3y ago
See also the proposal for language-support for scoped allocations: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2685r0.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p26... There are some issues with PMR usage that it hopes to resolve, for example: struct Aggregate { std::pmr::string data1; std::pmr::string data2; std::pmr::string data3; }; std::pmr::polymorphic_allocator a1; Aggregate ag = {{"Hello", a1}, {"World", a1}, {"!", a1}}; std::pmr::vector<Aggregate> va(a1); va.emplace_back(std::move(ag)); // Correct allocator retained by moves va.emplace_back(ag); // Error, copied lvalue has wrong allocator va.resize(5); // Error, new values have wrong allocator va.resize(1); // OK, remove all objects with bad allocators The proposed syntax is via a "using" keyword: std::pmr::polymorphic_allocator a4; ScopeAggregate s1 using a4 {"Hello"};
keithalewis 3y ago
> You must go far out of your way, at Bloomberg, to encounter a container that works the same way as in the ordinary C++ STL. When I worked in the group writing the Bloomberg Enterprise backbone we would go out of our way to avoid using the BDE/BSL library. OP is right about it not working the same way as ordinary C++. :-(

141 points by jandeboevrie 3y ago

rwmj 3y ago

How do you update pointers when relocating the object? I assume this must be combined with some rust-ish assertions about the number of references to the object? Or I suppose it's C++ so you just have to do it right or you get to keep the pieces.

elteto 3y ago
Raw C or C++ pointers you can’t, at least not trivially. You either have a double pointer masquerading as a single pointer, or some other fanciness. Come to think of it, std::shared_ptr has a control block that points to the actual data. I think implementations allocate the control block and the data contiguously for performance reasons, but you don’t really have to.
- ksherlock 3y ago
  There is a std::make_shared( constructor arguments... ) function which will do one allocation for the control block + item data. I don't think compilers will do it automatically (it has other implications over a normal std::shared_ptr) so you need to opt into it.
- maccard 3y ago
  std::make_shared exists to allocate the control block at the same time as the memory itself. This has a pretty major disadvantage, the memory for the shared pointer won't be deallocated until the last std::weak_ptr has been destroyed, even if the object has been destroyed.
  - pjmlp 3y ago
    And the major advantage that object data by being coupled with control block reduces fragmentation, and avoids the error of wrongly handling memory leaks when new obj() fails as parameter to shared pointer construction.
    - maccard 3y ago
      Yep, I realise I only talked about the negatives, not the advantages. In general I prefer to use make_shared and be careful with uses of weak pointers.
  - elteto 3y ago
    Ah good point. But in exchange you get cache locality of control block + data and single instruction deref.
    - maccard 3y ago
      Indeed. It's a tradeoff, and I personally prefer std::make_shared.
- Conscat 3y ago
  `boost::intrusive_ptr` or the proposed `std::retained_ptr` is required to guarantee that.
monocasa 3y ago
> Or I suppose it's C++ so you just have to do it right or you get to keep the pieces. Yep. One reason why giving out pointers/references all willynilly to items in something like a std::vector can be fraught with peril. If you push to that vector, it could trigger a realloc of all of the previous items, leaving you with dangling pointers to everything you previously took references of.
- CyberDildonics 3y ago
  By the time someone gets to the point where they are keeping pointers while reallocating the data structure that contains the objects, they have made a bunch of wrong turns already. It is much better to use indices or keys instead of pointers since that is the interface to the data structure.
- CoastalCoder 3y ago
  An occurrence of this bug caused a lot of pain for one of my previous employers. One way we tried to isolate the bug was creating a replacement for std::vector. This vector used an array for the elements, but capitalized on the x86 page-protection system: - Between every pair of adjacent elements, this vector allocated a dummy page, marked as un-readable and un-writeable. Any attempt to access it would immediately trigger a segfault. This was to detect erroneous attempts to access some vector element; e.g. punning it to a type larger than the element's actual type. - Any time the vector needed to replace (or just retire) its internal array, it would not return the array to the free pool. Instead, it would leave it allocated, but mark all of its elements as un-readable and un-writeable. This was to detect usage of stale pointers into the vector. I think the team discovered the bug by other means, but I still think this approach has some merit. TL;DR: - The basic idea was inspired by Electric Fence. - This vector wasn't exactly a drop-in replacement for std::vector, because (at the time) it seemed like that would require a lot of additional code. - Obviously this wastes a lot of memory. It's only something one would use in certain debugging situations.
  - yakubin 3y ago
    At that point you might as well use a dynamic array which doesn't invalidate old pointers, when growing the internal buffer: <https://yakubin.com/notes/comp/reserve-and-commit.html https://yakubin.com/notes/comp/reserve-and-commit.html>. It also exhibits much better space utilisation than std::vector, not worse. (Sorry about the suboptimal formatting. It appears that web technologies aren't up-to-par when it comes to this type of content. I intend to rewrite this post in TeX and add some graphs in TikZ when I find a spare moment.)
dundarious 3y ago
Indices, regular or generational.
barbariangrunge 3y ago
In game dev, you sometimes avoid holding on to pointers for more than a single frame or operation because of this. Especially since many things get created or destroyed over time, and we want to keep our arrays densely packed to reduce cache misses. We are trying a database like approach for retrieving references to things in our current project. It adds a small performance penalty, but it’s far from a bottleneck and it’s been nice to work with
- doctorpangloss 3y ago
  Did you ever work on a game development project where you would have rather done what you did versus using Unity? Would you want to work in a way where performance didn't matter? How could you tell the difference between the following two scenarios: - A specific kind of higher performance was important. - Higher performance wasn't important: you'd get the same reviews, sell the same copies, whatever graphics improvements you got didn't matter, and maybe you even finish your game 2x sooner because you weren't writing an engine, all else being equal. But because it was intellectually stimulating to you to deal with performance, you committed code every day, which is better than nothing.
  - sillysaurusx 3y ago
    Yes. Sorry for the low brow comment, but fuck unity. I really dislike the fact that if someone wants to become a gamedev in 2023, their only practical options are to write everything themselves, learn unity, or learn unreal engine. I’ve been putting together an alternative. https://github.com/shawwn/noh https://github.com/shawwn/noh It’s frankly amazing to work with a production grade engine that compiles in three minutes. I wouldn’t trade it for all the complexity in unity, regardless of how many extra copies I’d sell. But I realize I’m in the minority. I think it matters to love the tech stack you use, and gamedev has gone out of fashion mostly because no one loves any of the stacks. They deal with them, which is different.

MathMonkeyMan 3y ago

> You must go far out of your way, at Bloomberg, to encounter a container that works the same way as in the ordinary C++ STL. You need only disable the "bsl overrides std" build option. Whether you can do that is another question.

frutiger 3y ago
-DBSL_OVERRIDES_STD has been gone for a while now.

cmrdporcupine 3y ago

Have to admit to skimming -- this is complicated, but neat! -- but I also have to say lack of pluggable per-container allocators in Rust is perhaps my chief complaints at this point; really miss this from the C++ STL, even if this article does point out how it can get snakey and foot-gunny. I don't pay attention much the process or politics, but allocator_api feels like it is stuck in permanent limbo. https://github.com/rust-lang/rust/issues/32838 https://github.com/rust-lang/rust/issues/32838 -- opened 6 years ago, still pending.

gavinray 3y ago

See also the proposal for language-support for scoped allocations: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2685r0.html https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p26... There are some issues with PMR usage that it hopes to resolve, for example: struct Aggregate { std::pmr::string data1; std::pmr::string data2; std::pmr::string data3; }; std::pmr::polymorphic_allocator a1; Aggregate ag = {{"Hello", a1}, {"World", a1}, {"!", a1}}; std::pmr::vector<Aggregate> va(a1); va.emplace_back(std::move(ag)); // Correct allocator retained by moves va.emplace_back(ag); // Error, copied lvalue has wrong allocator va.resize(5); // Error, new values have wrong allocator va.resize(1); // OK, remove all objects with bad allocators The proposed syntax is via a "using" keyword: std::pmr::polymorphic_allocator a4; ScopeAggregate s1 using a4 {"Hello"};

keithalewis 3y ago

> You must go far out of your way, at Bloomberg, to encounter a container that works the same way as in the ordinary C++ STL. When I worked in the group writing the Bloomberg Enterprise backbone we would go out of our way to avoid using the BDE/BSL library. OP is right about it not working the same way as ordinary C++. :-(