bokner

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 :slight_smile:

https://github.com/bokner/inplace

First Post!

garrison

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

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

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

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

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 :slight_smile:

Where Next?

Popular in Announcing Top

tmbb
I’ve published the first version of my Makeup library. It’s a syntax highlighter for Elixir in the spirit of Pygments, Currently it highl...
New
danschultzer
In short Plug n’ play OAuth 2.0 provider library. Just set up a resource owner schema with Ecto (your user schema), install the dependen...
New
anshuman23
Hello all, I have been working on my proposed project called Tensorflex as part of Google Summer of Code 2018.. Tensorflex can be used f...
New
nikokozak
Hello all, I’ve been working on Svonix - a library for quickly integrating Svelte components into Phoenix views. It’s a much-needed succ...
New
zachdaniel
Ash Framework What is Ash? Ash Framework is a declarative, resource-oriented application development framework for Elixir. A resource can...
New
zoltanszogyenyi
Hey everyone :waving_hand: Excited to join this forum - I am one of the founders and current project maintainers of a popular and open-s...
New
markmark206
simple_feature_flags is a tiny package that lets you turn features on or off based on which environment (e.g. localhost, staging, product...
New

Other popular topics Top

JakeBecker
TL;DR: I’ve just released an implementation of Microsoft’s IDE-independent Language Server Protocol for Elixir. It adds language support ...
1144 55125 245
New
joeerl
Hello again - after a longish gap I’ve decided I really must dig into Elixir and see what’s been happening here - so I have a few questio...
New
dogweather
I wrote this comment on r/haskell, and it’s not popular there. :wink: But I think I’m on to something… Haskell reminds me of Java, and e...
New
sorentwo
Hello! tl;dr Announcing Oban, an Ecto based job processing library with a focus on reliability and historical observability. After spen...
985 44778 311
New
albydarned
Hello all! I am typing this post from my new MacBook Pro with the M1 chip. I’m loving it so far, and will probably use it as my daily dr...
New
sergio
Kind of like when jquery came out, it was super necessary. Existing drag and drop libraries have a bunch of baggage to support old browse...
New

We're in Beta

About us Mission Statement