Fix for TODO in OpenStreetMapAsyncTileProvider

[GoogleCodeExporter]

Cleaned up OpenStreetMapAsyncTileProvider to do the TODO.  Specifically:

 - Changed pending map to pending TreeSet and Sorting on PendingEntry
 - Synchronizing on pending set to prevent concurrent modification exception.  I realize this was breaking the loop to ensure the next tile loaded was the last added...but I think using the sorted set and not iterating over the entire pending map will make this better.

OpenStreetMapAsyncTileProviderTest passes.

Original issue reported on code.google.com by yelirk...@gmail.com on 18 Jul 2010 at 4:27

Attachments:

• osm_async_tile_provider_cleanup.patch

[GoogleCodeExporter]

Ooops!  Wrong patch.  This one should be correct.

Original comment by yelirk...@gmail.com on 18 Jul 2010 at 5:01

Attachments:

• osm_async_tile_provider_cleanup.patch

[GoogleCodeExporter]

Hi
Bear with me as I'm not so familiar with the osmdroid code yet.
Can you explain what you mean by "I realize this was breaking the loop to 
ensure the next tile loaded was the last added"?

In your patch:
+           PendingEntry ent = new PendingEntry(aTile);
+           mPending.remove(ent);
+           mPending.add(ent);
What's the logics behind doing mPending.remove(ent)? Could two entries ever 
have the same System.currentTimeMillis()?

Original comment by andpet@gmail.com on 18 Jul 2010 at 10:00

• Changed state: Accepted

[GoogleCodeExporter]

Basically, the TileLoader.nextTile() method used to iterate over all of the 
entries in mPending until it reached the tail.  I believe it used 
ConcurrentModificationException as a signal to restart the iteration as this 
would have been thrown when an entry was added to mPending.  The patch I 
submitted should remove the need for the iteration (thus "do the todo") and 
remove the need to use ConcurrentModificationException as a signal.

The remove() followed by the add() is necessary because we want to ensure that 
the most recent tile requested is the next tile loaded, even if the tile has 
already been requested.  If the tile was previously requested and is in the 
mPending set, it should be moved to the top of the set.  To achieve this 
behavior, when PendingEntries refer to the same (.equal()) tiles, they are 
determined equal even with different add timestamps.  So the remove() will 
remove the existing entry and the add() ensures its at the head.

I apologize if I've misinterpreted the code or its intent as I am new to the 
codebase as well.

Original comment by yelirk...@gmail.com on 19 Jul 2010 at 4:35

[GoogleCodeExporter]

Thanks for your explanation. Using an exception as a control signal sounds like 
a bad thing so your patch seems much better.

  "To achieve this behavior, when PendingEntries refer to the same (.equal()) tiles, they are determined equal even with different add timestamps."
Don't you need a custom equals() in PendingEntry for this?

Original comment by andpet@gmail.com on 19 Jul 2010 at 8:28

[GoogleCodeExporter]

Because the Set uses .compareTo() for Comparable items, I used that instead.  
See the first two lines of PendingEntry.compareTo for details.

Original comment by yelirk...@gmail.com on 19 Jul 2010 at 4:35

[GoogleCodeExporter]

Committed in r292

Original comment by andpet@gmail.com on 20 Jul 2010 at 9:01

• Changed state: Fixed

[GoogleCodeExporter]

The code that you changed was introduced as a result of issue 27.

I haven't compared the performance yet, but using a LinkedHashMap had a great 
performance improvement.

Of course catching a ConcurrentModificationException isn't great design, but it 
seemed like a reasonable compromise.

You've also changed a catch Throwable into a catch Exception. I haven't checked 
this specific case, but in general the reason for catching Throwable is because 
OutOfMemoryError is not an Exception.

So although the code is tidier, performance is more important. So you should 
check that the remove/add and the synchronization doesn't add too much 
performance overhead.

Just to be clear, I'm not criticising this change - I'm glad that more people 
are looking at the code.  I'm just trying to point out the history to anyone 
who's newer than me.

Original comment by neilboyd on 21 Jul 2010 at 8:41

[GoogleCodeExporter]

I'm certainly newer than neilboyd. The code seemed reasonable enough to me but 
if you have a better idea, of course I don't mind.

Original comment by andpet@gmail.com on 21 Jul 2010 at 8:52

[GoogleCodeExporter]

Neil,

I understand your concerns.  I can try to put together some tests which will 
determine if the synch decreases performance over the previous code.

I did find, however, that there is a bug in my code.  The remove/add will not 
work properly when more than one pending entry exist between two pending 
entries referencing the same tile.  Basically, the sorted set will not remove 
the existing pending entry as I thought because the set is obviously not 
comparing each item for insert/removal.  Sorry...I don't know what I was 
thinking.

Anyway...I will attach another patch shortly.  Unfortunately it will most 
likely require maintaining multiple collections of pending entries :(.

Original comment by yelirk...@gmail.com on 21 Jul 2010 at 11:11

[GoogleCodeExporter]

Heres a new patch with an updated unit test.  I'm not sure I really like having 
to maintain multiple collections so I won't be upset if you simply revert my 
previous patch.

Original comment by yelirk...@gmail.com on 21 Jul 2010 at 11:28

Attachments:

• osm_async_tile_provider_take2.patch

[GoogleCodeExporter]

Neil, andpet

I think I've come up with a decent compromise.  Its still synchronized but 
instead of using a sorted set, its using something similar to a LinkedHashMap.  
The insertion time and remove time should be constant like the LinkedHashMap 
but entries may be popped off the top.  

Let me know what you guys think.

Thanks,

-mark  

Original comment by yelirk...@gmail.com on 22 Jul 2010 at 2:55

Attachments:

• osm_map_tile_queue.patch

[GoogleCodeExporter]

I've remove your change because I'm pretty sure the previous version worked 
okay, even though it's not the best solution.

I think the two lists are fundamentally required
 - mPending is tiles that need to be processed
 - mWorking is for tiles in mPending that are currently being processed.
If you removed tiles from mPending while they're being processed then they 
would get added back again if they're requested again. I think that's what 
happens with your last patch.
You could have only one queue if the items in it also had a flag to say whether 
they're being processed.

I think the ideal solution would be to write something like LinkedHashMap that 
gets the most recent entry rather than the oldest entry. That's what you did 
with OpenStreetMapTileQueue, but I was trying to avoid duplicating code. I 
originally looked at extending LinkedHashMap, but the relevant bits are 
private, and I didn't want to duplicate the whole thing. Writing your own 
version is more error-prone than relying on native Java code. LinkedHashMap 
also has the functionality to limit the size, which is also important here.
If you do that then you wouldn't need the TODO part, and you wouldn't get the 
ConcurrentModificationException.

My subjective feeling is that adding synchronisation causes the code to 
noticeably hang occasionally. I think you can avoid it, for example by not 
worrying about occasional threading "errors", such as getting a tile that isn't 
strictly the correct next one, or by having tiles in mWorking that are not in 
mPending.

So that's my thoughts again ;-)

I'd be very happy if you could continue looking at this because it's a tricky 
and important piece of code, but I'll reserve committing until we're all sure 
it's an improvement.

Original comment by neilboyd on 22 Jul 2010 at 1:53

• Changed state: Started

[GoogleCodeExporter]

"If you removed tiles from mPending while they're being processed then they 
would get added back again if they're requested again."

>  I'm not sure this is true as the code in 
OpenStreetMapAsyncTileProvider.loadMapTileAsync still checks mWorking.

With that said, I'm working on merging the working map with the mTileMap in 
OpenStreetMapTileQueue similar to the way you've suggested.

I'm also going to tighten the synchronization a bit.

Finally, I'm going to write some tests that will hopefully expose any 
performance problems with synchronization.  My plan is to write a simple app 
that will add/remove tiles from the different types of queues and record time.  
If you guys have any other suggestions for testing performance I will gladly 
write the code.

-mark

Original comment by yelirk...@gmail.com on 22 Jul 2010 at 5:49

[GoogleCodeExporter]

This issue is about synchronization again. It's been fixed in issue 78.

Original comment by neilboyd on 10 Sep 2010 at 2:39

• Changed state: Fixed

[GoogleCodeExporter]

Neil,

I thought I would finally post the patch that I've been using for a while in 
case you had a change heart.  I'm also attaching a test app I wrote as an 
attempt to test the performance of the LinkedHashMap vs the custom queue.  Its 
not the best test, but its something I threw together quickly to test the 
performance on the phone.  Note:  If you don't want to build it, you can 
download it: http://www.markriley.net/files.php/a.apk.

I'm not seeing any real different in performance of the OpenStreetMapTileQueue 
with synchronization vs the LinkedHashMapTileQueue without synchronization on 
my phone.  If you get a chance, give it a try and let me know if you see 
something different. 

I won't be upset if you don't want to change what exists.  I still understand 
your concerns.

-mark

Original comment by yelirk...@gmail.com on 22 Sep 2010 at 6:47

Attachments:

• osm_async_tile_provider_final.patch
• OSMTileQueueTest.tgz