allocation/deallocation issues [general C++/vectors]

If you are a new Irrlicht Engine user, and have a newbie-question, this is the forum for you. You may also post general programming questions here.
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

Right, cutealien, I tried using both .at() and raw access as such:

Code: Select all

delete loadID[it];
delete loadID.at(it);
Neither worked


Seven, I have no particular preference for whether to use iterators or not, I'm just unfamiliar with STL in general.
The only reason I use vectors is because I had a vague recollection that they were like dynamic arrays and that solves having to code an array that can change size from scratch. (so no, I don't particularly try to avoid iterators. I'm just wholly unfamiliar with them, most of my code is more or less C with classes, most of the C++ mindset isn't present).


As for the various lists I'm deleting I don't touch the bList (which is of bools) I do however delete the nodes list and the chunk data list (I'd make them the same but couldn't think of any straightforward method of doing that, two lists seemed to be the most elegant since I want to be able to defer the building/rebuilding of meshes or defer the unloading of block data as needed (say, the block data is still being modified when the chunk is supposed to be unloaded, in this case I would like to allow that to continue before unloading, another good example is if I do a lot of operations like exploding a chunk in a short timespan, then I'd like to be able to defer mesh updates until the chunk is done being modified).

I didn't realize I'd need to free the scene nodes however, I expected that to happen when deleting the data stored in the pointer (I was apparently wrong).

The example looks very useful, I'll see what I can get from it (most likely I'll figure out why my iterators are wrong and how to make them not wrong).
"this is not the bottleneck you are looking for"
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

Yeah, looks like you use an iterator there in both cases (given the name 'it'). But 'at' and operator[] both don't work with iterator but with normal indices (aka an int ... or more correctly a size_t).
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

That does indeed seem to be the case, however http://www.cplusplus.com/reference/vector/vector/ doesn't even briefly mention that.
"this is not the bottleneck you are looking for"
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

Well, it kinda does. The parameter-type is size_type while for iterators it says the parameter is an iterator (check for comparision the insert function). But it's also a logic thing - this are functions to find an element at a certain position. While when you have an iterator it means you already have the element.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

Okay, it seems my deallocation issues are solved.
Here's log output (it still crashes but it crashes when allocating more nodes for the obvious reason that I clear the node list which means it's of length 0, trying to access element 1 of 0 is going to crash :P)

Code: Select all

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check
Reached 20 "ticks", polling chunk manager for updates
Polling Lists...
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Deleting chunk data of chunk #6329672 & nodes of chunk #6356440
Do we clear the lists?
populating build list
indx 0
 
I don't know why the log prints arbitrary numbers, my old method printed proper numbers
Here's my delete code now (the numbers change every time, might be because it's a random access iterator or maybe I'm just talking out of my arse)

Code: Select all

void chunkMgr::unloadList()
{
    std::vector<chunk*>::iterator it;
    std::vector<IMeshSceneNode*>::iterator it2;
    it = loadID.begin();
    it2 = nodes.begin();
    while(it != loadID.end())
        {
            printf("Deleting chunk data of chunk #%d & nodes of chunk #%d\n",it,it2);
            delete ( (*it) );
            it=loadID.erase(it);
            delete ( ( *it2 ) );
            it2=nodes.erase(it2);
        }
        printf("Do we clear the lists?\n");
        nodes.clear();
        loadID.clear();
//I should push back new empty entries to the list to allow for repopulating (well, actually that'll happen when I move chunks from the loaded list to the unload list but for now I'm just clearing the loaded list since I could just hotswap any of the lists as I please so long the are of equivalent type)
}

UPDATE:
Here's a new version after I reallocate the lists with empty pointers to allow for generating new batches of chunks:
Irrlicht Engine version 1.8.1
Microsoft Windows 7 Ultimate Edition Service Pack 1 (Build 7601)
Using renderer: OpenGL 2.1.0
Intel(R) HD Graphics: Intel
OpenGL driver version is 1.2 or better.
GLSL version: 1.2
Resizing window (800 600)
Number of blocks: 31
Loaded texture: C:/Users/shiina/Projects/projects/HW/res/texture.png
Loaded texture: C:/Users/shiina/Projects/projects/HW/res/texture1.png
bList contains 8 elements with a capacity of 32
loaded ID list contains 8 elements with a capacity of 8
Time: 378 ms
Time: 422 ms
Time: 465 ms
Time: 506 ms
Time: 548 ms
Time: 591 ms
Time: 633 ms
Time: 674 ms
do we get to the end of the build function?
tick 1
tick 2
tick 3
tick 4
tick 5
tick 6
tick 7
tick 8
tick 9
tick 10
tick 11
tick 12
tick 13
tick 14
tick 15
tick 16
tick 17
tick 18
tick 19
tick 20
Reached 20 "ticks", polling chunk manager for updates
Polling Lists...
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Deleting chunk data of chunk #6657352 & nodes of chunk #6684120
Do we clear the lists?
populating build list
indx 0
adding entry to list
indx 1
adding entry to list
indx 2
adding entry to list
indx 3
adding entry to list
indx 4
adding entry to list
indx 5
adding entry to list
indx 6
adding entry to list
indx 7
adding entry to list
Time: 9216 ms
Time: 9257 ms
Time: 9298 ms
Time: 9337 ms
Time: 9379 ms
Time: 9433 ms
Time: 9479 ms
Time: 9526 ms

RUN FAILED (exit value -1,073,741,819, total time: 12s)
It crashes, I'm not sure why but at least the deallocation bug is gone.

I'd wager it's because I'm using indices to reallocate the lists and to allocate the original lists, either way I consider the original issue of this thread to be solved now.

Again, huge thanks for having patience with my incompetence, without you guys I'd get nowhere.


EDIT2: Now that I think about it I'm probably printing the memory address of the iterator... Ah well, can't say That really bothers me (so long it actually prints things), the only slight difference I've made is to dereference it so I print the address of the element it deletes (that way I have unique numbers for each line which makes the log more readable).

EDIT3: The only reason I can think of for why it would crash where it does is because I'm allocating scene nodes before the endscene, other than that I can't see any reason for it to crash....

EDIT4: That didn't seem to make a difference, the allocation/deallocation worked the same and it crashed at the same point... ah well, still doing progress.
"this is not the bottleneck you are looking for"
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

The strange numbers are like you guessed - you print out the iterators.
I see nothing about crashes. The code should now work. But it can still improve:

You have now both "it=loadID.erase(it);" and "loadID.clear();". The last line will do nothing as you already cleared all elements. But I would remove the first one instead and replace it with a "++it;" which will make this a lot faster (because deleting from the start of an array is slow).

I would use 2 loops in your case. It works as loadID and nodes have the same size. But what if you decide to change that at some point? Better program defensively and delete contents for each in it's own loop.

And you can get rid of some brackets. In this case "delete *it;" is enough (yeah I know I put one pair of brackets around it - but not needed for delete - only for function calls). Not wrong, just looks strange otherwise to experienced coders.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

Changing it makes no sense to me, I have chunk data and the scene node relating to that (I could optimize that to store that pointer in the chunk metadata and then delete that from the chunk constructor, but that's not necessarily needed).

As for the optimizations, yes I realized I had the clear in there still (that's just laziness on my end), your optimization is better than the one I had thought of (just skipping the clears).

And yes, I know the code *should* work now but it doesn't. It segfaults at the end of the second allocation, not sure why but I'm not going to investigate it now either (because it gives me a headache).

I have two theories for what could cause it though:
I need to compile a new irrlicht.dll (I use the one included in the 1.8.1 download that's been sitting on my drive forever, not sure if this is still the newest version but it might be incompatible with GCC 4.8.x, a tad unlikely perhaps since it seems to work fine for most everything but could be worth a shot)
Insane build environment (again unlikely since most code seems to come out working fine).
Me being incompetent and performing some silly error (reasonably likely, given that I am incompetent).
"this is not the bottleneck you are looking for"
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

How's your allocation code looking now?
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

Code: Select all

void chunkMgr::buildList()
{
    //@todo fixme, see notes from 4/4/2015
    fflush(stdout);
    printf("populating build list\n");
    
    if(bList.size() != bList.capacity())
    {
        fflush(stdout);
        printf("build list malformed!\n Rebuilding....\n");
        bList.clear();
        for(int i = bList.size(); i != bList.capacity(); i++ )
        {
            bList.push_back(false);
        }
    }
    if(loadID.size() != loadID.capacity())
    {
        fflush(stdout);
        printf("ID list malformed!\n Rebuilding....\n");
        loadID.clear();
        for(int i = loadID.size(); i != loadID.capacity(); i++ )
        {
            loadID.push_back(0);
        }
    }
    if(nodes.size() != nodes.capacity())
    {
        fflush(stdout);
        printf("node list malformed!\n Rebuilding....\n");
        nodes.clear();
        for(int i = nodes.size(); i != nodes.capacity(); i++)
        {
            nodes.push_back(0);
        }
    }
    
    for( int index = 0; index != indx; index++)
    {
        if(loadID.at(index) == 0)
        {
            fflush(stdout);
            printf("Queueing build of local chunk #%d\n",index);
            bList.at(index)=true;
        }
        else
        {
            fflush(stdout);
            printf("Not building local chunk #%d (already built?)\n",index);
            bList.at(index)=false;
        }
    }
    build();
}
void chunkMgr::build()
{
    for(int index = 0; index != indx; index++)
    {
        if(bList.at(index) == true)
        {
          loadID.at(index) = new chunk(index);
          bList.at(index) = false;
          fflush(stdout);
          printf("Local chunk #%d built...\n",index);
        }
    }
    fflush(stdout);
    printf("All Chunks Built.\n");
}
Really nothing particularly complicated, the initial chunk gen works fine, the diagnostic messages don't hint at anything being wrong (but there might be).
Oh, do look past the derpy index rebuilding code, it's as placeholder-y as placeholders get (which isn't a problem seeing that function is only called during the diagnostic run I'm doing right now, i.e when I know ahead of time that all lists are empty upon building new chunks).

I should update the indices used to iterators but they seem to me mathematically sound so I find it unlikely they would be the cause.

Really the most substantial thing it does is to instantiate the chunk class, set the appropriate entry in the build list to false (for later when I will build chunks as they unload)
as for the chunk class, it stack allocates some memory, builds a mesh, converts it to an IMeshSceneNode and adds it to the scene node list, I can post it if it might be relevant (I don't think it is, it generates n chunks when called standalone without my chunk management blob)
"this is not the bottleneck you are looking for"
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

I must admit I have no idea what your first loops are supposed to do. Where you fill the array up to capacity. If you want to fill it up to a certain size - please use an own parameter for size and just do that. The capacity is some internal value which you generally shouldn't ever care about. It basically tells how much size STL really allocated for the array (as it might allocate more than you need) - which is sometimes interesting, but nothing you use that way. I suspect your "indx" variable might be what you want to use instead (thought you should use a better name like numElements or so).

But even more - the idea of dynamic lists is that you do not need to fill them up ahead anyway. Just push the elements when you need them. So your 2 loops for pushing and adding - you could really do that in one loop where you just push the correct value directly.

I see nothing here that should crash, but as this is only a small part of the code it's hard to tell. In which line did it crash?

Btw, if you do fflush you want to do that after the printf - otherwise it's pointless (you flush what you printed out to the console). But you don't need it usually when you have a newline (aka "\n") as that also triggers a flush (unless it's explicitely disabled).
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

Hm, please also explain what it really *is* you are trying to do. I have the slight feeling that you are complicating your life.
If you have several std::vector's with the exact same size that's often a sign that you really should use a struct instead. Like:

Code: Select all

 
struct MyBaseObject
{   
    MyBaseObject() : id(-1), node (nullptr) {}
    int id;
    irr::scene::ISceneNode * node;
};
 
std::vector<MyBaseObject()> myObjects;
 
And that way you might also not need extra bools. You push an object to myObjects when you need it and then you loop up to myObjects.size() when you go over all objects. And the vector just contains all those objects you need. No need to pre-allocate memory and stuff. That kind of stuff is only so complicated it you work with c-arrays. Dynamic arrays like std::vector make life easier. You don't need extra bools to remember if that object exist already etc. - if it doesn't exist it's not in myObjects. And you don't need to remember array-sizes because myObjects.size() does that for you. And there are no empty places in between because you can remove objects from the array again when you no longer need them.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
Cube_
Posts: 1010
Joined: Mon Oct 24, 2011 10:03 pm
Location: 0x45 61 72 74 68 2c 20 69 6e 20 74 68 65 20 73 6f 6c 20 73 79 73 74 65 6d

Re: allocation/deallocation issues [general C++/vectors]

Post by Cube_ »

oh yes, the loops at the top are my catch all hack in case something goes wrong (however in the current build they are never called).

As for why I'm using vectors over structs is pretty simple (at least in my weirdly backwards way of thinking).
I have a list of chunks to build, this is just boolean true/false (reflecting which chunks to build, say we have local chunk 4 already built and we wish to build the rest, then we loop over it, push back false for the ones that are built and we push back true for the ones that aren't (this is entirely determined by the contents of the chunk metadata vector, if there's no chunk data there's no chunk at that location and as such it should be built).

Now how I intend to handle the chunk vector is that when a batch is unloaded I erase those, update with a new batch of chunks and top the struct off with new chunks (asynchronously, my code *should* be thread safe but I'm not going to implement multi-threaded terrain creation unless I really need the performance boost)

I think this image will explain it better
Image

Essentially the logic follows as such:
Initiate the main function, instantiate the global scene manager pointer (along with device pointer and whatnot, all the standard irr stuff here, just with access from other files)
Instantiate the chunk manager, step through the entire build chain and have the local chunks loaded.
then the main function starts counting ticks, at 20 ticks it calls ChunkMgr::poll() which calls the buildList() and unloadList() (for now, I'll have more lists later like visibility lists to not load a bunch of chunks that cannot be observed at all (underground for example).

Anyway, as I was saying; the lists are polled sequentially, the unloadList talks to the scene manager to nuke old chunks, then the build list is called which builds an appropriate list of boolean values for which chunks to build, once this is done it talks to the chunk manager which then instructs the chunk class to build new chunks that are added to the active list of chunk objects.
Each chunk object then calls its mesh builder function to generate the meshes, it adds these meshes to the nodes list and this concludes the chunk building.
(there's a reason I included a flowchart, it makes the logic a bit easier to follow)

As for my reasons regarding using capacity, that's merely for debugging that it indeed allocated the capacity I wanted (reallocating the entire vector is expensive and theoretically something that can happen if I push_back an element, hence why I check to make sure the capacity is what I intended).
My reasons for pushing back early are also pretty simple, I do checks on elements at location n at arbitrary times and as such I need all elements to be accounted for, even if they are NULL (I actually check for that when building the chunks...)


Note: some parts of the images make a few assumptions (such as the fact that it's clear what data is sent where, mainly I'm just checking lists and populating lists, there's very little other data circulating so I didn't feel it was necessary to include the lists), if something is unclear it's probably because of that.
"this is not the bottleneck you are looking for"
LunaRebirth
Posts: 386
Joined: Sun May 11, 2014 12:13 am

Re: allocation/deallocation issues [general C++/vectors]

Post by LunaRebirth »

I'm sorry I don't entirely understand your question(s).
But hopefully some information below will help you to learn vectors more simply.

Code: Select all

std::vector<int> myVec;
int main() {
   //Let's add 0,1,2,3,...,19,20 to myVec
   for (int x = 0; x < 20; x++)
      myVec.push_back(x);
   printf("I should get 3 here: %i",myVec[3]); //Access 3 from "array" number 3 (starts at 0)
   myVec.clear(); //myVec is now empty
 
   //Add 0,10,20,...,40,50 to myVec
   for (int x = 0; x < 5; x++)
      myVec.push_back(x*10);
 
   //This will work similarly to .clear()
   while (myVec.size() > 0)
      myVec.pop_back();
 
   //Add 0,1,2,3,...,191,192
   for (int x = 0; x < 192; x++)
      myVec.push_back(x);
   
   //Only check for the number 30
   bool run=true;
   int check=0;
   while (run) {
      if (check > myVec.size()) {
         printf("Value 30 wasn't found...");
         run=false;
         break;
      }
      if (myVec[check]==30) {
         printf("It has been found!");
         run = false;
      }
      check++;
   }
   return 0;
}
CuteAlien
Admin
Posts: 9734
Joined: Mon Mar 06, 2006 2:25 pm
Location: Tübingen, Germany
Contact:

Re: allocation/deallocation issues [general C++/vectors]

Post by CuteAlien »

Sorry, I was never good at understanding code explained with flowcharts and human language. I'm far better at reading code itself and then understanding what was meant. So only minor comments:

Checking if capacity really allocated as much as promised - ehm - is kinda careful. But I think you can trust STL that capacity really returns how many elements can be put in there without a re-allocation. And even if not - your loop doesn't really do any check. What it does is to inrease size() to capacity() in a slightly complicated (and slow) way. Not quite sure what the clear() before that is about.

And I don't complain about filling arrays early - that makes often a lot of sense in game programming.
But there is probably no reason to resizing and initialization in 2 different loops. If you want to avoid re-allocations then start by reserving enough memory. You can do that with vector::reserve. Note that this does not change the size - just allocats enough memory that it will not do any re-allcoations until size is beyond the number of reserved elements. And you can initialize values directly with push_back - no need to use vector::at at all. And if you fill all the elements with the same value you can do that even easier. Use resize(size, element_value). That will do it all in one step and fill out all elements with a value. The same can also be done directly in the constructor of std::vector.
IRC: #irrlicht on irc.libera.chat
Code snippet repository: https://github.com/mzeilfelder/irr-playground-micha
Free racer made with Irrlicht: http://www.irrgheist.com/hcraftsource.htm
thanhle
Posts: 325
Joined: Wed Jun 12, 2013 8:09 am

Re: allocation/deallocation issues [general C++/vectors]

Post by thanhle »

@LunaRebirth

I think your example will break at check = myVec.size();

@aaammmsterdddam

I think like CuteAlien mentioned.
You can use an object or struct to store your data.

vector is already dynamic array. You don't need to allocate it at the beginning.

Regards
thanh
Post Reply