bokner
InPlace - mutable data structures based on atomics
InPlace is an experimental library that has implementations of several ADTs based on atomics module
In short, the ‘atomics’ API allows operations on mutable arrays of integers.
What is implemented:
- arrays
- stacks
- queues
- heaps
- priority queues
- linked lists
Check out the implementation of X algorithm by Donald Knuth, accompanied by the implementation of Sudoku as an example of usage.
X algorithm is built on the idea of Dancing Links, which relies on the modification of linked lists in place.
The implementation of Dancing Links with immutable data is usually considered to be close to impossible ![]()
First Post!
garrison
lmao this is so unhinged I absolutely love it.
Does anyone know how the lookup from reference => atomic is actually done internally? Is there a table, or something more clever? I feel like you could do some sort of inline caching-style trick.
Most Liked
Schultzer
They are indeed faster, and my first attempt with atomics was extremely fast, I only saw the issues when I had to push harder for correctness and extreme concurrency where my pool ended up allowing multiple processes to use the same connection at the same time.
So I had to lean into the BEAM for correctness which also reduced cache misses, I could properly have kept the original design and just built a queue, but it got to a place where I had to trade simplicity vs complexity.
All that being said, I want to see more of this, since we can get bare metal performance on the BEAM without writing low level code.
Schultzer
This is awesome to see, although be careful about atomics as they can be slow, I had to completely avoid them for my SOTA pool implementation as they got extremely slow due to how schedulers work in conjunction with processes that can move around freely.
If you can keep your atomics on each scheduler then you can avoid global contention.
bokner
I just found out that Donald Knuth had his birthday yesterday.
I have to say that a sizeable part of my motivation to do this project was to have more of Knuth algos in Elixir :-).
Last Post!
garrison
Oh, that’s interesting.
References themselves are heap terms so we have to chase two pointers to get the atomic, correct? Or would that be three with the refcounting?
My understanding of the reference encoding comes from here, but it seems incomplete. I assume the atomics references take up the same space but have a pointer encoded in them? And I assume they must be tagged somehow?
Are other uses of reference overloaded in this way? E.g. an ETS table ref, or monitor ref?
I should really start reading the source ![]()
Popular in Announcing
Other popular topics
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #deployment
- #library
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #channels
- #elixirconf
- #exunit
- #discussion
- #code-sync
- #javascript
- #podcasts
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ecto-query
- #elixir-ls
- #phoenix_html
- #iex
- #blog-post
- #graphql
- #genstage
- #ai
- #websockets
- #supervisor
- #elixirconf-us
- #advent-of-code
- #distillery
- #processes
- #api
- #forms
- #metaprogramming
- #security
- #hex









