assembly VS multiversion-concurrency-control

When you're learning something for the first time, it can be hard to know what mental model you need to have to be effective with the tool.

Some documentation is reference material. With reference material you might navigate the reference material in a particular traversal to get what you need to do what you want.

But at the beginning of your journey, you need to be taught a "flow" an expected pattern of operation to build up the right mental model of how an average session with the tool works. For programming this might be the edit file, compile, run, debug loop, or TDD or IntelliJ's build and deploy. Or a CI system commit, push, deploy, promote cycle. Or kubernetes kubectl edit, apply.

I opened the "dining philosophers TLA+" example and ran it - this seemed to be an affordance of the TLA+ Toolbox GUI which was straightforward to understand.

But then I tried to use the tool with my own. I interpreted the existing code of the dining philosophers and tried to make my own ringbuffer model.

It took me a while that I needed to update this screen to put in the following details that I have filled in on the screenshot:

https://github.com/samsquire/assembly/blob/main/screenshots/...

You have to put your entrypoint in the "temporal formula" and then put your model arguments on the right hand side.

I was able to piece together the operation of this tool by piecing together various reference details together, it wasn't until I saw that screenshot I referenced in my OP that I realised I needed to do that step to get the PlusCal code to update the TLC code that follows it. I was wondering why it didn't work until I saw that screenshot.

Thank you for this in-depth article.

I am a less than a C++ beginner but I asked Stack Overflow how to run C++ coroutines in a thread pool. It seems coroutines in C++20 are unfinalised but don't quote me on that but I did get some sourcecode for older versions of the C++20 standard.

I used Marce's Col's excellent blog post about how to create coroutines in assembly by adjusting the RSP pointer.

https://blog.dziban.net/posts/coroutines/

I extended Marce's code to run the coroutines in kernel threads:

https://github.com/samsquire/assembly (see threadedcoroutines.S)

I have been thinking of coroutines in terms of query compilation for database engines and the volcano query model and this article:

https://www.chiark.greenend.org.uk/~sgtatham/coroutines.html

Tying together two pieces of code that call eachother in push or pull driven style is really powerful. Or if you're running multiple independent tasks that need their own state. This as I understand it is the original intent of object orientation that Alan Kay wanted and is represented by Erlang and partly Go.

Specifically, I am thinking of compiler created coroutines where code can be interleaved at compile time rather than at runtime.

Thank you for your ideas and thoughts.

This might be relevant - I've been playing around with some assembly to unwind the stack, but it occurred to me I don't need to pop the stack to scan through it. So like C++ exception handling (I learned about it in the Itanium C++ ABI) or algebraic effects, you can scan memory if you have access to the stack start in memory (I do that by storing the rsp somewhere in .global main) in theory it's just data.

I need to generate sections of lookup data for range information for associating .text code section addresses with function names.

In theory this would also be useful for coroutines since a coroutine position/state is just a program counter position of code that you can JMP to in your yield function (that isn't a call but an offset)

To move a coroutine from one thread to another or another machine over the network or persist to disk, let me think. We could do what C++ coroutines does and have a promise struct object that is presumably on the stack when a coroutine resumes by jumping to that coroutines location.

I think the hard part is being stackless and persisting the current coroutine state. You could mov $COMPILER_DETERMINED_OFFSET into -10(%rbp) that promise object and then when the coroutine resumes it does a JMP -10(%rbp) in a label before the coroutine body.

I am a beginner to assembly programming but here is my program: https://github.com/samsquire/assembly/blob/main/stackunwind....

https://github.com/samsquire/assembly/blob/main/coroutines.S

This might be useful to someone who wants to port this to C. This uses the stack switching idea. So they are stackful coroutines.

There's also Tina a header only coroutine library

The code is in this repository https://github.com/samsquire/multiversion-concurrency-control in MultiplexingThread.java and MultiplexProgramParser.java

https://github.com/samsquire/multiversion-concurrency-contro...

And I implemented a 3 way text diff with myers algorithm based on https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm...

https://github.com/samsquire/text-diff

I implemented an eventually consistent mesh protocol that uses timestamps to provide last write wins

I think I lean towards per-thread sharding instead of mutex based or lock free data structures except for lockfree ringbuffers.

You can get embarassingly parallel performance if you split your data by thread and aggregate periodically.

If you need a consistent view of your entire set of data, that is slow path with sharding.

In my experiments with multithreaded software I simulate a bank where many bankaccounts are randomly withdrawn from and deposited to. https://github.com/samsquire/multiversion-concurrency-contro...

I get 700 million requests per second due to the sharding of money over accounts.

If you want some sample code to implement MVCC, I implemented MVCC in multithreaded Java as a toy example

https://github.com/samsquire/multiversion-concurrency-contro...

First read TransactionC.java then read MVCC.java

I wrote an unrolled switch statement in Java to simulate eager async/await across treads.

https://github.com/samsquire/multiversion-concurrency-contro...

The goal is that a compiler should generate this for you. This code is equivalent to the following:

   task1:

https://doc.rust-lang.org/book/ch16-00-concurrency.html

I've been working on implementing Java async/await state machine with switch statements and a scheduling loop. If the user doesn't await the async task handle, then the task's returnvalue is never handled. This is similar to the Go problem with the go statement.

https://github.com/samsquire/multiversion-concurrency-contro...

If your async call returns a handle and

yield value2++

https://github.com/samsquire/multiversion-concurrency-contro...

I am still working on allowing multiple coroutines to be in flight in parallel at the same time. At the moment the tasks share the same background thread.

I asked this stackoverflow question regarding C++ coroutines, as I wanted to use coroutines with a thread pool.

https://stackoverflow.com/questions/74520133/how-can-i-pass-...

This is very interesting. Thank you for submitting this and thank you for working on this.

I am highly interested in parallelism and high concurrency. I implemented multiversion concurrency control in Java.

https://github.com/samsquire/multiversion-concurrency-contro...

I am curious how to handle replication with high concurrency. I'm not sure how you detect dangerous reads+writes to the same key (tuples/fields) across different replica machines. In other words, multiple master.

I am aware Google uses truetime and some form of timestamp ordering and detection of interfering timestamps. But I'm not sure how to replicate that.

I began working on an algorithm to synchronize database records, do a sort, then a hash for each row where hash(row) = hash(previous_row.hash + row.data)

Then do a binary search on hashes matching/not matching. This is a synchronization algorithm I'm designing that requires minimal data transfer but multiple round trips.

The binary search would check the end of the data set for hash(replica_a.row[last]) == hash(replica_b.row[last]) then split the hash list in half and check the middle item, this shall tell you which row and which columns are different.