Joint Allocations in C++
turingtester.wordpress.com
turingtester.wordpress.com
If I stumbled across the latter version, I would just scratch my head. And I've seen sooo many projects just end up in a big code bloat just because some programmers wanted to add tons of "new" features like this that add nothing and just complexify the code for no reason.
And to me, the first version does look like someone used to C who comes to write C++ but writes their C++ like it is C. Wrapping it in the second version (as others have pointed out) is safer because it is reusable, and cleans itself up.
And seriously, did you read the initial point? The problem is that the first approach must be fully rewritten for every new class with different members that exists in your code. Given how HN is butthurt over off-by-one and out-of-buffer errors, you can't say that the first example can really be debugged easily when you have 30 of them in your code. If you only had the Mesh class in your code and nothing else similar maybe it would not be worth it.. but only maybe.
The final example is incredibly simple to use, hides the complexity in one single point and prevents you from ever making mistakes outside of it and seriously, it is not that complex.
There are two 3 wrong premises in this article (IMHO): - It makes you think that using raw pointers (so called 'low level types' in the article) is more error prone than using combined types. - It makes you think that adding abstraction removes complexity. - Makes you think that you should combine/factor everything because repeating yourself is forbidden.
These assertions are straight false.
- Adding abstraction does NOT remove complexity. It ADDS complexity, and then HIDES it. The ArrayView class has absolutely no use whatsoever. Every C/C++ programmer is used to access arrays through pointers. Creating a class for that just makes a reader wonder "what the hell is this thing?". And then you have to crawl in the code to understand what is this thing. And of course, in 3/5 years from now, this ArrayView class will have tripled in size. For something as simple as reading numbers in memory, i don't want any abstraction.
- There is nothing wrong in repeating yourself once on a while => if it improves readability! Factoring too much IS wrong. It makes reading the code a pain. When I read code, I don't want to read an abstract version of what the code does. I want to grasp the maximum possible information with the minimum noise. After reading the final version of this Mesh class, I have no idea of its memory layout. I see some ArrayView and a magical create_contiguous_memory function. I'm lost. I don't know where the memory come from, whether or not I own it, what will happen if I hand a pointer to it. Everything is hidden, and that's a pure pain to understand.
> should we be using these low level types in this particular class, or use classes that better represent what we need and leave the low level types to them?
There is no mention that we want to remove complexity. Instead, the aim of modern C++ is in fact to hide it, so that high level code can be written as simply as possible while hiding all the implementation details in classes. The code you see in this article is no different from the code you find in the implementation of the standard library; in fact since it is simpler it is even easier. Does not mean that the standard library does not have complexity - but it hides it from me, possibly with low expense. Also it never mentions pointers, the problem there is all the arithmetic which is not portable and highly prone to bugs should it ever need to be modified.
The article is not factoring. It is coalescing a feature in a simple, single purpose class which does very little, and has a very simple use case and usage. If you have no idea of the memory layout, then you need to read the class, exactly as you would if you wanted to know the memory layout of std::list or std::vector. Making a class does not prevent the complexity from existing, it just prevents you making silly mistakes while using it. It never allows you not to know your trade and forget how to program.
It seems to me you are a C guy. Really, I get what you are saying, it is just not the philosophy of C++, and if you disagree, maybe you shouldn't be using C++. That's perfectly fine, and I love that there are C people doing C things - it's not my cup of cake, but I'm happy they're there. And I would understand also if you were complaining about C++ trying to do something it is not. But what's happening here it really not the case, so I don't agree with you either.
IMO, of course.
I've seen great C++ code that I just thoroughly enjoy reading, because it doesn't make assumptions about anyones' intelligence, and I've seen C++ code that is purely designed exclusively for only the elite who are mighty enough to wield the sticks that the C++ committee provide. C++ really gives all kinds of control authority to any style you wish to use .. another of those quaint software ironies that the power that makes one weak, enlightens another ..
C++ is getting better, but its early development was driven by questionable features (iostreams, ugh) and denial that the language / runtime needed some basic features, like string and buffer types that didn't suck.
I've been using the language since 1987, and still have my own safe subset, augmented recently with some of the C11 stuff that's become solid in the toolchains I use.
But it's still a misfeature-ridden grabfest of a language.
Every C++ programmer I know uses their own narrow subset of C++. Except that those using "hardcore" ++ features appear to be far more vocal about their subset being the one true way to use C++.
Still, this article is the exact reason why I just can't stand "the new C++ trend": Code bloat for no added value, false sense of safety with fragile abstractions, pointless factoring which makes code unreadable :(
Why do you keep saying that? Do you think repeating it will make it true?
First, the computation of uvs_size is wrong; it's using sizeof(indices[0]) rather than sizeof(uvs[0]). Since the the former is an int and the latter is a Vector2 (presumably 16 bytes), the system doesn't allocate enough memory and there will be a heap overflow.
Second, it tries to do pointer arithmetic on void pointers which is undefined.
Third, it doesn't take into account alignment requirements. For example the Vector2 class would ideally be defined as 16-byte aligned so that the Vector2's can be operated on by SSE instructions. This code gets that wrong or right depending on the number of integers in the adjacent array. So in the worst case it'll be lovely code that works until a data file is changed, and then suddenly starts crashing in odd places.
Sorry, screw raw pointer arithmetic when 7 lines of code have three non-obvious errors, one of which is extremely serious. It seems like a pretty good counterargument to your claim that using raw pointers is not error prone.
I would say the code doesn't go far enough. Instead of using `std::unique_ptr<char[]>`, it should define some kind of memory_block abstraction (using `unique_ptr` internally), where the copy constructor and `operator=` both do a byte-wise copy of the data. Then alongside `make_contiguous`, you would have an analogous `copy_contiguous`, where the base case of `make_contiguous_helper` would instead call `memory_block.resize(total_size)` and the base case of `copy_contiguous_helper` would call memory_block = other_memory_block. This would remove the boiler-plate code for the copy constructor in Mesh, which can instead be:
Mesh::Mesh(const Mesh& other)
: memory_block(copy_contiguous(other.memory_block,
positions, other.positions,
indices, other.indices,
vertices, other.vertices))
{
}
In any case, having a sensible copy constructor on the memory_block (and any necessary associated data) would at least make the copy constructors in the client classes (assuming you have more than one user of this pattern) cleaner.
It's a really good pattern, though. Excellent blog post.
If you did that with the C++ code in this article there would be errors too. Major straw man.
The bug where you copy a line, need to change a bunch of spots and miss one is a common pattern. It happens even when writing real code into a real editor/IDE, and especially when dealing with code that has lots of repetition (as advocated by Galanwe). It's also usually not detected by the compiler, and detected at runtime by simple smoke tests only if you're lucky.
So I don't think it's a strawman argument. It's exactly what you'd expect to happen at some point when using a style that encourages copy-paste programming. You can easily find lots of examples of similar bugs in the wild, in production code that has been running for months or years. It's just fortunate that the example code had an instance of that bug pattern.
But also, even if I didn't have a choice and had to write the code in C++, I would do it in the style on the slide, not the style endorsed by the link on this HN thread.
I do agree that copying a line and changing spots is a common mistake pattern. However, I also still think that in many cases that is the best thing to do because it results in the simplest code. So rather than go through contortions in the actual code to try and prevent this, I am wondering if some kind of IDE pattern matching is a better way to catch this class of errors.
In generally I tried to avoid an overly negative tone when referencing your code or statements, I hope you find that it's reflected in the post.
I think that a "combined type", can be safer if well written than a raw pointer. Surely you don't disagree with that? That's not the same as saying all combined types are better.
Similarly, adding abstraction can be good, it can also be bad. C adds abstraction to assembly. I'm guessing though that you would choose C over assembly for many things?
Repeating yourself is a bad thing in general. It could be that to get rid of the repetition we'd have to incur other costs that might be worse. I don't think that's the case here.
I just don't understand your "magical create_contiguous_memory" comment. Do you feel like the sort function is magic, and instead we should write all of our sorts out at the call site? More practically, we write a good sort once, document it carefully. The users of sort know roughly how it works and exactly how to use it. In the rare cases they care, they read the code. make_contiguous is exactly in this boat: you write it once, you write it carefully, and then you use it without worrying about the details every single time. Our brains are just too small to deal with all the details all the time, that's why we're trying to hide complexity that isn't as immediately relevant.
Your post is mostly sweeping generalities which aren't true in general, and as far as talking about the code goes, you mostly just say you don't like it or find it hard to read, and brush aside anything concrete like reusability, testability, bounds checking, etc, specific things that are actually useful.
From an ok, not great programmer with a year's experience, I wouldn't necessarily expect them to fully understand make_contiguous right away. But I would expect them to understand who owns the memory, and the memory layout.
It's simpler at the expense of being more bug prone. Notice that the "simpler" struct has no housekeeping code to "delete[]" the memory. The programmer now has to manually "manage" that cleanup somewhere.
>, and the layers of abstraction added are of pretty much no value here.
The "value" he's addressing from the "simpler" but more fragile code:
1) remove bug-prone code which requires manually synchronization (copy&paste) of pointer types in both the lines defining the variable and the subsequent lines casting the pointer from a raw buffer: "mesh->positions = (Vector3 )mesh->memory_block;"
2) remove brittle manual arithmetic of pointer offsets embedded inside contiguous arrays such as: "mesh->uvs = (Vector2 )(mesh->memory_block + positions_size + indices_size);"
Calculating offsets (and/or enforcing logical boundaries) inside of arrays is very error prone and the OpenSSL Heartbleed bug was an example of that type of defect.
3) manage the release of memory using unique_ptr. Obviously, it is to help the programmer (and other coworkers using Mesh data structs) avoid memory leaks.
>features like this that add nothing and just complexify the code for no reason.
It doesn't look like "no reason" to me. The attempt was to reduce bugs, and add memory safety.
Regrettably this trend is all but new. Boost is god knows how old now and just look how popular it is in certain circles.
D represents a much better attempt at what C++ ought to have been.
Also at some point you're going to have to promote this to the GPU, at that point the original code will have a closer affinity to the GPU code rather the nonsense c++. I can forgive this though as he states he's not a games programmer.
Code like that is the main culprit of C++ is still considered an "unsafe" language, despite a correct usage of it, although more verbose and with more abstractions, brings both the benefits of C-like speed and higher level languages safety.
See, this is what I never quite understand. I use C++ when I want to do C type things. Manage my own memory. Bit twiddle with speed. Avoid all dynamic allocations. Increase cache coherency. Call inline assembler. Use the CRTP to achieve static polymorphism. Design my own containers. Lock free containers with atomics. Etc. If I'm using C++ I want nastiness. I want to get down and dirty.
Why on earth would you ever want to use it as a higher level lanuage? It sucks balls at that. Just go and use a proper, nice, well designed high level language instead. If I want a language that holds my hand and protects me from the evil pointers, I'm not choosing C++. Using C# or Java (for example) is complete luxury compared to C++.
But apparently, there are a whole bunch of people that do attempt to use C++ for this purpose. Who strive to achieve a language where you never see a raw pointer, but you are still stuck with maybe 30% of the productivity you'd have in a proper higher level language. It boggles my mind. Congratulations, now you have no garbage collection, a crap IDE, you're still wrestling with forward declarations of classes and header files and the preprocessor and linker options and slow compilation and you've now buried the machine under a layer of abstraction. The absolute worst of both worlds.
>brings both the benefits of C-like speed and higher level languages safety.
It doesn't. You end up with neither!
Except that it does. This article clearly demonstrates one way that C++ provides higher level safety without overheads - the allocated memory is guaranteed to be freed.
Nobody is saying you can't do low-level stuff in C++. They're just saying that C++ provides a zero-overhead way to do it safely. Why wouldn't you want that?
Use std::string everywhere and the (re)allocation rate / fragmentation will make your allocator very sad. C-style strings are not "fast" per-se, but at least they make all the overhead explicit.
Use std::shared_ptr for everything and you'll end up with a higher overhead than any proper GC, particularly on a multicore system.
Use templates too much and your code size will blow away any L1 cache very soon.
Use std::mutex/std::lock to protect shared state and it is going to cost you much more than synchronized in Java, which Java often turns into a noop, but C++ compiler can't.
Use virtual functions and (in all except very trivial cases) they will prevent strong opimizations like inlining in many cases where C# or Java would have no problem.
Want to have safe array access? Sure, still possible to add range checks (e.g. use at instead of []), but are you really sure C++ compilers are as strong in eliding these checks as compilers for the languages with mandatory array bound checking?
Oh, you can even go the Java/C# style very heavily and use Boehm GC. Because you can. Who said C++ is lower-level? Except it is nowhere near the performance levels achieved by proper modern GCs.
Also, not sure why if someone points to the obvious places where C++ could be slow, people treat it personally as an attack on "their" language. The fact that many high-level abstractions are not-free in C++, doesn't preclude it from being still highly performing, particularly if you know the cost of these abstractions and you know when to avoid them.
The thing about templates is misleading. Sure, if misused they can hurt your cache. But they also move branching from run time to compile time, which is a very good thing. Google some benchmarks of C++ sort vs C qsort; the former is much faster because the comparator can easily be inlined.
The templates used in my post, for example, either bloat the code not at all, or very little. They are either generating tiny functions that get inlined anyway (like ArrayView; once a function is inlined its irrelevant whether it came from a template or not for code bloat purposes) or they are generating code that would just need to be written by hand (like make_contiguous).
I've actually personally witnessed two fairly detailed accounts of people that actually got themselves into situations where template or template-like bloat became a performance negative, relative to the benefits they provided. They didn't cite a cliche about code bloat, they actually benchmarked and found the cost. What both of them were doing was very extreme; nobody who's not using very extreme template techniques (and therefore is sold on it) is hitting that point.
Cache locality. Cache coherency is something different.
In a scenario where users can access elements of a joint array of requested size without limitations, they can access memory outside the array. Memory block's total requested size may overflow size_t. Fortunately, overflow prevention is easy to add to the generic version.
What the hell are you talking about? It's a game.
> In a scenario where users can access elements of a joint array of requested size without limitations, they can access memory outside the array
Welcome to modern computing! A process can access any part of its mapped address space without limitation. Joke aside, are you suggesting a process should hide memory from itself? Forget it, I can't even make sense out of your comment.
> Memory block's total requested size may overflow size_t
Are you serious? Then please suggest a fix for C, C++, Java, and whatsnot, because nothing will prevent you in pretty much any language to ask for more memory than you can handle. This is not a _bug_, it's just expecting the programmer not to fuck around.
Here's an example with a better description: https://www.verisign.com/en_US/security-services/security-in...
>(...) could allow an attacker to execute arbitrary code with the privileges of the current user.
>The vulnerability occurs when reading the header of the Pack200 compressed Jar file during decompression. To calculate the size of a heap buffer, the code multiplies and adds several 32-bit integers. The bounds of these values are not checked, and the arithmetic operations can overflow. This results in an undersized buffer being allocated, which leads to a heap-based buffer overflow.
I remember there was a similar bug in some other decompression library.
Your comment that this is less readable is valid. Readability varies widely with background, skillset, consistency, and a host of other factors. If your team finds C-style code more intuitive, don't write Java style code. If your team finds malloc error prone, use smart pointers.
Perhaps the biggest advantage of C++ is its flexibility, at least compared to the other mainstream languages. This means everyone can write code the way they want and others can use it (a).
(a) OK. There is still a large list of gotchas around types, the preprocessor, header inclusions, namespacing, etc. that you need to know about to be a good citizen, at least until C++ can figure out how to support modules.
As a lifetime C++ guy I find this new paradigm (inline code a-la structured code) brittle and fragile. App assumptions are laced throughout; nothing can be changed without a rewrite. And my go-to code-reading techniques (follow a class through all its incarnations with grep etc) fail - they rarely subclass, just overriding existing classes locally to create callbacks etc.
So I'm not a fan of the new order. I see it's a productivity tool for the app writers out there. Especially with the one-off code that startups write, expecting to do a rewrite once they're funded. It really makes sense for them.
But I weep for the craft.
I'm curious as to the problem you're exploring/solving here?
"Concatenated struct's in single chunk" is a neat trick. The use case seems a bit broken[1], but I'm assuming that it's from the original video, and your c++-ifying it? Or at least trying to find a nicer way to write this style of code?
If you'r going this route, I'd be tempted not to use pointers at all, and just use offsets and accessors.[2]
* Lack of pointers means you can load in 1 read. (endian needs to be watched, and assumes you can get the entire size elsewhere)
* You can also shuffle it around in memory should you be doing something fancy. (defragging heaps might be useful if doing a sandbox)
* Better encapsulation? maybe..
[1] Verts and Indices are generally uploaded to a GPU then discarded, but this has the counts, which is needed CPU side for draw calls, in the same chunk so would need to be copied before freeing.
[2]
struct Mesh
{
int32_t num_indices,
num_verts;
// inline to this struct..
// assumes Vector3 is aligned 4 bytes.
// and that Mesh has been alloced to same alignment.
//
// Vector3 positions[num_verts];
// int32_t indices[num_indices];
// Vector2 uvs[num_verts];
inline const Vector3* PositionsBegin() const { return reinterpret_cast<const Vector3*>(this + 1); }
inline const Vector3* PositionsEnd() const { return PositionsBegin() + num_verts; }
inline const int32_t* IndicesBegin() const { return reinterpret_cast<const int32_t*>(PositionsEnd()); }
inline const int32_t* IndicesEnd() const { return IndicesBegin() + num_indices; }
// etc
};
I guess we'll agree to disagree, I think that C++ gives us some nice ways of writing it, I think that's what the post shows :-)
These "joint allocations" seem to be "a small pool of heterogenous types." The motivation is that heap allocations are expensive, so we want to coalesce them. The only way this would matter at all is if we are creating lots of these Mesh objects.
The given solutions make one heap allocation per Mesh object, as opposed to three. Create six million Meshes and you get two million allocations.
Instead, one pool should be created for each of the three array types: Vector2, int, and Vector3. Now, create six million Meshes and you can do somewhere between three and a few dozen allocations, depending on your pool's initial size and growth strategy.
I didn't watch the presentation so I may be wrong but it's possible you're misinterpret how Mesh was intended to be used.
The "million" objects is meant to be inside one Mesh. Mesh is singular. The vertices are plural (millions).
If there's more than one Mesh, it would be dozens or hundreds of Mesh (per video game characters).
I think it's risky to say that it's misguided without the full context of the problem.
Perhaps there's a reason allocators wouldn't work here, but if so, it deserves a little discussion.
I think I did give it a "little" discussion :-). Guess it depends on your definition of a little. I didn't want to talk more about it because I didn't want to get sidetracked, and this is ultimately the way I chose to do it.
Hope that sheds some light on the post and the choices I made with it.
Automating the calculation of offsets and assigning pointers definitely eliminates a lot of potential bugs, but I do wonder if this isn't a bigger deficiency in C++. Why force storing an extra pointer per array? I am still not sure why C++ doesn't allow FAMs [1].
There's probably a question of which would be more efficient, storing pointers in the object and calculating the offset from the pointer, or dynamically calculating the offset within the object. Still, it doesn't seem like a problem developers should need to solve.
Regardless, I'm still not sure what the justification is requiring it be UB even for just primitive types.
The thing is, who should solve it? The different approaches you listed have different advantages, there isn't one right answer. If the language itself solves it for you, you are stuck with whatever solution the language picked. This would be fine in a higher level language, but not in C++.
You're right though that individual devs shouldn't be solving it, it should be in a library. If there's enough interest in these posts, I'm happy to put up my work (fully fleshed out and documented) on a github for people to use.
I think the library approach is right. It would be nice to see the language transparently support contiguous array members, but supporting it in a library will allow more people to use it regardless of compiler. It avoids the standards approval process and implementation as well, which take non-trivial amounts of time. The 0x/1y features definitely make it a lot more feasible.
It would probably give people a better chance to play with the source if you could post a link to it somewhere. I'm not sure what you plan to license it under.
I'll keep an eye out for the next post.
1. Why is the goal to put everything in one block with a single allocation? Could everything still work if they were separated?
2. What do Vector2 and Vector3 look like? What if they say "int a, b" and "int a, b, c" respectively? If a perfectly-aligned "new int[total]" would have fixed the problem, it should have been tried from the start and the code refactored accordingly to not necessarily use structure types to look up the data.
3. Conversely, are Vector2 and Vector3 complex classes with special constructors (or equally important, could they someday become that way)? If so, even a "fixed" memory-allocation solution will be equally fragile to maintain because there is a responsibility to ensure that constructors are called correctly.
4. What is the memory profile of the rest of the application, e.g. how many Mesh objects themselves are created and is the entire approach to managing Mesh objects wrong? Maybe the focus on optimizing one piece has missed an entire problem somewhere else that is more fundamental.
Clearly the original code has bugs but it is also only 14 lines, the fixes for the bugs are straightforward and the right solution (after other analysis) may well have been to remove the code entirely instead of doing the same thing in a different way. Beware of the tendency to "fix" things without looking more deeply at the actual problem.
Indices are not vertex attributes and thus should not be interleaved with the other data.