Pointers are too costly memory wise?

Question

I know this is not appropriate , but I wanted to get SO's opinion .

I am building a simulation where the objects have to interact with each other. So inorder too keep track of the other object an object interacts with , I am keeping pointers to them. But in my case , an object might have to interact with about 15 000 other objects and hence I end up having to keep 15 000 pointers in a vector for each of the objects . I want at least 1 billion , hopefully more of these objects to do a proper simulation of my problem .

I am thinking of storing the objects in a vector and then just using an index to refer to the object. This way I will be able to just need to keep a vector of 15,000 32 bit integers rather than storing 15,000 64 bit pointers.

One disadvantage of this might be that there will be slow down in performance , but I am willing to give up some performance for larger scale ?

15 000 is the maximum , sometimes I just need to point to a 1000 objects.

Are there any better solutions to this problem ? Has anyone else faced similar problems in simulation etc , and what did you do ?

Are there any good books / articles etc on doing large scale simulation in cpp ? I am also worried about how issues like caching , locking and memory alignment is going to hit my performance .

Thank you for the suggestions in the comments. I wanted to give more information about locality within the problem.

An object only interacts with other objects in its vicinity , and this vicinity are different sections . Meaning , there are sections within the larger space. And if an object is within a section , it only has to interact with other objects within that section. There are some object which interact across sections , but I am ignoring them.

This seems to be the only relevant information that I can give you.

Answer 1

An object only interacts with other objects in its vicinity , and this vicinity are different sections . [...] And if an object is within a section , it only has to interact with other objects within that section.

If every object within a section interacts with every other objects in the same section, you can just keep track of the section your objects live in. Considering you don't have too many sections, you can probably do that with a single int per object. When you want to know whether two objects have to be interacting, compare their section number.

Another, hopefully better way to do that might require you to redesign your simulation. If objects only live within sections, then make these sections own your objects. That way, you don't need the extra "section number" for each object. When considering interactions, simply operate within one section at a time.

Also, as vu1p3n0x said in the comments, you might want to consider using quadtrees (or similar higher dimension trees). It really depends on the kind of simulation you are building.

There are some object which interact across sections , but I am ignoring them.

There are several ways to represent interactions across sections.

One way is to make them a totally different kind of data. An interaction would be represented by two sections, and within these sections, either the list of objects that are "on the edge" and can interact across the sections, or the list of actual interactions between couples of objects, depending on your simulation.

Another way is, in each section, to store differently objects that can interact across sections, let's call them border objects. Let's say that each section can interact with (objects within it can interact across) four other sections. You then store your objects in five different containers : one where objects cannot interact across sections, let's call them center objects, and one per other section for border objects. These four latter containers represent the borders of the section. When iterating over objects of a section, you first consider the center objects as you would before. Then, for each border, you consider its border objects as well as the border objects from the corresponding section. This assumes that any object in a given section can interact with objects within the same section or within only one other section.

Answer 2

If you don't have the memory to store, for each object, the list of other objects it interacts with, then an easy way to save memory is to simply not store the list and recompute it every time you need it.

Or, if needed, store a small amount of information that lets you regenerate the list.

This assumes that your problem actually allows that.

---

Similarly, you can save portions of the data to disk and reload it as necessary. This requires knowing how to do I/O efficiently, of course. (unless you're doing a lot of computation on each part of the data before moving onto the next part)

Answer 3

It think that there is no need to keep a vector of pointers for each object, unless the vector is going to be different for each object. If each object is going to interact with all other objects, you only need to keep one vector of references and just skip the interaction between an object and itself when it occurs.

I would not keep information about each couple objects' interaction in memory, I would try and recompute it on the spot (given the size of the problem, that's the only think you can do, unless you are working with super-computers). That includes the information about whether the interaction will take place at all.

If the objects have memory about their past relationship... I don't know, that's a harder problem. In that case you may be lucky and the set of "memorable relationships" is small for each object, otherwise... It's harder!

Answer 4

Simulation is just too broad to answer exactly what you are asking.

The best thing I could say is that there is always a:

trade-off between speed and space.

So, usually more space means more speed (you pay more space to get faster execution, makes sense, doesn't it?).

---

If you use integers of 32 bits, rather than pointers of 64 bits, then you would decrease the space requirements of your project. However, when it comes to speed, you can only know if it is acceptable or the performance drops rapidly.

I would suggest you to test/profile your code, by enabling optimization flags for your compiler (for examle -03 in g++) with both cases and measure the execution time.

If the execution time differs by little with the approach that takes less memory, then I would probably choose than one. But again here, it is worth-noting that:

you should decide what's critical for your application, speed or space!