nbronson / ccstm Goto Github PK

Perhaps we can even unify the implementation using Numeric.

We can use update to let the assignment operator for Refs be ()=. This is not quite as pretty (in my opinion), but it has higher precedence, which prevents parsing problems when the result of a for comprehension is assigned into a Ref. It is also a bit more symmetric with reads.

Lock management code is duplicated between object NonTxn and class NonTxnBound, with slightly different calling conventions. This should be merged.

Can we get something that looks like
atomic {
..
} orElse {
..
} orElse {
..
}
By hook or by crook?

It is not possible to return an instance from the original atomic call, because standalone atomic blocks can yield a useful return type (we don't want to mess up val x = atomic { .. }). When executing the original atomic block we need to know that an alternative is present, so the orElse must be evaluated before the original atomic.

Currently a method implemented with CCSTM that supports transactions has a distinct call signature from one that does not support transactions, because of the implicit Txn parameter. If we add a trait/class Context that is a superclass of Txn, and then provide an implicit Context that indicates the absence of a transaction, we can let a single method be callable from all locations. The method would then need to take responsibility for choosing the correct course of action.

If STM.atomic also took such an argument, then it could perform a dynamic txn lookup (#3) in the NoTxn case, or use subsumption or true nesting if a txn was already available. The result would look something like:

def foo(args)(implicit ctx: Context) = STM.atomic { implicit t: Txn =>
  // body
}

With slightly lower overhead the caller could roll their own subsumption

def foo(args)(implicit ctx: Context) = ctx match {
  case NoTxn => STM.atomic(foo(args)(_))
  case t0: Txn => { implicit val t = t0
    // body
  }
}

Good implementations of TSet and TMap should be chosen and moved from the experimental.impl area into the main src.

We should rename BindingMode to AccessMode, now that we have renamed Ref.Bound to Ref.View. The last question is what Ref.bind(txn) should be called.

TxnFieldUpdater leads to some boilerplate, which should be automated with a compiler plugin that processes a per-field annotation. The resulting fields would get transactional getters and setters, and also a getter that would produce a Ref instance for non-transactional access and more sophisticated operations.

It should be straightforward to provide an @atomic annotation for methods that automatically generates the code described in #10. Such methods would join an existing transaction (possibly in a nested context) or create a new one if none was active.

Currently the unit tests produce a very large number of performance samples. To actually catch performance regressions this should be reduced to a smaller set of metrics that can be stored and charted.

Can we define the extra ops on IntRef using Numeric? The tricky bit is taking advantage of the representation specialization of StripedIntRef.

TArray already uses a Manifest to select the correct initial value for boxed primitive elements in _data; it should go further and switch among multiple TArray implementations. AtomicReferenceArray adds N extra objects, an extra indirection, and some extra dynamic type check. As a bonus, we can get better cache locality by packing primitives into the same AtomicLongArray already used for _meta.

CCSTM threads the current txn statically (through an implicit) for performance. Once it is lost there is no way to recover it, however, even if performance is not critical. We should add and evaluate the use of a ThreadLocal for this.

Based on some initial experiences and some talks, we should revisit the use of unary_! for read barriers. apply() has the advantage that it goes on the right end of the expression, which dramatically simplifies chaining. It also has the advantage that it reads correctly inside conditionals.

The @specialized annotation (in combination with the -Yspecialize option for scalac) has the promise of reducing boxing overheads, especially for reads (txn and non-txn) and non-txn writes. (Txn writes must place something in the write buffer, which requires either a runtime manifest check to use separate code paths, or boxing.) Care must be taken to ensure that the specialization extends all the way from the caller to the innards, otherwise we can actually introduce extra boxing!

The primary complication with specialization is its tricky interaction with subclassing.

To facilitate comparison with other STMs. We should include both directly transformed collection and index structures and transactionally-predicated ones.

To properly support retry/orElse we must implement partial rollback, at least when rolling back with retry. There are several components

• child vs. top-level commit and rollback handlers
• dynamic lookup of the parent txn (see #3)
• capture of the partial read set during partial rollback for retry
• capture or release of locks whose handle is removed from the write buffer during partial rollback

It would also be nice to generate partial rollback on conflict when possible.

maybe this requires sbt to be convenient?

Perhaps hosted on ppl.stanford.edu for the time being?

Currently the best examples are in the test src, but they are not constructed to facilitate learning, they are not gathered together, and there is no supporting documentation. This should be fixed.

related to #24

The main branch should get subsumption immediately, as there is no performance penalty and it is not too hard to do.

Currently, Ref.bind always binds to a transactional context and Ref.nonTxn always binds to a non-transactional context. This makes Ref.nonTxn an escape action if used in a transaction, which is different semantics than a nested atomic block. Since Ref.nonTxn.transform and friends are supposed to be convenience and performance enhancements for tiny transactions, we should provide nested semantics for them as well.

Perhaps we can provide three bindings:

• bind(implicit t: Txn) : bind to a transaction
• escaped : always non-transactional
• direct : dynamically select between bind and escaped using Txn.current

Scala 2.8 now supports the implicit keyword on closure parameters, so Atomic and AtomicFunc are no longer needed for simple atomic blocks. Their only remaining use is for orElse, but it seems that with an implicit conversion from (Txn => Z) to AtomicBlock[Z] we can also handle that.

To accommodate multiple use cases for CCSTM (such as interfacing to a persistent store, or ordered transactions with TLS) we should allow in-object metadata to be any type (inclusing unit or references), without requiring source recompilation. This has several implications:

• MetaHolder must either be eliminated (we could identity hash to get the metadata for TxnFieldUpdater, which would make it less performant but much easier to use), expanded (to include a long and an AnyRef), or must always use boxing
• Concrete Ref instances must be moved into impl, and should no longer be publicly visible. If there are any performance concerns about the use of ClassManifest when constructing Ref[T] where T <: AnyRef, then they must be addressed via additional factory methods in Ref's companion object.
• We should remove the ability to create concrete Txn instances, even for unit tests.

Question to be resolved later: If we have multiple back-ends should we be able to unit test all of them in a single JVM?

Names should be revisited while it is still easy to change them:

• STM.atomic : perhaps atomic? Previously I didn't want to pollute the top-level namespace, but perhaps atomic should be defined in a package object or should be apply() on object atomic? How will this integrate with import ...ccstm.Dynamic._ to get the alternate atomic block syntax?

  Yes: 20ef254 (no tests or doc yet)

• atomicOrElse : perhaps atomic.oneOf?

  Yes: 20ef254 (no tests or doc yet)

• Ref.Bound : perhaps Ref.View? The term bind is overloaded for functional programming. View is used in the collections to capture the concept of a transformation that always refers back to the original instance, which is one way to look at these.

  Yes: 194d654

• Ref.map(f) : perhaps Ref.apply(f)? In the more verbose terminology used elsewhere, it is really getAndMap, but that's pretty ugly. Compare
  val x = Ref(10)
  if (x map { _ > 5 }) ...
  if (x.map({ _ > 5 })) ...
  if (x.map( _ > 5 )) ...
  if (x({ _ > 5 })) ...
  if (x( _ > 5 )) ...
  and the original
  if (x() > 5) ...

  apply(f) is good for the short form, but what should the long form be called? Some possibilities are:

  • view - nice because we are switching to view serializability for this read, but confusing with regard to Ref.View
  • observe
  • applyMap or mapApply
  • getThenMap
  • mappedGet
  • watch
  • getVia
  • getWith - After discussions, this is the obvious choice. This is nice enough that we should not have the 1-arity apply.

  getWith - bc93668

• getAndSet(v) : perhaps swap(v)? getAndSet comes from AtomicInteger, swap from Akka's refs. swap reads more nicely, but doesn't generalize quite as easily.

  Yes: ce93028

• tryWrite(v) : perhaps trySet(v)? There is a lack of parallelism between set and tryWrite.

  Yes: d30fa6e

• readForWrite : perhaps remove from the public interface? transform performs the same optimization internally, if it is absolutely required

  No: Let's leave it, along with the non-standard name.

• weakCompareAndSet and weakCompareAndSetIdentity : remove entirely. Not that useful unless we can guarantee that they will never be obstructed.

  Yes: 4560d71

• transformIfDefined(pf: PartialFunction[T,T]) : should this return Option[T] instead of Boolean (acting like getAndTransformIfDefined)?

  No: That would be confusing semantics.

From user:

one thing i notice is that although "prepare" is called on the WriteResource, neither "processCommit" nor "processRollback" are... as a work-around i use "afterCommit" and "afterRollback" on the txn now, but i guess the missing invokations on WriteResource are a bug?

The scaladoc should be updated to reflect the possibility of nested atomic blocks, and of the dynamically-resolved single binding mode. The current dichotomy between txn and non-txn contexts does not reflect the actual hybrid between the static and dynamic binding. doc/contexts.md should be completed and expanded.

The modular blocking operator (and the non-transactional single-Ref equivalent) would be more useful if they also provided a timeout. Since the underlying implementation uses Object.wait(), this should be possible.

The only method signatures that Ref and Ref.View have in common are those inherited from AnyRef. This implies that if we are careful in our definition of equals we can use the same instance for both the reference and the single-operation view! This would avoid any object creation overhead for the use of .single.

Direct use of the concrete instances such as TIntRef would no longer be convenient, because an ambiguity would be created. When typecast to either a Ref[Int] or Ref.View[Int], however, things would work fine.

Is this clever or evil?

Currently, the bodies are Txn => Unit. This allows a single body to be reused for multiple transactions, but seems to be making code that uses lifecycle callbacks more bulky than necessary. We should change this to Unit => Unit, hopefully in a backward-compatible fashion.

TxnLocal should get some of the methods from Ref:

• the access shortcuts apply() and update(v)
• read+write forms swap, transform, transformIfDefined, +=, -=, and *=

I think compareAndSet (and other Ref methods whose success or failure is determined by concurrent accesses) would be misleading, because TxnLocal instances are isolated.

Also, overriding initialValue should perhaps be replaced with a by-name parameter to a factory method. This is more Scala-ish, but makes it more difficult to get access to the current Txn context.