Benchmark Collection shoot out (Array vs Table vs HashSet vs LinkedList)

[weaaddar]

Hi all,
Here is a benchmark between 4 different types of collections. I am trying 4 different standard things to try against a collection.

Each of these collections was populated with the first 1000 values of the function Sum(n), [Sum(n) = (n * n+1)/2].

The benchmarks rules were slacked because of concerns of the op limit and the constraint of uniqueness. Each result will be compared to the winner of the set. The array was mostly there as the token winner, and the real comparison is against table.
Comparison:
Set 1:: Build collection
Set 2:: Find a cache_hit (value 280875) and set it 280876
Set 3:: Contains cache_miss (value 8675309)
Set 4:: iteration

[LJASS]norm[][/LJASS] vs [LJASS]table[/LJASS]vs[ljass]hset[/ljass] vs [ljass]linkedlist[/ljass]​

Approximate Results & Conclusions:
Tested on Warcraft III Version 1.24c.

Set 1:: Build collection (here we're just testing the setter or the Add function, as all are suffering the cost of reading the values array and iteration)

• [LJASS]norm[][/LJASS] 100% (1.553)
• [Ljass]table[/ljass] 192% (2.984)
• [LJASS]hset[/LJASS] 1335% (20.734)
• [LJASS]list[/LJASS] 719% (11.166)

Set 2:: Find a cache_hit (value 280875) and set it 280876.
Array and table are just doing the following::

[ljass]for(int i = 0; i < 1000; i+=1) if(colname == 280875){ colname = 280876 [/ljass]​

Hashset is removing the old one, and adding the new one.
List is using its fetch method to grab a node and modify its value.

• [LJASS]norm[][/LJASS] 1111% (.733)
• [Ljass]table[/ljass] 2141% (1.413)
• [LJASS]hset[/LJASS] 100% (.066)
• [LJASS]list[/LJASS] 1553% (1.147)

​

Set 3::Contains cache_miss (value 8675309)
Same as before, except nothing was put in the conditional evaluations as apparently, we don't have Jenny's number, and it was less typing

• [LJASS]norm[][/LJASS] 7885% (1.025)
• [Ljass]table[/ljass] 15085% (1.961)
• [LJASS]hset[/LJASS] 100% (.013)
• [LJASS]list[/LJASS] 11600% (1.508)

Set 4::Iteration through the collection
Here we are just looping through and assigning it to a local variable. Standard iteration patterns are being used. Norm & Table have the same code, and Hset and list have the same code.

• [LJASS]norm[][/LJASS] 100% (1.098)
• [Ljass]table[/ljass] 172% (1.894)
• [LJASS]hset[/LJASS] 147% (1.616)
• [LJASS]list[/LJASS] 154% (1.695)

Comments & Personal Criticism:

• First, as before unless you need don't use a hashtable, array is faster, using a hashtable like an array is much slower then array.
• Iterating through linked list is slower then iterating through arrays, but still iterating through a table. If you have an unknown number of elements the linked list or set provide nice functionality as array or table actually don't know when they end. You'll have to store that in another var or as an index.
• The hashtable natives are really fast. Much faster then o(n) collection searches.

Code:

Spoiler

    ///////////////////////////////////////////////
    // Native declarations for stopwatch natives //
    //  - Requires no modified common.j import   //
    ///////////////////////////////////////////////
    native StopWatchCreate  takes nothing returns integer
    native StopWatchMark    takes integer stopwatch returns real
    native StopWatchDestroy takes integer stopwatch returns nothing

//! textmacro TestPattern takes Name,code
    TriggerSleepAction(0);
    BJDebugMsg("Test Name::$Name$");
    sw = StopWatchCreate();
    $code$
    result = StopWatchMark(sw);
    StopWatchDestroy(sw);
    BJDebugMsg(R2S(result*1000));
//! endtextmacro
//! zinc
library CollectionTest requires LinkedList,Dictionary,Table
{
    integer values[];
    integer norm[];
    Table   table;
    Set_integer hset;
    List list;
    public function Trig_CollectionTest_Actions()
    {
        integer i;
        integer sw;
        Node node;
        RO_SetNode_integer ro;
        real result;
        integer num;
        BJDebugMsg("Set 1::Build collection");
        //! runtextmacro TestPattern(&quot;norm[]&quot;,&quot;for(i = 0;i&lt;1000;i+=1) norm<i> = values<i>;&quot;)
        //! runtextmacro TestPattern(&quot;table&quot;,&quot;for(i = 0;i&lt;1000;i+=1) table<i> = values<i>;&quot;)
        //! runtextmacro TestPattern(&quot;hset&quot;,&quot;for(i = 0;i&lt;1000;i+=1) hset.Add(values<i>);&quot;)
        //! runtextmacro TestPattern(&quot;list&quot;,&quot;for(i = 0;i&lt;1000;i+=1) list.Add(values<i>);&quot;)
        TriggerSleepAction(0);
        BJDebugMsg(&quot;Set 2:: Find a cache_hit (value 280875) and set it 280876&quot;);
        //! runtextmacro TestPattern(&quot;norm[]&quot;,&quot;for(i = 0; i &lt; 1000; i+=1) if(norm<i> == 280875){norm<i>=280876; break;}&quot;)
        //! runtextmacro TestPattern(&quot;table&quot;,&quot;for(i = 0; i &lt; 1000; i+=1) if(table<i> == 280875){table<i>=280876; break;}&quot;)
        //! runtextmacro TestPattern(&quot;hset&quot;,&quot;if(hset.Remove(280875)) hset.Add(280876);&quot;)
        //! runtextmacro TestPattern(&quot;list&quot;,&quot;node =list.Fetch(280875);if(node != 0) node.Object=280876;&quot;)
        TriggerSleepAction(0);
        BJDebugMsg(&quot;Set 3::Contains cache_miss (value 8675309)&quot;);
        //! runtextmacro TestPattern(&quot;norm[]&quot;,&quot;for(i = 0; i &lt; 1000; i+=1) if(norm<i> == 8675309) break;&quot;)
        //! runtextmacro TestPattern(&quot;table&quot;,&quot;for(i = 0; i &lt; 1000; i+=1) if(table<i> == 8675309) break;&quot;)
        //! runtextmacro TestPattern(&quot;hset&quot;,&quot;if(hset.Contains(8675309)){}&quot;)
        //! runtextmacro TestPattern(&quot;list&quot;,&quot;if(list.Contains(8675309)){}&quot;)
        BJDebugMsg(&quot;Set 4:: iteration.&quot;);
        //! runtextmacro TestPattern(&quot;norm[]&quot;,&quot;for(i = 0;i&lt;1000;i+=1) num = norm<i>;&quot;)
        //! runtextmacro TestPattern(&quot;table&quot;,&quot;for(i = 0;i&lt;1000;i+=1) num = table<i>;&quot;)
        //! runtextmacro TestPattern(&quot;hset&quot;,&quot;for(ro = hset.GetReadOnlyNode();ro != hset;ro = ro.Next) num = r<img src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" class="smilie smilie--sprite smilie--sprite12" alt="o_O" title="Er... what?    o_O" loading="lazy" data-shortname="o_O" />bject;&quot;)
        //! runtextmacro TestPattern(&quot;list&quot;,&quot;for(node = list.First;node != list;node = node.Next){ num = node.Object;}&quot;)
        

    }

    function onInit()
    {
        integer i;
        table = table.create();
        hset = hset.create();
        list = list.create();
        for(i = 1; i &lt; 1000; i+=1)
        {
            values<i> = i+ values[i-1];
        }
    }
}

//! endzinc
//===========================================================================
function InitTrig_CollectionTest takes nothing returns nothing
    set gg_trg_CollectionTest = CreateTrigger(  )
    call TriggerRegisterPlayerEventEndCinematic( gg_trg_CollectionTest, Player(0) )
    call TriggerAddAction( gg_trg_CollectionTest, function Trig_CollectionTest_Actions )
endfunction
</i></i></i></i></i></i></i></i></i></i></i></i></i></i></i>

As for the linked list its a custom grown solution, pretty close to what the set used.

Spoiler

//! zinc
library LinkedList
{
    public struct Node
    {
        thistype Next;
        thistype Prev;
        integer Object;
        static method create(integer object)->thistype
        {
            thistype n = thistype.allocate();
            n.Object = object;
            return n;
        }
    }
    public struct List extends Node
    {
        method operator Count()->integer
        {
            return Object;
        }
        
        method operator Count=(integer value)
        {
            Object = value;
        }
        
        method operator First()-> Node
        {
            return Next;
        }
        method Add(integer object) // not checking because it's faster.
        {
            Node node = Node.create(object);
            Prev.Next = node;
            node.Next = this;
            Prev = node;
            Count+=1;
        }
        
        method Fetch(integer object) -> Node
        {
            Node node;
            for(node = Next; node != this; node=node.Next)
            {
                if(node.Object == object)
                {
                    return node;
                }
            }
            return 0;
        }
        
        method Contains(integer object)-> boolean
        {
            return Fetch(object) > 0;
        }
        
        method RemoveNode(Node node) -> integer
        {
            integer retVal = node.Object;
            if(node != 0)
            {
                node.Prev.Next = node.Next;
                node.Next.Prev = node.Prev;
                node.destroy();
                Count -=1;
            }
            return retVal;
        }
        method Remove(integer object)->boolean
        {
            Node node = Fetch(object);
            if(node != 0)
            {
                node.Prev.Next = node.Next;
                node.Next.Prev = node.Prev;
                node.destroy();
                Count-=1;
                return true;
            }
            return false;
        }
        static method create()->thistype
        {
            thistype n = thistype.allocate(0);
            n.Next = n;
            n.Prev = n;
            return n;
        }
    }
}
//! endzinc

Set is the resource submitted on this site.

Anyother requests? I'll try bsearch vs hashtable natives on table and norm[] but its hard to write it as a one liner

 

[Jesus4Lyf]

It looks really messy. I think you've butchered the template horribly.

Are you testing O(n) complexity searches against O(1) complexity hashing? How do you even hope to come up with a useful number? The efficiency is completely different in scale...

>Iterating through linked list is slower then iterating through arrays
That's not truth.

Stop using Zinc. I can't read your tests, they're a real mess.

>The hashtable natives are really fast. Much faster then o(n) collection searches.
That is a conclusion, not criticism.

Edit:
The guidelines state:

• This code must be pastable into a blank WC3 map and work without any other modifications (if possible).
• The code being benchmarked must be executed at least 10 times consecutively at a time (without loop checks).
• Code must be readable (reasonable layout).

 

[weaaddar]

Well Zinc is still easier to work with :/. As for the iteration pattern just take a look, Linked List/Set which are both linked list doing the following::

for(node = list.First; node != list;node = node.Next)
{
    num = node.Object;
}

was much slower then

for(i = 0; i < 1000; i+=1)
{
    num = normalarray<i>;
}
</i>

As for the unfair comparison there was some theory that hashtables were slow (or atleast vex use to think that).

 

[Azlier]

You should really put each separate benchmark into different functions called via TriggerExecute.

 

[vuongkkk]

Someone can tell me why linked list can be faster than array while "List" is a strust and strust base on array :-??

 

[tooltiperror]

Not really sure what you're asking, because you didn't specify. Linked lists are faster for some things while arrays are faster for some things.

 

[kingkingyyk3]

Because when iteration is in progress, there is no maths involved, just array reading.

 

[Nestharus]

Actually, linked list iteration speed depends on the exitwhen statement.

There are 3 types of exiting linked list. One type compared to the head node, the slowest of the three. The second type compares the current node to 0 and the third type stores a boolean into the head for comparing against that.

Comparing against 0 requires overhead be added to the add/remove operations on a list.

Iterating through a list comparing to the head node might actually be slower than iterating through an array (slower in this thread). Iterating through a linked list comparing to a boolean or comparing to 0 is actually faster depending on how many globals are in the map. Iterating through a 100% local linked list would be blazing fast when comparing to 0 or a boolean.