Crystal: Array of Atomic unusable.

[didactic-drunk]

Is there a way to have a working Array of Atomic? Especially multidimensional? StaticArray won't do.

Code:

ary = [Atomic(Int16).new(0)]

ary.each do |a|
        a.add 1
end

p ary

Output:

Atomic(Int16)(@value=0)]

[jhass]

Ah well, the old it's a struct thus copy on value issue. It works if you reset the value into the array: https://carc.in/#/r/8w7a

ary = [Atomic(Int16).new(0)]

ary.each_with_index do |a, i|
  a.add 1
  ary[i] = a
end

p ary

But of course that operation is no longer atomic.

[oprypin]

@jhass Please write code samples directly into the post, for convenience and reliability. carc.in should be only supplementary.

[asterite]

Atomic is not meant to be used inside containers, or anything else. You can just assign them to vars, instance vars or class vars.

[didactic-drunk]

I need a dynamic amount. I guess I'll use a linked list or skip list variant.

[bcardiff]

Using Pointer to malloc a dynamic amount and Atomic::Ops (which is :nodoc:) can help you in this scenario.

I would like to suggest you to use Slice, but you will stumble on the same problem since Slice#[] will return a copy due to Pointer#[] implementation.

[didactic-drunk]

@bcardiff All Ops require a pointer as a first argument. Could this be refactored in to Pointer::Atomic for more general use? Atomic(T) would remain the preferred method.

[bararchy]

So, I was hit by this as well.

a = Hash(String, Atomic(Int32)).new
a["Bar"] = Atomic(Int32).new(0)

a["Bar"].add(5)
a["Bar"].get # => 0

I guess it would be nice to get some kind of a warning in the docs of Atomic to not use it inside a container.

[asterite]

Maybe you could all explain what you are trying to do with those dynamic atomics.

[jhass]

Yes, reassigning the hash value with the updated atomic makes it completely loose its point.

```

Assuming atomics initialized to 1

foo = hash["foo"]
foo = hash["foo"]

Each thread has a copy of the value now

foo.add(5)
foo.add(2)

Each thread atomically updated its local copy of the value now.

Given it's a local variable this could never have conflicted in the first place.

hash["foo"] = foo
hash["foo"] = foo

Either thread could get to updating hash["foo"] first.

Which value ends up being stored in the hash is nondeterministic.

Of course in addition to the usual out of order problems where either thread

could update the value before the other fetches it.

So the possible results now are 3 (1 + 2), 6 (1 + 5) and 8 (6 + 2, 3 + 5).

[didactic-drunk]

Implement lock free data structures.

[jhass]

I think the question was geared towards some real world example/code. I'm sure I can implement some random "lock free data structure" without a variable amount of atomics :)

[bcardiff]

The easiest workaround @bararchy is to use boxed atomics. So the atomic operations will be applied on the same memory locations.

a = Hash(String, Box(Atomic(Int32))).new
a["Bar"] = Box.new(Atomic(Int32).new(0))

a["Bar"].object.add(5)
a["Bar"].object.get # => 5

There might be a need to lock the whole hash depending on the kind of updates you want to do.

[didactic-drunk]

@jhass I read variants of this algorithm in 2 different code bases but didn't retain links. If the algorithm has a name I don't know it.

Pseudo code:

class LockFreeArray(T)
  # macro needed for Reference/Value/Union types.
  @slots = Array(Atomic(Array(T)).new 32

  def []=(idx, val)
    slot, slot_idx = slot_for(idx)
    slot[slot_idx].set val
    val
  end

  private def slot_for(idx)
    slot_no = Math.log2(idx)
    # retrying CAS loop to get or set @slots[slot_no]
    { slot, slot_idx }
  end
end

[didactic-drunk]

@jhass I'm also experimenting with lock free queues/stacks/skip lists. All are textbook implementations.