2
\$\begingroup\$

Say I have a GameObject class that is being extended by all of the objects in the game that are moving around. (This class provides basic stuff like a sprite, draw method, update method with application of move vector and so on...) I also have a class Asteroid that like I said extends GameObject

Then there are two versions of the game:

Version 1: Somewhere in the game there is a Collection that holds all of the Asteroid-objects. The update Method is something like this:

for(Asteroid a : asteroids)
    a.update(...)

Draw method goes equivalent.

Version 2: I decided to put all of my GameObjects in a single collection, so that all moving stuff is being handled in one single loop like this:

for(GameObject o : gameObjects)
    o.update(...)

Again, draw method goes equivalent.

The problem I am facing with version 2 is that the game loop basically takes twice as long. (The update method as well as the draw method.) I am astonished at the draw method, since in either version there is the exact same amount of object being drawn. So my question is: Does this abstraction in version 2 affect the game's performance in any way? (I can imagine that version 2 requires the JVM to alway cast the GameObject implicitly to it's specific type which it does not have to do when the type is already given like in version one, but I am not sure about that.) (I am using Java with LibGDX if it matters)

\$\endgroup\$
  • \$\begingroup\$ If gameObjects is a collection of subtype of GameObject then - no, it doesn't affect the performance, as you are just looping over objects like in any other loop. In C# in Unity there is a foreach loop and it created a lot of garbage a while ago, maybe, it's also a case for java. I prefer using standard loops, in this case they could even give more description about problem. \$\endgroup\$ – Candid Moon _Max_ Jun 5 '18 at 9:27
  • \$\begingroup\$ @CandidMoon this is not quite true - see the answer below. The unnecessary boxing we used to get from foreach would create at most one extra allocation of a few bytes for the loop as a whole. It could add up over time and trigger more GC work, but it wouldn't account for something like the 2x slowdown described here. \$\endgroup\$ – DMGregory Jun 5 '18 at 11:01
  • \$\begingroup\$ @DMGregory yeah, you are right. In comment I didn't consider all of those things like virtual methods... I just assumed that the problem lied in iterating over collection. \$\endgroup\$ – Candid Moon _Max_ Jun 5 '18 at 19:03
5
\$\begingroup\$

It looks like you don't really need to ask "Does abstraction influence performance?" - because you did one better: you tested and measured it! "The problem I am facing with version 2 is that the game loop basically takes twice as long. (The update method as well as the draw method)"

So we know something is causing slowness. The question is where exactly it creeps in and why.

  1. Indirection

    When you have a collection of all one concrete/final type, any method calls like asteroid.update() can point directly to the compiled code for that method - or even get automatically inlined in some cases.

    When the collection may contain multiple types each with their own different update method, there's an extra step of indirection required: we need to use the type information to look at the appropriate vtable, then use that to point to the appropriate update method code. So there's at least one extra step in every update() call.

    This is normally a reasonably small hiccup for the flexibility it gives, and you might pay it either way if the Asteroid type isn't final, since you might have IronAsteroid and Iceteroid subtypes with their own update methods. But it sets us up for...

  2. Misprediction

    Modern CPUs have deep pipelines, so often they don't know the result of some operation until quite a few cycles after they started working on it. If everything that depended on that operation had to wait for the result, they'd slow to a crawl. So instead they have sophisticated features to guess what the result will be and execute chains of instructions on that assumption, then invalidate/roll back only if they guessed wrong.

    They're surprisingly good at guessing right, which gives them a tremendous speed-up compared to naive execution. But code patterns that confuse their predictions can throw all that out the window and force them to keep re-doing work due to a wrong guess.

    If you're always calling the same method in a loop, those jumps are easy to predict correctly, and the prediction machinery can learn which way that method's branches tend to go, so you rarely guess wrong.

    If you're calling multiple different methods in a random mish-mash with no discernible pattern, the predictor is more likely to guess wrong and have to re-do work.

  3. Cache Thrashing

    If you're always using the same chunk of instructions in asteroid.update() over and over, they stay in the processor's innermost cache levels and are very quick to access repeatedly.

    If you switch between lots of different update() methods, the code for each one needs to get pulled into cache, which might kick out part or all of a different update() method, which then needs to be re-fetched from slower cache or main RAM the next cycle.

    The same thing can happen with your data. You probably have a loading/generation step somewhere in which you spawn all your asteroids for the level/chunk at once. Those are likely to end up close-together in memory, and iterating over them in order will tend to make good use of the cache. In a collection of mixed types though, which were probably spawned in different times, the memory accesses can jump around almost randomly, so your CPU has to spend more time waiting for data to get pulled in from main RAM.

    (Learn more about this under the names of "locality of reference" or "code & data locality")

  4. Draw Calls & State Changes

    This one's more speculative, since I don't know the details of your draw method. But if it involves setting up any render state like making sure the asteroid's texture and shader are bound, then this can have an impact. Rendering a lot of the same object back-to-back is usually more efficient for the graphics pipeline, making full use of its silicon.

    When you draw one asteroid, then a rocket, then a planet, then another asteroid, each with their own shader or texture, the GPU can often draw only one at a time, waiting for the full operation to complete before swapping its rendering state to start on the next one. This leaves a lot of performance on the table and wastes time switching states back and forth.

None of this is to say that object oriented programming abstractions are always awful or slow and that you shouldn't use them. Very often, the flexibility and clarity they offer can make them worthwhile for many developers' working styles, and performance can often be very good. The best thing you can do is exactly what you're doing: write code that makes sense to you, and profile it so you understand its real cost, and can make informed decisions about where to structure things differently.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for this detailed answer, I really appreciate it. It was indeed very helpful at some points. \$\endgroup\$ – purpule Jun 5 '18 at 12:52
  • \$\begingroup\$ (1) - I am not that familiar with vtables, but according to this codebetter.com/patricksmacchia/2008/01/05/… JIT compiler can do some optimizations in C# for sealed classes. final in Java might do the same. \$\endgroup\$ – Candid Moon _Max_ Jun 5 '18 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.