Java Concurrency in Practice - Summary - Part 10

This is part 10 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 15 - Atomic Variables and non-blocking synchronization

1. Non-blocking algorithms use low-level atomic machine instructions like compare and swap (CAS) instead of locks to ensure data integrity under concurrent access.  An algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread.  An algorithm is called lock-free if some thread can make progress at each step.
2. Locking has many disadvantages.  For small operations like incrementing a counter, the overhead imposed by locking is just too much.
3. Almost every modern processor supports atomic Compare and Swap (CAS) instructions.  CAS atomically updates a memory location to a new value if the old value matches what we expect.  Otherwise it does nothing.  In either case, it returns the original value of the memory location.
1. CAS: "I think V should have the value A.  If it does put B there, otherwise don't change it but tell me I was wrong."
2. CAS is an optimistic technique - proceeds with update and detects collisions.
3. A thread that loses in CAS is not suspended.  It can choose to retry,  do some other recovery action or do nothing.
4. Primary disadvantage of CAS is that the caller must deal with contention.  Locking automatically deals with contention by blocking.
5. Rule of thumb : cost of uncontended lock acquisition and release is twice the cost of a CAS on a multi-processor system.
4. Atomic Variables
1. AtomicInteger, AtomicLong, AtomicBoolean, AtomicReference
2. Elements in the atomic array classes (available in Integer, Long and Reference versions) can be updated atomically.  
3. Not good candidates for keys in hash based collections since they are mutable.
4. At low to moderate contention, Atomic variables provide better scalability.  At high contention, locks are better.
5. Refer the book for non-blocking stack and linked list code listing.
6. Atomic field updaters can be used to update existing volatile variables atomically.  Only to be used when there is a performance problem associated with creating multiple new Atomic* variables (like for each node of a linked list).
7. ABA problem - During an update, the value of a reference field can change from A to B and back to A.  In this case, we do not want the update to proceed.  But in regular CAS, it will.  This problem usually happens when we manage our own object pools.  One option to avoid this problem is to use versioned references with AtomicMarkedReference and AtomicStampedReference.

Chapter 16 - The Java Memory Model

1. A memory model is required because compilers can reorder instructions, store variables in caches instead of memory, etc.  Hence the result of assigning a value to a variable may not be immediately visible to another thread.  The Java Memory Model (JMM) specifies the minimal guarantees the JVM must make about when writes to variables become visible to other threads.
2. The JMM shields application developers from differences in memory models across different processor architectures.
3. Within a single thread, the JVM must maintain serial semantics.
4. Actions - reads/writes to variables, locks/unlocks, starting/joining threads.
5. The JMM defines a partial ordering called happens-before between actions:
1. Program rule order - Each action in a thread happens-before every subsequent action in that thread.
2. Monitor lock rule - An unlock on a monitor happens-before every subsequent lock on the same monitor lock.
3. Volatile variable rule - A write to a volatile variable happens-before every subsequent read of that same variable.
4. Thread start rule - A call to Thread.start happens-before every action in the started thread.
5. Thread termination rule - Any action in a thread happens-before any other thread detects that it has terminated (either by successfully returning from Thread.join or by Thread.isAlive() returning false).
6. Interruption rule - A thread calling interrupt() on another thread happens-before the interrupted thread detecting the interrupt.
7. Finalizer rule - The end of an object's constructor happens-before the start of its finalizer.
8. Transitivity - A happens-before B and B happens-before C implies A happens-before C.
9. Placing an item in a thread-safe collection happens-before another thread retrieves that item.*
10. Counting down on a CountdDownLatch happens-before a thread returns from await().
11. Releasing a permit to a Semaphore happens-before acquiring a permit from the same Semaphore.
12. A FutureTasks computation happens-before another thread successfully returns from Future.get().
13. Submitting a Runnable/Callable to an Executor happens-before the task begins execution.
14. A thread arriving at a CycleBarrier or Exchanger happens-before the barrier action, which happens-before threads are released from the barrier.
6. Piggybacking - advanced technique that uses an existing happens-before ordering to ensure visibility of an object X, rather than creating an happens-before relationship for publishing X.  Do not use unless absolutely necessary for performance.
7. Static initialization provides safe publication as static initializers are run by the JVM at class initialization time.  You can use static initialization lazily by using a private static holder class.
8. Double-checked locking - incorrect technique to avoid synchronization during lazy initialization.  First check if resource is non null without holding lock.  If non-null, just use it. If null, synchronize and initialize it.  The problem is that using the resource without any happens-before relationship can expose it in a partially constructed state.

Java Concurrency in Practice - Summary - Part 9

This is part 9 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it.

Chapter 13 - Explicit Locks

1. Unlike intrinsic locking, the Lock interface offers unconditional, polled, timed, and interruptible lock acquisition.
2. Lock implementations provide the same memory visibility guarantees as intrinsic locking.  They can vary in locking semantics, scheduling algorithms, ordering guarantees and performance.
3. ReentrantLock has same semantics as a synchronized block.
4. Why use explicit locks over intrinsic locks?
1. Unlike intrinsic locking, a thread waiting to acquire a ReentrantLock can be interrupted. 
2. ReentrantLock also supports timed lock acquisition.  
3. WIth intrinsic locks, a deadlock is fatal.
4. Intrinsic locks must be released in the same code block they are acquired in.  This makes non-blocking designs impossible.
5. ReentrantLock is much faster than intrinsic locking in Java 5.0
5. Lock objects are usually released in a finally block, to make sure that it is released if an exception is thrown.
6. lockInterruptibly() helps us build cancelable tasks.
7. tryLock() returns false if the lock cannot be acquired.  Timed tryLock() is also responsive to interruption.
8. ReentrantLock offers two fairness options
1. Fair - threads acquire locks in order of requesting.
2. Non-fair (default) - thread can acquire lock if it is available at the time of the lock request, even if earlier threads are waiting.  Non-fair locking is useful because it avoids the overhead of suspending/resuming a thread if the lock is available at time of the lock request.  
3. Fairness is usually not needed, and has a very high performance penalty (multiple orders of magnitude).
4. Fair locks work best when they are held for a relatively long time or when the mean time between lock requests is large.
9. When to use intrinsic locks?
1. synchronized blocks have a more concise syntax.  You can never forget to unlock a synchronized block.
2. Use ReentrantLock only when advanced features like timed, polled, interruptible lock acquisition, fairness or non-block structured locking are needed.
3. Harder to debug deadlock problems when using ReentrantLock because lock acquisition is not tied to a particular stack frame, and thus the stack dump is not very helpful.
4. synchronized is likely to have more performance improvements in the future (eg: lock coarsening) as it is part of the Java language spec.
10. Read-Write Lock - protected resource can be accessed by multiple readers or one writer at the same time.
1. offers readLock() and writeLock() methods which return a Lock object that must be acquired before doing the respective operations.
2.  More complex implementation.  Hence has lower performance except in read-heavy workloads.
11. Lock can only be released by thread that acquired it.

Chapter 14 - Building Custom Synchronizers

1. State-dependent classes - blocking operations can proceed only if state-precondition becomes true (for example, you cannot retrieve result of FutureTask if computation has not yet finished).
2. Try to use existing state-dependent classes whenever possible. 
3. Condition queue - allows a group of threads (called wait set) to wait for a specific condition to become true.
4. Intrinsic condition queues - Any java object can act as a condition queue via the Object.wait(), notify() and notifyAll() functions.
1. Must hold intrinsic lock on an object before you can call wait(), notify() or notifyAll().   
2. Calling Object.wait() atomically releases lock and suspends the current thread.  It reacquires the lock upon waking up, just before returning from the wait() function call.   wait() blocks till thread is awakened by a notification, a specified timeout expires or the thread is interrupted.
3. In order to use condition queues, we must first identify and document the pre-condition that makes an operation state-dependent.  The state variables involved in the condition must be protected by the same lock object as the one we wait() on.
4. A single intrinsic condition queue can be used with more than one condition predicate.  This means that when a thread is awakened by a notifyAll, the condition it was waiting on need not be true.  wait() can even return spuriously without any notify().  The condition can also become false by the time wait() reacquires the lock after waking up.  Hence when waking up from wait(), the condition predicate must be tested again and we must go back to waiting if it is false.  Hence, call wait() in a loop: synchronized(lockObj) { while(!conditionPredicate()) { lock.wait();} // object is in desired state now
5. Notifications are not sticky - i.e. a thread won't know about notifications that occurred before it called wait().
6. In order to call notify() or notifyAll() on an object, you must hold the intrinsic lock on that object.  Unlike wait(), the lock is not automatically released.  The lock must be manually released soon as none of the woken up threads can make progress without acquiring the lock.
7. Use notifyAll() instead of notify().  If multiple threads are waiting on the same condition  queue for different condition predicates, calling notify() instead of notifyAll() can lead to missed signals, as only the wrong thread may be woken up.
1. However using notifyAll() can be very inefficient, as multiple threads are woken up and contend for the lock where only one of them can usually make progress.
2. notify() can be used only if 
1. The same condition predicate is associated with the condition queue and each thread executes the same logic on returning from wait().
2. A notification on the condition queue enables at most one thread to proceed.
8. A bounded buffer implementation needs to call notify only when moving away from the empty state or full states.  Such conditional notifications are efficient, but makes the code hard to get right.  Hence, avoid unless necessary as an optimization.
9. A state dependent class should either fully document its waiting/notification protocols to sub-classes or prevent sub-classes from participating in them at all.
10. Encapsulate condition queue objects in order to avoid external code from incorrectly calling wait() or notify() on them.  This often implies the usage of a private lock object instead of using the main object itself.
11. Explicit Condition objects - Condition 
1. Each intrinsic lock can have only one associated condition queue.  Hence multiple threads may wait on same condition queue for different condition predicates.
2. A Condition is associated with a single Lock object.   A Condition is created by calling Lock.newCondition().  You can create multiple Condition objects per Lock.
3. Equivalents of wait(), notify() and notifyAll() for Condition are await(), signal() and signalAll().  Since Condition is an Object, wait() and notify() are also available. Do not confuse them.
4. Explicit Condition objects make it easier to use signal() instead of signalAll().
12. Synchronizers
1. Both Semaphore and ReentrantLock extend AbstractQueuedSynchronzer (AQS) class.
2. AQS is a framework for building locks and synchronizers.
3. When using AQS, there is only one point of contention.
4. Acquisition - state dependent operation that can block.
5. Release - allows some threads blocked in acquire to proceed.  Not-blocking
13. AQS manages a single integer of state for the synchronizer class. It can be accessed with getState(), setState() and compareAndSetState() methods.  The integer can represent arbitrary semantics.  For example, FutureTask uses it to represent the state (running, completed, canceled) of the task.  Semaphore uses it to track the number of permits remaining.
1. Synchronizers track additional state variables themselves.
2. Synchronizers override tryAcquire, tryRelease, isHeldExclusively, tryAcquireShared and tryReleaseShared.  The acquire, release, etc methods of AQS call the appropriate try methods,

Java Concurrency in Practice - Summary - Part 8

This is part 8 of  my notes from reading Java Concurrency in Practice.

NOTE: These summaries are NOT meant to replace the book.  I highly recommend buying your own copy of the book if you haven't already read it. 

Chapter 11 - Performance and Scalability

1. Avoid premature optimization - first make it right, then make it fast, if not fast enough already (as indicated by actual performance measurements)
2. Tuning for scalability is often different from tuning for performance, and are often contradictory.
3. Amdahl's Law : Speedup <= 1/( F + (1-F)/N) where F is the fraction of computation that must be executed serially, and N is the number of processors.
4. A shared work queue adds some (often overlooked) serial processing.  Result handling is another form of serialization hidden inside otherwise seemingly 100% concurrent programs.
5. Costs of using threads
1. context switches - managing shared data structures in OS and JVM take memory and CPU. Can also cause flurry of processor cache misses on a thread context switch.
2. When a thread blocks on a lock, it is switched out by JVM before reaching its full scheduled CPU quantum, leading to more overhead.
6. Context switching costs 5000-10000 clock cycles (few microseconds).  Use vmstat to find % of time program spent in the kernel. High % can indicate high context switching.
7. synchronized and volatile result in the use of special CPU instructions called memory barriers that involve flushing/invalidating CPU caches, stalling execution pipelines, flushing hardware write buffers, and inhibit compiler optimizations as operations cannot be reordered.
8. Performance of contended and uncontended synchronization are very different.  synchronized is optimized for the uncontended scenario (20 to 250 clock cycles).  volatile is always uncontended. 
9. Modern JVMs can optimize away locking code that can be proven to never contend.
10. Modern JVMs perform escape analysis to identify thread-confined objects and avoid locking them.
11. Modern JVMs can do lock coarsening to merge multiple adjacent locks into a larger lock to avoid multiple lock/unlocks.
12. Synchronization by one thread affects performance of other threads due to traffic on the shared memory bus.
13. Uncontended synchronization can be handled entirely in JVM.  Contended synchronization involves OS activity - OS needs to suspend the thread that loses the contention.  
14. Blocking can implemented by spin-waiting or by suspending the thread via the OS.  spin-waiting is preferred for short waits.  JVM decides what to use based on profiling past performance.
15. Reducing lock contention
1. reduce duration for which locks are held.
2. reduce frequency at which locks are requested. Coarsen lock granularity by lock splitting (for moderately contended locks) and lock striping (for heavily contended locks).
3. replace exclusive locks with coordination mechanisms that permit greater concurrency.
16. Lock striping - ConcurrentHashMap uses 16 locks - bucket N is guarded by lock N % 16.  Locking for exclusive access to entire collection is hard when lock striping is used.
17. Avoid hot fields like cached values - for eg: size is cached for a Map, in order to convert an O(n) operation to a O(1) operation.  Use striped counters or atomic variables.
18. Alternatives to exclusive locks - concurrent collections, read-write locks, immutable objects, atomic variables.
19. Do not use object pools.  Object allocation and GC were slow in earlier versions of Java.  Now object allocation is faster than a C malloc - only 10 machine instructions.  Object pools also introduce synchronization overheads

Chapter 12 - Testing Concurrent Programs

1. Every test must wait till all the threads created by it terminate.  It should then report any failures in tearDown().
2. Testing blocking operations need some way to unblock a thread that has blocked as expected.  This is usually done by doing the blocking operation in a new thread and interrupting it after waiting for some time.  An InterruptedException is thrown if the operation blocked as expected.
3. Thread.getState() should not be used for concurrency control or testing.  Useful only for debugging.
4. One approach to test producer-consumer programs is to check that everything that is put into a queue or buffer eventually comes out of it, and nothing else does.  
1. For single producer-single consumer designs, use order sensitive checksum of elements that are added, and verify them when the element is removed.  Do not use a synchronized shadow list to track the elements as that will introduce artificial serialization.
2. For multiple producer-consumer designs, use an order insensitive checksum that can be combined at the end of the test to verify that all enqueued elements have been dequeued.
1. Make sure that the checksums are not guessable by the compiler (for eg: consecutive integers), so that they are not precomputed.  Use a simple random number generator like  xorShift(int y) { y ^= (y << 6); y ^= (y >>> 21); y ^= (y << 7); return y;}
5. Test on multi-processor machines with fewer processors than active threads.
6. Generate more thread interleaving by using Thread.yield() to encourage more context switches during operations that access shared state.  
7. Always include some basic functionality testing when doing performance testing to make sure that you are not measuring performance of broken code.
8. Non-fair semaphores provide better throughput, while fair semaphores provide lower variance in responsiveness.
9. Avoiding performance testing pitfalls
1. Ensure that garbage collection does not run at all during your test (check this using the -verbose:gc flag) OR ensure that garbage collection runs a number of times during the test (need to run test for a long time).
2. Your tests should run only after all code has been compiled; no point measuring performance of interpreted byte code.  Dynamic compilation takes CPU resources.  Compiled code executes much faster.
1. Code may be decompiled/recompiled multiple times during execution - for eg: if some previous assumption made by JVM is invalidated, or to compile with better optimization flags based on recently gathered performance statistics.
2. Run program long enough (several minutes) so that compilation and interpreted execution represent a small fraction of the results and do not bias it.
3. Or have an unmeasured warm-up run before starting to collect performance statistics.
4. Run JVM with -XX:+PrintCompilation so that we know when dynamic compilation happens.
3. When running multiple unrelated computationally intensive tests in a single JVM, place explicit pauses between tests in order to give the JVM a chance to catch up with its background tasks.  Don't do this when measuring multiple related activities, since omitting CPU required by background tasks gives unrealistic results.
4. In order to obtain realistic results, concurrent performance tests should approximate the thread-local computation done by a typical application.  Otherwise, there will be unrealistic contention.
5. Make sure that compilers do not optimize away benchmarking code.  
1. Trick to make sure that benchmarking calculation is not optimized away:  if (fox.hashCode() == System.nanoTime()) System.out.print(" ");
10. Complementary Testing Approaches
1. Code Review
2. Static analysis tools: FindBugs has detectors for:
1. Inconsistent synchronization.
2. Invoking Thread.run (Thread.start() is what is usually invoked, not Thread.run())
3. Unreleased lock
4. Empty synchronized block
5. Double-checked locking
6. Starting a thread from a constructor
7. Notification errors
8. Condition wait errors: Object.wait() or Condition.await() should be called in a loop with the appropriate lock held after testing some state predicate.
9. Misuse of Lock and Condition
10. Sleeping or waiting while holding a lock.
11. Spin loops