DEV Community: Kostiantyn Lysenko

Algorithm Complexity with Go — Linear Time Complexity O(n)

Kostiantyn Lysenko — Sun, 14 Jul 2024 09:13:10 +0000

Algorithm Complexity with Go — Linear Time Complexity O(n)

Today, we will focus on linear time complexity, often denoted as O(n).

Linear time complexity implies that the time required to complete the algorithm grows directly proportional to the input size. This type of complexity is efficient and clean because it scales predictably with input size. It is significant because it strikes a balance between simplicity and performance.

Analogy to Understand Linear Time Complexity

Imagine you are a postman 👮🏻‍♂️ delivering letters. You have a list of addresses, and you need to deliver one letter to each address.

If you have 10 letters to deliver, it takes 10 stops.

If you have 100 letters to deliver, it takes 100 stops.

If you have 1 000 000 letters to deliver, it takes 1 000 000 stops.

Each stop takes a consistent amount of time to park, deliver the letter, and return to the van.

The time taken grows proportionally with the number of letters.

As each stop takes the same amount of time as each memory access and write operation takes a consistent amount of time , so doubling the number of items roughly doubles the total time needed.

Real-world examples

Let’s consider the most common real-world examples of operations that typically have linear time complexity:

Iterating through a list to perform some action on each element. For example, printing each element of a list of names:

package main

import "fmt"

func main() {
    slice := []string{"Alice", "Bob", "Charlie"}
    for _, name := range slice {
        fmt.Println(name)
    }
    // Output: Alice
    // Output: Bob
    // Output: Charlie
}

Simple search operations in an unsorted list. Finding a specific number in an unsorted list of integers:

package main

import "fmt"

func main() {
    slice := []int{30, 10, 2, 15, 130}
    target := 30

    for _, value := range slice {
       if value == target {
          fmt.Println(value)
       }
    }

    // Output: 30
}

Summing all elements in a list:

package main

import "fmt"

func main() {
    slice := []int{1, 2, 3, 4, 5}

    sum := 0
    for _, value := range slice {
       sum += value
    }

    fmt.Println(sum) // Output: 15
}

Copying all elements from one list to another:

package main

import "fmt"

func main() {
    slice := []int{1, 2, 3, 4, 5}

    newSlice := make([]int, len(slice))
    copy(newSlice, slice)

    fmt.Println(newSlice) // Output: [1, 2, 3, 4, 5]
}

Merging two lists into one:

package main

import "fmt"

func main() {
    slice1 := []int{1, 2, 3}
    slice2 := []int{4, 5, 6}

    mergedSlice := append(slice1, slice2...)

    fmt.Println(mergedSlice) // Output: [1, 2, 3, 4, 5, 6]
}

Reversing a list:

package main

import "fmt"

func main() {
    slice := []int{1, 2, 3, 4, 5}

    for i, j := 0, len(slice)-1; i < j; i, j = i+1, j-1 {
       slice[i], slice[j] = slice[j], slice[i]
    }

    fmt.Println(slice) // Output: [5, 4, 3, 2, 1]
}

Benchmarks

Let’s benchmark copy() and confirm its linear time complexity.

Create a file named copy_benchmark_test.go:

package main

import (
    "fmt"
    "testing"
)

// copyArray copies all elements from one slice to another
func copyArray(arr []int) []int {
    newArr := make([]int, len(arr))
    copy(newArr, arr)
    return newArr
}

// BenchmarkCopyArray benchmarks the copyArray function
func BenchmarkCopyArray(b *testing.B) {
    sizes := []int{1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000}

    for _, size := range sizes {
       b.Run("Size="+fmt.Sprint(size), func(b *testing.B) {
          arr := make([]int, size)
          for i := 0; i < size; i++ {
             arr[i] = i
          }

          b.ResetTimer()

          for i := 0; i < b.N; i++ {
             _ = copyArray(arr)
          }
       })
    }
}

Run with:

go test -bench .

Enjoy the result:

goos: darwin
goarch: amd64
pkg: cache
cpu: Intel(R) Core(TM) i7-8569U CPU @ 2.80GHz
BenchmarkCopyArray
BenchmarkCopyArray/Size=1000
BenchmarkCopyArray/Size=1000-8 586563 1773 ns/op
BenchmarkCopyArray/Size=2000
BenchmarkCopyArray/Size=2000-8 459171 2582 ns/op
BenchmarkCopyArray/Size=3000
BenchmarkCopyArray/Size=3000-8 331647 3588 ns/op
BenchmarkCopyArray/Size=4000
BenchmarkCopyArray/Size=4000-8 263466 4721 ns/op
BenchmarkCopyArray/Size=5000
BenchmarkCopyArray/Size=5000-8 212155 5728 ns/op
BenchmarkCopyArray/Size=6000
BenchmarkCopyArray/Size=6000-8 179078 6902 ns/op
BenchmarkCopyArray/Size=7000
BenchmarkCopyArray/Size=7000-8 152635 7573 ns/op
BenchmarkCopyArray/Size=8000
BenchmarkCopyArray/Size=8000-8 142131 8423 ns/op
BenchmarkCopyArray/Size=9000
BenchmarkCopyArray/Size=9000-8 118581 9780 ns/op
BenchmarkCopyArray/Size=10000
BenchmarkCopyArray/Size=10000-8 109848 14530 ns/op
PASS

The following chart shows the almost straight line ↗ that proves the copy() operation has linear time complexity, O(n), as the time taken increases proportionally with the size of the array:

For very large slices, the linear time complexity means the performance will degrade in direct proportion to the size of the slice , making it important to optimize such operations or consider parallel processing for performance improvement.

Summary

Knowing about linear time complexity empowers to build efficient, scalable, and maintainable software, ensuring that applications perform well across a wide range of input sizes. This foundational knowledge is essential for anyone working with algorithms and data structures.

Use linear time complexity solutions carefully only if you make sure it’s the best option and there is no way to use a linked list, map, etc. 🐈‍⬛

Deadlocks in Go: Understanding and Preventing for Production Stability

Kostiantyn Lysenko — Sun, 23 Jun 2024 00:21:30 +0000

fatal error: all goroutines are asleep - deadlock!

Damn, not again! 💀

Yes, that’s often the reaction if you’re not aware of all possible deadlocks that might happen.

This article will help you prevent all possible deadlocks and understand their nature.

Introduction

Deadlocks in Go can cause your program to become unresponsive, leading to poor user experiences and potentially costly downtime. Even more, the Go compiler will NOT warn you about these issues because deadlocks are a runtime phenomenon, not a compile-time error. This means that your code might compile and pass initial tests, only to fail under specific conditions in a production environment.

Understanding Deadlocks

Deadlocks happen when a task gets stuck waiting for something that will never happen , causing it to stop moving forward.

This principle forms the foundation of your coding approach. Always inquire:

- Will someone write something into the channel I’ve created?

Similarly, consider:

- Am I trying to write to a channel without space?

Also:

- Am I attempting to read from a channel that is currently empty?

In other words:

to store something, you need a *place ready to receive * it;
to read something, you must ensure there’s something available to be read ;
to lock something, you must verify it’s free and will be released when needed.

Deadlock types

All possible cases might be grouped into the next two groups:

Channel misuse
Circular dependencies between goroutines

Let’s consider them in more detail.

Channel Misuse

Using channels incorrectly, like reading from an empty channel or writing to a full one, can make goroutines wait forever, causing deadlock. Let’s delve into and discuss all possible types within this category.

No receiver deadlock

It occurs when a goroutine attempts to send data to an unbuffered channel, but there is no corresponding receiver ready to receive that data.

package main

func main() {
   // Create an unbuffered channel of integers
   goChannel := make(chan int)

   // Attempt to send the value 1 into the channel
   // This operation will block indefinitely because there's no receiver 
   // ready to receive the value
   goChannel <- 1
}

This occurs specifically with unbuffered channels due to their lack of storage space. The same code with a buffered channel won’t have deadlock.

Got it! Let’s add a receiver and make it work:

package main

import "fmt"

func main() {
   goChannel := make(chan int)
   goChannel <- 1

   // Attempt to read the value from the channel
   fmt.Println(<-goChannel)
}

Wait… What? Why does it still throw deadlock? 😡

This is because channels aim to synchronize two or more goroutines. And if one writes to the channel, there should be another goroutine that reads from the channel. Let’s fix it:

package main

import (
   "fmt"
   "time"
)

func main() {
   goChannel := make(chan int)
   goChannel <- 1

   go func() {
      // Attempt to read from the channel
      fmt.Println(<-goChannel)
   }()

   // Waiting for the goroutine to be executed
   time.Sleep(2 * time.Second)
}

Wait! Why still? 🤬

Because, before putting value we need to make sure it will be received and reading must be called before writing. Let’s switch places of read and write calls:

package main

import (
   "fmt"
   "time"
)

func main() {
   goChannel := make(chan int)

   // Start reading from the channel
   go func() {
      // Attempt to read from the channel
      fmt.Println(<-goChannel)
   }()

   // Start writing to channel
   goChannel <- 1

   // Waiting for the goroutine to be executed
   time.Sleep(2 * time.Second)
}

Yeah, finally it works. 🥳

This rule doesn’t apply to buffered channels since they have a place to store value and one goroutine might handle both actions — read and write. The following code that previously didn’t work with unbuffered channel works now:

package main

import (
   "fmt"
)

func main() {
   // Define buffered channel
   goChannel := make(chan string, 1)
   // Attempt to write to the channel
   goChannel <- "hey!"
   // Attempt to read from the channel
   fmt.Println(<-goChannel)
}

No sender deadlock

It occurs when a goroutine tries to read data from a channel, but no value will ever be sent :

package main

func main() {
   // Create a channel of integers
   goChannel := make(chan int)

   // Attempt to read a value from the channel
   // This operation will block indefinitely because there's no value
   // previously sent
   <- goChannel
}

This logic applies to both buffered and unbuffered channels.

Writing to a Full Channel

A deadlock can occur when a goroutine attempts to write to a buffered channel that is already full, and no other goroutine is available to read from the channel. This leads to the write operation blocking indefinitely , causing deadlock:

package main

import "fmt"

func main() {
   // Create a buffered channel with a capacity of 1
   ch := make(chan int, 1)

   // Send a value into the channel
   ch <- 1

   // Attempt to send another value into the channel
   // This will block because the channel is full and there's no receiver or place to store value
   ch <- 2

   fmt.Println("This line will never be printed")
}

Reading from an Empty Channel

Another case is when a goroutine attempts to read from an already emptied channel , resulting in the read operation blocking indefinitely:

package main

import "fmt"

func main() {
   // Create a buffered channel with a capacity of 1
   ch := make(chan string, 1)

   // Send a value into the channel 
   ch <- "first"

   // Attempt to read the value (will be printed)
   fmt.Println(<-ch)

   // Attempt to read the value again (will fail)
   fmt.Println(<-ch)
}

Unclosed Channel Before Range

The following code demonstrates one of the most common deadlocks that happens to developers when a goroutine iterates over a channel using a for-range loop, but the channel is never closed. The for-range loop requires the channel to be closed to terminate iteration. If the channel is not closed, the loop will block indefinitely, leading to a deadlock. Try to run with commented and uncommented close(ch):

package main

import "fmt"

func main() {
   // Create a buffered channel
   ch := make(chan int, 2)

   // Send some values into the channel
   ch <- 1
   ch <- 2

   // Close the channel to prevent deadlock
   // close(ch) // This line is intentionally commented out 
   // to demonstrate deadlock

   // Iterate over the channel using a for-range loop
   for val := range ch {
      fmt.Println(val)
   }

   fmt.Println("This line will be printed only if the channel was closed")
}

Don’t leave channels opened 🫢

Circular dependencies between goroutines

Circular dependencies between goroutines occur when multiple goroutines are waiting on each other to perform actions or exchange data, creating a situation where none of them can proceed without the others’ participation, leading to a deadlock.

Correct managing dependencies between goroutines is crucial to prevent the mentioned deadlocks-situations. Let’s discuss the most common cases.

Mutex and Locking Issues

If one goroutine locks resource A first and then waits to lock resource B, while another goroutine locks resource B first and then waits to lock resource A, a deadlock can occur if both goroutines end up waiting indefinitely for each other to release their locks.

Try the following example:

package main

import (
 "fmt"
 "sync"
 "time"
)

func main() {
   // Declare two mutexes
   var mu1, mu2 sync.Mutex

   var wg sync.WaitGroup
   wg.Add(2)

   // Goroutine 1
   go func() {
      defer wg.Done()

      mu1.Lock()
      // Simulate some work or delay
      time.Sleep(1 * time.Second)
      mu2.Lock()

      mu2.Unlock()
      mu1.Unlock()
      fmt.Println("Goroutine 1: Unlocked")
   }()

   // Goroutine 2
   go func() {
      defer wg.Done()

      mu2.Lock()
      // Simulate some work or delay
      time.Sleep(1 * time.Second)
      mu1.Lock()

      mu1.Unlock()
      mu2.Unlock()
      fmt.Println("Goroutine 2: Unlocked")
   }()

   // Wait for all goroutines to finish
   wg.Wait()
}

To prevent such deadlocks in Go, ensure that goroutines acquire locks in a consistent and mutually agreed order. This prevents situations where one goroutine is waiting for a lock held by another goroutine, which is also waiting for a lock held by the first goroutine.

Deadlock Due to Misuse of WaitGroup

Missing to call wg.Done() can cause other goroutines waiting on the WaitGroup to block indefinitely, assuming that all tasks have been completed:

package main

import (
   "sync"
   "time"
)

func main() {
   var wg sync.WaitGroup

   wg.Add(1)

   go func() {
      // Uncomment wg.Done below to make it work
      // defer wg.Done()

      // Simulating some work
      time.Sleep(1 * time.Second)
   }()

   wg.Wait()
   // This would deadlock if wg.Done() was missing.
}

Make sure to always use wg.Done() when using sync.WaitGroup to properly signal the completion of goroutines and avoid the deadlock.

Conclusion

By implementing these best practices and understanding the scenarios that lead to deadlocks, you can significantly reduce the risk of encountering them in your Go programs.

Consider using this checklist when developing your program in Golang:

❗ Channel: Ensure no receiver or sender deadlock.

❗ Channel: Avoid writing to a full channel or reading from an empty one.

❗ Channel: Always close before using range.

❗ Mutex: Prevent deadlocks by managing locking order.

❗ WaitGroup: Use wg.Done() correctly to avoid blocking.

Keep coding efficiently and watch out for those sneaky deadlocks! 🐈‍⬛

Algorithm Complexity with Go - Part 1

Kostiantyn Lysenko — Sat, 04 May 2024 23:47:33 +0000

Understanding algorithm complexity is essential for developing efficient software solutions. One key aspect of algorithm complexity is ordering growth types, which describe how the runtime of an algorithm scales with the size of the input.

In this series of articles, we’ll explore several ordering growth types , ranging from constant time to exponential time, and discuss their implications for algorithm design and performance.

Constant time complexity

Imagine you have a super speedy delivery service that guarantees your package arrives in the same amount of time, no matter the distance, or your old laptop that infinitely opens as much as Paint and Adobe Photoshop. That’s constant time complexity in action!

Constant time complexity means that the time taken to execute an operation remains constant regardless of the input size.

I’m going to show you this hackneyed example with accessing array element (boring), but with Go benchmarks to give you visualization and make it clear:

func accessElement(arr []int, index int) int {
    return arr[index]
}

Here no matter the size of the array, retrieving an element by index takes the same amount of time.

Let’s prove it in practice by running benchmarks with arrays of 10, 1000, 100000, 100000000 items in length.

package main

import (
    "testing"
)

func accessElement(arr []int, index int) int {
    return arr[index]
}

func BenchmarkAccessElement10(b *testing.B) {
    arr := make([]int, 10) // Array size of 10
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 5 // Fixed index for the array of size 10

    b.ResetTimer() // Isolate all code above
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement1000(b *testing.B) {
    arr := make([]int, 1000) // Array size of 1000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 500 // Fixed index for the array of size 1000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement100000(b *testing.B) {
    arr := make([]int, 100000) // Array size of 100000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 50000 // Fixed index for the array of size 100000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

func BenchmarkAccessElement100000000(b *testing.B) {
    arr := make([]int, 100000000) // Array size of 100000000
    for i := 0; i < len(arr); i++ {
        arr[i] = i
    }
    index := 5000000 // Fixed index for the array of size 100000000

    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        _ = accessElement(arr, index)
    }
}

go test -bench .

goos: darwin
goarch: amd64
pkg: algorithms/complexity
cpu: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
BenchmarkAccessElement10
BenchmarkAccessElement10-4 1000000000 0.6557 ns/op
BenchmarkAccessElement1000
BenchmarkAccessElement1000-4 1000000000 0.6056 ns/op
BenchmarkAccessElement100000
BenchmarkAccessElement100000-4 1000000000 0.6613 ns/op
BenchmarkAccessElement100000000
BenchmarkAccessElement100000000-4 1000000000 0.6689 ns/op
PASS

Nice! Around 0.6 to 0.7 nanoseconds per operation — execution time remains unchanged even as the array size increases.

Why does it take the same time?

Because the operation is pretty simple — determine the memory address of the desired element based on its index.

How does it determine?

To calculate the memory address of an element, Go takes the base memory address of the array (the address of its first element) and adds an offset to it. This offset is determined by the index of the desired element and the size of each element in the array.

The offset for accessing the element at index i in the array is calculated using the formula offset = i * size_of_element where size_of_element represents the size of each element in bytes.

Once the offset is calculated, it is added to the base memory address of the array and this results in the memory address of the desired element:

desired = base address + offset

As a result, this calculation can be performed very quickly by modern processors and the time taken to perform this calculation remains the same.

That’s it!

If you wish to know another example — retrieving data from a Hash Table is a good one.