Duplicate queues in scheduler(s)

[hkaiser]

Duplication of the thread queues in the schedulers (let's start with the local_priority_queue_scheduler) would possibly allow to reduce the work-stealing overheads by minimizing cache interference. The idea is to add a 'passive' queue next to each 'active' one. The 'active' queue is used as long as it holds threads to run. As soon as it runs empty the scheduler swaps the queues and continues executing threads from the now 'active' (formerly 'passive') queue. New threads are scheduled on the currently 'passive' queue. Work-stealing happens from the 'passive' queue first and only if that was unsuccessful tries to steal from the 'active' queues (as before).

This change should include a thorough performance analysis on various workloads.

[arpittkhandelwal]

Hi @hkaiser sir,

Based on my research into the local_priority_queue_scheduler and thread_queue
implementations, I would like to propose an optimization aimed at reducing
cache contention and improving scheduling efficiency.

Proposed Solution: Active/Passive Queue Duplication

The core idea is to move scheduling and work-stealing overhead away from the
primary execution path of worker threads by introducing a duplicated queue
structure per worker.

1. Duplicated Queue Structure

Each worker thread’s normal-priority queue will be extended into a pair of queues:
an active queue and a passive queue.

struct duplicated_queue {
    thread_queue_type* active_;
    thread_queue_type* passive_;
};

2. Refined Scheduling (Push)

All new threads (and recycled ones) will be scheduled onto the passive queue.
This reduces cache line contention on the active queue, which is being actively
consumed by the worker thread.

3. Execution Flow (Pop)

Worker threads will always pop work from the active queue. Once the active queue
is empty, the scheduler will swap the active and passive queues and continue
execution from the new active queue.

4. Optimized Work-Stealing

When a worker attempts to steal work from another thread (victim), it will first
attempt to steal from the victim’s passive queue. This allows stealing of "fresh"
work with minimal disruption to the victim’s execution. If the passive queue is
empty, it will fall back to stealing from the active queue.

5. Cohesive Management

All scheduler-level methods (such as get_queue_length, cleanup_terminated, and
on_start_thread) will be updated to transparently operate across both queues in
the pair.

Next Steps

If this approach looks good, I will proceed with the following:

1. Updating the local_priority_queue_scheduler class members and initialization
   to use duplicated_queue.
2. Implementing the active/passive swap logic inside get_next_thread.
3. Adjusting the work-stealing logic in attempt_stealing_pending to prioritize
   the passive queue.
4. Verifying correctness and performance using existing and new unit tests.

Please let me know if I can proceed with the implementation or if you have any
suggestions or concerns.

Thanks!

[Leonid-Margulis-03]

Hi. I see there is already some interest here, but I've been studying the HPX scheduler architecture and would love to tackle this or collaborate on the implementation.

I've built a custom C++ task executor (https://github.com/Leonid-Margulis-03/executor), so thread pool queues, lock-free structures, and concurrency are exactly what I enjoy working on.

If I were to help tackle this, here is my technical roadmap based on the HPX codebase:

1. Queue Structure Update: Instead of a single pending queue per worker in the scheduler, I would introduce the dual-queue structure (active/passive) by modifying the internal abstractions (likely wrapping the PendingQueuing lockfree structures inside hpx::threads::policies::thread_queue).
2. Spawn vs. Execute: Route new task enqueue operations to the passive lock-free queue. Update the execution loop (get_next_thread) to solely pop from the active queue to keep the worker's CPU cache strictly hot.
3. Atomic Swapping Strategy: Implement a lightweight mechanism (e.g., atomic pointers/indices) to safely swap the active and passive queues when the active queue drains, ensuring minimal overhead.
4. NUMA-Aware Stealing: Update the work-stealing logic. When iterating through victim queues (respecting NUMA domains), the stealer must attempt to pop from the victim's passive queue first, only falling back to the active queue if the passive one is empty.
5. Benchmarking: Run comprehensive performance analyses (using tools like hwloc and HPX's built-in APEX/performance counters) across various highly concurrent workloads to validate the reduction in cache contention overhead.

Let me know how you'd like to proceed!

[hkaiser]

@arpittkhandelwal, @Leonid-Margulis-03 please coordinate on this.

[arpittkhandelwal]

Hi @Leonid-Margulis-03,

Thanks! I’d be happy to collaborate on this.

I went through your roadmap and it aligns really well with what I had in mind,
especially around separating execution vs scheduling paths and prioritizing
the passive queue for stealing. Your experience with executors and lock-free
structures will definitely add strong value here.

Would you be open to collaborating along these lines?

• I can take the lead on integrating the active/passive queue model into
  local_priority_queue_scheduler (initial prototype and correctness).
• You could focus on refining lower-level aspects like atomic swap strategies,
  lock-free behavior, and NUMA-aware stealing optimizations.

Once we have a working prototype, we can iterate together on performance tuning
and benchmarking.

If this works for you, I can start with a draft implementation so we have
something concrete to build on and review.

Looking forward to working together!

Thanks!

[Leonid-Margulis-03]

Hi @arpittkhandelwal
I'd be very happy to collaborate too!

First of all, hkaiser said this to me on discord:

While I said on the ticket that the first target should be the local_priority_queue_scheduler, 
I think that the main changes will happen in the thread_queue.
It might be even a good idea to leave the current thread_queue unchanged and create a new type that
exposes the same interface, but implements the duplicate queue idea.

So I assume we should create a new scheduler type exposing the same interface.

I like your idea. If I understand it correctly, you want to create this scheduler. And I will go through it to make sure everything is right.

[arpittkhandelwal]

Hi @Leonid-Margulis-03,

That sounds great, really glad we're aligned on this!

Thanks for sharing hkaiser’s input — I agree that introducing a new
thread_queue/scheduler type is a clean and safe way to experiment with this
approach.

I’ll start working on a prototype for the active/passive queue-based scheduler
and share an initial version soon so we can iterate together.

Also just to align — are you planning to target this as a GSoC project?

Looking forward to working together!

Thanks!

[hkaiser]

A new scheduler type is not necessary, it may however simplify benchmarking as everything would be in the same binary. I'll leave that to you, even if that may be more involved as you'd have to look at command line handling, scheduler instantiation, and other, possibly unrelated things.

[Leonid-Margulis-03]

Hi! @arpittkhandelwal
To be honest, I was considering it as an opportunity to apply for GSoC, yes. What about you?
Do you think it's possible that we will both work on this project for GSoC?

[hkaiser]

Hi! @arpittkhandelwal To be honest, I was considering it as an opportunity to apply for GSoC, yes. What about you? Do you think it's possible that we will both work on this project for GSoC?

@Leonid-Margulis-03 I think you can go ahead and submit a proposal for this. IIUC, @arpittkhandelwal will submit another project.