[SERVER-56423] Explore CPS-like approach in SBE VM and BSON parser Created: 28/Apr/21  Updated: 06/Dec/22

Status: Backlog
Project: Core Server
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Improvement Priority: Major - P3
Reporter: Nikita Lapkov (Inactive) Assignee: Backlog - Query Execution
Resolution: Unresolved Votes: 0
Labels: sbe-post-v1
Remaining Estimate: Not Specified
Time Spent: Not Specified
Original Estimate: Not Specified

Assigned Teams:
Query Execution
Participants:

 Description   

A few days ago one of the developers from Google Protobuf team wrote an interesting post on how they achieved 2 GB/s parsing speed, which is almost 2x of previous state of art.

The general idea is to use a chain of tail calls instead of one big while loop with switch statement inside. This forces compiler to optimize most of the tail calls and keep most of arguments on the registers. Wasm3 runtime for WebAssembly uses the same approach.

It could be interesting for us to experiment with this approach in the SBE BSON parser or SBE VM.

Alternatively, we could use computed gotos approach, which is used by Python VM. In this case instead of using switch statement, we can use goto with computed address of label for next instruction.

Protobuf article: https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html
Wasm3 wiki: https://github.com/wasm3/wasm3/blob/main/docs/Interpreter.md#m3-massey-meta-machine
Article about computed goto: https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables



 Comments   
Comment by Kyle Suarez [ 29/Apr/21 ]

Parking this in the SBE spillover project for now so we don't lose track of it.

Generated at Thu Feb 08 05:39:13 UTC 2024 using Jira 9.7.1#970001-sha1:2222b88b221c4928ef0de3161136cc90c8356a66.