UIAtlas cached dictionary of UISpriteData to improve GetSprite() performance

[andreyd]

On the very large UIAtlases with a lot of small sprites in it, there is a considerable amount of time spent in GetSprite() method (most of the time spent comparing string names). This is noticeable when you have a lot of elements on the screen (like in UIScrollView) that have different sprites and scrolling becomes somewhat laggy. In most cases this behavior could be solved by adding a dictionary to UIAtlas, something like Dictionary<string, UISpriteData> spriteDataDictionary. Yes, there is some memory overhead for this, but GetSprite could be replaced by just calling spriteDataDictionary[name] and is O(1) instead of O(n).

[andreyd]

I did a quick dictionary implementation and my performance in the scroll view improved dramatically. I shaved off about 4-5ms per frame when I was scrolling. It now takes 0.4ms to UIAtas.GetSprite() instead of 5ms before.

[Nicki]

Sounds good to me, I'll try to make a little test version of it and pull request it into NGUI if it gives significant results.

[ArenMook]

The problem with a dictionary is that Unity won't be able to serialize it anymore, so there has to be both, and both need to be kept in sync with each other. Currently UIAtlas.spriteList can be modified freely, so that's a problem.

[Nicki]

My findings were something of the same, there's a bunch of places where the spriteList is accessed directly from outside the UIAtlas, making this a bit difficult to implement properly.

I suppose an easy way was to sacrifice a little bit of loading time and memory and make the dictionary at run time, since the atlases don't change at that point (or shouldn't really) and use that for the GetSprite access. I'll poke a little more at it.

[Nicki]

Ok so I made a preliminary version, where I generate a Dictionary<string,int> with indexes in the spritelist, which gets Generated when you access GetSprite, if it's not there already.

1.  
2. private Dictionary<string, int> mSpriteIndexes = new Dictionary<string, int>();
3. private bool mIndexesDirty = true;
4. //(...)
5. public UISpriteData GetSprite (string name)
6.         {
7.                 if (mReplacement != null)
8.                 {
9.                         return mReplacement.GetSprite(name);
10.                 }
11.                 else if (!string.IsNullOrEmpty(name))
12.                 {
13.                         if (mSprites.Count == 0) Upgrade();
14.  
15.                         if (mIndexesDirty || mSpriteIndexes.Count != mSprites.Count) GenerateSpriteIndexes();
16.                         int index;
17.                         if (mSpriteIndexes.TryGetValue(name, out index))
18.                         {
19.                                 return mSprites[index];
20.  
21.                         }
22.                         else
23.                         {
24.                                 for (int i = 0, imax = mSprites.Count; i < imax; ++i)
25.                                 {
26.                                         UISpriteData s = mSprites[i];
27.  
28.                                         // string.Equals doesn't seem to work with Flash export
29.                                         if (!string.IsNullOrEmpty(s.name) && name == s.name)
30.                                                 return s;
31.                                 }
32.                                
33.                         }
34.                 }
35.                 return null;
36.         }
37.  
38. (...)
39.  
40. void GenerateSpriteIndexes()
41.         {
42.                 mSpriteIndexes.Clear();
43.                 for (int i = 0; i < mSprites.Count; i++)
44.                 {
45.                         var uiSpriteData = mSprites[i];
46.                         mSpriteIndexes.Add(uiSpriteData.name, i);
47.                 }
48.                 mIndexesDirty = false;
49.         }
50.  

You'll notice that it's somewhat naieve, and you need to manually set mIndexesDirty if the content of the spriteList is changed, sorted or some such. It also incurs a higher cost the first time, as it has to do a run through of the sprite list to generate the dictionary. That however pales in comparison with the otherwise constant iteration of the old version.

test case

1. void Test1()
2.         {
3.                 var sprite = GetComponent<UISprite>();
4.  
5.                 Stopwatch sw = Stopwatch.StartNew();
6.  
7.                 for (int i = 0; i < 1000; i++)
8.                 {
9.                         sprite.spriteName = SPRITE_A;
10.                         sprite.GetAtlasSprite();
11.                         sprite.spriteName = SPRITE_B;
12.                         sprite.GetAtlasSprite();
13.  
14.                 }
15.                 sw.Stop();
16.                 Debug.Log("Time to switch: " + sw.Elapsed);
17.  
18.         }

GetAtlasSprite triggers the actual getting of data, which otherwise would only be fired once per update, which would otherwise make it impossible to test without many, many different sprites that changes. You'd also have to have the stopwatch persist for all the time, polluting the results. Point being, the results might be exaggerated, but should be representative.

Results:
Tested with an atlas that has 323 sprites in it. (the higher, the worse for the old way)


For the first tests, the SPRITE_A and SPRITE_B where randomly selected (both number 73 and 74).
Test with 1.000 (x2) sprite changes shown in ticks (http://msdn.microsoft.com/en-us/library/system.timespan.ticks.aspx)
List search -  first run: 38.724, subsequent: ~33.000
Dictionary lookup -  First run: 6.613, subsequent: ~4.800

Improvement: factor of ~6.

Test with 10.000 (x2) changes
List search -  first run: 352.759, subsequent: ~340.000
Dictionary lookup -  First run: 48.725, subsequent: ~47.000

Improvement: factor of ~7.

In the last test, I specifically chose the two last sprites in the list (322, 323) to show worst case (or bad case) scenario:

Test with 10.000 (x2) changes
List search -  first run: 1.364.008, subsequent: ~1.350.000
Dictionary lookup -  First run: 45.522, subsequent: ~43.000

Improvement: Factor of ~30.

So it does seem like the standard way gets significantly slower as the amount of sprites grow, ~300 sprites = factor 30, ~70 sprites = factor 7 suggests that +10 sprites adds a factor.


So, this treatise does suggest some merit in a dictionary wrapper for sprites.

[ArenMook]

Well, I've made my own set of changes adding the dictionary and pushed them to Github. I tried to make them more robust, so they only take place at runtime, making it far less likely that the user will need to ever call the "rebuild indices" function.

[andreyd]

Thanks Aren and Nicki. Any chance those changes will make into the next release?

[ArenMook]

Already a part of 3.6.7 that was released a few days ago.