A couple remarks on BFS-based patch:
- nothing guarantees that you'll get a msec resolution
- 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;
}
the product is computed as double, and then promoted as (long double).
- the code uses a lot of floating point calculation, which is slower than integer

Otherwise:
"- You know, I almost wonder whether this whole issue could be fixed by just adding a user-callable function to optionally set a thread priority number.  For example:

    sys.setpriority(n)

Modify the new GIL code so that it checks the priority of the currently running thread against the priority of the thread that wants the GIL.  If the running thread has lower priority, it immediately drops the GIL."

The problem with this type of fixed-priority is starvation. And it shouldn't be up to the user to set the priorities. And some threads can mix I/O and CPU intensive tasks.

> It's a dual-core Linux x86-64 system. But, looking at the patch again, the reason is obvious:
>
> #define CHECK_SLICE_DEPLETION(tstate) (bfs_check_depleted || (tstate
> >tick_counter % 1000 == 0))
>
> `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 ?