Why does one iteration of my arraylist work, while the other does not?

Question

(TLDR: Why does the while-loop repeat infinitely, where the for-loop always works?)

I am writing an Android app, and have a queue of Runnables that need to be run, then removed from this queue:

List<Runnable> queue = new ArrayList<Runnable>();

I wanted to do this the most optimal way, and thought of the following algorithm:

synchronized(queue)
{
    while(queue.size() > 0) 
    {
        queue.remove(0).run();
    }
}

This caused errors, so I had to add this check: if (queue.size() > 0) before the loop (is that really necessary?). Now, however, this seems to be stuck in an infinite loop. I had to change my loop to this, which works well:

synchronized(queue)
{
    for (int i = 0; i < queue.size(); i++)
    {
        queue.get(i).run();
    }
    queue.clear();
}

My question is - what is the low-level difference between these loops? Why does the while loop fail?

Why would it be more optimal to edit the contents of the queue multiple times? The second option you show only edits the contents of the queue once, so it should perform better anyway. — Nathaniel Jones, Jan 10 '14 at 22:08
Are you manipulating the ArrayList in multiple threads? It's not a thread-safe class, so you'll see weird behavior if you are. — John R, Jan 10 '14 at 22:10
@NathanielJones `clear()` loops through the items in the `ArrayList`, making this *O(n)* time complexity - so basically its like two simultaneous *for-loops*. The first option would only be one iteration. — Phil, Jan 10 '14 at 22:10
Even if you are using synchronization for reading we cant be sure you are using it for writing. Maybe some other thread is adding values to queue in unsynchronized way while you are reading/removing your data from it. — Pshemo, Jan 10 '14 at 22:11
Why not use one of the actual queue implementations from `java.util.concurrent` ? — Mike B, Jan 10 '14 at 22:14
@Phil `clear()` does loop through the array, but `remove()` calls `System.arraycopy()` each time you call it, so `clear()` still should perform better. — Nathaniel Jones, Jan 10 '14 at 22:14
@NathanielJones thanks for the optimization tip! That is great to know. I will definitely stick with the second loop - but I *am* still curious about this problem. — Phil, Jan 10 '14 at 22:15

score 1 · Accepted Answer · answered Jan 10 '14 at 22:43

Actually I can not mention the reason why the while loop snippet freezes. A noticeable difference is that in the first scenario the condition in the while loop depends on what happens in the body. What i mean is this line

queue.remove(0).run()

is supposed to decrease the size of the queue and if it does not the loop won't end. In the second scenario the loop condition does not depend on what happens in the loop body. The queue is not changed in the for loop body and when the loop starts it is predefined how many iterations there will be. So my conclusion is that something with this line:

queue.remove(0).run()

messes the things up. Can you please try this:

synchronized(queue)
{
    for (int i = 0; i < queue.size(); i++)
    {
        queue.remove(0).run();
    }
}

and see what happens. The possible reasons for this problem may be: - The remove method may not work properly - Threads started within the loop may cause the problem.

Good answer. Somehow the code began to work - but with my runnable code in the dark, I think this provides the *best guess* for where something went wrong (that is - what could have caused a delay or an infinite loop). — Phil, Jan 10 '14 at 23:13

Mike B · Answer 2 · 2014-01-10T22:27:47.583

I just tried this (not in Android though) and it worked fine:

public class Main
{           
    public void run()
    {       
        final Runnable runMe = new Runnable()
        {
            @Override
            public void run()
            {
                System.out.println("Hi");               
            }           
        };

        List<Runnable> queue = new ArrayList<Runnable>() {
            private static final long   serialVersionUID    = 1L;
            {
                add(runMe); add(runMe); add(runMe); add(runMe);
            }
        };

        synchronized(queue)
        {
            while(queue.size() > 0)
            {
                queue.remove(0).run();
            }
        }
    }   

    public static void main(String[] args)
    {       
        new Main().run();
    }
}

[are-works-for-me-answers-valid](http://meta.stackexchange.com/questions/118992/are-works-for-me-answers-valid) — Pshemo, Jan 10 '14 at 22:33

Why does one iteration of my arraylist work, while the other does not?

2 Answers2