I uploaded an update to bfs.patch which improves behavior in particular on non-Linux multi-core (4+) machines. 

Hi Charles-Francois, Thanks for taking the time to review this patch!

> - nothing guarantees that you'll get a msec resolution

Right, the code should behave well with low precision clocks as long as short (sub-tick) tasks are not synchronized with the slice interval. There is a related discussion of this problem in schedulers in the section on sub-tick accounting in: http://ck.kolivas.org/patches/bfs/sched-BFS.txt

On which target systems can we expect not to have high precision clock?

> - gettimeofday returns you wall clock time: if a process that modifies time is running, e.g. ntpd, you'll likely to run into trouble. the value returned is _not_ monotonic, but clock_gettime(CLOCK_MONOTONIC) is
> - inline functions are used, but it's not ANSI
> - static inline long double get_timestamp(void) {
>    struct timeval tv;
>    GETTIMEOFDAY(&tv);
>    return (long double) tv.tv_sec + tv.tv_usec * 0.000001;
> }

I added timestamp capping to the code. timestamp is used for waiting and therefore I think the source should be either CLOCK_REALTIME or gettimeofday().

> > `tstate->tick_counter % 1000` is replicating the behaviour of the old GIL, which based its speculative operation on the number of elapsed opcodes (and which also gave bad latency numbers on the regex workload).
>
> I find this suspicous too. I haven't looked at the patch in detail, but what does the number of elapsed opcodes offers you over the timesplice expiration approach ?

More accurate yielding. It is possible a better mechanism can be thought of and/or maybe it is indeed redundant.

> It is thus recommended that a condition wait be enclosed in the equivalent of a "while loop" that checks the predicate."

Done.