Map is 20x faster than List?

Monkey Forums/Monkey Programming/Map is 20x faster than List?

slenkar(Posted 2011) [#1]


This speed test is based on a real world problem,
there are 300x300 characters and the game can only display a 30x30 portion of the map at a time, so using a Map or list the game has to decide which chars are on the screen to draw.

the characters have to be drawn in order so they look right for the z-order, so that is why i go through 30x30 iterations

i went through the list to see which characters lie within the range 0 to 30 and added them to a drawing list

with Map I didnt even need to do anything like that ;)
In MING-GLFW
Map took 13 millisecs
and list took 243 millisecs
In Flash
List time 4907
map time 62
In html/javascript
map time 6
List time 219


FlameDuck(Posted 2011) [#2]
Three things:

1) Please GOD, indent!
2) Your benchmark is set up with a massive map bias. The list benchmark is doing two orders of magnitude more work.
3) You're wrong. Since the list is doing two orders of magnitude more work, and in less than two orders of magnitude of time (that is it only took 243ms instead of the 1300 we would expect) your numbers indicate that lists outperform maps by at least a factor of 5.

The speed difference is mainly due to the underlying implementation. I'm guessing the List uses a LinkedList, while Map uses a HashMap. In this case the List will (generally) perform better for sequential access (that is iterating through the list) and the Map will (generally) perform better for random access. In your case I suspect, a 2D, or jagged array would outperform both Lists and Maps.


GC-Martijn(Posted 2011) [#3]
weird topic :S

If I understand it..

slenkar say that he works with Maps because they are a lot faster.
flameDuck say that that's not correct.

Maybe there is some way to test this correctly so we know what to use (and when)

For example, I have a lot objects inside a List something like this.
Field myobjects:List<MyObject> = New List<MyObject>


And then the only thing I do with in every Render loop is

For Local obj:= Eachin myobjects
   obj.Draw()
Next


Or is it in this case better to use a Map ?


muddy_shoes(Posted 2011) [#4]
"Is Map faster than List?" only results in another question: "When doing what?". I attempted to explain the point in this thread: http://monkeycoder.co.nz/Community/posts.php?topic=1527 .

@GC-Martijn: For your example a simple array would probably be faster, but your usage is clearly incomplete because it doesn't include populating the list.


Jesse(Posted 2011) [#5]
@GC-Martijn
No in your case it s best to use List as FlameDuck states: sequential access is faster.
and better yet use arrays.
you must also take into consideration that if you are removing objects randomly through "list.Remove()" in this case maps will be faster. but there are ways to help lists perform faster by removing objects from the list in a more direct way. For my personal purposes, I have found that list perform faster than maps but I am sure there are other reasons to use maps over lists.


FlameDuck(Posted 2011) [#6]
flameDuck say that that's not correct.
Actually FlameDuck is saying "That's not what your example shows". Slenkars example shows that 90000 operations takes up to 20 times longer than doing 900 operations. Now the numbers provided isn't really the greatest sample size, but it's clear from casual reading of the algorithm that he is benchmarking 2 different units of work, and therefore cannot be comparable. It should be self evident that doing something 900 times is going to be significantly faster than doing something 90000 times. Now reasonably you would expect 100 times the work, to take 100 times longer, but interestingly enough it only takes about 20 times longer, thus we can logically deduct that while the overall amount of work takes longer (because it's larger), the individual work unit is actually much faster (because it finishes faster).

So for *his* *example* *only* what the data conclusively shows is actually that Lists are 5 times faster than Maps, and not that which was indicated in the OP.

I am sure there are other reasons to use maps over lists.
Maps are "associative arrays". You use them in situations where you want to associate one thing with another. For instance if you have an RPG which has a sword, an axe and a polearm as weapons, you could have a weapons Map of those values which map to the relevant objects. So your code could go map.get("sword") and you would get the object which represents the sword weapon.

Maybe there is some way to test this correctly so we know what to use (and when)
Read a good book on data structures and/or algorithms. This one's good.


slenkar(Posted 2011) [#7]
my overall message is that map is crazy fast for random access compared to list


AdamRedwoods(Posted 2011) [#8]

my overall message is that map is crazy fast for random access compared to list

WTF? o_O
From that example? No!

The LIST LOOP is going through 300*300 samples before it does it's own 30*30 loop. The MAP LOOP is only going through 30*30 iterations!!!!

Arrays would be the correct route if you are making map access for a game.

ADDITIONALLY: the map access is a string key (vs. int key), MAKING EVERY ACCESS longer than it should be.


AdamRedwoods(Posted 2011) [#9]
I've plugged in an array example and my array loop time is < 1ms.




slenkar(Posted 2011) [#10]


The LIST LOOP is going through 300*300 samples before it does it's own 30*30 loop. The MAP LOOP is only going through 30*30 iterations!!!!



if you move the 'camera' you would have to do that do get the list of chars to render to the screen.
Its faster than NOT doing it.

ADDITIONALLY: the map access is a string key (vs. int key), MAKING EVERY ACCESS longer than it should be.


im storing the characters in the map by their position, I cant get individual numbers from their x and y coords. Ill get repeats


slenkar(Posted 2011) [#11]


The LIST LOOP is going through 300*300 samples before it does it's own 30*30 loop. The MAP LOOP is only going through 30*30 iterations!!!!



if you move the 'camera' you would have to do that do get the list of chars to render to the screen.
If I dont do that the list take 20 seconds.


ADDITIONALLY: the map access is a string key (vs. int key), MAKING EVERY ACCESS longer than it should be.


im storing the characters in the map by their position, I cant get individual numbers from their x and y coords. Ill get repeats


Jesse(Posted 2011) [#12]
I would really like to see your real world example in which the map is faster than the list.


AdamRedwoods(Posted 2011) [#13]
I think the correct title to this thread should have been "what is the fastest way to access a map grid?" List vs. Map vs. Array, and Array wins.


As for a STRINGMAP vs. INTMAP, you can make an x-y int map key by the algorithm:

mapkey:int = x Shl 5 + y
c.map.Set(mapkey,c)
..and..
Local c:char=char.map.Get(mapkey)

As long as your x and y values are less than 65535 ($FFFF) then it'll work.
The key will be stored internally as ($FFFF0FFFF). And this type of access (int) is faster than string comparing, which StringMap does in the background for each key.


slenkar(Posted 2011) [#14]
thanks for the tip, i could implement IntMap now

the reason I dont use an array is because I want a large map which takes up a lot of memory, using a Map I only have to make a mapsquare if there is something on the square,
so a 50,000 square map which only holds 1000 characters and buildings is 1/50 of the size of an array


AdamRedwoods(Posted 2011) [#15]
so a 50,000 square map which only holds 1000 characters and buildings is 1/50 of the size of an array


A valid point-- but for the sake of other peeps learning-- there would be ways to get around this for the array. A 250x250 array (unless you mean 50000x50000* ) is not very large, depending on the array class. Put simply, you could have unallocated (null) field classes within the grid class. You allocate the field on demand (If (building) Then Field building:Building = New Building) and leave the others with empty values. Remember, behind the scenes classes are just pointers, which are either 32-bit or 64-bit which takes up the space of approx an integer (but not really-- I don't want to start a debate here).

If you wanted to be ANAL-EFFICIENT, you could create a class that pointed to another class containing all your info so the array would ONLY be storing pointers, if valid and allocated. (confusing? don't worry just ignore)

*If you mean 50000x50000 then you would break this down, each grid contains other grids. so 100x100 megagrids (pointers to) 500x500 grids each (or broken down even further).

But it's your choice and that's the beauty of indie game development. You should be ok with a MapInt.


FlameDuck(Posted 2011) [#16]
*If you mean 50000x50000 then you would break this down, each grid contains other grids. so 100x100 megagrids (pointers to) 500x500 grids each (or broken down even further).
Like for instance Minecraft does. Of course this is more feasible in a language which supports weak references (Java).