Using anonymous Functions to avoid type dispatch

General Usage Performance
, ,
1

This question is about the merits of a methods of avoiding type dispatch in some low-level functions. I’ve included the context below; though the question itself can probably be understood and answered without the context.

Context

This is all part of a project I’m currently calling Air that has a goal of bringing Clojure’s philosophy of “fearless concurrency” to Julia. As part of this, I’m writing a multi-threaded transaction system that supports a type Volatile{T} which is essentially a Ref{T} that coordinates updates across threads using syncronized transaction blocks. In short, volatiles are refs except that they:

  1. throw an exception if one attempts to call setindex! on them unless the call was from within a transaction block
  2. are updated atomically with all other changes to Volatile refs when they are changed within a single transaction.

A simple example of how this works:

const vol1 = Volatile{Symbol}(:startval1)
# ==> Volatile{Symbol}(@0x2551dcc819b0060a: :startval1)
const vol2 = Volatile{Symbol}(:startval2)
# ==> Volatile{Symbol}(@0x96db24c5c70b3672: :startval2)

vol1[] = :newval
# ==> ERROR: cannot update volatile outside of a transaction

(vol1[], vol2[])
# ==> (:startval1, :startval2)

tx() do # Start of transaction block
    vol1[] = Symbol("next_" * String(vol1[]))
    vol2[] = Symbol("next_" * String(vol2[]))
end # End of transaction block

(vol1[], vol2[])
# ==> (:next_startval1, :next_startval2)

Critically, the updates to and reads from vol1 and vol2 in the tx transaction block above are guaranteed to be atomic—i.e., no matter how many threads are running this same transaction simultaneously, none of them will ever read a state in which vol1 has been updated to have a different number of next_ prefixes than vol2.

In order to accomplish this, the tx() function, which manages the transaction in the example above, needs to keep track of all the Volatile objects that are read during the transaction as well as all the changes made to Volatiles. At the end of the transaction, it locks all of these (in an ordering that prevents deadlocks) and checks to see if they have changed since the transaction started. If so, it aborts and starts over, and if not, it commits all the changes while they are locked then unlocks them (transaction successful). The tx() block can keep track of all the read/updated volatile objects because whenever a call gets made to, e.g., Base.getindex(v::Volatile{T}), the volatile adds itself to a task-local array called touched_vols.

The problem

The problem arises from the fact that the transaction block needs to have a minimal overhead, but the Volatile objects that it keeps track of can in fact have infinite different types, leading to a type unstable code. At the end of the transaction, when the objects are locked, validated, and committed, this all ends up in a set of loops that look like this:

# touched_vols is a vector of Volatile objects, each of which is
# a Volatile{T} object for some type T.
touched_vols::Vector{Volatile}
# Lock the volatiles first:
for vol in touched_vols
    lock(vol)
end
try
    # Validate them (or retry if they have changed)
    for vol in touched_vols
        validate(vol) || throw(TxRetryException())
    end
    # None have changed, so commit the changes.
    for vol in touched_vols
        commit(vol)
    end
finally
    # Always unlock them all when finished.
    for vol in touched_vols
        unlock(vol)
    end
end

Each of the above loops is type unstable because those Volatile objects will have different type parameters.

One way that occurred to me to reduce this instability is to have the getindex function put functions rather than objects in the touched_vols array. This way, touched_vols has a type that is something like Vector{Tuple{Function, Function, Function}} where instead of vol = touched_vols[k] we have (vol_k_lock_fn, vol_k_validate_fn, vol_k_commit_fn) = touched_vols[k]. These functions can each get run in the loops without the loops having any type instability whatsoever. And the getindex function just needs to replace the line push!(touched_vols, vol) with push!(touched_vols, (() -> lock(vol), () -> validate(vol), () -> commit(vol)). Since the exact type of the vol is known at the time of the getindex call, this should, as I understand it, avoid all type instability.

That said, I’m not sure whether calling an anonymous Function itself counts as a type-unstable action? Since all of these are different precise function objects, will I incur a penalty calling them? Presumably, when the compiler can’t know precisely what function I’m calling, there must be some penalty in that the function can’t be inlined and there will need be something like a virtual lookup performed. Is this a substantial cost? (Note: In some trivial tests using @btime, this doesn’t seem to be a major cost.) Are there other other costs I’m not considering, such as a penalty for the compiler to compile these anonymous functions? My intuition is that these should get compiled essentially when the getindex methods get compiled, but I also don’t think that benchmarks typically count compile time, so this is hard to measure. Are there other pitfalls to this method and/or other mechanisms in Julia that are meant to deal with this kind of situation?

Thanks in advance.