MMF2/CF2.5 Optimization Superthread

[DimensionWarped]

NOTE: You might want to skip to the bottom to see if this read is worth your time, it's rather lengthy. and all the fun stuff starts at the image

This thread is for discussing common performance problems in MMF2 and how to deal with them.

Object selection and iteration

One of the most common object selection problems is that you need to be able to iterate through all of the objects of a certain type for some reason. If you've ever done serious object linking in MMF2, then at some point you've probably made a construction like this...
 

Start of Frame

spread value 0 into Alterable Value A("active1")



Always

start loop ("active1_step") for NumObjects("active1")



On Loop ("active1_step")

Alterable Value A of ("active1") == LoopIndex("active1_step")

//actions here

With that last event, you just made your critical mistake.





It's important to realize that MMF2's object selection system can be very taxing if you don't know what you are doing, and Click Team has done a very poor job of explaining how various procedures work from a programmer's point of view. It isn't obvious exactly what you are doing for instance when you create a condition like...

* Alterable Value A of ("active") == 1

Simplistically speaking, we would say "Oh, well this just selects all the instances of the "active" object which have their alterable value of a being 1." and as to the effect, you would be absolutely correct. But eventually you get to the point where you have a thousand of these actions taking place in a fast loop and you are crying because you have a ridiculous level of CPU consumption and little to show for it.

Strictly speaking, when you say...

* Alterable Value A of ("active") == 1

What you are actually doing is iterating through every instance of the "active' object and adding them to a list of "active" objects you are working on for the purpose of any actions you add to the event that have an effect on "active". This is fine when you only have a few instances of an object you need to work on, but it can become exceptionally taxing when you are trying to execute more and more selections based on this kind of criteria, it gets problematic.



As above, one of the most common problems when acting on objects involves iterating through them. This generally means you have some way of ordering them and then you act on them in that order. Normally this is pretty simple, especially if you have some kind of prebuilt list of them for the purpose of iterating, but MMF2 has no such list... at least not one accessible to you.

When we use the spread value method, the basic idea is that we are making this list ourself by assigning values to each of those objects in order. And for the most part, this works fine as long as you don't have just too many objects.

Yesterday I started experimenting though, since I had suspicion for a while now that spread value would not likely be a fast way to handle this... for one, when we are looking at a spread value within an alterable value, MMF2 shouldn't have any way to look at that alterable value and inately know that there aren't multiple instances of the object with the value being sought. This means that it will have to keep looking for valid objects to act until they have all been looked at regardless of whether the object needed was the first or the last looked at.

Suppose we are iterating and we have 100 objects we are looking at only one of which we want to select each time. This means that one of those searches will find the object on its first try... and go through 99 more times evaluating all the others. Meanwhile the last will also use its 100 comparisons. All together, you are using an average of 50 comparisons extra per object when the average number of comparisons should just be a bare fifty. That's already making the operation twice as expensive as it should be.

But wait a minute. Actually, that's not necessary at all. If you have a shopping list of the items, you shouldn't even need to search for them. You should already have an exact address (a pointer) to them.

Unfortunately I'm sad to say MMF doesn't quite have something that awesome. It does however have something much more decent than iterating through everything over and over again.


Enter the fixed value.

I was experimenting this weekend with fixed value and was initially rather dismayed. I tried storing all of the fixed values for an object within an array and then using
fixedvalue of ("active") == loopindex("step")

to select my objects instead of the above method. What I found though was something amazingly fucked up. When you use that condition type, it is actually almost twice as expensive as doing the above operation. So in order to select the object type, you need to go to the generic object conditions and select the one that says:

"pick an object with reference to their value -> fixed value"

and this was much, much, much faster... though I have to comment that it doesn't seem nearly as much faster as it should be if the fixed value is the equivalent to a pointer. I suspect that it actually still has to run what is known as a binary search on objects when selecting by their fixed value.

I also tested this condition for other behaviors such as "what does it do when the fixed value provided doesn't exist/isn't the right object type" and the answer was mercifully "nothing".



Anyway, here's some performance analysis:


THE TEST

This was a simple test to link objects using fixed values in an array and compare it to the equivalent operations using selection by spread value in an alterable value. The user has control over the blue diamonds while the orange diamond pieces follow their parents.

every frame I would run an event called step to reset the orange object positions. The actual implementation for both of these is the same, and the approaches only vary in how the conditions for object selection are set up.

For the test, I created two groups of events, only one of which is supposed to be active.

The first event group selects by fixed values in positions of the array selected based on the loop index. The array was populated at the beginning of the frame during object creation.

The second event group selects by spread values compared to the loop index which were set in the beginning of the frame during object creation.

The results for this test will vary from computer to computer. I'm including the mfa file so you can check your own results. I've set the frame rate peak to 999 (the max is 1000, but it bugs out if you use that and sets a hard cap at 500), which should generally be unobtainable unless you are running this in the future.

The Difference
For me, the control test... that being the one which uses the spread value to select the objects, yielded frame rates of:
85 - 105

But the version that used the array of fixed values to select the objects yielded frame rates between
250 and 650

with the highs occurring during objects standing still and the lows occurring while objects were moving.

So all in all, I'd call this test a success.

Feel free to give the test a whirl yourself and tell me your own results.








Also, as the other purpose of this topic, discuss other problems and we'll try and figure out how to optimize them properly. Now, if you'll excuse me, I need to go reprogram all of my gimmicks to use this more intelligent method of object selection.



EDIT: Here are some more interesting findings too.

Doubling the number of objects brings performance of the spread value method down to between 24-30... dropping slightly to about a third.
Tripling the number of objects brings performance of the spread value method down to 12-13... which is basically half of the value at double (so 50% more objects reduced it by half again)

Tripling the number of objects brings performance of the fixed value method down to 90-400, so that's basically slightly worse than halving instead of being cut to a sixth.

 

optimization.mfa

[Strife]

Note: Here's an alternate download link for those who aren't registered on the forums: http://games.galaxytrail.com/optimization.mfa

Oh. My. Godwin. DW, thank you for this wonderful discovery! You should share this over at the Clickteam forums if they haven't found out about it already.

I've been looking over the MFA file, and I think it would be worthy to note how you'd update the array when objects are created and destroyed during runtime, such as for enemies and projectiles. You'd have to constantly check the array for fixed values that no longer have an associated object and remove those entries. Likewise, when an object is created, you'd need to run a loop through the array and fill in the first empty slot it comes across. In each case, you should run the loop X times, where X is the number of objects in existence.

Also, if you have "child objects" that are attached to the one that you destroyed (i.e. a ball with chain objects attached to it), you'd need to figure out when those child objects are orphaned and remove them.

[DimensionWarped]

I would, but... um, for reasons I'm not going to discuss I wont. I don't mind if someone else does so.

I will document the process better though in the near future.

Actually, as far as creation and destruction goes, your best bet is probably to leave the array as it is and just delete the associated objects. I'll talk later about how to make an array backed 'deletion' stack for keeping the array clean and able to accept new objects without having to constantly expand the array if old objects have been destroyed, but it shouldn't be necessary really unless you are using the array to keep track of lots of newly created and destroyed objects.

[TailsSena]

What it you used the array for rings though? The way I play Sonic games, that would kill the array.

[Serephim]

Holy shit dude.

I dont really have time to check right now, but DW do you believe this method would work in conjunction with LarkSS' Instanced Sensors engine? Making enemies that spawn with 4-5 sensors each, i can't go farther than about 6 or 7 without the framerate suffering, and thats in a frame that only includes the enemies. You seem to have gotten past that issue, with 70 parents with 4 children each...

[TailsSena]

Ah-heh... Hummm... Can someone give me a breezer on how to make Worlds Delta run off an array object instead of alterable values of several objects? My game is running two copies of the Delta engine at once, and it's really CPU intensive. (Worse than The Sims 3, in fact.) FPS tends to hang around 46, with native being at 60, and it even bogged itself down to 15 at one point... Then crashed.

[Serephim]

Be more specific....why on earth would your game be running off "2 copies" of the engine at the same time? How is that even working out?

[DimensionWarped]

Holy shit dude.

I dont really have time to check right now, but DW do you believe this method would work in conjunction with LarkSS' Instanced Sensors engine? Making enemies that spawn with 4-5 sensors each, i can't go farther than about 6 or 7 without the framerate suffering, and thats in a frame that only includes the enemies. You seem to have gotten past that issue, with 70 parents with 4 children each...

Yes, this will substantially improve any kind of sensor binding on multiple instances of an object substantially. The more sensors and the more objects, the greater the improvement will be over the spread value method.

That said, I still recommend you keep the number of sensors as minimal as possible, because collision checks are still expensive.

Ah-heh... Hummm... Can someone give me a breezer on how to make Worlds Delta run off an array object instead of alterable values of several objects? My game is running two copies of the Delta engine at once, and it's really CPU intensive. (Worse than The Sims 3, in fact.) FPS tends to hang around 46, with native being at 60, and it even bogged itself down to 15 at one point... Then crashed.

If it got like that and actually crashed, it's not because of just poor performance. More likely you caused some manner of non-terminating (aka infinite) loop.

[TailsSena]

Be more specific....why on earth would your game be running off "2 copies" of the engine at the same time? How is that even working out?

If it got like that and actually crashed, it's not because of just poor performance. More likely you caused some manner of non-terminating (aka infinite) loop.

@Serephim: Two copis of the 360 base engine, for physics. Why? One for you, one for your partner. AI controls them, but I plan on adding a 1.5 player function ala Sonic 2.

@Dimension Winnie: I had activated the online loop, but it's not infinate, it triggers once whenever the player moves.

[DimensionWarped]

I'd advise against trying to implement such systems if you don't have a firm grasp of optimization. I don't think there is really any big advantage to be had from using arrays and fixed values to differentiate between player 1 and 2, except in terms of memory. It is however perhaps a little easier.

But yeah, you are going to need every optimization to handle two simultaneous players.

[TailsSena]

And does it work against me in any way that "Player 2" is really an AI? I'll flip you my mfa in a little bit so you can get a better look, alright?

[DimensionWarped]

No, not as long as your AI just uses the controls in the same way a second player would.

And no, I don't especially want to look at your code. No offense, but I spend waaaaaay too much time looking at code as it is.

[TailsSena]

Ahh. That's alright then. I'll see what I can do.

[DimensionWarped]

Actually, I might be able to have a look at it this weekend... but just a cursory glance really.

[TailsSena]

Haha! Thanks! Just got the action-point bugs ironed-out. Still trying to make it so that Knuckles and Amy can't spindash or roll, since no sprites for such actions exist.

[Strife]

Yes, this will substantially improve any kind of sensor binding on multiple instances of an object substantially. The more sensors and the more objects, the greater the improvement will be over the spread value method.

That said, I still recommend you keep the number of sensors as minimal as possible, because collision checks are still expensive.

I never use sensor objects for anything other than players and bosses, if I can help it. It may be worth your while to use embedded collision detectors instead.

There's an article at The Daily Click that describes the process in more detail:

http://create-games.com/article.asp?id=1639

[DimensionWarped]

You can actually just keep shuffelling a single set of collision detectors between a single type of object as needed. It's sort of the same concept used when drawing multiple instances of the same sprite to a screen.

[Serephim]

I dont know if i'd call it "optimization", but for the AI controlled enemies in my game that aren't bosses or bigger enemies, i actually use a set of "stage sensors" instead of individual sensors on the enemies.

For example, i'd position left/right wall sensor near walls or boundaries, ceiling sensors on the ceilings, ect ect. It allows me to basically build AI that runs completely off alt. values, which allows me to have an insane number of enemies on the stage at once without even a hiccup (on HWA, anyway.)

Only issue is that it gets annoying to position them on some more complex terrain, and limits me in terms of a few things i could have them do. They can start to build up, too. But honestly i find it much less tedious than the bullshit MMF2's instancing puts you through.

[TailsSena]

I dont know if i'd call it "optimization", but for the AI controlled enemies in my game that aren't bosses or bigger enemies, i actually use a set of "stage sensors" instead of individual sensors on the enemies.

For example, i'd position left/right wall sensor near walls or boundaries, ceiling sensors on the ceilings, ect ect. It allows me to basically build AI that runs completely off alt. values, which allows me to have an insane number of enemies on the stage at once without even a hiccup (on HWA, anyway.)

Only issue is that it gets annoying to position them on some more complex terrain, and limits me in terms of a few things i could have them do. They can start to build up, too. But honestly i find it much less tedious than the bullshit MMF2's instancing puts you through.

What's HWA anyway? MMF2 told be that Worlds Delta Release was saved as an HWA version file, while still being an mfa... It said I might loose some effects and stuff if I opened it... What's the all-fired important difference?

[LarkSS]

MMF2 HWA uses Direct3D9 for many graphical operations so that the GPU can handle some of the load and improve performance where much of the lag was caused by drawing routines rather than expensive code. It also enables more precise scaling/rotation, alpha blending vs semi-transparency (double precision), and pixel shaders which you can import to make your own custom effects.

Nice find DW. I found my performance with those kind of loops to increase when using the ForEach object, but your method seems to yield a much more substantial speedup. I rarely use MMF2 anymore myself, but those making big games with this program should definitely learn what's going on here.

[TailsSena]

Wai-wai-wait... I think I just figured something out. Regular MMF2 gives drawing method options in the runtime properties... I'm thinking it'll work faster/better if instead of using "Normal" I used "DirectX" or "DirectX + VRAM".........

I'll test it!

EDIT: Now that it's running DirectX + VRAM, it can achieve up to 120fps, but doing so makes the whole game run at 2x speed since it's a fastloop-based engine... I think I'll leave it at 60.

[DimensionWarped]

MMF2 HWA uses Direct3D9 for many graphical operations so that the GPU can handle some of the load and improve performance where much of the lag was caused by drawing routines rather than expensive code. It also enables more precise scaling/rotation, alpha blending vs semi-transparency (double precision), and pixel shaders which you can import to make your own custom effects.

Nice find DW. I found my performance with those kind of loops to increase when using the ForEach object, but your method seems to yield a much more substantial speedup. I rarely use MMF2 anymore myself, but those making big games with this program should definitely learn what's going on here.

For Each is on my to do list of experiments. I imagine the actual best combination for the purpose of getting the coding done is actually going to be a combination of for each and array backed pointers like I've shown here.

Anyway, I post now to present some more fixed value wizardry. Now entering...

Linked List

Linked list is a pretty simple concept. You have an object in a list, and it contains a reference to the next item in the list. Easy as that.

How do we do it?

Well, in MMF it's slightly tricky to set up properly because you can't have two of the same object selected in a meaningful way, so you can't just iterate through them one by one picking up the fixed value each time... here's how I do it:

start:
    set proxy.oldFixed to headObject.fixedValue
    start build loop 500 times

On build loop:
    create new object
    set proxy.newFixed to object.fixedValue

On build loop
Select object by fixed value == proxy.oldFixed
    set oldObject.next = proxy.newFixed
    set proxy.oldFixed = proxy.newFixed

That's the basic idea anyway. It's actually slightly more complicated than that simply because I was wrong about the pick object by fixed value keeping you from modifying objects of a different type than what was selected. Yes, this makes things substantially trickier to set up, I might have to recommend using a qualifier, as much as I'm loath to recommend that. The easier alternative is to just track what you should be working on by the loop index.

Without further ado, I present my chain demo. It easily runs at 200 frames per second without even beginning to approach the full processor load.... which really just makes me wonder why it can't go a little higher and top it, but whatever. 500 links. Not bad for something that isn't even especially taxing. I challenge you to spell your name.

And uh... tomorrow I'll explain why this is interesting and useful.

MMF2_linkedlist_practical.mfa

[Felik]

[qimg]http://i96.photobucket.com/albums/l172/DimensionWarped/linkdemo.png[/qimg]

And uh... tomorrow I'll explain why this is interesting and useful.

Um... it terminates instantly when I try to run it.

[DimensionWarped]

Interesting, but without any more details than that, all I can guess is that you should turn down the number of items being created. Or turn down the frame rate.

[Asuma]

They know about the poor, erm less desirable object handling in MMF2. Their excuse for not fixing it is due to the fact that will break people who haven't updated or something like that. Construct has a better object system. You can define different values for one object.

They are working on C2, but C1 is still pretty good, despite that it crashes often. But it is OS, so if any want ot take a crack at it. It's on the SVN. But, I'll save that for another topic. It's nice to see people trying to work around MF2.