TODO list for this PR

• documentation
• iterator instead ofsplit_list::snap() method
• rename to intrusive_split_list
• add chunked_fifo

upd:

• reimplemented iteration with "standard" iterators approach. This did saved one instruction in assembly and improved the cycles a bit (5.8 -> 5.2)

split-list main loop decoded

  43b540:   89 c2                   mov    %eax,%edx  43b542:   83 c0 01                add    $0x1,%eax  43b545:   83 e2 0f                and    $0xf,%edx  43b548:   48 8b 4c d4 88          mov    -0x78(%rsp,%rdx,8),%rcx  43b54d:   8b 79 10                mov    0x10(%rcx),%edi  43b550:   48 8b 49 08             mov    0x8(%rcx),%rcx  43b554:   48 01 fe                add    %rdi,%rsi  43b557:   48 89 4c d4 88          mov    %rcx,-0x78(%rsp,%rdx,8)  43b55c:   44 39 c0                cmp    %r8d,%eax  43b55f:   75 df                   jne    43b540 <_ZNK8sum_perf8sum_sl16Ev+0x80>

This is a really interesting and clever implementation. I think its benefit over regular intrusive singly-linked lists is closely tied to how prefetching works on contemporary CPUs - that it actually prefetches data pointed by any pointer it sees, so it is helpful to let it see a few (F) pointers in advance instead of just the next one. I wonder how much this advantage remains if the scanning code does something more than just advance but actually do a bit more work on each item - in this case the pre-fetching of F items in advance might be too early - as we still have a lot of work to do before we're ready to need the Fth next item. Also in this case the speedup of just the scan might be negligible compared to the real amount of work we need to do on the items.

Do you know if something like your "split list" was ever done before? I searched a bit and got to a concept called a "chain" for each of the individual linked list, and "multi-chain" for the idea of having multiple independent lists each allowing one prefetching - but most discussions I read about these ideas where how to write a better prefetcher - not how to write a linked list that works better with the existing prefetcher. Maybe you can write a paper - or at least a blog post - on this new (?) technique :-)

You mentioned that you were looking for the ability to "push_back and push_front" - does your intended use case (run-queue) actually use both? chunked_fifo<> doesn't do push_front, but this was a decision to simplify the API - it's not that it was algorithmically impossible to implement. Of course if your goal is to be anintrusive collection, then obviously chunked_fifo is not what you're looking for and you needed to create a new type. But in that case I think the wordintrusive should be part of the new collection's name, and part of the pull request's title. If, on the other hand, "intrusive" was not very important to you - it appears that the existing chunked_fifo is actually a tiny bit more efficient than the new split_list, right?

I wonder how much this advantage remains if the scanning code does something more than just advance but actually do a bit more work on each item - in this case the pre-fetching of F items in advance might be too early - as we still have a lot of work to do before we're ready to need the Fth next item. Also in this case the speedup of just the scan might be negligible compared to the real amount of work we need to do on the items.

It's perfectly valid concern. I will be able to answer it more reliably after I rebase#3125 onto this new container and see more real-life-ish example of tasks queue processing. There's a perf test for runqueue scan in that PR too. It runs no-op tasks, so it's still a simplification.

Do you know if something like your "split list" was ever done before?

I'm pretty sure that someone did that. At least, Redpanda says that theycoded something similar. I also tried to find more info aboutthis Avi's concen, and also found some "related" discussions, but overall no, I didn't find any deep research on that topic.

Maybe you can write a paper - or at least a blog post - on this new (?) technique :-)

I already did :) I'll send you a link

You mentioned that you were looking for the ability to "push_back and push_front" - does your intended use case (run-queue) actually use both?

Yes.reactor::add_task() does push_back andreactor::add_urgent_task() does push_front.

Of course if your goal is to be an intrusive collection, then obviously chunked_fifo is not what you're looking for and you needed to create a new type. But in that case I think the word intrusive should be part of the new collection's name, and part of the pull request's title.

Yes, definitely. Renaming of the collection is in theTODO list as well.

If, on the other hand, "intrusive" was not very important to you - it appears that the existing chunked_fifo is actually a tiny bit more efficient than the new split_list, right?

Yes, that's correct. And chunked_fifo is actuallyfaster than split-list, so we have a choice of three elements

• circular_buffers -- the fastest (3.8 cycles per element), but allocates and potentially performs "large allocation"
• chunked_fifo -- a bit slower (4.6 cycles per element), also allocates, but doesn't suffer from large allocation problem
• split-list -- the slowest (5.2 cycles per element), but doesn't needextra memory to maintain elements (tasks)

(and a reminder, to have some reference number for those "cycles" numbers -- plain intrusive list takes 25.8 cycles per element; all numbers are for 10k elements in the collection)

upd:

• I updated the PR description with test results on i7 processor (previously I ran it on AMD threadripper). On i7 split-list beats chunked_fifo!

upd:

• renamed the collection to beintrusive_split_list
• re-implemented properly theoperator-> andoperator* for iterator
• initialize objects in base class constructor. This allows avoiding the uglyinit_once() call and drop the manual start_measuring/stop_measuring tuning
• introduced generic tests parametrization. This allows having a single scanning test function implemented and change the collection size from the command-line

Documentation is yet to be written 😕

Looks like chunked_fifo wins. And again I need to re-measurehttps://github.com/avikivity/seastar/commits/sort-tasks/, I found some bugs in it.

Looks like chunked_fifo wins

Looks like it doesn't :) I measured on i7i.2xlarge instance with Xeon processor -- split-list 2.1 vs chunked-fifo 2.4

I updated the PR description with full table

Added (to PR description) results for Threadripper, but with different compiler (clang-20). Split-list 4.9 vs chunked-fifo 6.9

upd:

• addedsize_t intrusive_split_list::size() needed to implement task queue using this collection

Would it be worth considering chunked_fifo as a first iteration?

It's better to discuss it in#3125 , because that's the place where the new collection is actually used. This PR just adds some benchmarks. However ...

I assume the main concern with circular_buffer is the potential reallocation when it reaches max capacity - is that correct?

Not only. It's other main concern is that it allocates at all, thus making task wakeup potentially failing operation. However, I agree, that the problem is amortized, the buffer is never shrank back, so once it passes a wake-up storm, it survives until next, larger tsunami.

Additionally, it would be helpful to include circular_buffer in the benchmarks, since that's the current implementation for the scheduler run-queue. This would provide a clearer picture of the actual improvement.

Agree. Actually, the purpose of this test was to show the difference in handling different memory layouts, and circular_buffer is layed out as vector. But I think that testing differentimplementations of the same layout is worthwhile.

My feeling is that this thing is more sensitive to different workloads than chunked_fifo.

A run with very small+fast tasks will prefer large F, so that prefetch can happen in time.
A run with large+slow tasks will prefer small F, so there is smaller cache footprint and less chance we lost the data structure roots from the cache.

I believe the second effect is much less important so we'd choose a reasonably large F (say, 8 -- what did you measure with?).

A different objection is that I'd like to pursue my sort-tasks thing which un-FIFOs the task queue. But it needs more work.

Would it be worth considering chunked_fifo as a first iteration?

It's better to discuss it in#3125 , because that's the place where the new collection is actually used. This PR just adds some benchmarks. However ...

I assume the main concern with circular_buffer is the potential reallocation when it reaches max capacity - is that correct?

Not only. It's other main concern is that it allocates at all, thus making task wakeup potentially failing operation. However, I agree, that the problem is amortized, the buffer is never shrank back, so once it passes a wake-up storm, it survives until next, larger tsunami.

The tasks themselves are allocated; if we can allocate a task, we can allocate a chunk for chunked_fifo.

what did you measure with?

16