ArrayList Iterator Remove is very slow compared to normal computer

[LordTylus]

Please ensure you have given all the following requested information in your report.

Issue details

Hello,

I had to filter a huge ArrayList on my iPad today. Which I realized via an Iterator with conditional remove call.

I noticed, removing 100,000 entries from the list takes about 1100 ms on my Windows-Device. But for some unknown reason it takes about 200,000 ms on the iPad.

Reproduction steps/code

Please provide detailed step by step instructions that will reproduce this issue

 List<String> strings = new ArrayList<>();
        
        for (int i = 0; i < 100_000; i++)
            strings.add(i + ""); //$NON-NLS-1$

        Iterator<String> iterator = strings.iterator();

        while (iterator.hasNext()) {
            iterator.next();
            iterator.remove();
        }

Of course this test-code removes all entries from the list which can be done by calling the clear method, but in my case I ran into the situation where I had to remove about 80 % of the lists content. The list was slightly larger too.

I was able to help myself by using a different kind of collection but I wonder if there is something wrong with the implementation on IOS side, since it seems unusual slow for such a simple task compared to a Windows machine handling the same in just one second.

Configuration

Please provide the build system, version(s), and targets affected.

Build Tools:

• [ ] IDEA plugin
• [ * ] Eclipse plugin
• [ ] Gradle plugin

Versions:

Please provide the version of RoboVM, XCode and JDK used

• Robovm: 2.3.3
• XCode: 8.3.3
• JDK: 1.8.144

Build Targets:

Please provide the build targets this issue is seen on if applicable. e.g. iPhone 4s Simulator 32bit

iPad Air 1 (IOS 10.3)

[clydebarrow]

An ArrayList is a very bad choice if you intend removing elements. Filtering any collection, especially if you expect to end up with a small subset, is best done by creating a new collection and adding the desired elements to it. Removing an element from an ArrayList results in a call to arraycopy() which on RoboVM is implemented as a loop for non-primitive types which is why it's so slow, but since ArrayList it is not intended to be used in that manner, I would see little value in anyone spending time to improve it.

[LordTylus]

Indeed thats true.

I was able to improve it by not using an Arraylist but Instead a LinkedList which improved it a lot. I just reported it because the very same test is so much faster on other devices.

I dont really intend to revert it back to an ArrayList because the LinkedList works just fine. So I dont really mind if this one gets closed. But I thought it may be a good idea to take a closer look at it. Well or at least to let people know that they should not do the same as I did.

[clydebarrow]

Sigh.. I just couldn't leave this one alone. So, first up, here is a test file and some results.

package example.com.lib


/**
 * Created by clyde on 9/2/18.
 */
class ArrayCopyTest(val value: String) {
    companion object {
        const val LENGTH = 100000
    }

    fun testStringArrayCopy() {
        val array = Array<String>(LENGTH, { it.toString() })
        // copy backwards
        System.arraycopy(array, 1, array, 0, LENGTH - 1)
        var i = 0;
        for (el in array) {
            if (i == LENGTH - 1) {
                if (el != i.toString())
                    throw IllegalStateException("Final element is incorrect")
            } else if (el != (i + 1).toString())
                throw IllegalStateException("Element ${i} is incorrect - should be ${i + 1} but is ${el}")
            i = i + 1
        }
    }

    fun testIntArrayCopy() {
        val array = IntArray(LENGTH, { it })
        // copy backwards
        System.arraycopy(array, 1, array, 0, LENGTH - 1)
        var i = 0;
        for (el in array) {
            if (i == LENGTH - 1) {
                if (el != i)
                    throw IllegalStateException("Final element is incorrect")
            } else if (el != i + 1)
                throw IllegalStateException("Element ${i} is incorrect - should be ${i + 1} but is ${el}")
            i = i + 1
        }
    }

    fun speedTestInt(): Long {
        val then = System.currentTimeMillis()
        val array = IntArray(LENGTH, { it })
        for(i in 0 until LENGTH)
            System.arraycopy(array, i, array, i+1, LENGTH-i-1)
        return System.currentTimeMillis() - then
    }

    fun speedTestString(): Long {
        val then = System.currentTimeMillis()
        val array = Array<String>(LENGTH, { it.toString() })
        val list = ArrayList<String>(LENGTH)
        list.addAll(array)
        while (!list.isEmpty())
            list.removeAt(0)
        return System.currentTimeMillis() - then
    }
}

Running on Android, Genymotion simulator on a late model iMac, the times are: 02-12 14:41:12.111 4084-4098/com.example.speedtest I/TAG: speed test Int: 1770 02-12 14:41:14.675 4084-4098/com.example.speedtest I/TAG: speed test String: 2562

Not too shabby, and reasonably consistent between the two (string is presumably slower because pointers are 64 bit vs ints being 32 bit.)

On RoboVM running on an iPad simulator, same host machine:

2018-02-12 14:42:37.853 IOSLauncher[88151:44776385] [info] TAG: speed test Int: 1428 2018-02-12 14:43:22.885 IOSLauncher[88151:44776385] [info] TAG: speed test String: 45031

The String case is pretty pathetic, due to the array copy being done by a Java loop.

Stand by for more....

[clydebarrow]

Now with some VM tweaks - same simulator, same host:

2018-02-12 15:29:49.455 IOSLauncher[5937:44926248] [info] TAG: speed test Int: 349 2018-02-12 15:29:50.355 IOSLauncher[5937:44926248] [info] TAG: speed test String: 884

[clydebarrow]

64 bit iPad mini 4:

2018-02-12 15:43:55.428693+1100 IOSLauncher[583:702557] [info] TAG: speed test Int: 2998
2018-02-12 15:44:02.176306+1100 IOSLauncher[583:702557] [info] TAG: speed test String: 6701

32 bit iPad 4th Gen - faster on String arrayCopy due to 32 bit pointers. CPU clock speed is similar to the mini:

2018-02-12 15:45:31.414004+1100 IOSLauncher[436:192326] [info] TAG: speed test Int: 2929
2018-02-12 15:45:34.350298+1100 IOSLauncher[436:192326] [info] TAG: speed test String: 2837

[clydebarrow]

And completing the comparison - reverting back to the original VM on 32 bit iPad gives these numbers:

2018-02-12 16:09:03.982765+1100 IOSLauncher[607:199256] [info] TAG: speed test Int: 10512
2018-02-12 16:13:49.947069+1100 IOSLauncher[607:199256] [info] TAG: speed test String: 285851

Pull request to follow.