Immutability 101
Singapore, 08.2024 CPaaS, Messaging team
Agenda:
- Intro to Immutability
- Immutable Types
- Immutable Collections
Introduction to Immutability
What is Immutability?
Rules:
- All fields should be readonly
- All properties should provide getters only
- All members should be of immutable types
- All collections should be Immutable
- All state updates should return a new state
Why do we need it?
- Facilitates problems from concurrent and parallel programming
- Predictability and easier debugging
- Less side effects + referential transparency
- Mutation tracking, data versioning
- More suitable for uni-direction data flows
Is it a wasting of resources?
Yes, but no... 🙂
Immutable Types
- Primitives (int, bool, ...)
- Some built-in types like Uri, string, Guid and etc.
- Data containers like Tuples/ValueTuples
- Readonly fields, ref readonly variables, in parameters
- Some iterators
- UDT with custom implementation of immutability
- Records
Quiz time:
Quiz time:
What will be printed before and after increment?
- 1 and 2
- 1 and 1
- App crashes
The right answer: 1
Quiz time:
Quiz time:
What will be printed before and after increment?
- 1 and 2
- 1 and 1
- App crashes
The right answer: 2
Defensive copying
Can we do better?
`IN` parameters
`IN` parameters
Collection enumerators
Quiz time:
What will be printed in the console?
- Empty
- 1,2,3
- App crashes
The right answer: 2
Collection enumerators
Quiz time:
What will be printed before and after increment?
- Empty
- 1,2,3
- App crashes
The right answer: 3
Why?
Bonus
+ record struct
Bonus 2
Immutable collections
Different types of immutability
- Immutable* collections
- ReadOnly* collections
- Frozen* collections
Complexities
| Operation | Mutable (amortized) | Mutable (worst case) | Immutable |
|---|---|---|---|
| Stack.Push | O(1) | O(n) | O(1) |
| Queue.Enqueue | O(1) | O(n) | O(1) |
| List.Add | O(1) | O(1) | O(logn) |
| List lookup by index | O(1) | O(1) | O(logn) |
| List enumeration | O(n) | O(n) | O(n) |
| HashSet.Add + Lookup | O(1) | O(n) | O(logn) |
| SortedSet.Add | O(logn) | O(n) | O(logn) |
| Dictionary.Add | O(1) | O(n) | O(logn) |
| Dictionary Lookup | O(1) | O(n) | O(logn) |
| SortedDictionary.Add | O(logn) | O(nlogn) | O(logn) |
+ What happens if we modify element?
Immutable Stack
Immutable List
Immutable Array
- Copies the whole array before mutation
- Performance-wise the same as regular array
Immutable Dictionary
- Balaned binary tree of balanced binary trees
- Slower and consumes more memory comparing to regular Dictionary
Bulk operations