ConditionVariable::notify_one notifies all fibers?

[google]

ConditionVariable::notify_one notifies all fibers?

[ben-clayton]

Good spot, Ben. Yes this was a bug introduced in ecd5ab3.

I noticed that waiters are inserted at the front of the list which seems like it may also be intentional to try to keep wait/notify pairs on the same thread (or at least provide some ordering); is that right?

There was no strong reason, and perhaps it should be reversed. You could argue that FILO is good for icache, but certainly isn't fair, and does contradict the FIFO nature of scheduler. It is the way it is because it was simpler to implement (marl:: containers::list doesn't actually keep a pointer to the end item), and there's no order guarantees in the documented interface. It might be worth implementing FIFO for ConditionVariable and doing some benchmarking.

I need to customize ConditionVariable a bit for my use case, so I was trying to understand the load-bearing parts of the implementation

Are you able to share what sort of customizations you need to make?

[benvanik]

There was no strong reason, and perhaps it should be reversed. You could argue that FILO is good for icache, but certainly isn't fair, and does contradict the FIFO nature of scheduler. It is the way it is because it was simpler to implement (marl:: containers::list doesn't actually keep a pointer to the end item), and there's no order guarantees in the documented interface. It might be worth implementing FIFO for ConditionVariable and doing some benchmarking.

Good points! FIFO may work better for what I'm doing, but that would require a doubly-linked list probably.

Are you able to share what sort of customizations you need to make?

The synchronization primitive I'm working with is basically Vulkan's timeline semaphore/D3D12's fence - so a single monotonically increasing payload value that is signaled and waiters wait for a specific payload value to be reached or exceeded. It could be implemented as a uint64_t + marl::ConditionVariable, but by specializing it I can keep track of waiters with the value they expect and only notify those whose who need to be when signaling (and avoid an extra mutex).

It may be a useful primitive to have in marl itself - if there's interest I'd be happy to upstream!

[ben-clayton]

FIFO may work better for what I'm doing, but that would require a doubly-linked list probably.

Yes, probably. Happy to make changes here if we feel there's wins to be had.

The synchronization primitive I'm working with is basically Vulkan's timeline semaphore/D3D12's fence - so a single monotonically increasing payload value that is signaled and waiters wait for a specific payload value to be reached or exceeded. It could be implemented as a uint64_t + marl::ConditionVariable, but by specializing it I can keep track of waiters with the value they expect and only notify those whose who need to be when signaling (and avoid an extra mutex).

Similar to (but clearly not the same as) marl::Ticket::Queue. In fact, the original implementation of marl::Ticket::Queue was based around internals very similar to this. I'm not happy about the performance of tickets, so if you come up with something awesome, perhaps I'll take a look at whether its possible to re-implement tickets to use it.

It may be a useful primitive to have in marl itself - if there's interest I'd be happy to upstream!

Certainly sounds like it. Very happy to accept new primitives!

[benvanik]

Interesting! I was about to take a deeper look at Ticket::Queue to see if I could use it for modeling vkQueueSubmit ordering behavior (the ordering described here: https://www.khronos.org/registry/vulkan/specs/1.2/html/vkspec.html#synchronization-implicit), but now that you mention it this may be better served by a simple FIFO chain as all I'd be doing with Ticket::Queue is taking a new ticket and waiting on the previous one such that things behaved like a FIFO. That definitely calls for a doubly linked list so that may be worth adding (marl::containers::deque?).