Equivalence lock in Scala/Java?

Question

Is there anyway to lock on the object equality instead of referential equality in Scala/Java e.g.

def run[A](id: A) = id.synchronized {
  println(s"Processing $id")
  Thread.sleep(5000)
  println(s"Done processing $id")
}

Seq(1, 1, 2, 3, 1).par.foreach(run)

I want this to print something like:

Processing 3
Processing 1
Processing 2
// 5 seconds later
Done processing 1
Done processing 2
Done processing 3
Processing 1
// 5 seconds later
Done processing 1
Processing 1
// 5 seconds later
Done processing 1

http://stackoverflow.com/a/5640671/2158288 – ZhongYu Nov 04 '15 at 00:09 — ZhongYu, Nov 04 '15 at 00:09

pathikrit · Accepted Answer · 2015-11-03T22:35:01.037

2

The best I could come up with is something like this:

import scala.collection.mutable

class EquivalenceLock[A] {
  private[this] val keys = mutable.Map.empty[A, AnyRef]

  def apply[B](key: A)(f: => B): B = {
    val lock = keys.synchronized(keys.getOrElseUpdate(key, new Object()))
    lock.synchronized(f)
  }
}

Then use it as:

def run[A](id: A)(implicit lock: EquivalenceLock[A]) = lock(id) {
  println(s"Processing $id")
  Thread.sleep(5000)
  println(s"Done processing $id")
}

EDIT: Using the lock striping mentioned in the comments, here is a naive implementation:

/**
  * An util that provides synchronization using value equality rather than referential equality
  * It is guaranteed that if two objects are value-equal, their corresponding blocks are invoked mutually exclusively.
  * But the converse may not be true i.e. if two objects are not value-equal, they may be invoked exclusively too
  *
  * @param n There is a 1/(2^n) probability that two invocations that could be invoked concurrently is not invoked concurrently
  *
  * Example usage:
  *   private[this] val lock = new EquivalenceLock()
  *   def run(person: Person) = lock(person) { .... }
  */
class EquivalenceLock(n: Int) {
  val size = 1<<n
  private[this] val locks = IndexedSeq.fill(size)(new Object())

  def apply[A](lock: Any) = locks(lock.hashCode().abs & (size - 1)).synchronized[A] _   // synchronize on the (lock.hashCode % locks.length)th object
}

object EquivalenceLock {
  val defaultInstance = new EquivalenceLock(10)
}

Guava's Striped is best suited if you don't want to reinvent the wheel here.

edited Nov 03 '15 at 22:35

answered Nov 03 '15 at 19:22

pathikrit

32,469
37
142
221

WeakReferences are compared by identity, so how is that different than synchronized? `ConcurrentHashMap.compute` or striping on an array of locks would be the easiest. – Ben Manes Nov 03 '15 at 20:30
@BenManes: You are right. I should use a regular `Map`. Updated my answer. But, it would create a memory leak as it would store all the invoked ids. I guess what I need here is a map with a TTL. – pathikrit Nov 03 '15 at 20:32
1

Its probably better to let some collisions occur instead of TTL races. So lock striping (e.g. Guava's `Striped`) is probably as fast and less error prone. – Ben Manes Nov 03 '15 at 20:35
@BenManes: I see. So what you are saying is - to save memory, let's not use a map or rely on TTLs but have an array of lock objects in hand. Use the provided key to index into that array to grab a locking object. If collisions do occur, worst case two invocations that could have been invoked concurrently is not invoked concurrently. – pathikrit Nov 03 '15 at 20:47
That would be my preference. The less attractive alternative is a mapping of the key to weak locks (weak value cache) so that the entry is GC'd due to no strong reference (no in-flight operation). That fix of your original idea maximizes concurrency, but puts burden on the GC. In comparison to hashing its probably a poor trade-off in most cases. – Ben Manes Nov 03 '15 at 23:41
with weak reference, the JMM semantics is quite hard to analyze (though I believe it should work in practice) – ZhongYu Nov 04 '15 at 00:12
I don't understand how striped lock can be recommended without knowing the use case. It's got to be a wrong solution for many cases. – ZhongYu Nov 04 '15 at 00:15

Equivalence lock in Scala/Java?

1 Answers1

Linked