Arrays vs Dictionary overhead.

Post » Wed Apr 26, 2017 8:55 am

I did some optimization tests to understand a bit more how to improve my performance on some projects. I couldn't figure out what was wrong so I made this test to see what it was.

I wasn't looking for this but It seems arrays has a lot more overhead and way slower than for example Dictionary. Check out this example to see what I mean.

Here's a link to test project.
https://www.dropbox.com/s/yhikh6nqdsy10yk/array_overhead.c3p?dl=0

Even a simple 1 dimensional array is much slower than dictionary. Does anyone know why this is the case?. It doesn't use more or less cpu, but seems to lag a bit compared to Dictionary.
Follow my progress on Twitter
or in this thread Archer Devlog
B
42
S
18
G
19
Posts: 1,060
Reputation: 14,054

Post » Wed Apr 26, 2017 9:24 am

Inserting and deleting elements from an array is O(n) since it uses contiguous storage and has to shunt along all the elements after the affected index. However adding and removing items from the end is fast, because there is nothing else to shunt along. If you can rearrange it to only modify the end it should be faster. Another technique is if you have a fixed size array you can cycle through the same set of elements without inserting/deleting anything (i.e. a circular buffer).

Dictionaries have per-key storage which means nothing else needs to be modified to add and remove items. Arrays are usually faster if you need to iterate them or do lots of random access, but inserting/removing anywhere apart from the end is usually a pretty bad case for arrays.

This is all standard computer science stuff, it's the same in pretty much every language.
Scirra Founder
B
403
S
238
G
89
Posts: 24,654
Reputation: 196,155

Post » Wed Apr 26, 2017 10:02 am

Ashley wrote:Inserting and deleting elements from an array is O(n) since it uses contiguous storage and has to shunt along all the elements after the affected index. However adding and removing items from the end is fast, because there is nothing else to shunt along. If you can rearrange it to only modify the end it should be faster. Another technique is if you have a fixed size array you can cycle through the same set of elements without inserting/deleting anything (i.e. a circular buffer).

Dictionaries have per-key storage which means nothing else needs to be modified to add and remove items. Arrays are usually faster if you need to iterate them or do lots of random access, but inserting/removing anywhere apart from the end is usually a pretty bad case for arrays.

This is all standard computer science stuff, it's the same in pretty much every language.


Thanks for the info Ashley. I did not know that adding to arrays att back would make that much of a difference. But in this case, where I constantly need to update a kind of custom (SOL) list of UID's it seems dictionary would be better, as in an array, i could be deleting an entry anywhere in the array... and whenever I delete an entry it has to update the the array.

In this particular test I will be deleting any UID entry that is outside the radius of 50 pixels.

I will make a mental note, that I should always add or delete stuff from an array from the back if possible.
Follow my progress on Twitter
or in this thread Archer Devlog
B
42
S
18
G
19
Posts: 1,060
Reputation: 14,054


Return to General Discussion

Who is online

Users browsing this forum: No registered users and 0 guests