Optimize ZEnvironment

[jdegoes]

ZEnvironment is implemented atop existing data structures, which are not optimized for environment usage patterns.

A custom ZEnvironment can achieve significantly better performance by taking advantage of the following facts:

1. Single writer, (usually) single reader. Environments are in fact read by other fibers, but for the most part, they are read by the fiber that owns them. They are always written to by the fiber that owns them.
2. Frequent gets. Gets are the most common operation, and need to be extremely fast, even at the cost of slowing down other operations.
3. Common statically-known keys. Some things, like Scope, are routinely stored in nearly every environment. This suggests a register-based hybrid design could be useful to accelerate performance for the services that are nearly always used in every ZIO application.
4. Push / pop access pattern. A common access pattern is to add a service, execute an effect, then remove it. While the effect is executing, it may add another service, execute an effect, then remove it, etc. This leads to a "push / pop" access pattern that could be taken advantage of, e.g. by having an outer ZEnvironment link to an inner one, so when the "pop" occurs, the inner one is used.
5. Small(ish) size. Environments would "never" contain thousands of services, and seldom contain hundreds; they're much more likely to contain dozens of services.
6. Static inheritance hierarchies. Inheritance hierarchies are static, which is not taken advantage of. Every tag has N supertypes that it can be indexed under. Probably most of these supertypes are not likely to be used, and only a few. These could be globally precomputed and stored in a single concurrent map.

One idea that could be explored (not to imply it is the best): append-only arrays with atomic reference for writer index, and snapshot int for reader index (see how appending a single element is implemented in Chunk for the idea). One array stores tags, the other, services. You lookup by traversing the array in reverse order, respecting the snapshot index so you don't read more than your copy is supposed to know about. Another idea: a linked list, where later ZEnvironment points to earlier ZEnvironment (I think this will be great at reusing structure, but poor at lookup performance due to cache locality issues).

[jdegoes]

/bounty $1500 for a notably faster implementation of ZEnvironment that takes advantage of its unique usage patterns, and a benchmark proving this (with before / after results in PR).

Ping @kyri-petrou

[algora-pbc]

💎 $1,500 bounty • ZIO

Steps to solve:

1. Start working: Comment /attempt #8828 with your implementation plan
2. Submit work: Create a pull request including /claim #8828 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		#8846

[kyri-petrou]

Thanks I'll give it a go 👍

[algora-pbc]

💡 @kyri-petrou submitted a pull request that claims the bounty. You can visit your bounty board to reward.

[algora-pbc]

🎉🎈 @kyri-petrou has been awarded $1,500! 🎈🎊

• Share on socials
• Give feedback