Iteration over List performance improvement

[tiatin]

Hello!

Frequent garbage collection in JME 3.1 worries me a little. I have been profiling my application and here is a list of allocation hot spots: objects, which are GCed within some minutes:

Vsync is off, about 600 fps for renderer and 120 fps for BulletPhysics. Scene has about 2000 objects spread among ~40 batch nodes.

Leader of objects allocation is ArrayList.iterator (38%) and there are 2 hot spots for It: Material and Technique. There is an article about performance and avoiding garbage collection. Notably test 9 “Iteration over ArrayList” is interesting.

There is a small contribution, where iteration over a list is changed to manual iteration for 2 hot spots.

Old code:

com.jme3.material.Material

private int applyOverrides(Renderer renderer, Shader shader, List<MatParamOverride> overrides, int unit) {
        for (MatParamOverride override : overrides) {
            VarType type = override.getVarType();

            MatParam paramDef = def.getMaterialParam(override.getName());

            if (paramDef == null || paramDef.getVarType() != type || !override.isEnabled()) {
                continue;
            }

            Uniform uniform = shader.getUniform(override.getPrefixedName());

            if (override.getValue() != null) {
                if (type.isTextureType()) {
                    renderer.setTexture(unit, (Texture) override.getValue());
                    uniform.setValue(VarType.Int, unit);
                    unit++;
                } else {
                    uniform.setValue(type, override.getValue());
                }
            } else {
                uniform.clearValue();
            }
        }
        return unit;
    }

com.jme3.material.Technique

private void applyOverrides(DefineList defineList, List<MatParamOverride> overrides) {
        for (MatParamOverride override : overrides) {
            if (!override.isEnabled()) {
                continue;
            }
            Integer defineId = def.getShaderParamDefineId(override.name);
            if (defineId != null) {
                if (def.getDefineIdType(defineId) == override.type) {
                    defineList.set(defineId, override.type, override.value);
                }
            }
        }
    }

New code:

com.jme3.material.Material

private int applyOverrides(Renderer renderer, Shader shader, List<MatParamOverride> overrides, int unit) {
    MatParamOverride override;

    // manual iteration is used to avoid iterator allocation and to increase iteration performance
        for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
            override = overrides.get(i);

            VarType type = override.getVarType();

            MatParam paramDef = def.getMaterialParam(override.getName());

            if (paramDef == null || paramDef.getVarType() != type || !override.isEnabled()) {
                continue;
            }

            Uniform uniform = shader.getUniform(override.getPrefixedName());

            if (override.getValue() != null) {
                if (type.isTextureType()) {
                    renderer.setTexture(unit, (Texture) override.getValue());
                    uniform.setValue(VarType.Int, unit);
                    unit++;
                } else {
                    uniform.setValue(type, override.getValue());
                }
            } else {
                uniform.clearValue();
            }
        }
        return unit;
    }

com.jme3.material.Technique

private void applyOverrides(DefineList defineList, List<MatParamOverride> overrides) {
    MatParamOverride override;

    // manual iteration is used to avoid iterator allocation and to increase iteration performance
        for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
            override = overrides.get(i);

            if (!override.isEnabled()) {
                continue;
            }
            Integer defineId = def.getShaderParamDefineId(override.name);
            if (defineId != null) {
                if (def.getDefineIdType(defineId) == override.type) {
                    defineList.set(defineId, override.type, override.value);
                }
            }
        }
    }

Diff:

jme3-core/src/main/java/com/jme3/material/Material.java
@@ -750,7 +750,12 @@ public void selectTechnique(String name, RenderManager renderManager) {
     }
 
     private int applyOverrides(Renderer renderer, Shader shader, List<MatParamOverride> overrides, int unit) {
-        for (MatParamOverride override : overrides) {
+        MatParamOverride override;
+
+        // manual iteration is used to avoid iterator allocation and to increase iteration performance
+        for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
+            override = overrides.get(i);
+
             VarType type = override.getVarType();
 
             MatParam paramDef = def.getMaterialParam(override.getName());

jme3-core/src/main/java/com/jme3/material/Technique.java
@@ -111,7 +111,12 @@ final void notifyTechniqueSwitched() {
     }
 
     private void applyOverrides(DefineList defineList, List<MatParamOverride> overrides) {
-        for (MatParamOverride override : overrides) {
+        MatParamOverride override;
+
+        // manual iteration is used to avoid iterator allocation and to increase iteration performance
+        for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
+            override = overrides.get(i);
+
             if (!override.isEnabled()) {
                 continue;
             }

Allocation hot spots after this update:

Now ArrayList.iterator allocation is insignificant in comparison with the rest.

If to turn on vsync, fps will be changed from ~600 to 60. Situation with GC objects will be better (iteration update is applied), because update is 10 times less frequent, but now 1st place for GC is LWJGL:

I guess it is hard to do anything with it. Maybe things are better in LWJGL 3.

PR: Garbage collection and list iteration improvements by tiatin · Pull Request #515 · jMonkeyEngine/jmonkeyengine · GitHub

[Dokthar]

@tiatin

List<MatParamOverride> overrides
…
for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
override = overrides.get(i);
…
}

You are iterating through a List assuming this is an ArrayList, which is not certified by the method declaration.

(and the variable override can be declared in the for loop.)

[tiatin]

@Dokthar

You are iterating through a List assuming this is an ArrayList, which is not certified by the method declaration.

size() belongs to List interface, so no assumption about ArrayList takes place.

@Dokthar

(and the variable override can be declared in the for loop.)

override is declared outside of loop to avoid declaring it each time for every iteration. Even if it is created in the stack and does not pollute the heap, I think it has sense to declare it once before the loop. JVM could optimize it, but need to check the specification.

Anyway, thank you for the comments!

[Dokthar]

@tiatin

size() belongs to List interface, so no assumption about ArrayList takes place.

well you are iterating with .get(i) which is assuming this is an ArrayList, when dealing with LinkedList you would iterate through an iterator which is way more efficient than using get(index)
edit : LinkedList is not good at random access .

[tiatin]

@Dokthar

well you are iterating with .get(i) which is assuming this is an ArrayList, when dealing with LinkedList you would iterate through an iterator which is way more efficient than using get(index) edit : LinkedList is not good at random access .

This is a good point Get by index has a complexity O(n/4) average for LinkedList, so iterator is preferable in this case. Currently those overrides come from

protected ArrayList<MatParamOverride> worldOverrides;
...
private final List<MatParamOverride> forcedOverrides = new ArrayList<>();

so they are always ArrayList, but we can’t assume, that they will stay ArrayList in the future.

Need to think how to clean up the code to avoid using instanceof.

[Dokthar]

@tiatin

so they are always ArrayList, but we can’t assume, that they will stay ArrayList in the future.

Need to think how to clean up the code to avoid using instanceof.

i was thinking of method overloading (kind of polymorphism) …

[tiatin]

What do you think about such approach

private void applyOverrides(DefineList defineList, List<MatParamOverride> overrides) {
    MatParamOverride override;
    boolean isArrayList = overrides instanceof ArrayList;
    Iterator<MatParamOverride> iterator = isArrayList ? null : overrides.iterator();

            
        // manual iteration is used to avoid iterator allocation and to increase iteration performance in case of ArrayList
        for (int i = 0, listSize = overrides.size(); i < listSize; i++) {
            override = isArrayList ? overrides.get(i) : iterator.next();
            ...            
        }
    }

?

@Dokthar

i was thinking of method overloading (kind of polymorphism) …

Method overloading will fail, because applyOverrides(dynamicDefines, worldOverrides); passes List to the method. If we create

private void applyOverrides(DefineList defineList, ArrayList<MatParamOverride> overrides) {

we need to pass ArrayList explicitly, but we can’t cast applyOverrides(dynamicDefines, (ArrayList)worldOverrides);, because we don’t know for sure, that worldOverrides is ArrayList. So in the end we will need to move instanceof to the parent and we win nothing.

[Dokthar]

I don’t know …
this is how i would not do it :

    private final MyShityOptimizedIterator shityOptimizedArrayListIteratorPool = new MyShityOptimizedIterator();

    private int applyOverrides(Renderer renderer, Shader shader, List<MatParamOverride> overrides, int unit) {
        Iterator<MatParamOverride> it;
        if(overrides instanceof ArrayList) {
            shityOptimizedArrayListIteratorPool.setArrayList((ArrayList) overrides);
            it = shityOptimizedArrayListIteratorPool;
        } else {
            it = overrides.iterator();
        }

        while (it.hasNext()) {
            MatParamOverride override = it.next();
            ...
        }
        return unit;
    }
    
    private static class MyShityOptimizedIterator implements Iterator<MatParamOverride> {

        private int i;
        private int listSize;
        private ArrayList<MatParamOverride> array;
        
        public void setArrayList(ArrayList<MatParamOverride> al){
            array = al;
            i = 0;
            listSize = array.size();
        }

        @Override
        public boolean hasNext() {
            return i < listSize;
        }

        @Override
        public MatParamOverride next() {
            return array.get(i++);
        }
        
    }

[tiatin]

Well, idea is to avoid iterator completely if possible. Implementing own iterator for ArrayList is a bad idea from the start. Allocation hot spots after adding the ArrayList safe check:

[Ali_RS]

thanks a lot @tiatin the article was informative.

[shamanDevel]

A small note: if we want to use instanceof to check which version to use, I would check against RandomAccess instead of ArrayList to be more flexible.

But I’m not sure if this instanceof + casting would not be actual slower than using the normal iterator? Has someone tested that? I’ve heard that using instanceof and casting can slow down the code because it disables some optimizations of the JIT.

[Dokthar]

@shamanDevel

A small note: if we want to use instanceof to check which version to use, I would check against RandomAccess instead of ArrayList to be more flexible.

didn’t know that interface exist .

---

Op is talking about two different performances issues : Garbage collection and iteration speed.
And I assume the problem is memory consumption than speed.

[pspeed]

Would be even better to hunt down where the original lists are… if we can convert them to SafeArrayList then we could just be passing an array to this method, get better performance overall, no allocations, and go back to the less ugly for-each code.

[tiatin]

@shamanDevel

But I’m not sure if this instanceof + casting would not be actual slower than using the normal iterator? Has someone tested that? I’ve heard that using instanceof and casting can slow down the code because it disables some optimizations of the JIT.

If to talk about performance, then instanceof happens once per method, but in case of iterator next() method is called during each iteration.

@pspeed

Would be even better to hunt down where the original lists are… if we can convert them to SafeArrayList then we could just be passing an array to this method, get better performance overall, no allocations, and go back to the less ugly for-each code.

I didn’t know about com.jme3.util.SafeArrayList. As I see it is possible to get array through getArray() and for-each code doesn’t produce an iterator for regular array, which is very good. As applyOverrides methods do not modify/remove overrides, it is ok to pass MatParamOverride[] to the methods. I will update ArrayList to SafeArrayList and refactor the code. Thank you, Paul!

[pspeed]

@tiatin

for-each code doesn’t produce an iterator for regular array, which is very good.

Also, it’s faster than the get(index) style code… because the compiler can generate much more efficient code for an array loop (and on desktop hotspot can do way better with it, too).

[tiatin]

@pspeed, ArrayLists have been changed to SafeArrayLists. PR cumulative change.

Need to mention, that Spatial public methods getLocalMatParamOverrides(), getWorldMatParamOverrides() now return SafeArrayList<MatParamOverride>. As before they returned List, user’s code, which uses these methods is compatible with this update. The same is for RenderManager.

I see, there is no serialization implemented for SafeArrayList, and fallback to ArrayList is used in some places. Is there any technical difficulty to implement “true” SafeArrayList serialization? Or is it done to maintain serialization compatibility with previously used ArrayList?

I have also fixed SafeArrayList.equals(). It is obvious, that objects are not equal when either of them have more items. SceneMatParamOverrideTest.testOverrides_CloningScene_DoesntCloneMPO() assertEquals(clonedOverrides, originalOverrides); brought out the bug.

If anyone is interested here is an allocation hot spots for current revision (Integer.valueOf is not related to JME):

It would be nice to get a code review. Thank you!

[pspeed]

@tiatin

Need to mention, that Spatial public methods getLocalMatParamOverrides(), getWorldMatParamOverrides() now return SafeArrayList<MatParamOverride>. As before they returned List, user’s code, which uses these methods is compatible with this update. The same is for RenderManager.

Was this change really necessary? It does force a recompile of any code that uses it and in general we’ve tried not to expose SafeArrayList through public APIs when it’s not strictly necessary.

@tiatin

I see, there is no serialization implemented for SafeArrayList, and fallback to ArrayList is used in some places. Is there any technical difficulty to implement “true” SafeArrayList serialization? Or is it done to maintain serialization compatibility with previously used ArrayList?

You shouldn’t need to do this… just have to make sure to convert the regular array list to a SafeArrayList when you read it.

[tiatin]

@pspeed

Was this change really necessary? It does force a recompile of any code that uses it and in general we’ve tried not to expose SafeArrayList through public APIs when it’s not strictly necessary.

It is not necessary, but if we keep List we need to cast it to SafeArrayList. For example in this place: SafeArrayList<MatParamOverride> overrides = geometry.getWorldMatParamOverrides();. Cast will be needed because getArray() is absent in List interface. So, which is better, keep List and cast to SafeArrayList, or keep SafeArrayList everywhere? From my point, it is better to keep SafeArrayList and avoid casting. Current user’s code expects List, and SafeArrayList implements this interface, so user’s code won’t be broken. What do you think?

@pspeed

You shouldn’t need to do this… just have to make sure to convert the regular array list to a SafeArrayList when you read it.

And I do it this way. Regular ArrayList is converted to/from SafeArrayList.

[pspeed]

@tiatin

What do you think?

Yeah. It’s only an issue when external libraries use it… which it hasn’t been around long enough for that to have happened.

Else when we change method signatures like that we break every already compiled class so any libraries, user code, etc. has to be clean built against the new API. (It doesn’t matter that it’s still List as you will get method not found errors for any code still compiled against the plain List version.)

This code is new enough that it shouldn’t affect anyone, I guess.

[tiatin]

Got it. It has sense. As current master is meant to be part of JME 3.2, such public method change is ok to do. Probably, 3.1 is also ok.