Here is a rather silly benchmark. However, assuming you have a group of units you are always keeping track of, you may want to know (for some inexplicable reason) what is the most optimal structure to hold these units. [Here's a hint as its been the winner in all my benchmarks thus far].
I'm not including Table as I've demonstrated that, it will be about twice as slow as the array variant. Nor am I including Set, as Set isn't an approved resource, and since it's enumeration pattern is that of a circular list, it'll probably perform exactly the same as linked list for enumeration.
The benchmark is two tests.
1. Create the collection of units you care about [N/A for the filter only pattern].
2. Then enumerate through the collection and set all unit's HP to 23.
To make the code simple, I've decided that I want to test enumeration of all units on the map, which just so happen to be 740 footmen I've created.
in the stopwatched section, each action is run 10 times, then the result is multiplied by 100. As the time of this excercise is microscopic due to the small amount of units available. I could've used a much larger set, but to make things easy, I've decided I didn't want to care about memory on the linked list, so I just create a new one, and say screw the old one.
Anyway the first benchmarking::
Comparison: Building up the set
With the following filter functions::
To be extra safe, and silly, I decided that it might be worthwhile to avoid the call to Filter(function A/B), so I put these as variables.
Since if you only use a filter you never have to worry about construction, it is not included in this construction trial. Here is the result, everything is being compared against using a group as it won this trial.
Results (winner = [ljass] group [/ljass])
Okay now on to benchmark 2::
Comparison: Enumeration and applying a native.
Here for each collection we went through each unit and set their health to 23. This is a somewhat plausible scenario.
The enumeration was done slightly different for each contestant.
Results (winner = [ljass]array (nes way)[/ljass])
Here the results are displayed as percentages of the winner.
Comments & Personal Criticism:
Finally here is the library used to do this::
LinkedList is the same library used in my collection shoot out, except Object is now a unit, it is about as optimal as a circular linked list can get in Jass (I'm welcome for suggestions of improvements).
Edit:
Zinc seems to break the spoiler tag. This is annoying. Sorry.
Edit again:
Per J4L's suggestion I've moved the LinkedList library here:
Here is the code, it is as optimal as the module just not a module. The only slight improvement is removing the count variable. [I didn't feel like making operators for it, and zinc lacks the [ljass]readonly[/ljass] keyword :/
I'm not including Table as I've demonstrated that, it will be about twice as slow as the array variant. Nor am I including Set, as Set isn't an approved resource, and since it's enumeration pattern is that of a circular list, it'll probably perform exactly the same as linked list for enumeration.
The benchmark is two tests.
1. Create the collection of units you care about [N/A for the filter only pattern].
2. Then enumerate through the collection and set all unit's HP to 23.
To make the code simple, I've decided that I want to test enumeration of all units on the map, which just so happen to be 740 footmen I've created.
in the stopwatched section, each action is run 10 times, then the result is multiplied by 100. As the time of this excercise is microscopic due to the small amount of units available. I could've used a much larger set, but to make things easy, I've decided I didn't want to care about memory on the linked list, so I just create a new one, and say screw the old one.
Anyway the first benchmarking::
Comparison: Building up the set
[LJASS]group[/LJASS] vs [LJASS]array[/LJASS] vs [Ljass]List[/ljass]
Each of these is using the native [ljass]GroupEnumUnitsInRect[/ljass], With the following filter functions::
- group used [ljass]null[/ljass]
- array used
JASS:function A()->boolean { U<s> = GetFilterUnit(); S+=1; return false; } </s>
[*] list used
JASS:function B()->boolean { L.Add(GetFilterUnit()); return false; }
To be extra safe, and silly, I decided that it might be worthwhile to avoid the call to Filter(function A/B), so I put these as variables.
Since if you only use a filter you never have to worry about construction, it is not included in this construction trial. Here is the result, everything is being compared against using a group as it won this trial.
Results (winner = [ljass] group [/ljass])
- [ljass]group[/ljass]: 3.700 -- 100%
- [ljass]array[/ljass]: 5.969 -- 161%
- [ljass]list[/ljass]: 13.988 -- 378%
Okay now on to benchmark 2::
Comparison: Enumeration and applying a native.
[LJASS]group[/LJASS] vs [LJass]array (nes way)[/ljass]
vs [LJASS]array (normal way)[/LJASS] vs [Ljass]List[/ljass] vs [ljass]Filter[/ljass]
You'll note the added contestants of array (nes way) and filter. vs [LJASS]array (normal way)[/LJASS] vs [Ljass]List[/ljass] vs [ljass]Filter[/ljass]
Here for each collection we went through each unit and set their health to 23. This is a somewhat plausible scenario.
The enumeration was done slightly different for each contestant.
- [ljass]group[/ljass] used -- [ljass]ForGroup[/ljass] with a 1-liner callback of [ljass] SetWidgetLife[/ljass]
- [ljass]array (nes way)[/ljass] used -- [ljass]for(j = S-1; j != -1; j-=1) SetWidgetLife(U[j],23);[/ljass]
- [ljass] array (normal way) [/ljass] used -- [ljass]for(j = 0; j != S; j+=1) SetWidgetLife(U[j],23);[/ljass]
- [ljass] list [/ljass] used -- [ljass]for(n = L.First; n != L; n = n.Next) SetWidgetLife(n.Object,23);[/ljass]
- [ljass] Filter [/ljass] used -- [ljass] GroupEnumUnitsInRect[/ljass] with a similar 1 liner callback of SetWidgetLife as group did.
Results (winner = [ljass]array (nes way)[/ljass])
Here the results are displayed as percentages of the winner.
- [ljass]group[/ljass] 6.508 -- 378%
- [ljass]array (nes way)[/ljass] 1.538 -- 100%
- [ljass] array (normal way) [/ljass] 1.587 -- 103%
- [ljass] list [/ljass] 1.973 -- 128%
- [ljass] Filter [/ljass] 6.673 -- 434%
Comments & Personal Criticism:
- First an interesting result of the combination is that using the array approach of building then iterating is ~7.507. Which is only 12% slower then doing just a filter alone.
- One can by looking at these results conclude that if you are only doing the enumeration against a collection of units once, its best to do it with a filter function. If you ever find yourself needing to do another enumeration against the same collection and you are a speedfreak, you should use this array approach.
- Another thing to appreciate is that there is almost no noticeable difference testing in a loop against a constant or a variable. Linked list once again are slower then arrays.
- I'm using zinc. The guidelines say use Vjass, but Zinc does make it a bit terser, and potentially harder to read then vJass. There are some shortcuts I'm exploiting that means that inadvertently Zinc might be doing silly, as Zinc is a higher level language then vJass which is more to the metal. Since zinc does translation of things like [ljass]for(;
[/ljass] and [ljass]j+=1[/ljass] inefficiencies may be introduced. I checked the compiled jass and the exitwhen's did not include anything crazy. That said I'm using oneliner's which some might argue are only appropriate when coming out of the mouth of Schwarzenegger Again, though I find zinc much easier to work with and they both are mostly equivalent. - I'm using [ljass]TriggerSleepAction[/ljass] some say you should use exec function. I don't really like that approach. I feel sleep cleans the thread limit, and i don't have to worry about losing local variables. There is stack to worry about, but since I'm not using any stack variables in the function [ljass]OnEsc[/ljass] its not a big deal.
- Linked list may have an unfair disadvantage. Since I used one letter variables to give the [ljass]array[/ljass],[ljass]group[/ljass] and [ljass]Filter[/ljass] the least worry about variable names, I didn't bother cleaning up the linked list library. As a result, linked list had the longest parse time of all the code, which may have had a very minor affect on the results. However, I still firmly believe that arrays will always be faster then linked lists.
Finally here is the library used to do this::
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
// Why this is in Zinc
//! textmacro TestPattern takes name,code
TriggerSleepAction(0);
BJDebugMsg("Test Name::$name$");
sw = StopWatchCreate();
$code$
$code$
$code$
$code$
$code$
$code$
$code$
$code$
$code$
$code$
result = StopWatchMark(sw);
StopWatchDestroy(sw);
BJDebugMsg(R2S(result * 100.0));
//! endtextmacro
//! zinc
library Tester requires LinkedList
{
group G = CreateGroup();
unit U[];
List L;
integer S = 0;
function A()->boolean
{
U<s> = GetFilterUnit();
S+=1;
return false;
}
function B()->boolean
{
L.Add(GetFilterUnit());
return false;
}
function C()
{
SetWidgetLife(GetEnumUnit(),23);
}
function D()->boolean
{
SetWidgetLife(GetFilterUnit(),23);
return false;
}
public function OnEsc()
{
integer sw = StopWatchCreate();
real result;
group g = CreateGroup();
integer i;
integer j;
Node n;
filterfunc a = Filter(function A);
filterfunc b = Filter(function B);
code c = function C;
filterfunc d = Filter(function D);
BJDebugMsg("Test building");
//! runtextmacro TestPattern("Use a Group","GroupEnumUnitsInRect( g,bj_mapInitialPlayableArea,null);")
//! runtextmacro TestPattern("Use an Array","GroupEnumUnitsInRect(G,bj_mapInitialPlayableArea,a);")
//! runtextmacro TestPattern("Use a List","GroupEnumUnitsInRect(G,bj_mapInitialPlayableArea,b);")
BJDebugMsg("Use Filter");
BJDebugMsg("N/A");
//Okay now we actually need to create the real stuff we care about, since the first example generated junk.
// We don't need to worry about the group, as Enumerating through a group always clears it out.
// I don't care about memory for this example.
//We should be okay for nodes with the list. And the array is fine provided we always stay with in [0,S)
S = 0;
GroupEnumUnitsInRect(G,bj_mapInitialPlayableArea,a);
L = List.create(); // who cares about that old one. Destroying it might take a while...
GroupEnumUnitsInRect(G,bj_mapInitialPlayableArea,b);
BJDebugMsg("Test enumeration by setting life to 23");
//! runtextmacro TestPattern("Use a group","ForGroup(g,c);")
//! runtextmacro TestPattern("Use an Array (nes way)","for(j = S-1; j != -1; j-=1) SetWidgetLife(U[j],23);")
//! runtextmacro TestPattern("Use an Array (normal way)","for(j = 0; j != S; j+=1) SetWidgetLife(U[j],23);")
//! runtextmacro TestPattern("Use a List","for(n = L.First; n != L; n = n.Next) SetWidgetLife(n.Object,23);")
//! runtextmacro TestPattern("Use Filter","GroupEnumUnitsInRect(G,bj_mapInitialPlayableArea,d);")
}
private function onInit()
{
integer i;
trigger t = CreateTrigger();
TriggerRegisterPlayerEvent(t,Player(0),EVENT_PLAYER_END_CINEMATIC);
TriggerAddAction(t,function OnEsc);
//BJDebugMsg("I'm being called");
L = List.create();
for(i = 0; i < 740; i+=1)
{
CreateUnit(Player(0),'hfoo',0,0,0);
}
}
}
//! endzinc
</s>LinkedList is the same library used in my collection shoot out, except Object is now a unit, it is about as optimal as a circular linked list can get in Jass (I'm welcome for suggestions of improvements).
Edit:
Zinc seems to break the spoiler tag. This is annoying. Sorry.
Edit again:
Per J4L's suggestion I've moved the LinkedList library here:
Here is the code, it is as optimal as the module just not a module. The only slight improvement is removing the count variable. [I didn't feel like making operators for it, and zinc lacks the [ljass]readonly[/ljass] keyword :/
JASS:
//! zinc
library LinkedList
{
public struct Node
{
thistype Next;
thistype Prev;
unit Object;
static method create(unit object)->thistype
{
thistype n = thistype.allocate();
n.Object = object;
return n;
}
}
public struct List extends Node
{
integer Count;
method operator First()-> Node
{
return Next;
}
method Add(unit object) // not checking because it's faster.
{
Node node = Node.create(object);
Prev.Next = node;
node.Next = this;
Prev = node;
Count+=1;
}
method Fetch(unit object) -> Node
{
Node node;
for(node = Next; node != this; node=node.Next)
{
if(node.Object == object)
{
return node;
}
}
return 0;
}
method Contains(unit object)-> boolean
{
return Fetch(object) > 0;
}
method RemoveNode(Node node) -> unit
{
unit retVal = node.Object;
if(node != 0)
{
node.Prev.Next = node.Next;
node.Next.Prev = node.Prev;
node.destroy();
Count -=1;
}
return retVal;
}
method Remove(unit 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(null);
n.Next = n;
n.Prev = n;
return n;
}
}
}
//! endzinc
