Key Timers Attachment System - The best?

03-06-2009, 02:11 AM	#1
TriggerHappy	http://www.thehelper.net/forums/showthread.php?t=78392 Thoughts? I have really no experience in benchmarking.

03-06-2009, 02:52 AM	#2
azlier	I think it's the best you can get, without a struct loop and a static timer. It's like TT, but slightly slower. But you can specify a period! That sounds good to me.

03-06-2009, 02:57 AM	#3
xombie	From the looks of it he uses triggers, is that faster than using function interfaces or is it kind of the same thing?

03-06-2009, 06:07 AM	#4
Viikuna-	You should see what function interfaces compile to...

03-06-2009, 06:14 AM	#5
Tyrande_ma3x	> It's like TT, but slightly slower. He says KT is the fastest (that's what the benchmarks point). Is it really faster than direct H2I?

03-06-2009, 11:36 AM	#6
Captain Griffen	Rapid Timers is faster. It's not so much that these methods are faster than direct H2I, but that timer timeouts are slower than TriggerEvaluate. Meh, just use TU really. Unless you need speed. Then you don't use a timer system, just one timer in your system running everything, because you're doing physics or something similar (or you don't need the speed).

03-06-2009, 11:45 AM	#7
akolyt0r	Hmmm..I like TU much more.... its just more flexible ... And this uses evaluate ....i dont want more evaluates in my map as necessary :>

03-06-2009, 02:14 PM

Vexorian

struct with loops: Easy, readable, fast.

struct with loops + trigger evaluate : harder to read, slower.

struct with loops + textmacro: Terribly harder to read, harder to code, as fast as struct with loops or even slower.

Purple/Red timer utils = Fastest timer attach method on earth for timers with flexible timeouts, that may be large or small. H2I+array lookup is a lower bound if you want timers with flexible timeouts. The other methods work only when the timeout is small. If the timeout is small and the timer is periodic, then it is retarded to even test TimerUtils with it. Just use an array and a loop, really. Besides of being so darn easy, it IS the fastest method.

A limit on different timer periods = bad.

Please notice that speed is meaningless if the method does not do the job correctly. Else we all would be using just globals to attach, there's a fast method (like key timers) that doesn't really work on MUI (just like key timers) , please pay attention to this:

Let's say I want to make a spell that does something after 5 seconds I cast the spell, something like this:

JASS:

function after2 takes nothing returns nothing
 local timer t= GetExpiredTimer()
 local struct f = struct( GetTimerData(t) )
    call f.do()
 call ReleaseTimer(t)
endfunction

function oncast takes nothing returns nothing
 local struct f= struct.generate()
 local timer t= NewTimer()
    call TimerStart(t, 5.0, false, function after2)
endfunction

I'll let you imagine the code using "key timers". Now, if I use Timer utils...

Table:

Game time	Action
00:03:02	Player A Casts spell
00:03:04	Player B Casts spell
00:03:07	Player A's spell calls after2
00:03:09	Player B's spell calls after2

It works ok. Now if I use "key timers":

Table:

Game time	Action
00:03:02	Player A Casts spell
00:03:04	Player B Casts spell
00:03:07	Player A's spell calls after2
00:03:07	Player B's spell calls after2

That's the sad reality. This method only works for small timeouts.

So I once tried to make a way to use only one Timer even on situations that require large, flexible time outs. And I invented TimeLib and following MagicTimers. Know this, I am absolutely sure that the only ways to have flexible, possibly-large and accurate timeouts are to use H2I or Griffen's sucky hack stuff. Anything else is slow, inaccurate or both.

Oh and I have my doubts about the benchmarks I wll work on them later.

---------

Edit: So seriously, I have to be tough on this because that thehelper thread is full of false claims and people blindingly following them, these are the conclusions:

a) keytimers are absolutely, undeniably slower than timer utils. So most likely his benchmarks are flawed. I am gonna review them up later. Edit: More details later.

b) keytimers are terribly limited. For all practical purposes if you want to use keytimers in your map, make sure to be the only one making code that use them. Else the varied timeouts used by different spells will make the timeout or the small instance limit get consumed.

c) keytimers are not MUI, if you use a larger than (let's say) 0.5 seconds timeout, you better use this timeout on only one spell instance at the same time, if you don't want your timing to get completely innacurate.

d) Even red timer utils are less limited than them.

e) The main difference between TimerUtils and this method is that if you start a timer and attach something to it using TimerUtils then tell the timer to last X seconds, it is guaranteed that the timer will do its work after X seconds. This is not the case with KT. You cannot have different timeouts, you can't have a timeout of 1.333 (for example if you want to run something after a unit's animation...) You can't have two things running at the same time if their timeouts are too close. Etc. KT are simply not accurate. This method works wonders when the timeout is <= 0.05 then it is just garbage. If you want to use this method for small timeouts, then use TT (cause it is faster since it doesn't have to have multiple timeouts) or like Griffen said RapidTimers (which are allegedly faster than TT but they are mostly the same thing) Or much better, have your own array and a loop, since that's definitely the fastest method.

03-06-2009, 02:36 PM	#9
azlier	Gah, and I spent a whole 5 minutes switching my spells to KT. Now I gotta switch 'em back. Please, people, stop with the big revelations!

03-06-2009, 09:34 PM

#10

Vexorian

Anyway, some oddities with his benchmarks:

1) I am not sure if executions per seconds works at all with timer systems, if you think about it, it may not make a lot of sense that they did. Though to prove this wrong I'll need to work more.

2) In KT's benchmark:

JASS:

            call KT_Add(function DoExample, Data, 1.0)

In H2I+subtraction benchmark:

JASS:

           set t=NewTimer()
            call SetTimerData(t,Data)
            call TimerStart(t,0.0,true,function DoExample)

Wtf?

3) The benchmarks are flawed by definition. Let me explain, to test his system he is using a single timeout. So his system would do all executions but only call the function that gets the timer's id once... Instead the other systems don't get this advantage, since they can't recognize that the interval is the same, and they don't separate things like that.

So I think the reason KT wins in benchmarks is because of the terrible flaw I mentioned in the last post. If it wasn't for that flaw, the timer would expire at different moments for each function and would have to do all the operations for each instance. Unfortunately, it doesn't work correctly, this boosts its performance, however it makes it a broken system.

He'll have to choose between making KT actually work or keeping them as a 'fast' thing.

---
Edit: Some better conclusions:

It is like Griffen said, it is about the timeout being slower than no timeout. It is true that KT are the fastest method - for his benchmark - Consider his benchmark, it involves running a lot of timers with the same timeout. His method saves operations, but it is only an improvement for that specific benchmark. If you want the timer system that will blow competition away in HIS benchmark then KT are the fastest one.

However, in a real life scenario:
a) The bug with KT would be fixed.
b) There fore there would be one timeout per TriggerEvaluate, unlike what there is right now.
c) There would also be a call to that function that gets the attached timer. Besides of the array lookups etc.
d) It will be (and I am 100% sure) slower than Red/Purple timer utils.

This system is perfect for performing the best at this benchmark, however in a real life scenario it is either slower or less accurate, enjoy.

Edit: If it is not clear enough, the reason KT is faster in those benchmarks is also a critical bug that makes this idea unusable on large timeouts. It should still work ok with small timeouts, but TT works ok with small timeouts as well and it is faster...

03-06-2009, 10:27 PM

#11

Vexorian

Taking a look at the paper:

Quote:

Structs are integers. Period.

Not really. Saying that structs are integers is an over simplification. Anyway, the spirit of that paragraph was that if you can store a integer somewhere you can store anything in it, which is true.

Quote:

2.2 What’s wrong with attaching with Gamecache?
It’s slow.
Strings leak.

R
Right.

Quote:

With gamecache, you leak a new string every time you declare a new instance.

Wrong.

Quote:

It isn’t a nice interface to work with. As in, the actual syntax for using it is fairly nasty.

That's appoachable anyway.

Quote:

It attaches directly to timers/triggers,
meaning timers can’t be used efficiently (ie. can’t be multi-instance).

Ok, this is just not true. First of all, gamecache isn't attached directly to timers/triggers more than TimerUtils. Efficiency in usage is unrelated to this aspect. And "can't be multi-instance" is absolue snake oil...

The only reason not to use gamecache for timer attaching is that there are better methods. But gamecache does work, just use it to attach an integer on it which would probably be a struct. DOTA in a way does this already. It works, it is "stable", speed could improve.

Quote:

Why have 3 timers going in the background when you can have 1?

Sometimes you can't have just 1.

Quote:

Here’s the other downside. Since they all execute together, if you say “Every 1 second, call function ProcessMySpell” using a multi-instance timer system, then the first time it executes may be anywhere between 0.001 and 1 second, because the timer it will be attached to is likely to be already firing. For most cases, I’ve found this doesn’t matter, because it will still be executed the same number of times in 10 seconds (considering spell balance). Also, sometimes it simply doesn’t matter because it’s controlling AI, or counting down a cooldown to see when it expires, which doesn’t need to be precise usually anyway.

So the guy knew about the bug and still released the system? Minimizing this issue is not the way to work around it. Releasing a bugged system on purpose just in the name of speed is just not right. It may not be a big issue when the timeout is less than a second, but it really is an issue later.

We are talking about spells here, and neglecting the visual part is really a bad mistake to make. Timers need to be accurate when you are synchronizing animation and movement and stuff. Sometimes you need something to happen exactly 0.45 seconds after a special effect has been created. Period. If this code is not executed after 0.45 seconds it will look bad. Balance is far from being the only problem here, But for large timeouts it truly is. If you want to make a spell like flame strike. Sometimes it will do the damage after 3 seconds and sometimes after 0.4 seconds, this is just wrong.

Quote:

this way you can attach structs (integers) to instances without using H2I or attaching directly to a timer or trigger. It’s very efficient, not to mention stable

Every correctly-coded timer system out there is stable. Efficiency also depends on how well you are measuring it (to be looked at later)

Quote:

and provides a nice syntax to code with.

TimerUtils makes more sense to me.

Quote:

This is the premise of timer systems having a Start(function, data) function and a GetData() function (which simply returns the data from the array, where the timer loop is up to). And there you have multi-instance timer theory.

That's the theory, even though he already knew of the flaw, he'll continue pushing for it:

Quote:

H2I attachment is very fast. It takes an object, and essentially returns an integer which is (I assume) it’s memory location (of some sort). Subtracting 0x100000 returns a number you can even stick into an array.
This is efficient, but still not as efficient as a GetData function. Furthermore, it isn’t as stable.

It is stable.

Quote:

This is a real problem. If your handle count exceeds the maximum array size

Red and purple timerutils come with previsions to prevent this from ever happening unless you have serious bugs when using the TimerUtils (if you have the same sort of serious bug when using TT-like thing -specially KT, since it is more limited than TT - they will also fall. Blue timer utils has a massive array, and it is just there in case you have these bugs it will still work.

Quote:

his is a real problem. If your handle count exceeds the maximum array size (8191… and if you think it will never happen, I did it in an RPG map I made called Savage Creed) then your attachment system either needs to use an alternative

If you use raw H2I it can become a problem, but we have work arounds and they work.

Quote:

(and I think CSData uses gamecache)

Why do people keep repeating this?

Quote:

Hence, I no longer use H2I for anything.

Bad choice.

Quote:

However, this is not the usual argument used against it. Usually people talk about reference counts, and some bug that it can happen to create.

What the hell is he talking about?

Quote:

Multi-instancing with a GetData function is faster anyway, leaving no reason to use H2I

a) It isn't.
b) You can't use GetData() methods for flexible timeouts as I have already shown.

Quote:

with the exception, perhaps, of high period timed effects which must wait the full period before the first execution of the effect… Talked about in the multi-instance timer section. Even then there’s alternatives)

No, there aren't alternatives to H2I for this case. Not good ones anyway.

Quote:

And here’s where theory turns to practise. Here are the 4 timer systems that I’ve looked at for the purposes of this report. Actually, I looked at Smart Timers (aka. SafeTimers) as well, but failed to get it working on Warcraft III version 1.20, which I did the bench testing on. It seemed inevitably slow anyway, as it did not apply the multi-instance timer theory.

Smart-timers (or dumb timers) are for practical purposes the fastest timer attach method for flexible timeouts (since they use the same method during timeouts as Red/purple timerutils, etc)

Either way, why is he calling the single-timer systems "multi instance timer systems"? That's ridiculous. Then he goes to complaint about ABCT, which is actually a fast system, and different to KT in the sense it actually works, then...

Quote:

This is a simple text macro that implements multi-instance timers. One per use of the macro. It allows multi-periods, but creates a new timer for every different piece of code you use. It has a nasty coding interface. There is no public release location for this system at the time of writing this document, except you may find it in an example map on the Key Timers 2 thread if you really want it.

If KT1 used textmacros, that was a good time to fix the bug. Using a textmacro you could do truly flexible time, using a FIFO queue, I tried this method, I use it at xe, however it is simply not as fast as H2I+subtraction, and textmacros are ugly.

Quote:

This is literally just the simplest implementation of a multi-instance timer possible. This system was the first multi-instance timer system (to the best of my knowledge).

Wrong. TimeLib and MagicTimers used a single timers for flexible timeouts a long time before this invention cam. TT came before as well and it exploits single timers.

Quote:

Timer Ticker (TT)
This is a multi-instance timer, but there is strictly one timer in this system. Therefore, it doesn’t support multi-periods at all.

Just like KT!

Quote:

This limits this system’s versatility for things like AI or timed effect spawning, but gives an efficiency gain in theory.

Also in practice.

Quote:

This was the first system to use trigger conditions to store functionality for use in a multi-instance timer.

Wrong again.

Quote:

Key Timers 1
Without a shadow of a doubt, the fastest, at 1.3 microseconds.
Timer Ticker
A distant second at 5.9 microseconds (+354% execution time).
Key Timers 2
A close third at 6.5 microseconds (+10% execution time on TT).
ABCT
A fourth. I assume hashing has slowed it down, and I may revisit this to fiddle with constants, but there was no documentation to suggest I should do this. Using the package straight out of the box, the average time for creating each of 4,000 instances was ~160 microseconds (+2362% on KT2).

The horribly inflated percentages show that there must be something broken with the benchmark - I should take a real good look at it later - or that he doesn't know how to calculate percentages.

Yes, probably Key Timers 1 was faster than TT, because of the lack of TriggerEvaluate. This also measn that array+loop is way faster than they all. With the addition it doesn't need horrid textmacros.

03-06-2009, 11:04 PM	#12
Av3n	At least Iron_Doors knew what the hell he was talking about to some extent and when people pointed out he was wrong, he gladly took in the advice. -Av3n

03-06-2009, 11:04 PM

#13

Vexorian

who?
edit: Ah.

BTW Purple TimerUtils is actually a good thing. Mostly because he managed to get the hashing stuff inlineable. Purple is almost as fast as Red, in fact until a recent update it was faster than Red. And it is also significantly safer than Red.

The answer to the timer systems feud was to make something like TimerUtils, which was implementation independent, this way things can evolve just fine. For example, what if blizz releases a SetHandleUserData native? With timer utils we would just replace the SetTimerData function and it would get inlined...

03-06-2009, 11:30 PM	#14
nooK	Ha this thief is still around, funny. Nice seeing his system getting raped ;)

04-04-2009, 04:58 PM	#15
Tyrande_ma3x	Didn't feel like creating a new thread, sorry for reviving this. Since he updated the system, he says that it is now the fastest timer system in existence, being ~22% over the speed of Timer Utils Red. I have no idea how it is possible, can someone benchmark and confirm it? It seems like he doesn't want to show his test triggers.