5 ms·

I share a dislike for std::vector type automatically reallocating arrays -- because of the "reallocating" part. I like preallocated chunks and stable pointers.

I share a dislike for std::vector type automatically reallocating arrays -- because of the "reallocating" part. I like preallocated chunks and stable pointers. To a degree, I agree with the premise of the post, we can preallocate huge chunks, and actual resource consumption will only happen on demand when the memory is first used. But note that there is still a resource whose allocation we can't delay: virtual address space, which must get acquired immediately obviously. When trying to be compatible with 32-bit machines (less than 4GB of virtual address space available), preallocating huge chunks is not practical. As to using static globals, I'm not sure it's the best idea. One can use mmap() (or Virtual Alloc() on Windows) to the same effect. That might be better from an architectural view, with regards to encapsulation and such, and allows a little more dynamicity, making multiple separate (but still large) allocations and such. It's possible to give debugger-visible names to these allocations as well, for example by way of the memfd_create() API.

082349872349872 2y ago
Somewhere I ran across the idea that programs should distinguish between errors and apologies in their messaging. An error indicates the user's fault: they need to correct their input before retrying. An apology indicates the program's fault: either logic for what had been incorrectly thought to be a rare^2 case is missing, or the program has only been configured to deal with N foos, and the user's input requires more. In the former case, the user needs to get a programmer fix before retrying, but in the latter, maybe they can just reconfigure and rebuild (even better, restart with different env vars?) then retry. The relevant point of this is that when the user is likely to be another programmer, "reconfigure" can be as simple as editing a static allocation.
- jstimpfle 2y ago
  I like the idea of "apologies" -- sometimes the best thing a program can do is to try, and if it doesn't work then re-try, maybe with a small change guided by the user. However, many programs require a bit more planning how to deal with unfortunate situations, at least without entirely restarting. It's good to not prevent repairing an unfortunate situation from the start by baking in certain constants that can't be practically assumed. Better than editing a static allocation, is if the program can cope with that situation automatically in some way. Next better thing, have it runtime configurable (e.g. command line arguments, no recompilation needed). I don't see a huge benefit to prefer global arrays over memory maps generally.
- Deukhoofd 2y ago
  Isn't that basically the distinction in HTTP error codes? The 4xx range indicates the user did something wrong, the 5xx indicates the program did something wrong.
wheybags 2y ago
I made an std::vector like wrapper[1] based on this principle, it was fun. Also focused on some of the other advantages you get, like never having to move data when you grow the array, and not invalidating pointers/iterators. Never really used it though. 1: https://wheybags.com/blog/pinned.html https://wheybags.com/blog/pinned.html
Veliladon 2y ago
> I share a dislike for std::vector type automatically reallocating arrays -- because of the "reallocating" part. I like preallocated chunks and stable pointers. Use request at creation to set a capacity for 99.9% of use cases. Still have realloc there to stop any sneaky buffer overflows. Have your cake and eat it too!
- jstimpfle 2y ago
  You can't just realloc you way out of your buffer overflow, when this will invalidate existing references to members in the old allocation.
  - MontagFTB 2y ago
    std::deque doesn’t invalidate existing elements when new ones are added to either end of it. It’s not a panacea, and has its own set of tradeoffs, but if non-invalidation is a requirement for you it is available.
- ape4 2y ago
  In that case if a realloc() happens won't it request double the existing size (ie 99.9% * 2) But if we had let the vector grow naturally it would probably not make such a big realloc()
Joker_vD 2y ago
The annoying thing about "reallocating" is that it's mostly the price of having the flat address space (and not dealing with 128-wide fat pointers). The virtual memory subsystem already juggles around physical pages to allow two non-overlapping virtual address ranges to transparently map to overlapping physical address ranges. The implementations of std::deque() from C++ standard library usually use the similar technique but it's arguably a bit silly since it essentially pushes a MMU-like system on top of an existing hardware one!
- gizmo686 2y ago
  I don't think are current memory architecture is fundamental incompatible with a paging based vector. Doubling the size of pointers is expensive. However, given current RAM sizes, our existing 48-bit effective pointer size is already large enough. It isn't enough to give every allocation a massive amount of virtual address space to grow into. But it should be more than enough to seperate out actual memory allocation from virtual address space allocation. This would mean a more complicated malloc, where you ask for both an actual memory allocation, and an amount of address space to be allocated. And will still require you to have some sense of the maximum size you might need in a given vector. Also, it forces memory allocations to be multiples of the page size, which isn't always ideal.
  - Joker_vD 2y ago
    Well, I am not exactly arguing with all of that but — have you heard of CHERI [0]? They are absolutely willing to double the size of the pointers. [0] https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri-publications.html https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri...
pjmlp 2y ago
That is what std::array is for.
- on_the_train 2y ago
  I'd really want a vector variant that is still on the heap but init-allocated. That's most of the use cases for a std vector in my experience. It's trivial to write yourself of course, but non-reserved vector usage is a very common perf problem
  - pjmlp 2y ago
    You can wrap a std::array into a std:unique_ptr, hardly much to write besides a couple of type alias.
    - jstimpfle 2y ago
      I'm sorry to say, TERRIBLE advice! As many (or most) of C++ features, std::array is a logical idea with terrible ergonomics, bordering to unusable. While they are potentially a little safer to use than plain C arrays (but compilers could easily add runtime checking for plain C arrays too), they are much less ergonomic, both in verbosity of declaration and errors. They can't replace an init-allocated std::vector either, because they have a size fixed at compile time. And unique_ptr itself is TERRIBLE to use too. If RAII is your thing, then still very often, it's totally worth the boilerplate to wrap individual objects in type-specific explicit "Holder classes", instead of relying on std::unique_ptr which has terrible ergonomics too, again both for declaration and use. Oh, and if you're using a free-standing destructor function for the managed object (which is often a very good idea because exposing the class definition in typical C++ style leads to TERRIBLE TERRIBLE compile times), you'll have to bake in a function pointer that is carried by unique_ptr at runtime (I suspect that is because they couldn't make the function a templated parameter because in C++, this leads to ambiguitiy if it is a static inline function declared in a header (terrible!)). So you're paying for all the all the drawbacks of the templated type and get none of the benefits (except for saving a few lines of boilerplate). TERRIBLE. And now you propose combining these two terrible things? How would you use this? #include <memory> #include <array> struct Foo { ~Foo() { printf("Bye!\n"); } }; int main() { // std::unique_ptr<std::array<Foo, 42>> foo = std::make_unique<std::array<Foo, 42>>(); // my fingers hurt and my eyes bleed auto foo = std::make_unique<std::array<Foo, 42>>(); // fingers hurt a little less but my brain will melt on next compiler error foo->at(0); // valid foo[0]; // error. TERRIBLE! return 0; } I wouldn't be so upset about your advice if I didn't know you often don't validate your claims and "references", but keep on suggesting and criticising existing practice that has evolved to certain points (and keeps evolving!) for a reason.

082349872349872 2y ago

Somewhere I ran across the idea that programs should distinguish between errors and apologies in their messaging. An error indicates the user's fault: they need to correct their input before retrying. An apology indicates the program's fault: either logic for what had been incorrectly thought to be a rare^2 case is missing, or the program has only been configured to deal with N foos, and the user's input requires more. In the former case, the user needs to get a programmer fix before retrying, but in the latter, maybe they can just reconfigure and rebuild (even better, restart with different env vars?) then retry. The relevant point of this is that when the user is likely to be another programmer, "reconfigure" can be as simple as editing a static allocation.

jstimpfle 2y ago
I like the idea of "apologies" -- sometimes the best thing a program can do is to try, and if it doesn't work then re-try, maybe with a small change guided by the user. However, many programs require a bit more planning how to deal with unfortunate situations, at least without entirely restarting. It's good to not prevent repairing an unfortunate situation from the start by baking in certain constants that can't be practically assumed. Better than editing a static allocation, is if the program can cope with that situation automatically in some way. Next better thing, have it runtime configurable (e.g. command line arguments, no recompilation needed). I don't see a huge benefit to prefer global arrays over memory maps generally.
Deukhoofd 2y ago
Isn't that basically the distinction in HTTP error codes? The 4xx range indicates the user did something wrong, the 5xx indicates the program did something wrong.

wheybags 2y ago

I made an std::vector like wrapper[1] based on this principle, it was fun. Also focused on some of the other advantages you get, like never having to move data when you grow the array, and not invalidating pointers/iterators. Never really used it though. 1: https://wheybags.com/blog/pinned.html https://wheybags.com/blog/pinned.html

Veliladon 2y ago

> I share a dislike for std::vector type automatically reallocating arrays -- because of the "reallocating" part. I like preallocated chunks and stable pointers. Use request at creation to set a capacity for 99.9% of use cases. Still have realloc there to stop any sneaky buffer overflows. Have your cake and eat it too!

jstimpfle 2y ago
You can't just realloc you way out of your buffer overflow, when this will invalidate existing references to members in the old allocation.
- MontagFTB 2y ago
  std::deque doesn’t invalidate existing elements when new ones are added to either end of it. It’s not a panacea, and has its own set of tradeoffs, but if non-invalidation is a requirement for you it is available.
ape4 2y ago
In that case if a realloc() happens won't it request double the existing size (ie 99.9% * 2) But if we had let the vector grow naturally it would probably not make such a big realloc()

Joker_vD 2y ago

The annoying thing about "reallocating" is that it's mostly the price of having the flat address space (and not dealing with 128-wide fat pointers). The virtual memory subsystem already juggles around physical pages to allow two non-overlapping virtual address ranges to transparently map to overlapping physical address ranges. The implementations of std::deque() from C++ standard library usually use the similar technique but it's arguably a bit silly since it essentially pushes a MMU-like system on top of an existing hardware one!

gizmo686 2y ago
I don't think are current memory architecture is fundamental incompatible with a paging based vector. Doubling the size of pointers is expensive. However, given current RAM sizes, our existing 48-bit effective pointer size is already large enough. It isn't enough to give every allocation a massive amount of virtual address space to grow into. But it should be more than enough to seperate out actual memory allocation from virtual address space allocation. This would mean a more complicated malloc, where you ask for both an actual memory allocation, and an amount of address space to be allocated. And will still require you to have some sense of the maximum size you might need in a given vector. Also, it forces memory allocations to be multiples of the page size, which isn't always ideal.
- Joker_vD 2y ago
  Well, I am not exactly arguing with all of that but — have you heard of CHERI [0]? They are absolutely willing to double the size of the pointers. [0] https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri-publications.html https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/cheri...

pjmlp 2y ago

That is what std::array is for.

on_the_train 2y ago
I'd really want a vector variant that is still on the heap but init-allocated. That's most of the use cases for a std vector in my experience. It's trivial to write yourself of course, but non-reserved vector usage is a very common perf problem
- pjmlp 2y ago
  You can wrap a std::array into a std:unique_ptr, hardly much to write besides a couple of type alias.
  - jstimpfle 2y ago
    I'm sorry to say, TERRIBLE advice! As many (or most) of C++ features, std::array is a logical idea with terrible ergonomics, bordering to unusable. While they are potentially a little safer to use than plain C arrays (but compilers could easily add runtime checking for plain C arrays too), they are much less ergonomic, both in verbosity of declaration and errors. They can't replace an init-allocated std::vector either, because they have a size fixed at compile time. And unique_ptr itself is TERRIBLE to use too. If RAII is your thing, then still very often, it's totally worth the boilerplate to wrap individual objects in type-specific explicit "Holder classes", instead of relying on std::unique_ptr which has terrible ergonomics too, again both for declaration and use. Oh, and if you're using a free-standing destructor function for the managed object (which is often a very good idea because exposing the class definition in typical C++ style leads to TERRIBLE TERRIBLE compile times), you'll have to bake in a function pointer that is carried by unique_ptr at runtime (I suspect that is because they couldn't make the function a templated parameter because in C++, this leads to ambiguitiy if it is a static inline function declared in a header (terrible!)). So you're paying for all the all the drawbacks of the templated type and get none of the benefits (except for saving a few lines of boilerplate). TERRIBLE. And now you propose combining these two terrible things? How would you use this? #include <memory> #include <array> struct Foo { ~Foo() { printf("Bye!\n"); } }; int main() { // std::unique_ptr<std::array<Foo, 42>> foo = std::make_unique<std::array<Foo, 42>>(); // my fingers hurt and my eyes bleed auto foo = std::make_unique<std::array<Foo, 42>>(); // fingers hurt a little less but my brain will melt on next compiler error foo->at(0); // valid foo[0]; // error. TERRIBLE! return 0; } I wouldn't be so upset about your advice if I didn't know you often don't validate your claims and "references", but keep on suggesting and criticising existing practice that has evolved to certain points (and keeps evolving!) for a reason.