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
Approximate Results & Conclusions:
Tested on Warcraft III Version 1.24c.
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.
Comments & Personal Criticism:
Code:
As for the linked list its a custom grown solution, pretty close to what the set used.
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
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::
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.
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
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)
- 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:
JASS:
///////////////////////////////////////////////
// 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("norm[]","for(i = 0;i<1000;i+=1) norm<i> = values<i>;")
//! runtextmacro TestPattern("table","for(i = 0;i<1000;i+=1) table<i> = values<i>;")
//! runtextmacro TestPattern("hset","for(i = 0;i<1000;i+=1) hset.Add(values<i>);")
//! runtextmacro TestPattern("list","for(i = 0;i<1000;i+=1) list.Add(values<i>);")
TriggerSleepAction(0);
BJDebugMsg("Set 2:: Find a cache_hit (value 280875) and set it 280876");
//! runtextmacro TestPattern("norm[]","for(i = 0; i < 1000; i+=1) if(norm<i> == 280875){norm<i>=280876; break;}")
//! runtextmacro TestPattern("table","for(i = 0; i < 1000; i+=1) if(table<i> == 280875){table<i>=280876; break;}")
//! runtextmacro TestPattern("hset","if(hset.Remove(280875)) hset.Add(280876);")
//! runtextmacro TestPattern("list","node =list.Fetch(280875);if(node != 0) node.Object=280876;")
TriggerSleepAction(0);
BJDebugMsg("Set 3::Contains cache_miss (value 8675309)");
//! runtextmacro TestPattern("norm[]","for(i = 0; i < 1000; i+=1) if(norm<i> == 8675309) break;")
//! runtextmacro TestPattern("table","for(i = 0; i < 1000; i+=1) if(table<i> == 8675309) break;")
//! runtextmacro TestPattern("hset","if(hset.Contains(8675309)){}")
//! runtextmacro TestPattern("list","if(list.Contains(8675309)){}")
BJDebugMsg("Set 4:: iteration.");
//! runtextmacro TestPattern("norm[]","for(i = 0;i<1000;i+=1) num = norm<i>;")
//! runtextmacro TestPattern("table","for(i = 0;i<1000;i+=1) num = table<i>;")
//! runtextmacro TestPattern("hset","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;")
//! runtextmacro TestPattern("list","for(node = list.First;node != list;node = node.Next){ num = node.Object;}")
}
function onInit()
{
integer i;
table = table.create();
hset = hset.create();
list = list.create();
for(i = 1; i < 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.
JASS:
//! 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;
}
}
}
//! endzincAnyother requests? I'll try bsearch vs hashtable natives on table and norm[] but its hard to write it as a one liner
