Getting address of an item in a std::vector

Started by
25 comments, last by DividedByZero 7 years, 9 months ago
I beg to differ on a couple of points. Not alltogether, but still somewhat. :)

No, that's not how ownership semantics work.[...] In a level-based game, assets are loaded for a particular level, and the sound-player is an object within that level. The level's assets are only unloaded when the level is unloaded, at which point, all level-specific objects (such as sound-players within the level) will also have been destroyed.

Yes, that is true, if you can arrange it that way, e.g. in most level-based games. It may not be that easy, however. For example, in an open-world game, some rare unit comes along (say, a wandering boss creature, I seem to remember Ryzom had these). The only working solution to the "you know because of contract" type of ownership is to load all bosses (whether one walks past you or not, and regardless which one it is) and keep them all loaded. Because hey, you never know what happens in half an hour, maybe. But that may be undesirable. It may be more desirable to only load the boss that is showing, on the clients that can see it. And free the memory once it's dead.
Another example would be a game with voice acting where a NPC tells some long sad story about how his father was killed by wolves and how he lost his aunt's ring which you are to retrieve. This is something you want to stream in once, listen to, and never use again. You definitively don't want to keep that around forever or load it ahead of time "just because", especially since there are maybe 50 such NPCs in this city.

The nice thing about the shared pointer approach is that you simply don't care (and you don't even know how long that will be, nor do you have to care!). What's needed stays in RAM, what's not needed is kicked. Eventually.

The performance impact of shared_ptr isn't great in single-threaded code, but is downright stupid in multi-threaded situations. If you saw the actual behavior of that solution written out as plain old C code -- without the use of shared_ptr to hide its stupidity behind an abstraction -- you'd fire whoever wrote it... at least in the context of a game engine.
e.g. The hidden reference counters used internally by shared pointers are thread-safe (via atomic increments), but the shared pointers themselves are not, so they need to be externally synchronized by a mutex/etc...

That's wrong, or rather it is correct but inconsequential.

The reference counter is updated with atomic increments/decrements, that's right. And this is a good thing most of the time (indeed always, except when you are strictly single-threaded, then it's wasting some cycles). The impact of this is however rather low. You do not load 250,000 assets every second. You do not copy around shared pointers 250,000 times per second. That's not what happens. For the comparatively low number of copies that you need to make (few hundred), the overhead of the atomic increments is very acceptable in comparison to the advantages that you buy with them. Yes, it's not free... but by no means a limiting factor unless you do very stupid things.

The pointer itself is, as you point out correctly, not thread-safe. But that is a good thing, not a bad thing. Not stupid, not in any way. You cannot create or reassign a shared pointer in a thread-safe manner. Yeah. Who cares! You don't want to do that anyway.

The shared pointers are created solely by the "manager". One thread, no concurrency. After that, they are, by all practical means, read-only objects (until destroyed). They are deleted solely by the last user decrementing the refcount (whoever that may be). Again, one thread, no concurrency anywhere (not anywhere where the fact that the pointer is not threadsafe would matter, anyway).

The weak pointers are admittedly upped concurrently (well, not necessarily, but at least possibly), but that's fine. The library guarantees that the refcount is managed correctly and once upping the weak pointer to a shared pointer has succeeded, the pointer is valid. Always, no exceptions. No mutex needed.
And if it didn't succeed, the pointer is invalid by definition, so you couldn't care less whether the value is garbled.

To use your wording: Shoot the guy who uses mutexes because they're not needed. :)

every lookup causes an atomic increment, hopefully with relaxed memory ordering

No. Every copy or upping a weak pointer (which is a kind-of copy) causes an atomic increment. Unless you do something very stupid and copy around the shared pointers all the time, the number of actual copies is comparatively low.
On the other hand, you can look up (dereference) the smart pointer a million times without an atomic operation otherwise. Because yeah, it's not threadsafe. Luckily.

The overall cost of upping the pointer is very moderate (I intentionally avoid saying "locking" because it gives a wrong impression). Something like once per frame per asset. How many textures and meshes do you have? A hundred? So that's 200 atomic increments per frame. And...? The problem being?

Consider how many cycles it costs to look up an asset in a map, or find it with a linear search in a vector of objects -- nobody even bothers about that. Why not? Well because it happens relatively rarely.

Like I said in my first sentence: It's maybe not a perfect fit for everybody, but I think it is overall a valid approach.
Advertisement

Morning again, so time to tackle the task again :)

Hopefully I can clear up what I am trying to achieve.

Here is the class and the routine I am presently using to instantiate it and make it a vector element.

I have pruned it back to the essential bits to save space, but it is complete in function (and inherent flaws).

int g_asset_id = 0;
 
class Asset
{
public:
 Asset()
 {
  memblock = NULL;
  memblock_size = 0;
  id = g_asset_id;
  g_asset_id++;
 }

 ~Asset()
 {
  if (memblock)
   delete memblock;
 }
 
 void data_set(char* data, int size)
 {
  memblock = new char[size];
  memblock_size = size;
  memcpy(memblock, data, size);
 }
 
 char* memblock;
 int memblock_size;
 float x, y, z;

private:
 int id;

};
 
 
std::vector<Asset> vectorAsset;
 
int asset_create()
{
 Asset assetTemp;
 vectorAsset.push_back(assetTemp);
 std::vector<Asset>::iterator it = vectorAsset.end();
 it--;
 return it->get_id();
}
 
void asset_data_set(int id, char* data, int size)
{
 for (std::vector<Asset>::iterator it = vectorAsset.begin(); it != vectorAsset.end(); ++it)
 {
  if (it->get_id() == id)
  {
   it->data_set(data, size);
   break;
  }
 }
 return;
}
 
char* asset_data_get(int id)
{
 for (std::vector<Asset>::iterator it = vectorAsset.begin(); it != vectorAsset.end(); ++it)
 {
  if (it->get_id() == id)
  {
   return it->data_get();
  }
 }
 return NULL;
}

From the main program, the theory behind this is to create an asset like this

int someAsset_0 = assetCreate();
asset_data_set(someAsset_0, data, 256);       // 256 is just an example. Could be any length.

From this point all works fine and the data stored in the vector is correct.

But if I create another asset and push it on to the vector like this...

int someAsset_1 = assetCreate();

... it will cause a heap corruption. Which I am guessing is caused by 'data' being in the wrong place, created by the class member 'data_set()'.

If I don't load any data (via asset_data_set() ) the whole thing works fine and I can create, query, and delete any element of asset that I like.

So essentially, I am trying to create a vector of classes that has the ability to store a chunk of data which will initially have an unknown size.

Thanks for persisting with me guys, it is greatly appreciated. :)

A few points.


void data_set(char* data, int size)  
{   
   memblock = new char[size];   
   memblock_size = size;   
   memcpy(memblock, data, size);
}

If memblock isn't null then you have a memory leak. You should check first and delete if it already points to something.


 ~Asset()
 {
  if (memblock)
   delete memblock;
 }

You assign an array so you need to use array delete otherwise you get another memory leak. Any time you do this:

memblock = new char[]

you have to do this:

delete[] memblock; // notice the []


~Asset()
{
   // There's no need to check if it exists before deleting since deleting a nullptr does nothing
   // but if someone disagrees I would love to be corrected on that so I can improve my own coding.
   // since you assigned an array you need to use array delete
   delete[] memblock;
}
 
 void data_set(char* data, int size)
 {
   // You should do some sanity checks here, is data null? is size 0 or negative etc
   // memblock might already contain data so you should delete it before assigning otherwise
   // you will be leaking memory
   delete[] memblock; // array delete
   // If you want to be robust you could assign null to memblock after deleting but here there is
   // no need since you are assigning to it right away
   memblock = new char[size];
   memblock_size = size;
   memcpy(memblock, data, size);
 }

With your vector, if you are pushing Asset objects onto it then you are making a copy. You need to be really careful with that because if you don't make a copy constructor then you have some seriously unpleasant behaviour if your object uses dynamic memory allocations which yours does. The original has a memblock which points to a block of memory, you make a copy (one in the vector), now if you have a default copy constructor then both of those objects have a memblock which points to the same memory. One gets deleted which hopefully deletes it's dynamic memory as it should but then the second one will still have a pointer pointing to that address which is no longer valid. The way you have your global id makes this a bit more complicated so I would disable the copy constructor and make a more constructor then use std::move when you push your assets onto the vector (actually I would rethink the whole design and go for one of the other suggestions in the thread).


// This constructor 'steals' the data/values from the other object so you aren't left with 2
// objects pointing to the same memory. You could make a copy of the data with a copy constructor
// but then you have ambiguity as to how to deal with the id.
Asset(Asset&& asset)
{
   memblock = asset.memblock;
   memblock_size = asset.memblock_size ;
   id = asset.id;

   asset.memblock = nullptr;
   asset.memblock_size = 0;
   asset.id = NO_ID;
 }
// prevent copying and so on
Asset(const Asset&) = delete;
Asset& operator=(const Asset&) = delete;
Asset& operator=(Asset&&) = delete;

I would definitely rethink how you deal with this though. There's been some good suggestions in this thread which I might steal myself (love the one with the smart handles that SeanMiddleditch posted).

Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.

... it will cause a heap corruption. Which I am guessing is caused by 'data' being in the wrong place, created by the class member 'data_set()'.

Are you using a C++11 conformant compiler, in case of MSVC at least Version 2015 or above? If not, than your problem most likely has to do with your "asset" class not having an explicit copy-constructor.

So what would happen here is that if you push a second asset to the vector, it will have to create a different memory buffer and copy the asset from the old vector to it. Since you don't have a copy constructor, it will perform a shallow copy, essentially just setting the memblock pointer to the value of the old asset instance. Then thiss instance is deleted, calling "delete memblock" in the destructor (note: if(p) delete p is not required, delete on nullptr is a valid operation). Anyways, now the memory "memblock" is pointing too is already deleted, but there is a second instance referencing the same memory, namely in the copied instance! And once this is deleted (ie. when you add another asset, or when vectorAsset-variable is deleted, it will call the Asset-destructor, which will try to delete the now-already-invalid memory region from before, via the memblock-member.

The reason I mentioned C++11 is because with this, there is a move-ctor which can also be implicitely generated (in visual studio only from 2015 onwards), and this problem would not happen with that. So if you are already using such a setup, your issue lies elsewhere. In any way, this is something you should adress, because it is almost certain to create problems at some point, ie. if you forget to take a reference to an asset and instead take a value-copy by accident. What you should do is eigther of those:

1) Create a custom copy-constructor, that makes a deep copy of the memory block that is owned by the asset.

2) Use a wrapper like std::string which will automatically take care of that without you having to write a custom copy-ctor

3) Disallow copying of the asset altogether (by making copy-ctor private or deleting it via delete modifier), though this will require you to use C++11 and use a move-ctor instead

Option 3 would be preferable, though if you require assets to be copyable at some point you will have to use eigther 1 or 2 anyways. Having a move-ctor in C++11 really is a bonus though, because otherwise adding any single asset will have a huge overhead if it requires to copy all existing assets via deep copy.

Awesome! Thanks for the clear explanation, guys.

So from my understanding then, with the current 'shallow' copy the vector is causing the destructor to be called which is then deleting cleaning up 'memblock' making the pointer to the copy of 'memblock' invalid.

This sound right?

No, that's not how ownership semantics work.[...] In a level-based game, assets are loaded for a particular level, and the sound-player is an object within that level. The level's assets are only unloaded when the level is unloaded, at which point, all level-specific objects (such as sound-players within the level) will also have been destroyed.

Yes, that is true, if you can arrange it that way, e.g. in most level-based games. It may not be that easy, however. For example, in an open-world game, some rare unit comes along (say, a wandering boss creature, I seem to remember Ryzom had these). The only working solution to the "you know because of contract" type of ownership is to load all bosses (whether one walks past you or not, and regardless which one it is) and keep them all loaded. Because hey, you never know what happens in half an hour, maybe. But that may be undesirable. It may be more desirable to only load the boss that is showing, on the clients that can see it. And free the memory once it's dead.
Another example would be a game with voice acting where a NPC tells some long sad story about how his father was killed by wolves and how he lost his aunt's ring which you are to retrieve. This is something you want to stream in once, listen to, and never use again. You definitively don't want to keep that around forever or load it ahead of time "just because", especially since there are maybe 50 such NPCs in this city.

The nice thing about the shared pointer approach is that you simply don't care (and you don't even know how long that will be, nor do you have to care!). What's needed stays in RAM, what's not needed is kicked. Eventually.

Actually I care. We had the "Player" class kill its engine sounds inside the destructor. Turns out some reference was still being held somewhere (which was a harmless accident), thus the engine sounds would still run even after game was over and you were inside the main menu. This had me chasing the bug.
If we had many live references, eventually memory would grow big enough for iOS to insta-kill our app for misbehaving. I had to chase all of them. It becomes a house of cards: one reference that holds a reference to a mesh, which holds references to materials (and these... to textures) would result in several megabytes of leaking.

Moral of the story: shared_ptr making you not care about ownership or releasing memory is a fallacy that brings you into a false sense of security. You must care just as much as you would do without shared_ptr. The only difference is that it won't crash on a dangling pointer; but I would argue shared_ptr makes people lazy, so the live reference wouldn't have happened if people were more conscious. Others may differ in this regard, but not on the fact that you still must care.

The performance impact of shared_ptr isn't great in single-threaded code, but is downright stupid in multi-threaded situations. If you saw the actual behavior of that solution written out as plain old C code -- without the use of shared_ptr to hide its stupidity behind an abstraction -- you'd fire whoever wrote it... at least in the context of a game engine.
e.g. The hidden reference counters used internally by shared pointers are thread-safe (via atomic increments), but the shared pointers themselves are not, so they need to be externally synchronized by a mutex/etc...

That's wrong, or rather it is correct but inconsequential.

The reference counter is updated with atomic increments/decrements, that's right. And this is a good thing most of the time (indeed always, except when you are strictly single-threaded, then it's wasting some cycles). The impact of this is however rather low. You do not load 250,000 assets every second. You do not copy around shared pointers 250,000 times per second. That's not what happens. For the comparatively low number of copies that you need to make (few hundred), the overhead of the atomic increments is very acceptable in comparison to the advantages that you buy with them. Yes, it's not free... but by no means a limiting factor unless you do very stupid things.

The pointer itself is, as you point out correctly, not thread-safe. But that is a good thing, not a bad thing. Not stupid, not in any way. You cannot create or reassign a shared pointer in a thread-safe manner. Yeah. Who cares! You don't want to do that anyway.

The shared pointers are created solely by the "manager". One thread, no concurrency. After that, they are, by all practical means, read-only objects (until destroyed). They are deleted solely by the last user decrementing the refcount (whoever that may be). Again, one thread, no concurrency anywhere (not anywhere where the fact that the pointer is not threadsafe would matter, anyway).

The weak pointers are admittedly upped concurrently (well, not necessarily, but at least possibly), but that's fine. The library guarantees that the refcount is managed correctly and once upping the weak pointer to a shared pointer has succeeded, the pointer is valid. Always, no exceptions. No mutex needed.
And if it didn't succeed, the pointer is invalid by definition, so you couldn't care less whether the value is garbled.


I'm afraid you misunderstood Hodgman's example. If Thread A loads textures, Thread B loads meshes, Thread C loads scripts and Thread D consumes all of this; all three threads would have to call Assets.add( assetThreadIsWorkingOn ) as they traverse data folders, while Thread D would have to also use a mutex for the "get" call.
In the end, the mutex is needed, and then the std::shared_ptr will sync again. Because of this, the caches and bus get so polluted and CPUs stalled so much that Thread A, B, C, and D become effectively serialized; would be the same as running everything in one thread.
If you know upfront how many assets you will be loading then it becomes easier and the mutex can be get ridden, but it adds additional constraints (the number of assets needs to be embedded with all the assets and be kept in sync with the actual number every time you build, or if the software scans all folders upfront on every run, then you could have expensive IO seeks).

We're starting to get quite far O/T on that one, but still (my last post, promised). :lol:

... do care

The example that you give, and the interpretation of my wording (although I'll give you that the wording "simply don't care" does lend for it) is somewhat unfair, though.

When I say "don't care" this obviously doesn't mean you just allocate what you like and forget about it, and expect it to magically work. That would be silly.

Nor does it mean you just leak until the OS kills your process because hey, you don't care. It also doesn't mean that you don't care when sounds stop playing (or, don't care if or when any X stops doing Y).

What "don't care" means is: You have the possibility of scheduling something for deletion. That's what the "manager" does by dropping its shared pointer, and it is what the users do as well. Indeed, you do care. By doing so, you state: "I don't need/want this any more, it can as well be deleted". But you don't care whether that happens immediately. You don't need to know, and don't want to know the bare metal details of the delete. But yes, overall you still have to get your deletions right, no surprise there.

The fact that you don't need something doesn't necessarily mean that someone else might not be needing the same thing. And this is just what's complicated to get right: Five different starships might use the same "peooow" sound when they shoot. Or two kinds of knight and an orc make the same "clank" sound when they hit you. One is destroyed, and you unload the sound. Blimey. Now none of the others may shoot, or the game will crash...
Reference counting (shared pointers) solves this non-trivial problem very elegantly.

You don't care whether "deleting" an object deletes the object now, or maybe in 0.1 or 3, or 5 milliseconds, it lives on for as long as someone is reading from it. And if crashing is no option, that's the only way it could possibly be, too.

The issue in your sounds-still-playing example is that your program logic was wrong. You state that sounds were still running, so the fact that a reference was being held and the asset was still loaded does not come as a surprise. But that isn't the shared pointer's fault, it is exactly the other way around. You had wrong program logic, and the shared pointer did its job correctly. It prevented a resource that was still being read from being deleted while it was being read.

Now, I'm willing to grant you that it's debatable if crashing wouldn't have been preferrable in this case. Ideally, wrong program logic should crash (or better, not compile at all), and in this case the smart pointer arguably helped a logic error to survive and hide.
But the world usually is not ideal, and also I guess what's "best" depends on how tight your schedule is, too. If you have time to fix the bad logic, a hard crash is surely preferrable as it forces you to fix it. On the other hand side, if you need to release, shipping a game that works with a non-critical bug (sometimes plays a few too many sounds) is probably more acceptable than a game that crashes hard, presumably without saving highscores and such. That's a very bad user experience.


I'm afraid you misunderstood Hodgman's example

That may be the case, but when reading your explanation, I still see nothing that is particularly a problem of shared pointers either. Yes, atomic increments are not free, never assumed they were. But there are much more heavyweight things going on, and at a higher rate.

A "manager" that runs in the described scenario and holds raw pointers would still have to do exactly the same locking, and don't forget what happens in your task system. It's not like pulling a work item from a queue is exactly free or doesn't involve either atomics or locks. Nor is calling any function of any importance in a sound or graphics library, or any type of syscall.

Maybe I'm really just not understanding properly, but to me, the perceived problem at hands looks (somewhat exaggerated) like this:

// worker thread
for(;;)
{
#if HAVE_BLOCKING_QUEUE
if(queue.is_empty()) event.wait(); // no worries, this actually saves CPU
#endif
while(!(work = queue.try_pop()) && (++spincount < 1000)) {} // no worries, this rarely spins much
do_work();
}
...
// where "work" causes e.g. code like this to run:
shared_pointer foo = // oh shit, the shared pointer costs me an extra 40 cycles and taints a cache line!
manager.get(); // no worries, this cannot be expensive, can it
glBufferSubData(...foo); // no worries, copying two megabytes is a breeze
alListener(...); // no worries, basically no-op, there are no locks or ref-counting that I can see

So from my understanding then, with the current 'shallow' copy the vector is causing the destructor to be called which is then deleting cleaning up 'memblock' making the pointer to the copy of 'memblock' invalid. This sound right?

Yes.

Google 'C++ rule of three' for some greater enlightenment.

Stephen M. Webb
Professional Free Software Developer

So from my understanding then, with the current 'shallow' copy the vector is causing the destructor to be called which is then deleting cleaning up 'memblock' making the pointer to the copy of 'memblock' invalid. This sound right?

Yes.

Google 'C++ rule of three' for some greater enlightenment.

Which is now the rule of 5 thanks to c++11 which will probably be useful given you are (currently) moving around potentially large objects.

https://en.wikipedia.org/wiki/Rule_of_three_(C%2B%2B_programming)

Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.

Nice! Thanks guys. Never heard of the rule of three (five)

This topic is closed to new replies.

Advertisement