Perfromance: Linear Searching vs Game Cache

[Justify]

Hey Guys
I have a rather simple question... I would test it myself, but I never get the stopwatch function working. Maybe someone could help me
I just want to know what is faster:

a) Linear Searching:

loop
    set I = I+1
    set Data = AggroData[I]
    exitwhen I >= StructCount or Target == Data.Unit
endloop

Depending on the situation there are around 5-30 structs to loop through.

b) Game Cache:
Have no example, since I'm using "a)" at the moment. I just would attach the ID of the struct to the unit.

What would be faster?
It's quite important, since this system will run very often and I want to improve the performance as much as possible

Greets, Justify

 

[Soga-]

I don't know too much about the way Game Caches work, but I know that they act like map containers (key -> value). At the worst, using them is as bad as using linear searches. At best, they use binary searching (which finishes in log n time).

So in my opinion, I would suggest using caches. I strongly believe you have nothing to lose in doing so.

 

[Dr Super Good]

Linear searching will be faster I expect for small numbers of objects as game cache systems like handle vars are process intensive in nature. At larger object numbers I would say the cache gains preformance.

All in all it is best to use an array system as that is pretty direct as it does not use any loops at all.

 

[Soga-]

I wouldn't say handle vars are that process intensive. You're not actually processing handles, you're just storing and retrieving their memory addresses (and casting to string, I suppose).

But yeah, I've changed my mind: for small arrays, linear is better. Caches aren't as bad as Super Good makes them sound, though.

 

[Justify]

May I ask what an "array system" exactly does?
http://www.hiveworkshop.com/forums/f269/first-steps-pseudo-array-system-113117/
I think you mean this, but I just don't get how it works :/

Btw, if I remember correct a guy at wc3campaigns said that the cache itself is pretty fast, but the H2I function isn't.

 

[Dr Super Good]

No, that system seems some kind of slow search.

I mean systems where it stores a value in an array at a unique index, capable of being fetched from an objects handle value. It invlolves multiple arrays being fuesd and also the H2I function as well as subtracting the handle value by the lowest possiable handle value that is useable (EG a unit can not have a handle value of 0, infact is is more in the millions even if it is the first unit).

It is faster as you basically only use H2I, some simple arthimetic and a fused array system to directly fetch a value. You can look at it as attaching a value to a unit instead of attaching a value into a table or database using the unit as a field value and then searching for it. The loop method could only be faster for atmost 1-2 objects stored, but after which the direct method clearly wins as its execution time is near constant no matter how many objects are stored. Only problem with it is it bugs if too many handles are made, but weather a map needs that many means it is eithor leaking or badly coded.

This system kind of is what I mean.

 

[Captain Griffen]

GC is O(1). Cache ~ 2 1/2 array look ups if I remember correctly.

 

[Justify]

Using a own version of HSAS now since I need some special things that aren't supportet by HSAS. Doesn't matter know, thanks guys and +rep