parTraverseN fairness

[durban]

The documentation of parTraverseN explicitly mentions fairness:

Note that the semantics of this operation aim to maximise fairness: when a spot to execute becomes available, every task has a chance to claim it, and not only the next n tasks in ta

But, based on some testing, later tasks in ta have a very very small chance of overtaking earlier ones. I suspect this is very task- and processor dependent, but (based on the wording) it seems to me that whoever wrote the docs felt that this is an important feature of parTraverseN, so it might be worth looking into...

[armanbilge]

Hmmm ... I think the implementation detail that this is referring to, is that all tasks are submitted to the runtime at once, and then they race for the semaphore to get their turn to execute.

all tasks are submitted to the runtime at once

In an idealized runtime, such as the test runtime, this means there is no ordering/priority between the tasks.

based on some testing

Can you replicate these results on the test runtime?

[djspiewak]

This does make sense honestly. We traverse the list in order and start fibers as we get to them. So it's actually not unbiased scheduling even on an idealized runtime.

Amusingly, the test runtime will actually be fair because it runs in epochs with randomized sequencing within an epoch, so it's actually perfectly fair assuming infinitely fast compute.

[durban]

Okay, I've tried with TestControl.executeEmbed. Honestly, I've expected much "fairer", because of what @djspiewak says. But still, with the test runtime it's better than with the real one.

This is the test runtime for example:

List(2, 3, 1, 4, 5, 7, 6, 13, 11, 12, 15, 10, 16, 14, 17, 19, 22, 21, 18, 20, 25, 23, 24, 9, 26, 27, 29, 30, 31, 34, 33, 35, 37, 40, 39, 43, 41, 36, 42, 28, 38, 32, 8, 44, 45, 47, 49, 48, 46, 50, 52, 51, 53, 55, 54, 56, 57, 59, 62, 60, 63, 66, 65, 67, 68, 64, 61, 58, 69, 70, 72, 71, 73, 74, 76, 77, 78, 79, 80, 81, 82, 83, 86, 87, 88, 89, 75, 84, 85, 91, 90, 95, 92, 98, 97, 94, 96, 93, 99, 102, 100, 101, 103, 104, 109, 108, 110, 107, 106, 105, 112, 113, 115, 116, 114, 117, 118, 119, 120, 122, 125, 121, 123, 126, 128, 127, 124, 111)

This is a 12-thread WSTP on a 6-core CPU (with hyperthreading):

List(2, 1, 3, 4, 6, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128)