Benchmarks: Dictionary vs. Object vs. Array vs. LookupList

0 Flares Twitter 0 Facebook 0 Google+ 0 Pin It Share 0 Email -- Filament.io 0 Flares ×

[Update: I put the code of the LookupList class at the bottom of the article]
[BIG Update: there was an error in the LookupList class -> now it’s much slower than the rest]

And another benchmark comparing various ways of getting an object for a key that is stored in a table. The key is a String, otherwise I wouldn’t be able to compare the Dictionary with Object or Array. The value is an Object.
You all know what a Dictionary or an Object or an Array is, but you might ask yourself what is a LookupList. Well i’s simply a cutom “lookup table” that I build for the sake of this benchmark. It uses a linked list system to store pairs of key/value into a list. That system always starts at the very first key/value pair that was added, until the end of the list to check whether a key exists or not. It is a very simple and basic system.

I test both failures (when a key doesn’t exist) and successes (when the key exists and links to an object).

Here is the benchmark (you might have noticed that you actually can access previous benchmarks via the list “benchmarks”) :

Get Adobe Flash player

 

My results

Well, I was happily surprised to see that my LookupList is actually faster than any of its competitors, followed by the Object, then the Dictionary and finally the Array.
This is very interesting as the LookupList is a very basic system with no optimization (except for the linked list system) at all. Depending on the type of the key, you could add some sort of system to go straight to a certain key/value pair without going from the start to the end of the list each time you need a value for a key.

The way I see it is:

  • you need the most efficient way ?
    • go for LookupList
  • you don’t need the most efficient way ?
    • you only need a String as the key ?
      • go for Object
    • then go for Dictionary

It turns out there was a huge error in my LookupList class. It now is much slower than all the other options.
It looks like the Object way is the fastest for me, then Dictionnary and finally Array. The LookupList class being too slow for even considering it.

I also invite you to check the Fast Hash Tables from Polygonal. He apparently made a hash table that is faster than the Dictionary.

LookupList source code

LookupList

package benchmarks.benchmarks.lookuplist 
{
	/**
	 * ...
	 * @author Thomas John
	 */
	public class LookupList 
	{
		public var itemFirst:LookupListItem;
		public var itemLast:LookupListItem;

		public function LookupList()
		{

		}

		public function addObjectForKey(key:String, object:Object):void
		{
			var item:LookupListItem = new LookupListItem();
			item.key = key;
			item.value = object;

			if (itemLast)
			{
				item.prev = itemLast;
				itemLast.next = item;
				itemLast = item;
			}
			else
			{
				itemFirst = item;
				itemLast = item;
			}
		}

		public function getValueForKey(key:String):Object
		{
			var item:LookupListItem;

			for (item = itemFirst; item; item = item.next)
			{
				if ( item.key == key ) return item.value;
			}

			return null;
		}

	}

}

LookupListItem

package benchmarks.benchmarks.lookuplist 
{
	/**
	 * ...
	 * @author Thomas John
	 */
	public class LookupListItem 
	{
		public var prev:LookupListItem;
		public var next:LookupListItem;

		public var key:String;
		public var value:Object;

		public function LookupListItem()
		{

		}
	}

}
0 Flares Twitter 0 Facebook 0 Google+ 0 Pin It Share 0 Email -- Filament.io 0 Flares ×

18 Comments

  1. my results, for 1000000 iterations:
    Object (String to Object, miss, 1000 objects): 0.033
    Object (String to Object, miss, 10 objects): 0.049
    LookupList (String to Object, miss, 1000 objects): 0.053
    LookupList (String to Object, miss, 10 objects): 0.056
    Array (String to Object, miss, 10 objects): 0.078
    Array (String to Object, miss, 1000 objects): 0.084
    Dictionary (String to Object, miss, 10 objects): 0.151
    Dictionary (String to Object, miss, 1000 objects): 0.153
    LookupList (String to Object, 10 objects): 0.197
    LookupList (String to Object, 1000 objects): 0.20400000000000001
    Object (String to Object, 1000 objects): 0.341
    Object (String to Object, 10 objects): 0.368
    Dictionary (String to Object, 10 objects): 0.41100000000000003
    Dictionary (String to Object, 1000 objects): 0.449
    Array (String to Object, 10 objects): 0.459
    Array (String to Object, 1000 objects): 0.467

  2. boblemarin

    My results for 1000000 iterations :

    Object (String to Object, miss, 1000 objects): 0.12
    Object (String to Object, miss, 10 objects): 0.155
    Array (String to Object, miss, 10 objects): 0.192
    Array (String to Object, miss, 1000 objects): 0.199
    LookupList (String to Object, miss, 1000 objects): 0.27
    LookupList (String to Object, miss, 10 objects): 0.273
    Dictionary (String to Object, miss, 10 objects): 0.406
    Dictionary (String to Object, miss, 1000 objects): 0.447
    LookupList (String to Object, 10 objects): 0.709
    LookupList (String to Object, 1000 objects): 0.717
    Object (String to Object, 1000 objects): 0.852
    Dictionary (String to Object, 1000 objects): 0.866
    Object (String to Object, 10 objects): 0.907
    Dictionary (String to Object, 10 objects): 0.9460000000000001
    Array (String to Object, 10 objects): 1.006
    Array (String to Object, 1000 objects): 1.026

  3. Matej

    Object (String to Object, miss, 1000 objects): 0.009000000000000001
    Object (String to Object, miss, 10 objects): 0.009000000000000001
    Array (String to Object, miss, 10 objects): 0.013000000000000001
    LookupList (String to Object, miss, 10 objects): 0.015
    Array (String to Object, miss, 1000 objects): 0.016
    LookupList (String to Object, miss, 1000 objects): 0.018000000000000002
    Dictionary (String to Object, miss, 10 objects): 0.021
    Dictionary (String to Object, miss, 1000 objects): 0.024
    LookupList (String to Object, 10 objects): 0.045
    LookupList (String to Object, 1000 objects): 0.048
    Dictionary (String to Object, 1000 objects): 0.057
    Dictionary (String to Object, 10 objects): 0.059000000000000004
    Object (String to Object, 1000 objects): 0.061
    Object (String to Object, 10 objects): 0.061
    Array (String to Object, 10 objects): 0.065
    Array (String to Object, 1000 objects): 0.07

  4. Pavel

    But how is your lookup list implemented? Doesn’t it use array/object inside?

  5. Nemi

    1000000 iterations, Win7 64bit, Intel core2 duo 3.16GHz, 4GB RAM, FP 12.0 in Chrome

    Object (String to Object, miss, 1000 objects): 0.039
    Object (String to Object, miss, 10 objects): 0.05
    LookupList (String to Object, miss, 1000 objects): 0.07
    LookupList (String to Object, miss, 10 objects): 0.075
    Array (String to Object, miss, 10 objects): 0.076
    Array (String to Object, miss, 1000 objects): 0.094
    Dictionary (String to Object, miss, 10 objects): 0.158
    Dictionary (String to Object, miss, 1000 objects): 0.17200000000000001
    LookupList (String to Object, 10 objects): 0.203
    LookupList (String to Object, 1000 objects): 0.21
    Object (String to Object, 1000 objects): 0.358
    Object (String to Object, 10 objects): 0.374
    Dictionary (String to Object, 1000 objects): 0.39
    Dictionary (String to Object, 10 objects): 0.418
    Array (String to Object, 10 objects): 0.459
    Array (String to Object, 1000 objects): 0.5

  6. @ Pavel: I put the source code of the LookupList class at the bottom of the article. It’s using the linked list system. Basically linked lists are faster than arrays and vectors for accessing items (not in all cases, but for this one, it is faster)

  7. Redoc

    This doesn’t make any sense, you didn’t sepecify whats the index of the object you are looking for. If the object is near the last item in your list it will take ages to access compared to object or dictionary.

  8. @Redoc: it’s totally random access to be as fair as possible, but I’ll try when accessing the same index in an other benchmark.
    Also the LookUpList class is a very basic one, meaning there is no sorting or anything like a system to speed up the search. Depending on the type of the key, we could use different techniques: if it’s a number or int, we could sort them and store the minimum, maximum and the one in the middle. And depending on the key we are looking for, we could do a search either from min to middle or middle to max, or middle to min or max to middle.

  9. Redoc

    Can you post sources for the benchmark? Sorting would only complicate things and not always bring better results depending on use case. Anyway it is interesting find you got there.

  10. yeah sure, I’ll post the complete source in my next benchmark

  11. I posted a new benchmark comparing SetTimeOut, Timer and a CustomTimer.
    In that benchmark you can access all previous benchmarks, including this one that I modified a bit. The complete source code for every benchmarks is also available at the bottom of the article :
    http://blog.open-design.be/2014/02/27/benchmarks-settimeout-vs-timer-vs-customtimer/

    Now concerning the LookupList, it may surprise you but I added a test where it always looks for the last element in the list (it actually already existed as the “miss” test)… and it’s even faster than when it finds an element at a random location… a bit weird (maybe the Math.random() is creating that difference) but I strongly invite you to try it out and see the sources if you can find anything wrong as I quickly put all of it together at 3.00 in the morning last night 🙂

  12. BlueLink

    This is just a linked list.

  13. maliu

    my environment:
    1000000 iterations
    Win7 Ultimate 64bit
    Intel core i5-3210M 2.50GHz(notebook)
    4GB RAM
    FP 12.0
    FireFox 27.0.1

    Object (String to Object, miss, 1000 objects): 0.015
    Object (String to Object, miss, 10 objects): 0.016
    Array (String to Object, miss, 10 objects): 0.024
    Array (String to Object, miss, 1000 objects): 0.034
    LookupList (String to Object, miss, 1000 objects): 0.036000000000000004
    LookupList (String to Object, miss, 10 objects): 0.042
    Dictionary (String to Object, miss, 10 objects): 0.047
    Dictionary (String to Object, miss, 1000 objects): 0.051000000000000004
    LookupList (String to Object, 1000 objects): 0.1
    LookupList (String to Object, 10 objects): 0.106
    Object (String to Object, 10 objects): 0.124
    Dictionary (String to Object, 10 objects): 0.127
    Array (String to Object, 10 objects): 0.14200000000000002
    Object (String to Object, 1000 objects): 0.15
    Dictionary (String to Object, 1000 objects): 0.152
    Array (String to Object, 1000 objects): 0.159

  14. Chris

    Hi, you got an error in your LookupList source code…
    with
    LookupList Class – line 31,32: “itemFirst = item;
    itemFirst = item;” you could never reach more than the first item…
    need to change that to itemFirst = item; itemLast = item;

  15. You’re freaking right, that explains a couple of things.
    I rectified the benchmark and the results are quite different… the LookupList is much more slower than the rest.

    I’d still invite you to check this: http://lab.polygonal.de/?p=1325
    It’s a Hash Table that is apparently faster than Dictionary (from its author)

  16. LookupList (String to Object, miss, 10 objects): 12
    LookupList (String to Object, miss, 1000 objects): 12
    Object (String to Object, miss, 1000 objects): 17
    Object (String to Object, miss, 10 objects): 26
    Array (String to Object, miss, 1000 objects): 46
    Array (String to Object, miss, 10 objects): 47
    LookupList (String to Object, 10 objects, pick last): 53
    LookupList (String to Object, 10 objects): 54
    Object (String to Object, 10 objects): 67
    Dictionary (String to Object, 10 objects): 72
    Dictionary (String to Object, miss, 10 objects): 75
    Array (String to Object, 1000 objects): 94
    Array (String to Object, 10 objects): 116
    Dictionary (String to Object, 1000 objects): 129
    Dictionary (String to Object, miss, 1000 objects): 149
    Object (String to Object, 1000 objects): 152
    LookupList (String to Object, 1000 objects): 2033
    LookupList (String to Object, 1000 objects, pick last): 4112

Leave a Comment

*