04-concurrency-and-parallelism.slide

# Concurrency & Parallelism
Course Go
Tags: golang, go

## Outline

- Goroutines
- Runtime
- Channels
- Select
- Related packages

## Keywords

```
break       case     chan      const         continue
default     defer    else      fallthrough   for
func        go       goto      if            import
interface   map      package   range         return
select      struct   switch    type          var
```

You already know:

```
break       case               const         continue
default     defer    else      fallthrough   for
func                 goto      if            import
interface   map      package   range         return
            struct   switch    type          var
```

This session covers the rest:

```
                     chan
            go

select
```

After this lecture, you will know all of the Go keywords! Yaay!

## Concurrency

## Concurrency

*"Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once."*

~ [Rob Pike: Concurrency is not Parallelism](https://youtu.be/oV9rvDllKEg?t=143)
- Concurrency is possible with even a single CPU core
    - Parallelism is not
- Backbone of concurrency in Go:
    - Gouroutines
    - Channels
    - `select` construct

##

.image assets/lecture-04/goroutines/concurrency-parallelism.svg 550 _

## Goroutines

## Goroutines

- Core concept in Go
- Basically light-weight threads
    - Managed by the Go's runtime
        - Limited context switching and interactions with the OS
        - Goroutine scheduler is able to better optimize the workload
    - Generally cheap to spawn
        - Initial stack size is smaller compared to POSIX threads (8 KB vs 8 MB)
        - But do not get the false sense you can spawn infinite number of them, it is still a resource
            - Up to tens/hundreds of thousands are fine
    - Internally multiplexed across on kernel thread pool (M:N)

## Goroutines

.play assets/lecture-04/goroutines/goroutines.go

## Runtime

## Runtime

- Just a library
    - Same as the `libc` library in C
- Statically linked with your program upon compilation

.play assets/lecture-04/runtime/runtime.go /START OMIT/,/END OMIT/

[Go's runtime package](https://pkg.go.dev/runtime)

## Scheduler

- Orchestrator
- Runs goroutines
- Pauses and resumes them
- Pre-emptive since Go 1.14
    - Goroutines are pre-emted after [10ms](https://github.com/golang/go/blob/go1.19.1/src/runtime/proc.go#L5279-L5281)
    - Sysmon
- Work-stealing
- Handoffs
- Coordinates system calls, I/O operations, runtime tasks etc.

[Kavya Joshi: The Scheduler Saga](https://www.youtube.com/watch?v=YHRO5WQGh0k)

[Ardan Labs: Scheduling in Go](https://www.ardanlabs.com/blog/2018/08/scheduling-in-go-part1.html)

## Goroutine states

- Runnable
    - Can be run but is not assigned to a CPU core
- Executing
    - Currently running
- Waiting
    - System calls
    - Synchronization calls
    - I/O operations

## Naming

- **P** (Processor): Logical processor
- **M** (Machine): OS Thread
    - Initially, each P gets assigned one M
    - More can be spawned by the runtime
- **G** (Goroutine): Goroutine

## Scheduling

.image assets/lecture-04/runtime/scheduler.svg 450 _

## Scheduling algorithm

```
runtime.schedule() {
    // only 1/61 of the time, check the global runnable queue for a G.
    // if not found, check the local queue.
    // if not found,
    //     try to steal from other Ps.
    //     if not, check the global runnable queue.
    //     if not found, poll network.
}
```
[Jaana Dogan: Scheduler](https://rakyll.org/scheduler/) (CC BY SA 4.0)

## Channels

## Channels

- Way to transfer data between goroutines
- Data type is a part of the channel type
    - Functions can further specify whether channels passed as arguments are read/write-only
- Buffered and unbuffered
- Channels can be created only with `make`:
```
ch := make(chan int)
```
- New operator `<-` used to send and receive messages from channels:
```
value := <-ch   // reading
ch<-value       // writing
```

## Communication via message queues

- Analogy of phone calls
    - Phone ringing
        - Blocking call
    - Answerphone
        - Non-blocking call 
    - Multiple receivers
        - Call centre
    - Multiple senders
        - Conference call

## Unbuffered channels

- Note that this example is racy

.play assets/lecture-04/channels/unbuffered.go

## Unbuffered channels

.image assets/lecture-04/channels/unbuffered.svg

## Channel deadlocks

- Unbuffered channels do block
    - Buffered channels also block when full or empty
    - Go kindly detects deadlocks

.play assets/lecture-04/channels/deadlock.go

## Goroutine synchronization 

- Unbuffered channels can be used to synchronize goroutines

.play assets/lecture-04/channels/sync.go /START OMIT/,/END OMIT/

## Buffered channels

- The size of the channel is provided as the second argument to `make`

.play assets/lecture-04/channels/buffered.go /START OMIT/,/END OMIT/

## Buffered channels

.image assets/lecture-04/channels/buffered.svg 550 _

## Buffered channels

.image assets/lecture-04/channels/buffered-full.svg 550 _

## Pipeline

.image assets/lecture-04/channels/pipeline.svg 200 _

## Pipeline (1/2)

.play assets/lecture-04/channels/pipeline.go /START OMIT/,/MIDDLE OMIT/

## Pipeline (2/2)

.play assets/lecture-04/channels/pipeline.go /MIDDLE OMIT/,/END OMIT/

## Closing channels

- Channels can be closed with `close` function
    - Writers are responsible for closing the channels
    - Note that closing channels is not neccesary
        - Only used to signal the end of transmission to the readers
```
c := make(chan int)
close(c)
```
- Reading from a closed channel returns a default value
- Readers can check for closed channels using optional second return argument
    - Same as with maps
- Alternatively readers can detect closed channel with the loop over range
    - Does the same "comma ok" idiom under the hood

## Closed channel operations

- Writing to a closed channel

.play assets/lecture-04/channels/closed-write.go

## Closed channel operations

- Reading from a closed channel

.play assets/lecture-04/channels/closed-read.go /START OMIT/,/END OMIT/

- "Comma ok" idiom channel check

.play assets/lecture-04/channels/closed-read-ok.go /START OMIT/,/END OMIT/

## Range over channels

- For loop with range reads the messages when available
    - The loop breaks when the channel gets closed
    - Empties the channel's buffer first

.play assets/lecture-04/channels/range.go /START OMIT/,/END OMIT/

## Channel operations

.image assets/lecture-04/channels/operations.png 450 _

## Select

## Select

- Special construct and the last Go keyword we have not yet covered
- Syntactically similar to the `switch` statement
- Helps us manipulate multiple channels at the same time
    - You can read on/write to numerous channels at once
    - Prevents reads/writes that would otherwise block

## Select

- The `select` statement always chooses a `case` that does not block
- Both of the channels in the following example are ready to be read from
    - Therefore, the `select` chooses one of them at random

.play assets/lecture-04/select/select.go /START OMIT/,/END OMIT/

## Select

- The same works for writes
    - Neither channels is full
    - Writing to them would not block

.play assets/lecture-04/select/writes.go /START OMIT/,/END OMIT/

## Select

- The `chanB` would block on read
    - The `select` therefore always chooses the `chanA`

.play assets/lecture-04/select/single.go /START OMIT/,/END OMIT/

## Select default

- All channel reads block
    - `select` would panic
- We can leverage the `default` case
    - The `default` gets selected only when all the `case`s would block

.play assets/lecture-04/select/default.go /START OMIT/,/END OMIT/

## Fan-out

.image assets/lecture-04/channels/fanout.svg 500 _

## Fan-in

.image assets/lecture-04/channels/fanin.svg 500 _

## Fan-in (1/2)

.play assets/lecture-04/select/fanin.go /MIDDLE OMIT/,/END OMIT/

## Fan-in (2/2)

.play assets/lecture-04/select/fanin.go /START OMIT/,/MIDDLE OMIT/

## Signalling termination

- Usually done through `context`s

.play assets/lecture-04/select/done.go /START OMIT/,/END OMIT/

## Related packages

## Context package

- Introduced in Go 1.7
- Structure used for carrying deadlines, context cancellations 
and other request-scoped values across API boundaries
- Contexts can be inherited to further propagate cancallations
    - The changes to the child contexts are not propagated to the parents

```
type Context interface {
	Deadline() (deadline time.Time, ok bool)
	Done() <-chan struct{}      // channel used for signalling cancallation
	Err() error
	Value(key any) any          // map[any]any
}
```

[Go packages: context](https://pkg.go.dev/context)

## Context creation

- **TODO**: should never be used in production applications

```
ctx := context.TODO()
```

- **Background**: used when cannot inherit from other contexts

```
ctx := context.Background()
```

- **WithValue**: adds value to an existing context and returns it

```
parent := context.Background()
ctx := context.WithValue(parent, "API version", "v2")
version := ctx.Value("API version")
```

## Context creation

- **WithCancel**: returns a cancel function which can be called directly

```
parent := context.Background()
ctx, cancel := context.WithCancel(parent)
cancel()
```

- **WithDeadline**: adds deadline to an existing context and returns it
    - `Done` channels gets closed when the specified time passes

```
time := time.Now().Add(shortDuration)
parent := context.Background()
ctx, cancel := context.WithDeadline(parent, time)
```

- **WithTimeout**: adds timeout to an existing context and returns it
    - `Done` channels gets closed after the specified duration passes

```
parent := context.Background()
ctx, cancel := context.WithTimeout(parent, 10 * time.Second)
```

## Context

.play assets/lecture-04/contexts/contexts.go /START OMIT/,/MIDDLE OMIT/

## Context

.play assets/lecture-04/contexts/contexts.go /MIDDLE OMIT/,/END OMIT/

## Context propagation

.image assets/lecture-04/contexts/contexts-propagation.svg 550 _

## Time package

- Time manipulation

```
now := time.Now()
hour := now.Hour()

y2k := time.Date(2000, 1, 1, 0, 0, 0, 0, time.UTC)
y3k := time.Date(3000, 1, 1, 0, 0, 0, 0, time.UTC)
before := y2k.Before(y3k)
comparison := y3k.Compare(y2k)
```

- Time constants

```
threeSeconds := 3 * time.Second
```

- Durations

```
duration, err := time.ParseDuration("1h10m10s")
```

- Timer, Ticker, etc.

[Go packages: time](https://pkg.go.dev/time)

## Time parsing

- Uses special date for parsing

```
const Layout = "01/02 03:04:05PM '06 -0700"
```

- Some predefined standards:
```
RFC822      = "02 Jan 06 15:04 MST"
RFC822Z     = "02 Jan 06 15:04 -0700" // RFC822 with numeric zone
RFC850      = "Monday, 02-Jan-06 15:04:05 MST"
RFC1123     = "Mon, 02 Jan 2006 15:04:05 MST"
RFC1123Z    = "Mon, 02 Jan 2006 15:04:05 -0700" // RFC1123 with numeric zone
RFC3339     = "2006-01-02T15:04:05Z07:00"
Kitchen     = "3:04PM"
```

- Parsing:
```
t, err := time.Parse(time.RFC3339, "2024-08-12T04:02:32Z")
t, err := time.Parse("02 2006 01", "08 2024 12") // custom format: day year month
```

[Willem Schots: How to parse a time or date in Go](https://www.willem.dev/articles/how-to-parse-time-date/)

## Timer

- Structure that delivers a tick after a specified time

```
timer := time.NewTimer(time.Second)
timer.Stop()
timer.Reset(3 * time.Second)
```

```
type Timer struct {
	C <-chan Time // The channel that delivers the tick.
	// Other unexported fields...
}
```

## Timer

.play assets/lecture-04/time/timer.go /START OMIT/,/END OMIT/

## Ticker

- Structure for delivering ticks in a specified period
- Same as `timer` but ticks endlessly or unless directly stopped

```
ticker := time.NewTicker(time.Second)
ticker.Stop()
ticker.Reset(3 * time.Second)
```

```
type Ticker struct {
	C <-chan Time // The channel on which the ticks are delivered.
	// Other unexported fields...
}
```

```
<-ticker.C
```

## Ticker

.play assets/lecture-04/time/ticker.go /START OMIT/,/END OMIT/

## Sync package

- Contains synchronizations primitives, most notably:
    - **Mutex**: mutex
    - **RWMutex**: read-write mutex
    - **WaitGroup**: barrier
    - **Cond**: conditional variable
        - Can be simulated with just channels in most use cases
    - **Map**: 
        - Generally not recommended to be used

[Go packages: sync](https://pkg.go.dev/sync)

## Mutex

.play assets/lecture-04/sync/mutex.go /START OMIT/,/END OMIT/

## RWMutex

- Works the same way as mutex
- Additionally, exposes reader lock API:
    - `RLock()`
    - `RUnlock()`

## WaitGroup

.play assets/lecture-04/sync/waitgroup.go /START OMIT/,/END OMIT/

## Sync/atomic package

- Low-level synchronization primitives
- Atomic:
    - Bool
    - Integer
        - Signed/unsigned
        - 32/64
    - Generic Value
- Swaps
- Compares and swaps (CAS)

[Go packages: sync/atomic](https://pkg.go.dev/sync/atomic)

## Atomics

.play assets/lecture-04/sync/atomics.go /START OMIT/,/END OMIT/