I am deeply interested in parallelism, asynchrony and multithreading. I blog about it everyday in ideas4 (see my profile)
I try think of automatic parallelization approaches. And how to structure programs that take advantage of queuing theory and processing ratios. Imagine if the compiler could work out that one program has a ratio of processing of 2:1 then it could scale out automatically.
I am very interested in compilers that can automatically parallelise. I find Pony to be very interesting with its reference capabilities.
My problem with Rust is that is precludes many safe programs. References can be alive and be passed around.
Regarding bank account transactions, I worked on the same problem. It lead to me implementing multiversion concurrency control. Multiversion concurrency control allows thread safety avoiding locks except for internal data structures of the MVCC.
Multiple threads can read/write the same data but they'll never modify the exact same data due to the multiple versions.
I also implemented the bank account example but I serialised the account transactions to the same account numbers in ConcurrentWithdrawer.java - this solution doesn't use multiversion concurrency control.
My other solution BankAccounts2.java and BankAccounts3.java take different approaches.
The BankAccounts2.java has 1 thread out of 11 threads that synchronizes the bank accounts and performs the serialization of account balances. The other threads generate transactions.
BankAccounts3.java simply uses a lock.
The problem with the bank accounts problem is that I am yet to work out how to scale it. You could shard threads to serve a certain range of account numbers.
Or you can separate the current balance of each account across threads and if the receiving transaction is less than that balance, you don't need to read other threads to check.
I also experimented with other concurrency primitives.
One is a scheduler that receives requests to write to shared memory. Then it schedules the request then the thread marks a callback array and the next request can be served. There's scalability challenges.
> Imagine if the compiler could work out that one program has a ratio of processing of 2:1 then it could scale out automatically.
Don't think that's possible, as there rarely are programs where compute to IO ratio is constant. Even the simplest of say web API will have calls that take more CPU and calls that just wait for network somewhere.
It would be nice to have tooling to figure out whether app is "just" idling or waiting for network for scaling purposes, we already have that in form of IO wait on disk IO.
Then again Go's solution of "have threads so light you can just run 100000 of them to fill CPU even if each of them have a lot of network wait" works well enough. There is also of course async/event driven but that generally leads to code with worse readability (at best similar) and more annoying debugging
I am currently investigating coroutine transpilation with async await similar to Protothreads implementation that uses switch statements. I am trying to do it all in one loop rather than reentrant functions as in Protothreads.
Essentially I break the code up around the async/await and put different parts into a switch. I "think* it's possible to handle nested while loops inside these coroutines.
The problem I don't know how to handle is if a coroutine A calls coroutine B and B calls A. I get the growing data problem which I'm trying to avoid. I want fixed size coroutine list
I think some Microservices take more CPU than others. You can scale one Microservice more than another based on CPU usage.
Another of my benchmarks is multithreading message generation and sending it between threads in thread safe. I can get 20-100 million message sent per second, sending in batches
> I also implemented the bank account example but I serialised the account transactions to the same account numbers in ConcurrentWithdrawer.java - this solution doesn't use multiversion concurrency control.
Damn that's a lot of code. Mutability everywhere, nulls and special integers (-1), triply-nested for-loops, direct indexing into lists. And it's all in memory? If you're in a situation where you want multiple safe writers, just use software transactional memory.
I'm sorry about the code quality, I never got around to refactoring it, I was just trying to get it to work safely and reliably. Without any money destruction or creation.
Checkout MVCC.java and TransactionC.java for multiversion concurrency control. It's far easier to understand.
It takes less code to implement multiversion concurrency control.
Software transactional memory is great and I like it but it can have scalability problems.
I really enjoyed Joe Duffy's blog series on Midori, the Microsoft .NET software transactional memory implementation.
While MVCC works fine in the single-account case, it fails badly in cases where you want to maintain an invariant across accounts. For example, if a person can have two accounts at a bank with a total overdraft of no more than $100 (so A+B>-100), two MVCC transactions can alter one account each, checking for the invariant, and you still end up overdrawn beyond the limit. In general, the fact that MVCC only fully handles write-write hazards can cause many problems.
The whitepaper Serializable Snapshot Isolation talks more of dangerous read-write structures.
My MVCC may be vulnerable to write skew even though it generates the right result. I am yet to generate a test case that exhibits that behaviour. The write skew occurs when there's two dangerous read-write structures
> Imagine if the compiler could work out that one program has a ratio of processing of 2:1 then it could scale out automatically.
Cilk and Cilk++ are parallel variants of C that scale up automatically in the way you describe.
It is not hard to implement it in a scale out way in make (by following the example of distcc), and some of the big data frameworks get it right (especially ones with finer grained tasks than Hadoop MapReduce).
> My problem with Rust is that is precludes many safe programs. References can be alive and be passed around.
I do agree with this and it rubs me the wrong way. Sure I can put something into `std::mem::ManuallyDrop` and hand out transmuted unsafe `&'static mut` references to it but then people come and point out (rightfully) how this library is unsound.
Use something with interior mutability, like the Cell family; then you can hand out & references.
Safe Rust precludes some safe programs, but Rust's soundness rules preclude far fewer. I've only seen a couple of real-world programs that you couldn't express in Rust (without unnecessary runtime checks), and that's solely due to the hierarchical lifetimes.
Concurrency via transactional memory. Try and retry (potentially infinitely) until your transaction (copy) matches source. Then try to push the transaction headers …. The essence of a lock free queue …
I am deeply interested in parallelism, asynchrony and multithreading. I blog about it everyday in ideas4 (see my profile)
I try think of automatic parallelization approaches. And how to structure programs that take advantage of queuing theory and processing ratios. Imagine if the compiler could work out that one program has a ratio of processing of 2:1 then it could scale out automatically.
I am very interested in compilers that can automatically parallelise. I find Pony to be very interesting with its reference capabilities.
My problem with Rust is that is precludes many safe programs. References can be alive and be passed around.
Regarding bank account transactions, I worked on the same problem. It lead to me implementing multiversion concurrency control. Multiversion concurrency control allows thread safety avoiding locks except for internal data structures of the MVCC.
Multiple threads can read/write the same data but they'll never modify the exact same data due to the multiple versions.
https://github.com/samsquire/multiversion-concurrency-contro...
I also implemented the bank account example but I serialised the account transactions to the same account numbers in ConcurrentWithdrawer.java - this solution doesn't use multiversion concurrency control.
My other solution BankAccounts2.java and BankAccounts3.java take different approaches.
The BankAccounts2.java has 1 thread out of 11 threads that synchronizes the bank accounts and performs the serialization of account balances. The other threads generate transactions.
BankAccounts3.java simply uses a lock.
The problem with the bank accounts problem is that I am yet to work out how to scale it. You could shard threads to serve a certain range of account numbers.
Or you can separate the current balance of each account across threads and if the receiving transaction is less than that balance, you don't need to read other threads to check.
I recommend this article by Vale dev's
https://verdagon.dev/blog/seamless-fearless-structured-concu...
I also experimented with other concurrency primitives.
One is a scheduler that receives requests to write to shared memory. Then it schedules the request then the thread marks a callback array and the next request can be served. There's scalability challenges.