Object of arrays or array of objects?

Question

I'm making a management sim game, something along the lines of Roller Coaster Tycoon. I want to know what the best way to structure my world objects is so to maximise performance.

Let's say I have 5,000 people in my game I could:

Make an object and store them in an array like so;

class person() {
    this.x = 0;
    this.y = 0;
    this.thirst = 15;
    this.hunger = 15;
    // etc.. add methods:
    public findPath(int destX, int destY) {
    // and so on
    }

    people = new person[5000];

for (int = 0; i < 5000; i++) {
    people[i] = new person;
    }

Or should I make an object of people that contains many byte arrays representing attributes of people like so:

class people() {
    this.hunger = new byte[5000]
    this.thirst = new byte[5000]

    getThirst(int i) {
        return this.thirst[i]
        }

 // and so on....

Or am I totally off the mark?

Answer 1

The common terminology is "structure of arrays" (SOA) and "array of structures" (AOS) which come from C and is most often seen in terms of SIMD work.

Typically, the AOS approach is faster, if used appropriately, but SOA tends to be easier to work with (and hence optimizes for the more important quality - development time).

SOA, especially in Java, means that your data can remain tightly packed in memory. You can iterate over properties and expect the CPU cache and such to remain happy. With AOS, especially in Java, every object ends up allocated "somewhere" in memory. Iterating over objects could potentially thrash your CPU cache pretty heavily.

In the end, I would take whichever approach you find easiest to use. Your development time is far more valuable than whether your game supports 10 year old PCs or only 9 year old PCs (you're very unlikely to be doing anything htat needs the latest hardware).

Answer 2

There's no reason you can't have both, using the Facade pattern to translate from one interface to the other underlying representation. For example, using Sean's SOA/AOS terms:

SOA facade

class PeopleFacade {
    Person persons[5000];
    getThirst(int i) { return persons[i].thirst; }
}

AOS facade

class People { int thirsts[5000]; } people;
class PersonFacade {
    int i;
    getThirst() { return people.thirsts[i]; }
}

This way you can freely choose between a form you are comfortable with using, as a developer interface, vs whatever's best as an implementation for whatever reason, including efficiency/cache reasons.

Another advantage to the facade is that it leads very naturally to the Flyweight pattern, where you use an interface to represent much more persons than are actually in memory. For example, perhaps you have robotic patrons which are never thirsty; then you can put that special case into your PersonFacade, and users of that interface never have to know about robots:

class People { int nonRobotThirsts[1000]; } people;
class PersonFacade {
    int i;
    bool isRobot;
    getThirst() {
        if (isRobot)
            return 0;
        else
            return people.nonRobotThirsts[i];
    }
}

... or using a more OO approach, you'd have a separate Robot class which acts exactly like a Person except for getThirst().

Answer 3

Make objects and store them in an array! Making arrays for hunger and thirst may save a bit of space and run faster in some simple situations, but it's not OOP. Java and OOP will do a great deal for you if you give them a chance. For a really simple game, your second example might work fine, but even then you should be practicing your OO skills. Your first approach will work well for you no matter how large, complex, and hairy your program gets.

Think of all the times it will be handy to get a Person object back from a query. Who sent this message? for instance. A lot of methods you write will want to know who they're dealing with. And you'll have a lot of methods that will fit nicely into a proper Person class. If Person is static or a singleton, where do you put methods that act on individual people?

Should you ever do multithreading--and with 5000 users you might be pushed into it--you will find the Parent instance for each user a lot more practical.

(And that array of people: stick with it for now, but at some point you'll want other storage devices. A Map of some sort so you can find people by name. And maybe several lists with different keys, and probably bunches of lists each short enough to be arrays or linked lists.)