Bringing setTimeout to ECMAScript

David Bruant david.bruant at labri.fr
Sun Mar 20 10:11:28 PDT 2011


Le 20/03/2011 17:25, Jorge a écrit :
> On 20/03/2011, at 16:57, David Bruant wrote:
>
>> Le 20/03/2011 16:04, Jorge a écrit :
>>> On 20/03/2011, at 15:18, David Bruant wrote:
>>>> Le 20/03/2011 14:33, Jorge Chamorro a écrit :
>>>>>> A timer that expires is an event, and I would expect events to be serviced in the order they happen. As when I click twice, I'd expect the first click to be serviced before the second click.
>>>>>>
>>>>>> So given 2 timers, expiring at t0 and t1 with t0 < t1, if Date.now() is >= t0 and >= t1, I would expect t0 to be serviced first, yes.
>>>>>>
>>>> The difference is that the system can understand what is your expectation as a user when you've clicked twice. Both click are clearly sequenced. For timers, the non-determinism due to the computation time of computea and computeb prevents you from /expecting/ anything.
>>> Why ? When you do a setTimeout( f, ms ) you know you are saying "fire this @ t >= Date.now() + ms".(Let's leave aside for now the problems wrt Date.now() / wall clock time).
>> I agree that for one timer, there is no problem. Tricky case is if you
>> want to enforce a policy on how to deal with several delayed timers
>> (let's call it "scheduling policy"). That's where I say that it's not
>> possible to pretend expecting anything.
>>
>>
>>>> In low-memory environment, if a program does an intensive use of timers, maybe that heuristics on the time the timer firing will take could be used to try to get rid of a maximum of timers as soon as possible to save up memory. I would consider this policy as valid due to environment constraints. 
>>>>> And if t0 were === t1, I would also expect them to be serviced in the same order in which they were setup:
>>>>>
>>>>> setTimeout( f1, 0 );
>>>>> setTimeout( f2, 0 );
>>>>> setTimeout( f3, 0 );
>>>>> setTimeout( f4, 0 );
>>>>> setTimeout( f5, 0 );
>>>>>
>>>>> ->
>>>>> f1()
>>>>> f2()
>>>>> f3()
>>>>> f4()
>>>>> f5()
>>>>>
>>>> I think it is very dangerous to use talk about things like t0 === t1 and Date.now() >= t0 (concerned about the "or equal"). If ECMAScript has millisecond as granularity, most systems have microseconds if not nanoseconds. 1ms = 10⁶ns. That's a lot! It leaves a lot of room for interpretation. And even the setTimeout calls aren't instantaneous.
>>>>
>>>> Consider (milliseconds in comment):
>>>> // 0
>>>> setTimeout( f1, 1 );
>>>> setTimeout( f2, 0 ); // 1 (millisecond change in the middle of the call)
>>>> // 2
>>>> // -- decision to make on which timer to fire.
>>>> Since the millisecond change happened during the second setTimeout, when is scheduled this second timeout?
>>> A setTimeout( f, ms ) should be scheduled to fire at t = Date.now() + ms,so in the example above, both would be scheduled to fire at the same t,
>> "both would be scheduled to fire the same t". Who said that? The
>> millisecond change is in the middle of the setTimeout call. From the
>> external point of view, the second timer is scheduled to be called
>> between two milliseconds and you (external point of view, not
>> implementor) have no idea which one.
>>
>>> but, as f1 was setup before f2, f1 should be called before f2. You can achieve this easily with a stack per target time.
>> Your argument is based on the implementor point of view. I agree that
>> any policy can be implemented. I do not doubt that. I am just saying
>> that you cannot verify it from a script point of view, (and so there is
>> no point specifying it).
>>
>>> I don't see why "you can't verify your expectation".
>> If you think you can verify your expectation, please write ECMAScript
>> interoperable test cases that show how to test whether an ECMAScript
>> engine is conform to your scheduling policy or not. It will be enough to
>> convince me.
>> Testing one timer ("When you do a setTimeout( f, ms ) you know you are
>> saying "fire this @ t >= Date.now() + ms" ") will not be difficult.
>> Testing your scheduling policy is a different story.
>>
>> A spec is a contract between an provider (implementor) and a client
>> (ECMAScript script writer). If the client has no way to ensure that a
>> spec detail has been met, there is no point adding this detail to the
>> contract.
>> With maybe the exception of Date.now() and Math.random() which are
>> convinient but comes with no guarantee whatsoever. Their spec are empty
>> (not literally, but close). While you seem to have "expectations" on a
>> scheduling algorithm.
>>
>> If I am missing something and you can write test cases to enforce
>> expectation over a particular scheduling policy, please do so.
> In order to know *exactly* the target time (Date.now() +ms) that a given setTimeout() has been scheduled for, setTimeout() would have to return it (it doesn't currently):
>
> function newSetTimeout ( f, ms ) {
>   var targetTime= Date.now()+ ms;
>   scheduleTimeout(f, targetTime);
>   return [ targetTime ];
> }
>
> The way it's now, most of the times you can, but *sometimes* you can't tell:
>
> var ms= 50;
> var t= Date.now();
> setTimeout(f, ms);
> if (t === Date.now()) {
>   //We know: targetTime === t+ms
I am sorry, but we don't "know". Maybe that by the time we've "reached
the bracket", the millisecond has changed. We can have been pre-empted
by the OS scheduler, the system may be slow. There might have been
garbage collection, maybe a repaint of the screen. There is no guarantee
when it's about real time. The only guarantee is that the time moves
forward.
> }
> else {
>   //Not sure, it can be t+ms or t+ms+1
> }
>
> But honestly, I don't see what your point is.
When I write setTimeout(f, 1000), I expect f to be called "after at
least one second" (with the implicit "as soon as possible after the
given time"). That's what programmers have expected since the beginning
and implementors cannot really provide a better guarantee.

---
setTimeout(f1, 1);
setTimeout(f2, 0);
compute();
---
As a programmer, since you have no idea of how much time compute is
going to take, you cannot have any expectation on f1 being called before
f2 since at the end of compute one millisecond may have passed or not.
And you organize your program to be independent of the calling order. My
point is that since you can't rely on a scheduling policy and you
already organize your program to be independent of the scheduling
policy, there is no point standardizing the scheduling policy. No one
will benefit from it. Neither the implementor, nor the programmer.

If you write:
---
setTimeout(f1, 0);
setTimeout(f2, 0);
---
and expect f1 to be called before f2, then why don't you just do
"setTimeout(function(){f1(); f2();}, 0);" ?
the language already allows you to do what you want. There is no need to
enforce the scheduling policy.
If two timers happen to have been scheduled at the same target time by a
more complicated manner, then it's you are already aware in both calls
that the system doesn't guarantee anything about real time, so you're
prepared for a race condition and as such do not have expectations on
who will be fired first.

To answer your concern, my point is that imposing the scheduling policy
won't solve a use case for users and won't help the work of the
implementors (see my low-memory environment example).

The more I think about it and give counter-examples, the more I doubt
what Brendan Eich said that no-determinism can be avoided if the spec is
carefully written. The non-determinism due to code execution time seems
to be unavoidable and leaks to any determinism we could try to reach
with a scheduling policy as long as setTimeout respects "fire after at
least x milliseconds".

David


More information about the es-discuss mailing list