Lecture Notes for Concurrent Programming

7 July 2003 - Immutable Class Instances

Immutable Class Instances

• Immutability

• Immutable Classes

  • Final Fields

  • Construction

• Functional Programming

  • Mutating Immutable Data

Synchronization

• Synchronization is necessary.

  • It prevents incorrect execution sequences.

• Synchronization is expensive.

  • It cuts down on concurrency, and uses high-overhead mechanisms.

• Synchronization is difficult.

  • It's difficult to establish, and difficult to maintain.

• Synchronization: can't live with it, can't live without it.

  • Or can we?

• We need to avoid undesirable modifications to shared resources.

  • Avoid modifications.

  • Avoid shared resources.

Immutability

• Class instances that don't change can't cause interference.

  • No write conflicts, no time-dependent behavior.

  • No need for expensive and difficult synchronization.

• Class instances without state can't change.

  • There's nothing to change.

  • Not as dumb as it sounds (procedural objects, functional programming).

• Class instances with unchanging state can't change (duh).

  • Providing unchanging state can be tricky.

    • Optimization pressures; initialization problems.

• Immutable class instances also promote sharing.

  • Large, read-only data structures.

  • Boss-worker image processing algorithms.

Immutable Classes

• Java has a lot of immutable classes.

  • awt.Color, math.BigDecimal, lang.String.

• Immutable class instances have (surprise!) no mutating methods.

  • Except for initialization, not even hidden mutations are allowed.

  • But getting initialization right can be tricky.

• Roll-you-own enumerations are the canonical immutable-class example.

• Mutable class instances can be frozen into immutable instances.

  • Checkpointing, for example.

Immutable Classes and Final Fields

• Why not make all fields in an immutable class public?

  • After all, nothing can change, and method calls are expensive.

• This is dangerous thinking.

  • Without care, values can be changed.

  • Breaking encapsulation usually comes back to bite.

• Do not be seduced by the final keyword.

  • Only the final field itself is unchanging.

  • Unchanging references can change instances.

  • Similar to const T * vs. T * const in C++.

• Everything reachable from a final field must also be immutable.

  • Final fields of basic type are fine.

  • Final fields of immutable class instances are fine.

  • Final fields of mutable classes instances don't work.

Final Field Examples - The Good

• Good: basic type values.

  class fraction()
    public final long numerator, denominator
  

  • Legal: System.out.println(f.numerator)

  • Illegal: f.numerator = 3
f.numerator is final.

  • Atomicity is not the issue here.

• Good: references to immutable classes.

  class name()
    public final String firstName, lastName
  

  • Legal: System.out.println(n.firstName)

  • Illegal:
    n.firstName[0] = toUpper(n.firstName[0])
Strings are immutable.

• All of this still breaks encapsulation.

Final Field Examples - The Bad

• Bad: references to mutable classes

  class roster()
    public final Student classRoster[]
  

  • Legal: System.out.println(cs598.classRoster[0])

  • Legal: cs598.classRoster[0] = null

    The array reference is unchanging; the array is not.

    Neither are the array elements.

  • Here comes interference.

Construction

• An immutable class instance can't change after construction.

• Initialization can cause trouble.

• Prevent access to unitialized final fields

  • Hide this during initialization.

  • Watch the (virtual) method calls.

• Lengthly initializations may increase latency.

  • The shared image example.

  • Eat the latency or re-introduce synchronization.

• Don't forget Object.equals(Object) and Object.hashCode() contracts.

  • Increase sharing by reconginzing identical instances.

  • Instances that get compared or stored may need them.

  • With a perfect hash, equals() is the same as ==.

Procedural Classes

• A procedural class instance computes the values it returns.

  class NextTurn private int turn = 0 int next() turn = (turn + 1) % 2 return turn

  class ImmutableNextTurn int next(int lastTurn) return (lastTurn + 1) % 2

  • Procedures (that is, code) is inherently immutable.

• Arbitrary amounts of state can be passed in.

  • This is a convenient way to make a mutable class immutable.

    • Put all class fields in the argument parameter.

  • Each caller (thread) has its own mutable, unshared state.
    

Functional Programming

• Stateless objects are necessarily immutable.

• Functions are stateless objects.

  • Input comes in via the argument list.

  • Output comes goes out via the function return.

  • Nothing sticks around between.

• Functions must be side-effect free.

  • All output must be via the function return.

    • Via arguments too, with care (no aliases).

  • Unfortunately, I-O is an important side-effect.

• Functional programming is an important concurrency approach.

  • Evaluate argument expressions in parallel.

    • f(g(), h()) or i = f() + g()

• OOL aren't conductive to functional programming.

  • Functions are secondary, data are cumbersome.

Mutating Immutable Data

• How to mutate immutable data structures?

  • Build the new one using the old ones.

    String replace(
      String str, String old, String new)
    
      int i = find(str, old)
    
      return 
        str[0..i] + 
        new + 
        str[i+old.length()-1..str.length()]
    

• This can get inefficient.

  • Witness String vs. StringBuffer.

• Lisp programmers are familiar with this approach.

• Memory management makes C++ programmers afraid.

  • Don't be afraid, Java will help you (heh, heh).

Points to Remember

• Immutable data has no interference problems.

  • Easily shared; unsynchronized, safe concurrent access.

• Watch out for final.

  • Understand T * const vs. const T *.

• Initialization takes some care.

  • Particularly for immutable subclasses.

• Functional programming is an immutable-programming model.

  • It may be worth the oo-overhead to implement.

This page last modified on 8 July 2003.