sanjoy_das

> It is interesting to me that right now this is sitting on the HN homepage directly adjacent to: "Tesla to recall vehicles that may disobey stop signs (reuters.com)"

Based on https://www.forbes.com/sites/bradtempleton/2022/01/13/a-robo... Tesla's FSD has other issues as well.

Another data point: I tend to receive far more recruiter cold calls in an old email address that I no longer use than in my newer more active email address.

Similar: tfcompile AOT compiles TensorFlow models into native code using XLA (https://www.tensorflow.org/xla/tfcompile).

That's an especially interesting possibility since LLVM now has IR support for C++ coroutines.

> Recursion and memoization is easy but dynamic programming doesn't really feel as natural. Ways to get better? Just do more?

Once you have the recursive solution, the DP solution should be fairly easy. Draw out the recursion tree for an example (or do it more generally), convert it to a DAG by combining redundant nodes, and then do a topological sort. That topological sort is the order in which you need to solve the subproblems to get a DP solution.

I can never understand this attitude. Programmers are people -- why is it surprising that some of them are ethically flexible?

My guess is that they meant "up" in the sense of "up in post dominator tree".

> How did the other thread get the reference to the object? The only possible existing reference is the one we are using to decrement the shared counter.

I don't think this affects the point you're trying to make, but I suppose you could have three threads, where the logical operations are:

    ThreadA:
      obj = x->field_a;
    
    ThreadB:
      x->field_a = null;
    
    ThreadC:
      x->field_b = null;

with both field_a and field_b pointing to the same object initially. It does not affect your point, since ThreadA and ThreadB are now racing.

> Decrementing is done when the reference itself is being dropped (set to null or to point to a different object), which is a logically mutating operation (remember that only the reference count updates are atomic, the operations on the references themselves are not), thus no other acquire operation can be happening concurrently or it would be a data race.

It depends on your programming language. In Java racing on field updates (at the Java level) is well defined (but is allowed to return counter-intuitive results to some degree). That is:

    ThreadA
      int k = obj.field.hashCode()

    ThreadB
      obj.field = someOtherValue

is defined and is not allowed to have arbitrarily bad effects like crashing the VM. This is different from C++ (where these kind of accesses are UB, as you seem to imply). Generally, I think for high level languages it is better to have Java-like semantics where even racy accesses have some guarantees.

For C++, I can get the same Java-like guarantees by using `memory_order_relaxed` loads, but I suppose it is defensible for an atomic `shared_ptr` to have a complex refcounting protocol even for `memory_order_relaxed` loads and stores.

> Any concurrent operations on the reference itself must be synchronized via external means, usually a mutex.

Not sure how you're using a reference here, but if by "reference" you mean "a location in the heap" then that does not apply for Java. I personally tend to use "reference" in the same way as "pointer".

> Of course concurrently mutating distinct references which refer to the same object/ref count is fine. edit: rewording

edit: formatting

In (other) words, the situation is that you've just decremented the reference count of an object, because you've nulled out the only location in the heap that reached it. The reference count becomes zero after decrementing, so you know that _now_ there are no slots in the heap that point to it; but how do you know that there isn't a thread that fetched the object out of the heap before you started, and got stalled before it could increment the reference count and has been stalled since then?

(I'll try to edit the post to make this clearer ^).

I'd also like to stress that there are many ways around the problem, the only point of the post is that you'll have to solve some non-obvious problems if you try to generalize reference counting to a heap shared across threads.

Yup. The "obvious" downside to that is that you'll burn CPU cycles and memory by generating and keeping around a slow-but-correct compile for every function.

Is this what you're looking for: http://www.playingwithpointers.com/check-widening-in-llvm.ht... ?

Yes they're definitely close, but I don't know if there are subtle differences in semantics between what we have in LLVM and what Swift needs (since I'm not familiar with Swift).

Interesting observation -- just because I've checked `%i` is within array bounds, doesn't mean `a[%i]` is safe to access, since `%i` could be `undef` and pass the range check spuriously.

From the thesis the post linked to:

``` Although limbo lists are accessed using lock-free operations, and garbage collection does not interfere with other mutator processes, this reclamation scheme is not strictly lock-free. For example, a process which stalls for any reason during a shared-memory operation will not observe updates to the epoch count. In this situation the limbo lists will never be reclaimed and memory cannot be reused. Other processes can make progress only until the application reaches its memory limit. This drawback may also affect preemptively-scheduled systems, in which a process may be descheduled in the middle of a shared-memory operation with no guarantee when it will be rescheduled. ```

With ARC sharing objects across threads becomes trickier. First of all, in the general case you'll have to do atomic increments and decrements which tend to be fairly expensive, and they'll be sitting right in the middle your core application logic. Secondly, if you're sharing objects amongst threads, you cannot simply do:

  Thread1:
  Obj = Heap->field;
  Heap->field = null;
  // reduced a reference so:
  if (AtomicDecrement(Obj->refcount) == 0) {
    free(Obj);
  }

Since you'll be racing with

  Thread2:
  Obj = Heap->field;
  // stalls, and Thread1 deletes Obj
  AtomicIncrement(Obj->refcount)

The only satisfactory solution to this that I'm aware of is to use hazard pointers, and that is a fairly complex bit of logic. Maybe there's a better solution to this, but I've not come across one.

Another interesting data point is libFirm: http://pp.ipd.kit.edu/firm/ which regalloc's directly over SSA.