AnimationCurve vs Dictionary performance ?

Discussion in 'Editor' started by n0mad, May 10, 2012.

  1. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Hello,

    I'm nailing the last bits of performance crunching on my AI, and was searching for the most efficient and fast way to provide it a good prediction routine about the movements and bounds of AI's target. Most movements are animations, so I have to write down a hard imprint of each animation bounds position (at fixed steps). Until now I was doing runtime prediction, either using Animation.Sample or just a Bezier prediction routine, but Sample is costing too much for complicated predictions, and Bezier lacks of accuracy about the bounds size. Plus, Sample() is calculating every single child tansform, which is overkill as I only need one child info (the target's hitbox).
    So I chose to go the hard stored data route, and then lookup at runtime.

    So I thought first about storing steps into Dictionaries, as they're the fastest lookup structure around. But then I thought back about AnimationCurve. They would save me a lot of RAM at runtime, thanks to AnimationCurve.Evaluate avoiding to have tons of entries, and I would just have to clone each bound's animation key instead of retrieving/storing its coordinates in a Dictionary (using Editor script).

    "Cut the crap n0mad ! What's the question !"

    ---> What is the average time in miliseconds, on an average PC, to :
    1) build an AnimationCurve from let's say 200 keyframes ?
    2) retrieve a keyframe with Evaluate ?

    or if there's not precise answer (in miliseconds), what would be the fastest between :
    1) building an AnimationCurve with keyframes and building a Dictionary with new Bounds() as Values ?
    2) retrieving a keyframe with Evaluate and retrieve a Dictionary Value by Key ?


    The results are important only if the differences between those are more than 0.3 miliseconds (either it is for building a single AnimationCurve/Dictionary entry, or retrieving a value at runtime).
     
    Last edited: Nov 16, 2012
  2. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Ok I ran some tests :

    Created 2 Dictionaries with 1 entry each.
    One entry is an AnimationCurve[6] array (bounds position + size), each AnimationCurve being created with 1000 Keyframes.
    The other is a Bounds[1000] array. All coordinates are generated with Random.value. Keyframes time values are just the iterator converted to float.
    I also calculated the bytes needed, assuming that each keyframe is 4 * 2 bytes ([time + value] floats), and each Bound is 4 * 6 (center + size).

    Results :

    Code (csharp):
    1.  
    2. time to dataload 1000 x 6 keyframes : 6 ms, bytes in memory : 48000
    3. per bound : 0.006 ms to load, 48 bytes
    4.  
    Code (csharp):
    1.  
    2. Bounds test :
    3. time to dataload 1000 bounds : 2 ms, bytes in memory : 24000
    4. per bound : 0.002 ms to load, 24 bytes
    5.  
    The other main difference :

    The thing is, there will never be as many keyframes as there would be Bound entries, as the Bounds approach consists in "baking" the animation. So for the AI to be accurate, there should be 1 new Bound entry every 1/30 seconds (30 fps) at least, so every 0.0333 seconds.

    For one 1 second length animation, this would mean 30 entries. Or 0.06 ms to load, and 720 bytes.
    With 800 animations of 1 second each, the Bounds approach would mean a fixed 48 ms to load, 576 kBytes.

    But with keyframes, there's no need to bake as we're using curves. So unless we got a twitchy movement, 1 second animation could very possibly be just 3 keyframes. Let's take the worst case : 10 keyframes.
    For one 1 second length animation, this would mean 3 to 10 entries. Or 0.018 to 0.06 ms to load, and 144 to 480 bytes.
    With 800 animations of 1 second each, the AnimationCurve approach would mean 14 to 48 ms to load, 115k to 384k Bytes.

    Now, if we consider this test was run on a modern PC, this means we can multiply per 10 the results to have an estimation of loading times on a Samsung Galaxy S ->
    800 anims would be 0.5 seconds to load with Bounds, 0.14 to 0.5 seconds with Curves.

    So on the creation question, AnimationCurve clearly wins.
    Now with the runtime lookup :
    __________________

    For the runtime Lookup, I just made a 10000 loop iteration of one "new Bounds". Its input values are what is read from the data :
    1 x Dictionary Lookup + 6 x AnimationCurve.Evaluate for curves,
    1 x Dictionary Lookup for Bounds

    Results :

    Code (csharp):
    1.  
    2. AnimationCurve approach :
    3. time to read and create 10000 bounds : 45 ms
    4. time for 1 bound : 0.0045 ms
    5.  
    Code (csharp):
    1.  
    2. Bounds approach :
    3. time to read and create 10000 bounds : 6 ms
    4. time for 1 bound : 0.0006 ms
    5.  
    So on a Samsung Galaxy S, predicting one entire character Bound would be :
    0.045 ms for the AnimationCurve approach
    0.006 ms for the Bounds approach


    This runtime lookup test was important, as I knew the Dictionary lookup is already super fast, but I didn't know how fast was AnimationCurve.Evaluate.
    __________

    Comparison with runtime bounds guessing, using Animation.Sample() :

    Sample might be fast for what it accomplishes, but the two solutions above clearly blows it out of the water.
    As reference, Sampling a 42 bones character on my testing machine costs 0.17 ms.
    Means 1.7 ms on a Galaxy S.
    __________

    Conclusion :

    AnimationCurves win on data loading, but loses to Bounds baking on data runtime reading. But the difference between the two on runtime reading is so ridiculous that I won't bother to care.
    The Bounds baking costs a bit more memory too, but it's not that dramatic. Finally, the real game changer for me is that with Bounds baking, unless I crank it up to 1/60 seconds baking instead of 1/30 (which would make it lose its advantages), the AnimationCurve will always be more accurate.

    Result : for animation prediction, hard writing the AnimationCurves is the way to go.
     
    Last edited: May 10, 2012
  3. n0mad

    n0mad

    Member

    Joined:
    Jan 27, 2009
    Messages:
    3,731
    Update : as stated in this thread, hardwriting AnimationCurves inside C# dictionary is not the way to go, finally. Because of how Unity doesn't compress it, we end up with big freaking huge DLLs, which are impossible to compile on iOS.

    So the way to go would be to serialize those curves inside a binary asset, and deserialize at load.
    Unless Unity decides one day to expose animation clips' AnimationCurves at runtime ..........
     
  4. SARWAN

    SARWAN

    Member

    Joined:
    Oct 23, 2012
    Messages:
    8
    Anyone from this forum made the conversion from Hash table to Dictionary in the iTween Plugin.

    If anyone converted the script means post it. That ll be useful.