@category_xyz, ex @facebook, @ibm. Concurrent algorithms. High-throughput. Low-latency.
Joined July 2013
- Tweets58
- Following111
- Followers258
- Likes197
Maged Michael retweeted
Awesome explainer from @MagedMMichael on Monad's caching mechanism, which handles a problem specific to blockchain: caching state key-value pairs for pre-finalized blocks
Proud to be part of the team @category_xyz
Monad execution client is now open source (link below).
This is the result of thousands of hours of effort by the team at @category_xyz.
Enjoy
11
582
Hazard pointer protection is super fast, but is it scalable too? Yes. it is.
Hazard pointer protection is effectively perfectly scalable:
• Line 8: Writing to the hazard pointer almost never generates cache coherence traffic. Hazard pointers are padded and properly aligned to avoid false sharing among writes to different hazard pointers. Each hazard pointer is only written by one thread at a time (its owner) and is read very rarely (by a reclaimer). The ratio of writes (by owner) to reads (by a reclaimer) is in practice at worst in the order of 1,000:1 and more typically a lot higher (e.g., one write per lookup in a concurrent hash map vs one read per amortized reclamation of thousands of deleted items).
• Line 10: The lightweight asymmetric memory barrier doesn't generate any instructions.
• Line 12: Re-reading the pointer from the source is almost always an L1 cache hit and so it doesn't generate cache coherence traffic.
• Line 14: Perfectly scalable local computation that doesn't involve memory access or synchronization.
Maged Michael retweeted
This is a big milestone: half of the codebase, implementing MonadBFT, RaptorCast, blocksync, statesync, mempool, etc. is open source!
This codebase is a treasure trove of performant systems engineering work. We hope this materially pushes the space forward.
Step by step.
Monad consensus client is now open source (link below).
This is the result of thousands of hours of effort by the team at @category_xyz.
Enjoy
Maged Michael retweeted
Monad consensus client is now open source (link below).
This is the result of thousands of hours of effort by the team at @category_xyz.
Enjoy
Why is it so fast?
Hazard pointer protection is so friendly to modern microarchitecture features that its overhead is effectively hidden, amounting to a fraction of a cycle:
• Line 8: Writing ptr (pointer to the to-be-protected object) to the hazard pointer is done in parallel with other instructions.
• Line 10: The lightweight asymmetric memory barrier doesn't generate any instructions.
• Line 12: Re-reading the pointer from the source (that was just read in line 5) is almost always an L1 cache hit.
• Line 14: The branch based on comparing the two pointers is super easy to predict.
Together, these steps keep the pipeline flowing smoothly without stalls, thanks to instruction-level parallelism, pipelining, branch prediction, and speculative execution.
How fast is hazard pointer protection?
It takes a small fraction of a nanosecond to protect an object from unsafe reclamation using a hazard pointer.
Here is a concise representation of hazard pointer protection:
Some fascinating history of the IBM Lifo List, one of the most elegant concurrent algirthms.
This is a simplified variant without ABA problem in the Pop operation.
teapawt.net/MagedMMichael/status/1…
Maged Michael retweeted
"The goal of @category_xyz is to build a world class research team" @_jhunsaker
Monad will grow increasingly more performant and decentralized as the protocol matures
