Creating highly optimized and specialized fiber mailbox

[jdegoes]

Currently, ZIO 2 uses a concurrent linked queue for the mailbox. However, this data structure is very generic, and not optimized for the fiber runloop in particular. Therefore, it should be possible to create a specialized concurrent mailbox that performs significantly better for run loop workloads.

Facts we can take advantage of:

1. The fiber mailbox is SINGLE READER, MULTIPLE WRITER
2. The fiber mailbox is typically EXTREMELY SMALL, 1 - 4 entries
3. Sometimes, it is not necessary to have a precise answer to the question, "Is the mailbox empty?" (e.g. within the fiber run loop)

Random ideas to experiment with:

1. Core representation as an array of, say, 4 entries, followed by a growable linked list; could also experiment with a register-based approach, where there are no more than 4 slots (slot1, slot2, slot3, slot4)
2. Atomic integer is the natural thing to use to represent write position; given reads happen from only one thread, it's possible an ordinary variable might work for read position (the mailbox could extend an atomic integer for more efficient layout & caching)
3. Inefficiencies in "large" mailboxes is fine because they almost never happen
4. The runtime fiber class could extend the mailbox class for more efficient caching & smaller memory usage
5. A small amount of spin-looping is probably acceptable for unlikely and quickly resolved race conditions

[jdegoes]

/bounty $1250

[algora-pbc]

💎 $1,250 bounty • ZIO

Steps to solve:

1. Start working: Comment /attempt #8807 with your implementation plan
2. Submit work: Create a pull request including /claim #8807 in the PR body to claim the bounty
3. Receive payment: 100% of the bounty is received 2-5 days post-reward. Make sure you are eligible for payouts

Additional opportunities:

• 🔴 Livestream on Algora TV while solving this bounty & earn $200 upon merge! Comment /livestream once live

Thank you for contributing to zio/zio!

Add a bounty • Share on socials

Attempt	Started (GMT+0)	Solution
🔴 @kyri-petrou	Apr 30, 2024, 10:03:24 PM	WIP
🟡 @ajaychandran	May 14, 2024, 9:52:18 AM	WIP

[jdegoes]

cc @kyri-petrou

[jdegoes]

cc @kyri-petrou

[jdegoes]

cc @kyri-petrou

[jdegoes]

Another possible experiment: pull out head of queue separately for the 1 element case, put the rest of a small number into an array, and use a linked list for long tails.

[jdegoes]

Bounty is for an implementation that is notably faster than concurrent linked queue in run loop-type usage scenarios, together with a benchmark that proves it, and also before/after benchmark results for any existing benchmarks that can benefit from a specialized mailbox (probably fork).

[kyri-petrou]

@jdegoes sounds great, I'll give this a go!

/attempt #8807

Algora profile	Completed bounties	Tech	Active attempts	Options
@kyri-petrou	8 ZIO bounties	Scala, Python, Shell & more		Cancel attempt

[algora-pbc]

@kyri-petrou: Reminder that in 7 days the bounty will become up for grabs, so please submit a pull request before then 🙏

[hearnadam]

@kyri-petrou I started working on an Array backed implementation which is showing some promise. Let me know if you would like to work together.

[kyri-petrou]

Hey @hearnadam, thanks for reaching out! My time is going to be a bit sparse starting tomorrow as I'm going to be travelling, but I'm happy to share notes with you and provide insights if you like :)

Feel free to reach out to me on Discord, my username is kpetrou

[ajaychandran]

/attempt #8807

Working on an implementation based on Jiffy. The paper claims an improvement of 10x over MSQueue (the algorithm used in ConcurrentLinkedQueue).

Options

• Cancel my attempt

[algora-pbc]

Note

The user @kyri-petrou is already attempting to complete issue #8807 and claim the bounty. We recommend checking in on @kyri-petrou's progress, and potentially collaborating, before starting a new solution.

[ajaychandran]

@kyri-petrou The Jiffy algorithm is a novel one. Hope its fine if I attempt this in parallel.

[kyri-petrou]

@ajaychandran of course feel free to, and thanks for asking! :) curious to see what it yields!

[algora-pbc]

@ajaychandran: Reminder that in 7 days the bounty will become up for grabs, so please submit a pull request before then 🙏