Using the holidays for a 2-week coding session. Writing a new transactional memory manager that’s O(1) for all operations, completely non-blocking and progress-guaranteeing, and uses atomics only for writes.
-
Show this thread
-
All transactions are applied in a sequential order, but can run in parallel as long as there are no read-write conflicts. The big cost: all values > 48 bits in size must be heap-allocated. For this I wrote a non blocking concurrent garbage collector a couple years ago.
3 replies 1 retweet 55 likesShow this thread -
The “trick” is to store a 10-bit transaction id inside variables and use that to resolve conflicts. Any transaction can undo any earlier one, and can be undone by any later one, at any time, with detection at read and write points.
4 replies 2 retweets 87 likesShow this thread -
I view this algorithm as the last hope for performant software transactional implementations since the .NET team’s efforts failed and all experiments show hash table indirection adds too much overhead.
11 replies 5 retweets 103 likesShow this thread -
Replying to @TimSweeneyEpic
Are you familiar with this effort? https://github.com/mtak-/swym/ (blog posts: https://mtak-blog.github.io/generalizing-seqlocks …, https://mtak-blog.github.io/are-we-lock-free-yet …) (Or does that use "hash table indirection"? Sorry, not familiar with which part of the system the hash table resides in in the alluded-to experiments.)
1 reply 0 retweets 2 likes
Similar in the use of sequence numbers to indicate ownership of privatized data. Big difference is I’m nonblocking and writing eagerly, with the ability to undo other tx or be undone at any time.
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.