DEV Community: Souvik Kar Mahapatra

Fan-In Fan-Out Concurrency Pattern in Go: A Comprehensive Guide

Souvik Kar Mahapatra — Tue, 07 Jan 2025 14:00:00 +0000

⚠️ How to go about this series?

1. Run Every Example: Don't just read the code. Type it out, run it, and observe the behavior.
2. Experiment and Break Things: Remove sleeps and see what happens, change channel buffer sizes, modify goroutine counts.
Breaking things teaches you how they work
3. Reason About Behavior: Before running modified code, try predicting the outcome. When you see unexpected behavior, pause and think why. Challenge the explanations.
4. Build Mental Models: Each visualization represents a concept. Try drawing your own diagrams for modified code.

In our previous post, we explored the Pipeline concurrency pattern, the building blocks of Fan-In & Fan-Out concurrency patterns. You can give it a read here:

Pipeline Concurrency Pattern in Go: A Comprehensive Visual Guide

Souvik Kar Mahapatra ・ Dec 29 '24

#go #tutorial #programming #architecture

In this post we'll cover Fan-in & Fan-out Pattern and will try to visualize them. So let's gear up as we'll be hands on through out the process.

Evolution from Pipeline Pattern

The fan-in fan-out pattern is a natural evolution of the pipeline pattern. While a pipeline processes data sequentially through stages, fan-in fan-out introduces parallel processing capabilities. Let's visualize how this evolution happens:

Fan-In Fan-Out Pattern

Imagine a restaurant kitchen during busy hours. When orders come in, multiple cooks work on different dishes simultaneously (fan-out). As they complete dishes, they come together at the service counter (fan-in).

Understanding Fan-out

Fan-out is distributing work across multiple goroutines to process data in parallel. Think of it as splitting a big task into smaller pieces that can be worked on simultaneously. Here's a simple example:

func fanOut(input <-chan int, workers int) []<-chan int {
    // Create a slice to hold our output channels
    outputs := make([]<-chan int, workers)

    for i := 0; i < workers; i++ {
        // Each worker gets its own output channel
        outputs[i] = worker(input)
    }

    return outputs
}

func worker(input <-chan int) <-chan int {
    output := make(chan int)

    go func() {
        defer close(output)
        // Each worker reads from the same input channel
        for num := range input {
            // Simulate work with complex computation
            result := complexComputation(num)
            output <- result
        }
    }()

    return output
}

func complexComputation(n int) int {
    time.Sleep(100 * time.Millisecond) // Simulate work
    return n * n
}

Understanding Fan-in

Fan-in is the opposite of fan-out - it combines multiple input channels into a single channel. It's like a funnel that collects results from all workers into one stream. Here's how we implement it:

func fanIn(inputs ...<-chan int) <-chan int {
    // Create a channel to combine all results
    output := make(chan int)
    var wg sync.WaitGroup

    // Start a goroutine for each input channel
    for _, input := range inputs {
        wg.Add(1)
        // Create closure to capture current input channel
        go func(ch <-chan int) {
            defer wg.Done()
            // Forward all values from this channel to output
            for val := range ch {
                output <- val
            }
        }(input)
    }

    // Close output channel when all input channels are done
    go func() {
        wg.Wait()
        close(output)
    }()

    return output
}

Let's put it all together with a complete example that processes numbers in parallel:

func main() {
    // Create our input channel
    input := make(chan int)

    // Start sending numbers
    go func() {
        defer close(input)
        for i := 1; i <= 10; i++ {
            input <- i
        }
    }()

    // Fan-out to 3 workers
    workers := fanOut(input, 3)

    // Fan-in the results
    results := fanIn(workers...)

    // Collect and print results
    for result := range results {
        fmt.Printf("Got result: %d\n", result)
    }
}

Why Use Fan-in Fan-out Pattern?

Optimal Resource Utilization

The pattern naturally distributes work across available resources, this prevents idle resources,maximizing throughput.

// Worker pool size adapts to system resources
numWorkers := runtime.NumCPU()
if numWorkers > maxWorkers {
    numWorkers = maxWorkers // Prevent over-allocation
}

Improved Performance Through Parallelization

In the sequential approach, tasks are processed one after another, creating a linear execution time. If each task takes 1 second, processing 4 tasks takes 4 seconds.
This parallel processing reduces total execution time to approximately (total tasks / number of workers) + overhead. In our example, with 4 workers, we process all tasks in about 1.2 seconds instead of 4 seconds.

func fanOut(tasks []Task) {
    numWorkers := runtime.NumCPU() // Utilize all available CPU cores
    workers := make([]<-chan Result, numWorkers)

    for i := 0; i < numWorkers; i++ {
        workers[i] = processTask(tasks[i::numWorkers]) // Each worker takes a subset of tasks
    }
    // ... fan-in code ...
}

Real-World Use Cases

Image Processing Pipeline

It's like a upgrade from our pipeline pattern post, we need to process faster and have dedicated go routines from each process:

Web Scraper Pipeline
Web scraping is another perfect use case for fan-in fan-out.

The fan-in fan-out pattern really shines in these scenarios because it:

Manages concurrency automatically through Go's channel mechanics
Provides natural backpressure when processing is slower than ingestion
Allows for easy scaling by adjusting the number of workers
Keeps the system resilient through isolated error handling

Error Handling Principles

Fail Fast: Detect and handle errors early in the pipeline

Try to perform all sort of validations before or at the start of the pipeline to make sure it doesn't fail down the line as it prevents wasting resources on invalid work that would fail later. It's especially crucial in fan-in fan-out patterns because invalid data could block workers or waste parallel processing capacity.

However it's not a hard rule and heavily depends on the business logic. Here is how we can implement it in out real-world examples:

func imageProcessor(tasks <-chan ImageTask) <-chan ProcessedImage {
    results := make(chan ProcessedImage)
    go func() {
        defer close(results)
        for task := range tasks {
            // Validate early before processing
            if err := validateImage(task); err != nil {
                results <- ProcessedImage{
                    ID:    task.ID,
                    Error: fmt.Errorf("validation failed: %w", err),
                }
                continue
            }
            // Process if validation passes
            processImage(task)
        }
    }()
    return results
}

and

// Web Scraping Example
func scrapeWorker(task ScrapeTask) (*ScrapedData, error) {
    // Validate URL before making request
    if _, err := url.Parse(task.URL); err != nil {
        return nil, fmt.Errorf("invalid URL format: %w", err)
    }
    // Continue with scraping if URL is valid
    return performScrape(task)
}

Notice! error in one worker the other do not stop, they keep processing and that brings us to 2nd principle

Isolate Failures: One worker's error shouldn't affect others

In a parallel processing system, one bad task shouldn't bring down the entire system. Each worker should be independent.

// Image Processing Example
func fanOutImageProcessing(tasks []ImageTask) {
    workers := make([]<-chan ProcessedImage, numWorkers)
    for i := 0; i < numWorkers; i++ {
        workers[i] = func(id int) <-chan ProcessedImage {
            results := make(chan ProcessedImage)
            go func() {
                defer close(results)
                for task := range tasks {
                    result := ProcessedImage{ID: task.ID}
                    // Error in one worker doesn't affect others
                    if processedData, err := safeProcess(task); err != nil {
                        result.Error = err
                    } else {
                        result.Data = processedData
                    }
                    results <- result
                }
            }()
            return results
        }(i)
    }
}

// Web Scraping Example
func scrapeWorkerPool(urls []string) {
    errorChan := make(chan error, len(urls)) // Separate channel for errors
    for i := 0; i < numWorkers; i++ {
        go func() {
            for url := range urls {
                if err := scrape(url); err != nil {
                    errorChan <- err
                    // Continue processing other URLs
                    continue
                }
            }
        }()
    }
}

Resource Cleanup: Proper cleanup on errors

Resource leaks in parallel processing can quickly escalate into system-wide issues. Proper cleanup is essential.

That wraps up our deep dive into the Fan-In & Fan-Out pattern! Coming up next, we'll explore the Worker Pools concurrency pattern, which we got a glimpse of in this post. Like I said we are moving progressively clearing up dependencies before moving to the next one.

If you found this post helpful, have any questions, or want to share your own experiences with this pattern - I'd love to hear from you in the comments below. Your insights and questions help make these explanations even better for everyone.

If you missed out visual guide to Golang's goroutine and channels check it out here:

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20 '24

#go #programming #learning #tutorial

Stay tuned for more Go concurrency patterns! 🚀

Pipeline Concurrency Pattern in Go: A Comprehensive Visual Guide

Souvik Kar Mahapatra — Sun, 29 Dec 2024 18:32:09 +0000

⚠️ How to go about this series?

1. Run Every Example: Don't just read the code. Type it out, run it, and observe the behavior.
2. Experiment and Break Things: Remove sleeps and see what happens, change channel buffer sizes, modify goroutine counts.
Breaking things teaches you how they work
3. Reason About Behavior: Before running modified code, try predicting the outcome. When you see unexpected behavior, pause and think why. Challenge the explanations.
4. Build Mental Models: Each visualization represents a concept. Try drawing your own diagrams for modified code.

In our previous post, we explored the Generator concurrency pattern, the building blocks of Go's other concurrency patterns. You can give it a read here:

Generator Concurrency Pattern in Go: A Visual Guide

Souvik Kar Mahapatra ・ Dec 25 '24

#go #tutorial #programming #learning

Now, let's look at how these primitives combine to form powerful patterns that solve real-world problems.

In this post we'll cover Pipeline Pattern and will try to visualize them. So let's gear up as we'll be hands on through out the process.

Pipeline Pattern

A pipeline is like an assembly line in a factory, where each stage performs a specific task on the data and passes the result to the next stage.

We build pipelines by connecting goroutines with channels, where each goroutine represents a stage that receives data, processes it, and sends it to the next stage.

Let's implement a simple pipeline that:

Generates numbers
Squares them
Prints the results

// Stage 1: Generate numbers
func generate(nums ...int) <-chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        for _, n := range nums {
            out <- n
        }
    }()
    return out
}

// Stage 2: Square numbers
func square(in <-chan int) <-chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        for n := range in {
            out <- n * n
        }
    }()
    return out
}

// Stage 3: Print numbers
func print(in <-chan int) {
    for n := range in {
        fmt.Printf("%d ", n)
    }
    fmt.Println()
}

func main() {
    // Connect the pipeline
    numbers := generate(2, 3, 4)    // Stage 1
    squares := square(numbers)       // Stage 2
    print(squares)                   // Stage 3
}

✏️ Quick byte

<-chan int denotes a receive-only channel.
A channel of type <-chan int can only be used to receive values, not to send them. This is useful to enforce stricter communication patterns and prevent accidental writes to the channel by the receiver.

chan int This denotes a bidirectional channel.
A channel of type chan int can be used to both send and receive values.

Let's go ahead and visualize the above example:

Here you can see each the building blocks of the pipeline are goroutines following generator pattern. Implies that as soon as the data is ready at any step the next step in the pipeline can start processing it unlike sequential processing.

Error Handling in Pipelines

Core principles should be:

Each stage knows exactly what to do with both good and bad values
Errors can't get lost in the pipeline
Bad values don't cause panics
The error message carries context about what went wrong
The pipeline can be extended with more stages, and they'll all handle errors consistently

let's update our code with some proper error handling.

type Result struct {
    Value int
    Err   error
}

func generateWithError(nums ...int) <-chan Result {
    out := make(chan Result)
    go func() {
        defer close(out)
        for _, n := range nums {
            if n < 0 {
                out <- Result{Err: fmt.Errorf("negative number: %d", n)}
                return
            }
            out <- Result{Value: n}
        }
    }()
    return out
}

func squareWithError(in <-chan Result) <-chan Result {
    out := make(chan Result)
    go func() {
        defer close(out)
        for r := range in {
            if r.Err != nil {
                out <- r  // Forward the error
                continue
            }
            out <- Result{Value: r.Value * r.Value}
        }
    }()
    return out
}

func main() {
    // Using pipeline with error handling
    for result := range squareWithError(generateWithError(2, -3, 4)) {
        if result.Err != nil {
            fmt.Printf("Error: %v\n", result.Err)
            continue
        }
        fmt.Printf("Result: %d\n", result.Value)
    }
}

Why Use Pipeline Pattern?

Let's take an example to understand better, we have a data processing workflow that follows the pipeline pattern as shown below.

Each stage in a pipeline operates independently, communicating only through channels. This enables several benefit:

👉 Each stage can be developed, tested, and modified independently
👉 Changes to one stage's internals don't affect other stages
👉 Easy to add new stages or modify existing ones
👉 Clear separation of concerns

Pipeline patterns naturally enable parallel/concurrent processing. Each stage can process different data simultaneously as soon as the data is available.

And the best part? We can run multiple instance of each stage (workers) for more concurrent requirements like so:

🤔💡 Hey but isn't that the Fan-In and Fan-Out Concurrency Pattern?

Bingo! Good catch right there. It is indeed a Fan-Out, Fan-In pattern, which is a specific type of pipeline pattern. We are going to cover it in details in out next post so fret not ;)

Real world use case

processing images in a pipeline

type Image struct {
    Data   []byte
    Format string
}

// Stage 1: Load images
func loadImages(filenames ...string) <-chan Image {
    out := make(chan Image)
    go func() {
        defer close(out)
        for _, f := range filenames {
            data, _ := os.ReadFile(f)
            out <- Image{Data: data, Format: filepath.Ext(f)}
        }
    }()
    return out
}

// Stage 2: Resize images
func resize(in <-chan Image) <-chan Image {
    out := make(chan Image)
    go func() {
        defer close(out)
        for img := range in {
            // Simulate resize operation
            resizedData := img.Data // In reality, you'd resize here
            out <- Image{Data: resizedData, Format: img.Format}
        }
    }()
    return out
}

// Stage 3: Save images
func save(in <-chan Image) <-chan string {
    out := make(chan string)
    go func() {
        defer close(out)
        for img := range in {
            filename := fmt.Sprintf("resized%s", img.Format)
            // Simulate save operation
            out <- fmt.Sprintf("Saved: %s", filename)
        }
    }()
    return out
}

or something as complicated as log processing pipeline

Pipeline scaling patterns

Horizontal Scaling (Fan-Out, Fan-In)

This pattern is ideal for CPU-bound operations where work can be processed independently. The pipeline distributes work across multiple workers and then recombines the results. This is particularly effective when:

Processing is CPU-intensive (data transformations, calculations)
Tasks can be processed independently
You have multiple CPU cores available

Buffered Pipeline

This pattern helps manage speed mismatches between pipeline stages. The buffer acts as a shock absorber, allowing fast stages to work ahead without being blocked by slower stages. This is useful when:

Different stages have varying processing speeds
You want to maintain steady throughput
Memory usage for buffering is acceptable
You need to handle burst processing

Batched Processing

This pattern optimizes I/O-bound operations by grouping multiple items into a single batch. Instead of processing items one at a time, it collects them into groups and processes them together. This is effective when:

You're working with external systems (databases, APIs)
Network round-trips are expensive
The operation has significant fixed overhead per request
You need to optimize throughput over latency

Each of these patterns can be combined as needed. For example, you might use batched processing with horizontal scaling, where multiple workers each process batches of items. The key is understanding your bottlenecks and choosing the appropriate pattern to address them.

That wraps up our deep dive into the Generator pattern! Coming up next, we'll explore the Pipeline concurrency pattern, where we'll see how to chain our generators together to build powerful data processing flows.

If you found this post helpful, have any questions, or want to share your own experiences with generators - I'd love to hear from you in the comments below. Your insights and questions help make these explanations even better for everyone.

If you missed out visual guide to Golang's goroutine and channels check it out here:

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20 '24

#go #programming #learning #tutorial

Stay tuned for more Go concurrency patterns! 🚀

Generator Concurrency Pattern in Go: A Visual Guide

Souvik Kar Mahapatra — Wed, 25 Dec 2024 00:25:34 +0000

⚠️ How to go about this series?

1. Run Every Example: Don't just read the code. Type it out, run it, and observe the behavior.
2. Experiment and Break Things: Remove sleeps and see what happens, change channel buffer sizes, modify goroutine counts.
Breaking things teaches you how they work
3. Reason About Behavior: Before running modified code, try predicting the outcome. When you see unexpected behavior, pause and think why. Challenge the explanations.
4. Build Mental Models: Each visualization represents a concept. Try drawing your own diagrams for modified code.

In our previous post, we explored the basics of goroutines and channels, the building blocks of Go's concurrency. Read here:

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20

#go #programming #learning #tutorial

Now, let's look at how these primitives combine to form powerful patterns that solve real-world problems.

In this post we'll cover Generator Pattern and will try to visualize them. So let's gear up as we'll be hands on through out the process.

Generator Pattern

A generator is like a fountain that continuously produces values that we can consume whenever needed.

In Go, it's a function that produces a stream of values and sends them through a channel, allowing other parts of our program to receive these values on demand.

Let's look at an example:

// generateNumbers creates a generator that produces numbers from 1 to max
func generateNumbers(max int) chan int {
    // Create a channel to send numbers
    out := make(chan int)

    // Launch a goroutine to generate numbers
    go func() {
        // Important: Always close the channel when done
        defer close(out)

        for i := 1; i <= max; i++ {
            out <- i  // Send number to channel
        }
    }()

    // Return channel immediately
    return out
}

// Using the generator
func main() {
    // Create a generator that produces numbers 1-5
    numbers := generateNumbers(5)

    // Receive values from the generator
    for num := range numbers {
        fmt.Println("Received:", num)
    }
}

In this example, our generator function does three key things:

Creates a channel to send values
Launches a goroutine to generate values
Returns the channel immediately for consumers to use

Why Use Generators?

Separate value production from consumption
Generate values on-demand (lazy evaluation)
Can represent infinite sequences without consuming infinite memory
Allow concurrent production and consumption of values

Real-world Use Case

Reading large files line by line:

func generateLines(filename string) chan string {
    out := make(chan string)
    go func() {
        defer close(out)
        file, err := os.Open(filename)
        if err != nil {
            return
        }
        defer file.Close()

        scanner := bufio.NewScanner(file)
        for scanner.Scan() {
            out <- scanner.Text()
        }
    }()
    return out
}

Now you might be thinking, what's so special about it? we can do the same like generating sequence of data or read line by line without goroutines. Isn't it an overkill? Let's try to visualize both cases:

Without the goroutines

// Traditional approach
func getNumbers(max int) []int {
    numbers := make([]int, max)
    for i := 1; i <= max; i++ {
        numbers[i-1] = i
        // Imagine some heavy computation here
        time.Sleep(100 * time.Millisecond)
    }
    return numbers
}

Here you have to wait for everything to be ready before you can start processing.

With goroutines

// Generator approach
func generateNumbers(max int) chan int {
    out := make(chan int)
    go func() {
        defer close(out)
        for i := 1; i <= max; i++ {
            out <- i
            // Same heavy computation
            time.Sleep(100 * time.Millisecond)
        }
    }()
    return out
}

You can start processing the data while the data is still being generated.

Key Benefits of Generator Pattern:

Non-Blocking Execution: Generation and processing happen simultaneously
Memory Efficiency: Can generate and process one value at a time, no need to store in the memory right away
Infinite Sequences: Can generate infinite sequences without memory issues
Backpressure Handling: If your consumer is slow, the generator naturally slows down (due to channel blocking), preventing memory overload.

// Generator naturally handles slow consumers (backpressure handling)
for line := range generateLines(bigFile) {
    // Take our time processing each line
    // Generator won't overwhelm us with data
    processSlowly(line)
}

Common Pitfalls and Solutions

Forgetting to Close Channels

// Wrong ❌
func badGenerator() chan int {
    out := make(chan int)
    go func() {
        for i := 1; i <= 5; i++ {
            out <- i
        }
        // Channel never closed!
    }()
    return out
}

// Right ✅
func goodGenerator() chan int {
    out := make(chan int)
    go func() {
        defer close(out)  // Always close when done
        for i := 1; i <= 5; i++ {
            out <- i
        }
    }()
    return out
}

Not Handling Errors

// Better approach with error handling
func generateWithErrors() (chan int, chan error) {
    out := make(chan int)
    errc := make(chan error, 1)  // Buffered channel for error

    go func() {
        defer close(out)
        defer close(errc)

        for i := 1; i <= 5; i++ {
            if i == 3 {
                errc <- fmt.Errorf("error at number 3")
                return
            }
            out <- i
        }
    }()

    return out, errc
}

Resource Leaks: When using generators with resources (like files), ensure proper cleanup:

func generateFromFile(filename string) chan string {
    out := make(chan string)
    go func() {
        defer close(out)

        file, err := os.Open(filename)
        if err != nil {
            return
        }
        defer file.Close()  // Important: Close file when done

        scanner := bufio.NewScanner(file)
        for scanner.Scan() {
            out <- scanner.Text()
        }
    }()
    return out
}

Stay tuned for more Go concurrency patterns! 🚀

🚀💸 Let's Talk About Open Source Monetization 🚀💸

Souvik Kar Mahapatra — Mon, 23 Dec 2024 10:01:50 +0000

Hey folks 👋,

I came across this amazing resource on open-source monetization: awesome-oss-monetization.

In most conversations I’ve had, there’s this common perception:

Open Source Software = Free

but should it?

What are your thoughts on monetizing open-source software? How often do you consider sponsoring, donating, or contributing? Have you ever thought about paying for OSS?

With many AI startups going open-source-first these days, do you see this as a sustainable model? I'd love to hear your experiences, opinions, or examples of monetization done right in the OSS space.

Let’s discuss! 👇

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra — Fri, 20 Dec 2024 00:35:36 +0000

⚠️ How to go about this series?

1. Run Every Example: Don't just read the code. Type it out, run it, and observe the behavior.
2. Experiment and Break Things: Remove sleeps and see what happens, change channel buffer sizes, modify goroutine counts.
Breaking things teaches you how they work
3. Reason About Behavior: Before running modified code, try predicting the outcome. When you see unexpected behavior, pause and think why. Challenge the explanations.
4. Build Mental Models: Each visualization represents a concept. Try drawing your own diagrams for modified code.

This is part 1 of our "Mastering Go Concurrency" series where we'll cover:

How goroutines work and their lifecycle
Channel communication between goroutines
Buffered channels and their use cases
Practical examples and visualizations

We'll start with the basics and progressively move forward developing intuition on how to use them effectively.

It's going to be a bit long, rather very long so gear up.

we'll be hands on through out the process.

Foundations of Goroutines

Let's start with a simple program that downloads multiple files.

package main

import (
    "fmt"
    "time"
)

func downloadFile(filename string) {
    fmt.Printf("Starting download: %s\n", filename)
    // Simulate file download with sleep
    time.Sleep(2 * time.Second)
    fmt.Printf("Finished download: %s\n", filename)
}

func main() {
    fmt.Println("Starting downloads...")

    startTime := time.Now()

    downloadFile("file1.txt")
    downloadFile("file2.txt")
    downloadFile("file3.txt")

    elapsedTime := time.Since(startTime)

    fmt.Printf("All downloads completed! Time elapsed: %s\n", elapsedTime)
}

The program takes 6 seconds total because each 2-second download must complete before the next one starts. Let's visualize this:

We can lower this time, let's modify our program to use go routines:

notice: go keyword before function call

package main

import (
    "fmt"
    "time"
)

func downloadFile(filename string) {
    fmt.Printf("Starting download: %s\n", filename)
    // Simulate file download with sleep
    time.Sleep(2 * time.Second)
    fmt.Printf("Finished download: %s\n", filename)
}

func main() {
    fmt.Println("Starting downloads...")

    // Launch downloads concurrently
    go downloadFile("file1.txt")
    go downloadFile("file2.txt")
    go downloadFile("file3.txt")

    fmt.Println("All downloads completed!")
}

wait what? nothing got printed? Why?

Let's visualize this to understand what might be happening.

from the above visualization, we understand that the main function exists before the goroutines are finished. One observation is that all goroutine's lifecycle is dependent on the main function.

Note: main function in itself is a goroutine ;)

To fix this, we need a way to make the main goroutine wait for the other goroutines to complete. There are several ways to do this:

wait for few seconds (hacky way)
Using WaitGroup (proper way, next up)
Using channels (we'll cover this down below)

Let's wait for few seconds for the go routines to complete.

package main

import (
    "fmt"
    "time"
)

func downloadFile(filename string) {
    fmt.Printf("Starting download: %s\n", filename)
    // Simulate file download with sleep
    time.Sleep(2 * time.Second)
    fmt.Printf("Finished download: %s\n", filename)
}

func main() {
    fmt.Println("Starting downloads...")

    startTime := time.Now() // Record start time

    go downloadFile("file1.txt")
    go downloadFile("file2.txt")
    go downloadFile("file3.txt")

    // Wait for goroutines to finish
    time.Sleep(3 * time.Second)

    elapsedTime := time.Since(startTime)

    fmt.Printf("All downloads completed! Time elapsed: %s\n", elapsedTime)
}

Problem with this is, we might not know how much time a goroutine might take. In out case we have constant time for each but in real scenarios we are aware that download time varies.

Comes the `sync.WaitGroup`

A sync.WaitGroup in Go is a concurrency control mechanism used to wait for a collection of goroutines to finish executing.

here let's see this in action and visualize:

package main

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

func downloadFile(filename string, wg *sync.WaitGroup) {
    // Tell WaitGroup we're done when this function exits
    defer wg.Done()

    fmt.Printf("Starting download: %s\n", filename)
    time.Sleep(2 * time.Second)
    fmt.Printf("Finished download: %s\n", filename)
}

func main() {
    fmt.Println("Starting downloads...")

    var wg sync.WaitGroup

    // Tell WaitGroup we're about to launch 3 goroutines
    wg.Add(3)

    go downloadFile("file1.txt", &wg)
    go downloadFile("file2.txt", &wg)
    go downloadFile("file3.txt", &wg)

    // Wait for all downloads to complete
    wg.Wait()

    fmt.Println("All downloads completed!")
}

Let's visualize this and understand the working of sync.WaitGroup:

Counter Mechanism:

WaitGroup maintains an internal counter
wg.Add(n) increases the counter by n
wg.Done() decrements the counter by 1
wg.Wait() blocks until the counter reaches 0

Synchronization Flow:

Main goroutine calls Add(3) before launching goroutines
Each goroutine calls Done() when it completes
Main goroutine is blocked at Wait() until counter hits 0
When counter reaches 0, program continues and exits cleanly

Common pitfalls to avoid

// DON'T do this - Add after launching goroutine
go downloadFile("file1.txt", &wg)
wg.Add(1)  // Wrong order!

// DON'T do this - Wrong count
wg.Add(2)  // Wrong number!
go downloadFile("file1.txt", &wg)
go downloadFile("file2.txt", &wg)
go downloadFile("file3.txt", &wg)

// DON'T do this - Forgetting Done()
func downloadFile(filename string, wg *sync.WaitGroup) {
    // Missing Done() - WaitGroup will never reach zero!
    fmt.Printf("Downloading: %s\n", filename)
}

Channels

So we got a good understanding of how the goroutines work. No how does two go routines communicate? This is where channel comes in.

Channels in Go are a powerful concurrency primitive used for communication between goroutines. They provide a way for goroutines to safely share data.

Think of channels as pipes: one goroutine can send data into a channel, and another can receive it.

here are some properties:

Channels are blocking by nature.
A send to channel operation ch <- value blocks until some other goroutine receives from the channel.
A receive from channel operation <-ch blocks until some other goroutine sends to the channel.

package main

import "fmt"

func main() {
    // Create a channel
    ch := make(chan string)

    // Send value to channel (this will block main)
    ch <- "hello"  // This line will cause deadlock!

    // Receive value from channel
    msg := <-ch
    fmt.Println(msg)
}

why will ch <- "hello" cause deadlock? Since channels are blocking in nature and here we are passing "hello" it'll block the main goroutine until there is a receiver and since there is not receiver so it'll be stuck.

Let's fix this by adding a goroutine

package main

import "fmt"

func main() {
    ch := make(chan string)

    // sender in separate goroutine
    go func() {
        ch <- "hello"  // will no longer block the main goroutine
    }()

    // Receive in main goroutine
    msg := <-ch  // This blocks until message is received
    fmt.Println(msg)
}

Let's visualize this:

This time message is being sent from different goroutine so the main is not blocked while sending to channel so it moves to msg := <-ch where it blocks the main goroutine to until it receives the message.

Fixing main not waiting for others issue using channel

Now let's use channel to fix the file downloader issue (main doesn't wait for others to finish).

package main

import (
    "fmt"
    "time"
)

func downloadFile(filename string, done chan bool) {
    fmt.Printf("Starting download: %s\n", filename)
    time.Sleep(2 * time.Second)
    fmt.Printf("Finished download: %s\n", filename)

    done <- true // Signal completion
}

func main() {
    fmt.Println("Starting downloads...")

    startTime := time.Now() // Record start time

    // Create a channel to track goroutine completion
    done := make(chan bool)

    go downloadFile("file1.txt", done)
    go downloadFile("file2.txt", done)
    go downloadFile("file3.txt", done)

    // Wait for all goroutines to signal completion
    for i := 0; i < 3; i++ {
        <-done // Receive a signal for each completed goroutine
    }

    elapsedTime := time.Since(startTime)
    fmt.Printf("All downloads completed! Time elapsed: %s\n", elapsedTime)
}

visualizing it:

Let's do a dry run to have a better understanding:

Program Start:

Main goroutine creates done channel
Launches three download goroutines
Each goroutine gets a reference to the same channel

Download Execution:

All three downloads run concurrently
Each takes 2 seconds
They might finish in any order

Channel Loop:

Main goroutine enters loop: for i := 0; i < 3; i++
Each <-done blocks until a value is received
The loop ensures we wait for all three completion signals

Loop Behavior:

Iteration 1: Blocks until first download completes
Iteration 2: Blocks until second download completes
Iteration 3: Blocks until final download completes

Order of completion doesn't matter!

Observations:
⭐ Each send (done <- true) has exactly one receive (<-done)
⭐ Main goroutine coordinates everything through the loop

How two goroutines can communicate?

We have already seen how two goroutines can communicate. When? All this while. Let's not forget main function is also a goroutine.

package main

import (
    "fmt"
    "time"
)

func sender(ch chan string, done chan bool) {
    for i := 1; i <= 3; i++ {
        ch <- fmt.Sprintf("message %d", i)
        time.Sleep(100 * time.Millisecond)
    }
    close(ch) // Close the channel when done sending
    done <- true
}

func receiver(ch chan string, done chan bool) {
        // runs until the channel is closed
    for msg := range ch {
        fmt.Println("Received:", msg)
    }
    done <- true
}

func main() {
    ch := make(chan string)
    senderDone := make(chan bool)
    receiverDone := make(chan bool)

    go sender(ch, senderDone)
    go receiver(ch, receiverDone)

    // Wait for both sender and receiver to complete
    <-senderDone
    <-receiverDone

    fmt.Println("All operations completed!")
}

Let's visualize this and dry run this:

dry run:

Program Start (t=0ms)

The main goroutine initializes three channels:
- ch: for messages.
- senderDone: to signal sender completion.
- receiverDone: to signal receiver completion.
The main goroutine launches two goroutines:
- sender.
- receiver.
The main goroutine blocks, waiting for a signal from <-senderDone.

First Message (t=1ms)

The sender sends "message 1" to the ch channel.
The receiver wakes up and processes the message:
- Prints: "Received: message 1".
The sender sleeps for 100ms.

Second Message (t=101ms)

The sender wakes up and sends "message 2" to the ch channel.
The receiver processes the message:
- Prints: "Received: message 2".
The sender sleeps for another 100ms.

Third Message (t=201ms)

The sender wakes up and sends "message 3" to the ch channel.
The receiver processes the message:
- Prints: "Received: message 3".
The sender sleeps for the final time.

Channel Close (t=301ms)

The sender finishes sleeping and closes the ch channel.
The sender sends a true signal to the senderDone channel to indicate completion.
The receiver detects that the ch channel has been closed.
The receiver exits its for-range loop.

Completion (t=302-303ms)

The main goroutine receives the signal from senderDone and stops waiting.
The main goroutine begins waiting for a signal from receiverDone.
The receiver sends a completion signal to the receiverDone channel.
The main goroutine receives the signal and prints:
- "All operations completed!".
The program exits.

Buffered Channels

Why do we need buffered channels?
Unbuffered channels block both the sender and receiver until the other side is ready. When high-frequency communication is required, unbuffered channels can become a bottleneck as both goroutines must pause to exchange data.

Buffered channels properties:

FIFO (First In, First Out, similar to queue)
Fixed size, set at creation
Blocks sender when the buffer is full
Blocks receiver when the buffer is empty

We see it in action:

package main

import (
    "fmt"
    "time"
)

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

    // Send two messages (won't block because buffer has space)
    ch <- "first"
    fmt.Println("Sent first message")
    ch <- "second"
    fmt.Println("Sent second message")

    // Try to send a third message (this would block!)
    // ch <- "third"  // Uncomment to see blocking behavior

    // Receive messages
    fmt.Println(<-ch)  // "first"
    fmt.Println(<-ch)  // "second"
}

output (before uncommenting the ch<-"third")

Why didn't it block the main goroutine?

A buffered channel allows sending up to its capacity without blocking the sender.
The channel has a capacity of 2, meaning it can hold two values in its buffer before blocking.
The buffer is already full with "first" and "second." Since there’s no concurrent receiver to consume these values, the send operation blocks indefinitely.
Because the main goroutine is also responsible for sending and there are no other active goroutines to receive values from the channel, the program enters a deadlock when trying to send the third message.

Uncommenting the third message leads to deadlock as the capacity is full now and the 3rd message will block until buffer frees up.

When to use Buffered channels vs Unbuffered channels

Aspect	Buffered Channels	Unbuffered Channels
Purpose	For decoupling sender and receiver timing.	For immediate synchronization between sender and receiver.
When to Use	- When the sender can proceed without waiting for receiver.	- When sender and receiver must synchronize directly.
	- When buffering improves performance or throughput.	- When you want to enforce message-handling immediately.
Blocking Behavior	Blocks only when buffer is full.	Sender blocks until receiver is ready, and vice versa.
Performance	Can improve performance by reducing synchronization.	May introduce latency due to synchronization.
Example Use Cases	- Logging with rate-limited processing.	- Simple signaling between goroutines.
	- Batch processing where messages are queued temporarily.	- Hand-off of data without delay or buffering.
Complexity	Requires careful buffer size tuning to avoid overflows.	Simpler to use; no tuning needed.
Overhead	Higher memory usage due to the buffer.	Lower memory usage; no buffer involved.
Concurrency Pattern	Asynchronous communication between sender and receiver.	Synchronous communication; tight coupling.
Error-Prone Scenarios	Deadlocks if buffer size is mismanaged.	Deadlocks if no goroutine is ready to receive or send.

Key takeaways

Use Buffered Channels if:

You need to decouple the timing of the sender and receiver.
Performance can benefit from batching or queuing messages.
The application can tolerate delays in processing messages when the buffer is full.

Use Unbuffered Channels if:

Synchronization is critical between goroutines.
You want simplicity and immediate hand-off of data.
The interaction between sender and receiver must happen instantaneously.

These fundamentals set the stage for more advanced concepts. In our upcoming posts, we'll explore:

Concurrency Patterns
Mutex and Memory Synchronization

Stay tuned as we continue building our understanding of Go's powerful concurrency features!

Arrays vs Slices in Go: Understanding the "under the hood" functioning visually

Souvik Kar Mahapatra — Mon, 16 Dec 2024 04:27:00 +0000

Have you ever tried packing for a trip without knowing how long you'll be there? That's precisely what happens when we store data in Go. Sometimes, like when packing for a weekend trip, we know exactly how many things we need to store; other times, such as, when packing for a trip where we say, "I'll return when I'm ready," we don't.

Let's take a deep dive into the world of Go arrays and slice internals through simple illustrations. We will look into:

Memory layouts
Growth mechanisms
Reference semantics
Performance implications

By the end of this read, you'll be able to understand when to use arrays versus when to use slices with the help of real world examples and memory diagrams

Arrays: The Fixed-Size Container 📦

Think of an array as a single block of memory where each element sits next to each other, like a row of perfectly arranged boxes.

When you declare var numbers [5]int, Go reserves exactly enough contiguous memory to hold 5 integers, no more, no less.

Since they have contiguous fixed memory it can't be sized during runtime.

func main() {
    // Zero-value initialization
    var nums [3]int    // Creates [0,0,0]

    // Fixed size
    nums[4] = 1       // Runtime panic: index out of range

    // Sized during compilation
    size := 5
    var dynamic [size]int  // Won't compile: non-constant array bound
}

The size is part of the array's type. This means [5]int and [6]int are completely different types, just like int and string are different.

func main() {
    // Different types!
    var a [5]int
    var b [6]int

    // This won't compile
    a = b // compile error: cannot use b (type [6]int) as type [5]int

    // But this works
    var c [5]int
    a = c // Same types, allowed
}

Why Array is Copy By Default?

When you assign or pass arrays in Go, they create copies by default. This ensures data isolation and prevents unexpected mutations.

func modifyArrayCopy(arr [5]int) {
    arr[0] = 999    // Modifies the copy, not original
}

func modifyArray(arr *[5]int){
    arr[0] = 999  // Modifies the original, since reference is passed
}

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

    modifyArrayCopy(numbers)
    fmt.Println(numbers[0])  // prints 1, not 999

    modifyArray(&numbers)
    fmt.Println(numbers[0])  // prints 999
}

Slices

Alright so you can't do var dynamic [size]int to set dynamic size, this is where slice comes into play.

Slices under the hood

The magic lies in how it maintains this flexibility while keeping operations fast.

Every slice in Go consists of three critical components:

type slice struct {
    array unsafe.Pointer // Points to the actual data
    len   int           // Current number of elements
    cap   int           // Total available space
}

What's unsafe.Pointer??

The unsafe.Pointer is Go's way of handling raw memory addresses without type safety constraints. It's "unsafe" because it bypasses Go's type system, allowing direct memory manipulation.

Think of it as Go's equivalent to C's void pointer.

What's that array?

When you create a slice, Go allocates a contiguous block of memory in the heap (unlike arrays) called backing array. Now the array in slice struct points to the start of that memory block.

The array field uses unsafe.Pointer because:

It needs to point to raw memory without type information
It allows Go to implement slices for any type T without generating separate code for each type.

The dynamic mechanism of slice

let's try developing intuition for the actual algorithm under the hood.

If we go by intuition we can do two things:

We could set aside space so large and can use it as and when required
pros: Handles growing needs till a certain point
cons: Memory wastage, practically might hit limit
We could set a random size initially and as the elements are appended we can reallocate the memory on each append
pros: Handles the previous case, can grow as per the need
cons: reallocation is expensive and on every append it's going to get worst

We cannot avoid the reallocation as when the capacity hits one needs to grow. We can minimize the reallocation so that the subsequent inserts/appends cost is constant (O(1)). This is called amortized cost.

How can we go about it?

till Go version v1.17 following formula was being used:

// Old growth pattern
capacity = oldCapacity * 2  // Simple doubling

from Go version v1.18:

// New growth pattern
if capacity < 256 {
    capacity = capacity * 2
} else {
    capacity = capacity + capacity/4  // 25% growth
}

since doubling a large slice is waste of memory so as the slice size increases the growth factor is decreased.

Let's get a better understanding from usage perspective

numbers := make([]int, 3, 5) // length=3 capacity

// Memory Layout after creation:
Slice Header:
{
    array: 0xc0000b2000    // Example memory address
    len:   3
    cap:   5
}

Backing Array at 0xc0000b2000:
[0|0|0|unused|unused]

let's add some elements to our slice

numbers = append(numbers, 10)

Since we have capacity (5) > length (3), Go:

Uses existing backing array
Places 10 at index 3
Increases length by 1

// Memory Layout after first append:
Slice Header:
{
    array: 0xc0000b2000    // Same memory address!
    len:   4               // Increased
    cap:   5               // Same
}

Backing Array at 0xc0000b2000:
[0|0|0|10|unused]

Let's hit the limit

numbers = append(numbers, 20)  // Uses last slot
numbers = append(numbers, 30)  // Needs to grow!

Oops! Now we have hit our capacity, we need to grow. Here is what happens:

Calculates new capacity (oldCap < 256, so doubles to 10)
Allocates new backing array (a new memory address say, 300)
Copies existing elements to new backing array
Adds new element
Updates slice header

// Memory Layout after growth:
Old Backing Array at 0xc0000b2000:
[0|0|0|10|20]          // Will be garbage collected

New Slice Header:
{
    array: 0xc0000c8000    // New memory address!
    len:   6
    cap:   10              // Doubled
}

New Backing Array at 0xc0000c8000:
[0|0|0|10|20|30|unused|unused|unused|unused]

what happens if it's a large slice?

// Create slice with 256 elements
big := make([]int, 256)

// Append one more element
big = append(big, 1)

Since capacity is 256, Go uses the post-1.18 growth formula:

New capacity = oldCap + oldCap/4
256 + 256/4 = 256 + 64 = 320

// Memory Layout after growth
New Slice Header:
{
    array: 0xc0000c8000    // New memory address
    len:   257
    cap:   320             // Grew by 25%
}

Why reference semantics?

Performance: Copying large data structures is expensive
Memory efficiency: Avoiding unnecessary data duplication
Enabling shared views of data: Multiple slices can reference the same backing array

original := []int{10, 20, 30, 40, 50}
slice1 := original[1:3]    // [20, 30]
slice2 := original[2:4]    // [30, 40]

slice1[1] = 999           // Changes 30 to 999

this is how the slice headers will look:

Original Slice Header:
{
    array: 0xc0000b6000
    len:   5
    cap:   5
}

Slice1 Header:
{
    array: 0xc0000b6008    // Points to second element
    len:   2
    cap:   4               // Until end of original
}

Slice2 Header:
{
    array: 0xc0000b6010    // Points to third element
    len:   2
    cap:   3               // Until end of original
}

Backing Array at 0xc0000b6000:
[10|20|999|40|50]         // 999 is visible to all slices!

Usage patterns and cautions for slice

Accidental updates

since slice uses reference semantics, it doesn't create copies which might lead to accidental mutation to original slice if not being mindful.

original := []int{1, 2, 3, 4, 5}
slice1 := original[1:3]
slice2 := original[2:4]
slice1[1] = 999
// Now slice2[0] is also 999!

Expensive append operation

s := make([]int, 0)
for i := 0; i < 10000; i++ {
    // Each append might cause reallocation
    s = append(s, i)
}

// Better approach:
s := make([]int, 0, 10000)  // Pre-allocate capacity

Copy vs Append

// Expensive: Creates new backing array and copies from old
s = append(s, newElement...)

// More efficient for known sizes:
dest := make([]int, len(source))
copy(dest, source)

Let's wrap this up with a clear choice guide:

🎯 Choose Arrays When:

You know the exact size upfront
Working with small, fixed data (like coordinates, RGB values)
Performance is critical and data fits on stack
You want type safety with size

🔄 Choose Slices When:

Size might change
Working with dynamic data
Need multiple views of same data
Processing streams/collections

📚 Check out notion-to-md project! It's a tool that converts Notion pages to Markdown, perfect for content creators and developers. Join our discord community.

Testing REST APIs using Jest and Supertest ✅

Souvik Kar Mahapatra — Sun, 15 Dec 2024 20:06:43 +0000

originally published: souvikinator.xyz

Here’s how to set up unit tests for API endpoints.

We’ll be using the following NPM packages:

Express for the server (any other framework can be used)
Jest
Supertest

VS Code extension using:

Jest
Jest Runner

Installing dependencies

npm install express

npm install -D jest supertest

Here is what the directory structure looks like:

and lets not forget package.json

{
  "name": "api-unit-testing",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "jest api.test.js",
    "start":"node server.js"
  },
  "keywords": [],
  "author": "",
  "license": "ISC",
  "dependencies": {
    "express": "^4.18.1"
  },
  "devDependencies": {
    "jest": "^28.1.2",
    "supertest": "^6.2.3"
  }
}

Creating a simple express server

An express server that accepts POST requests with a body and title on the /post endpoint. If either one is missing, status 400 Bad Request is returned.

// app.js
const express = require("express");
const app = express();

app.use(express.json());

app.post("/post", (req, res) => {
  const { title, body } = req.body;

  if (!title || !body)
    return res.sendStatus(400).json({ error: "title and body is required" });

  return res.sendStatus(200);
});

module.exports = app;

const app = require("./app");
const port = 3000;

app.listen(port, () => {
  console.log(`http://localhost:${port} 🚀`);
});

The express app is exported for use with supertest.

Creating test file

// api.test.js
const supertest = require("supertest");
const app = require("./app"); // express app

describe("Creating post", () => {
    // test cases goes here
});

Supertest takes care of running the server and making requests for us, while we focus on testing.

The express app is passed to the supertest agent and it binds express to a random available port. Then we can make an HTTP request to the desired API endpoint and compare its response status with our expectation:

 const response = await supertest.agent(app).post("/post").send({
        title: "Awesome post",
    body: "Awesome post body",
 });

We’ll create test for 3 cases:

When both title and body are provided

  test("creating new post when both title and body are provided", async () => {
    const response = await supertest.agent(app).post("/post").send({
      title: "Awesome post",
      body: "Awesome post body",
    });

        // comparing response status code with expected status code
    expect(response.statusCode).toBe(200);
  });

When either of them is missing

  test("creating new post when either of the data is not provided", async () => {
    const response = await supertest.agent(app).post("/post").send({
      title: "Awesome post",
    });

    expect(response.statusCode).toBe(400);
  });

When both of them is missing

  test("creating new post when no data is not provided", async () => {
    const response = await supertest.agent(app).post("/post").send();

    expect(response.statusCode).toBe(400);
  });

and the final code should look like:

const supertest = require("supertest");
const app = require("./app"); // express app

describe("Creating post", () => {

  test("creating new post when both title and body are provided", async () => {
    const response = await supertest.agent(app).post("/post").send({
      title: "Awesome post",
      body: "Awesome post body",
    });
    expect(response.statusCode).toBe(200);
  });

  test("creating new post when either of the data is not provided", async () => {
    const response = await supertest.agent(app).post("/post").send({
      title: "Awesome post",
    });
    expect(response.statusCode).toBe(400);
  });

  test("creating new post when no data is not provided", async () => {
    const response = await supertest.agent(app).post("/post").send();
    expect(response.statusCode).toBe(400);
  });
});

Running Test

Run test using following command:

npm run test

If using VS Code extensions like jest and jest runner then it’ll do the work for you.

And this is how we can easily test API endpoints. 💪

The Wardrobe Strategy: How Shopping in Bulk Explains Amortized Cost

Souvik Kar Mahapatra — Fri, 13 Dec 2024 07:36:22 +0000

originally written at: souvikinator.xyz

Imagine you just landed your dream job, and you need 12 new shirts for your work wardrobe. You have two options:

Option 1

You could buy one $30 shirt each month, spreading the cost over a year.
It feels easier on your wallet right now, But by the end of the year, you'll have spent $360
Let's not forget the twelve separate trips to the store 😅

Option 2

You could buy all 12 shirts at once. The store offers a bulk discount of $25 per shirt.
Yes, it's a bigger upfront cost of $300, but you save $60 overall. 3. And again let's not forget the extra shopping trips.

This simple clothing dilemma illustrates one of the most powerful concepts in computer science: amortized cost analysis.

Just as smart shoppers think about long-term savings rather than just the immediate cost, efficient software systems often make similar trade-offs: investing resources upfront to gain better performance over time.

What's amortized cost?

This "averaging out" effect (learnt previously) is what computer scientists call amortized cost analysis.

Instead of looking at what each individual operation costs, we consider the total cost spread across all operations. Sometimes, like with our bulk shirt purchase, paying more upfront leads to significant savings over time.

But when do we know we need amortized analysis?

Growing Collections

"Pay a little extra now to avoid paying a lot more later"

Real-world example: HashMap doubles its size and rehashes elements when it's about 75% full

Resource Management

"Invest in bulk upfront to make individual operations cheaper"

Real-world example: Database connection pools create several connections upfront rather than making a new connection for each request

Performance Optimization

"Regular maintenance keeps everything running smoothly"

Spend time organizing books properly (balancing a B-tree)
Takes extra effort during insertion (rebalancing operations)
But finding any book remains consistently fast (O(log n) search)
Without organization, finding a book could require checking every shelf (O(n) search)

Understanding using simple maths

Let's take the dynamic array example and see how it plays out.

Approach 1: Grow by one

We increase our array size by just one slot each time we ran out of space. For 8 insertions starting with size 4:

First 4 insertions: 1 operation each = 4 operations
5th insertion: Create new array (size 5) + Copy 4 elements + Insert = 6 operations
6th insertion: Create new array (size 6) + Copy 5 elements + Insert = 7 operations
7th insertion: Create new array (size 7) + Copy 6 elements + Insert = 8 operations
8th insertion: Create new array (size 8) + Copy 7 elements + Insert = 9 operations

Total cost = 4 + 6 + 7 + 8 + 9 = 34 operations
Cost per operation = 34/8 ≈ 4.25 operations

Approach 2: Doubling strategy

First 4 insertions: 1 operation each = 4 operations
5th insertion: Create new array (size 8) + Copy 4 elements + Insert = 6 operations
Next 3 insertions: 1 operation each = 3 operations
Total cost = 4 + 6 + 3 = 13 operations
Cost per operation = 13/8 ≈ 1.6 operations

The Long-Term Impact:

If we extend this to inserting 1000 elements:

Grow-by-one approach:

Each time we're full, we need to copy all previous elements
Total operations ≈ n + (n * (n-1))/2
For n=1000, that's about 499,500 operations!

Doubling approach:

We double at sizes 4, 8, 16, 32, 64, 128, 256, 512
Total operations ≈ n + n = 2n
For n=1000, that's about 2,000 operations

This is why we say doubling gives us O(1) amortized time - even as n grows very large, the cost per operation stays constant.

Common Misconceptions

"Amortized Cost Means Average Cost"

Not quite. Average cost considers the typical case, while amortized cost gives a guaranteed bound over any sequence of operations.

Key Takeaways

Think Long-Term: Amortized analysis helps us understand the true cost of operations over time, not just individual operations. Sometimes paying more upfront leads to better overall performance.

When to Use It:

Your data structure needs to grow dynamically
You're optimizing for overall performance rather than individual operations
You have expensive operations that enable faster future operations

The Big Picture: Amortized analysis teaches us that optimization isn't just about making each operation fast - sometimes it's better to occasionally do more work to enable many fast operations later.

So there you have it! The next time someone asks you why you're buying 12 shirts at once or hoarding database connections like they're limited edition Pokémon cards, you can confidently explain that you're not just being quirky – you're implementing amortized analysis in real life!

Know The Web: SOP (Same Origin Policy)

Souvik Kar Mahapatra — Mon, 22 Feb 2021 19:29:14 +0000

Hey folks! in this post we'll learn about SOP (Same Origin Policy).

Before understanding what SOP is and why we need it, let's ask a question

What will happens if

If I try to access or modify an iframe contents using JS? Let's find out,

<body>
<iframe name="my_frame" src="http://google.com/webhp?igu=1"></iframe>
</body>

and open it in your browser. Now head over to the dev tools console and try accessing it using JS like so:

frames.my_name.document

Boom! we go an error:

VM1678:1 Uncaught DOMException: Blocked a frame with origin "null" from accessing a cross-origin frame.
at :1:17

notice, it says blocked frame from accessing cross-origin frame i.e since the origin inside the iframe and the origin of our website doesn't match the browser won't allow us to access the iframe contents.

Same Origin Policy

MDN Docs says:

The same-origin policy is a critical security mechanism that restricts how a document or script loaded from one origin can interact with a resource from another origin. It helps isolate potentially malicious documents, reducing possible attack vectors.

Okay so what they say is pretty clear but what is origin? How do we know whether two origins are the same or not?

Origin is the combination of protocols/scheme, hostname and port number.

now, not to get confused with URL and origin, both are different. Head over to http://example.com/abc/def. Now in the console do the following:

it's difficult to draw curly brackets 😅 but now you can see the difference between URL and Origin.

Here is an example to understand same-origin and cross-origin

origin-1	origin-2	cross-origin or same-origin
http://example.com:80/	http://example.com/	same-origin as 80 is default port number for http
	http://example.com:80/	same-origin as a port, protocol, and hostname are same
	https://example.co:80/	cross-origin as the protocol differs. Origin-1 has http and origin-2 has https
	http://www.example.com:80/	cross-origin as origin-2 is subdomain(www)
	http://example.net:80/	cross-origin as the top-level domain(.com,.net) in hostname do not match

from the above table, we can conclude that for two origins to be the same their protocols,hostname, and port number(if mentioned) have to be the same. Try testing the above examples using location.href and location.origin in the browser console.

We can explain why we were unable to access the content inside iframe in the very first question we asked. As the origin of our webpage and that of the website inside the iframe were different. Let's try to access iframe contents when the origin is same, here is a simple node js server:

//index.js
const app=require('express')();
const path=require('path');

app.get('/',(req,res)=>{
   res.sendFile(path.join(__dirname+'/main.html'));
});

app.get("/abc",(req,res)=>{
    res.send("Hi! I am inside iframe.");
});

app.listen(8080,(err)=>{
   if(err) console.log(err);
   console.log(">8080<");
});

and

<!--main.html-->
<body>
    <h1>Hi! I contain an iframe</h1>
    <iframe name="my_local_frame" src="/abc"></iframe>
</body>

after running, head over to http://localhost:8080. we access the iframe content and boom! we get no error.

if we check origin:

Okay, so things are pretty clear now. You may ask, how webpages are able to load external scripts and resources from CDNs, their origin does not match. It should rather block them.

Why would it block it?

SOP's purpose is not to block the dynamic loading of scripts, but to prevent a script from one site to access the data of another site.

Security

Suppose, Same-Origin Policy didn't exist.

Let's say you visit target.com, you log in, you get a valid session cookie & then you leave without logging out.

Next, you visit evil.com which tries to impersonate you & send an evil request to target.com(from your browser). Since you never logged out & you still have a valid session cookie (which follows every request your browser makes to target.com), the target will recognize your browser & (may) accept the evil request. This is called Cross-Site Request Forgery (CSRF). Using this attack, the attacker can access your personal details or may end up changing your account credentials and you are no longer able to log in.

This is where SOP comes into play.
Although the evil request won't be blocked by your browser (it's up to target.com to protect itself against CSRF attacks), the response won't be made available to evil.com.
So even if target.com is misconfigured & falls for a CSRF attack that requests your personal info, for example, SOP won't allow evil.com to see that info.

That's what SOP does and that's all for this post. Feel free to suggest improvements and point out any mistakes :)

Know The Web: HTTP Cookie 🍪

Souvik Kar Mahapatra — Wed, 17 Feb 2021 12:55:21 +0000

In this post, we are going to learn about Cookie certainly not the edible one. We'll discuss cookie properties and security stuff related to HTTP cookies, also create cookie on the way so make sure that you and your patience grab milk and cookie, enjoy the post.

Cookie Time!

While using Facebook, Instagram, or any other services online did you notice that once you logged into these services you don't have to log in when you visit these sites again?
You searched for shoes and the next moment when you visit any site, you get to see ads related to shoes.

Is there some mind-reading stuff going on?

To define, cookies are small chunks of temporary data (key-value pair) in the browser which helps in various functionalities in any web services (as mentioned above). These web services/websites setup cookie into your browser and use for features like managing you session on their service/website, to track you and stuff like that. They can also be used to remember pieces of information that the user previously entered into form fields, such as names, addresses, passwords(not a good idea😅), and payment card numbers.

Now as these websites/web services are able to access the cookie they place in your browser which makes it clear that, "every time you make a request to the website/web service, the cookie is sent to the server along with the request".

🕵️‍♂️ Sherlock mode ON!

Let's head over to a random site and have a look at their cookies. On the way, I'll explain about the properties. So I am heading to motherfuckingwebsite.com. In developer tools open the Application tab and then to cookie > https://mothe....
There you get to see the following:

Those with green underline are options. Name & Value are self explanatory. The rest are what we need to understand.

Domain

Each cookie has a domain pattern to which it belongs and can only be accessed by that specific domain pattern.

If a cookie named cookie-1 is added for .motherfuckingwebsite.com (notice the .) then cookie-1 can be accessed by any subdomain of motherfuckingwebsite.com. Example: cookie-1 can be accessed by the domain motherfuckingwebsite.com as well as its subdomain like www.motherfuckingwebsite.com or www2.motherfuckingwebsite.com and so on.

If a cookie named cookie-2 is added for a subdomain xyz.motherfuckingwebsite.com then it can be only accessed by its subdomain and itself. Example: cookie-2 can be accessed by subdomain xyz.motherfuckingwebsite.com and its subdomain abc.xyz.motherfuckingwebsite.com and so on.

you can read more at RFC2109

Path

Suppose you want to make a cookie accessible to a specific path then this option is used. Will explain in a while.

Expires/Max-age

As I have mentioned right in the start that "cookies are temporary data" i.e they have a validity duration after which they expire. How is validity duration determined? By the web service/website. Whenever a website/web service creates a cookie, it also mentions its lifetime.

HttpOnly, Secure and SameSite will be explained in the security section.

Okay! enough talks. Let's create some cookies, heat up your oven (browser)

👨‍💻 The Client Way

First we'll discuss about creating cookie from the client-side i.e from the browser using JS which is pretty easy.

document.cookie

How about having a look at existing cookie using JS? Just use document.cookie in the console and you'll see the following:

Notice, each cookie is separated by a semicolon(;).

creating simple cookie

document.cookie="itsME=1"

NOTE: Above code doesn't override cookies. It only created a new one.

You can see it's defined for domain motherfuckingwebsite.com now as per the properties we have discussed above, www.motherfuckingwebsite.com should not be able to access the cookie itsME.

and we don't see the cookie that we created hence we verified the properties.

setting up cookie path

How about adding the Path option to our cookie? Let's go...

document.cookie="itsMe=7; path=/test";

The above code will only set cookie for motherfuckingwebsite.com/test and can only be accessed by it. Here is the example.

document.cookie="itsME=7; path=/test";

Image 1: we are accessing cookie from motherfuckingwebsite.com and there is no such cookie.

Image 2: we are accessing cookie from motherfuckingwebsite.com/test and we can see it.

Setting cookie lifetime

Let's create a cookie with an expiry date. Now we can do this in two ways.

Expires: Takes date as value.

//86400e3 is same as 86400000 i.e 24 hours in milliseconds
var exp_date=new Date(Date.now()+86400e3);
//refer template literals in JS if not familiar with ${}
document.cookie=`itsME2=2;expires=${exp_date.toGMTString()}`;

Max-age: Takes time (in seconds) as value.

//86400 i.e 24 hours in seconds
document.cookie=`itsME3=3;max-age=86400`;

Above we have created both the cookie with a validity of 24 hrs. from the time the cookie was created. Here you can compare all three cookies we have set so far.

Notice! in the Expires/Max-age part you can see ItsME2 and ItsME3 has some date and time but ItsME shows session. It is so because when you don't mention any expiry time of the cookie then the browser considers it as a sessional cookie and it expires as soon as you close the browser. Go ahead, give it a try.

💡 Head over to didthanoskill.me and look for cookie from the URL bar. You'll see 1 cookie in use. When you do document.cookie in the browser console, an empty string is returned which is weird. Go to the Application tab in the developer tool and there also you'll see no cookie. Any idea why is so? Hint: have a look at the source and if still don't understand then run the debugger in the dev tool to understand why is it happening so?

🖥️ The Server Way

We saw the client's Way of creating cookies. Now we'll create a cookie from the server-side and I'll use NodeJS and express for this.

Basically what happens is when the client makes a request to the server, the server responds with a response which contains header and in that header, there is set-cookie option which tells the browser to create a cookie.

creating a simple cookie.

const app=require("express")();
app.get("/",(req,res)=>{
    //setting response header
    res.setHeader("set-cookie",["itsSERVER1=h1"]); 
    res.send("this is https://localhost:2000/");
});

app.listen(2000,()=>{
    console.log(">2000<");
})

and we have it.

setting up cookie path

const app=require("express")();
app.get("/",(req,res)=>{
    /*can also use res.setHeader() instead of
    res.cookie()*/
    res.cookie("itsSERVER1","h1");
    //for path /hahahayes
    res.cookie("itsSERVER2","yeet!",{path:"/hahahayes"});  
    res.send("this is https://localhost:2000/");
});

app.get("/hahahayes",(req,res)=>{
    res.send("this is https://localhost:2000/hahahayes");
});

app.listen(2000,()=>{
    console.log(">2000<");
});

gives following result:

so on and so forth for other options as well.

🔒 Security

Security is a very important topic of discussion over here. As mentioned earlier, services like social media use various cookies to keep you logged in. If such cookies get in hands of attackers they can easily break into your account and the rest you know.

When user privacy is a concern, it's important that any web app implementation invalidate cookie data after a certain timeout instead of relying on the browser to do it.

If you are using cookie to store some data and later rendering it in DOM (which is a super duper bad practice) then make sure to keep the valid formatting, they should be escaped using a built-in encodeURIComponent function:

var cookie_name="mycookie";
var cookie_value="myvalue";
document.cookie = `${encodeURIComponent(cookie_name)}=${encodeURIComponent(cookie_value)}`;

In section The Client Way, we easily accessed the website's cookie using JavaScript, so an attacker may find a vulnerability like XSS which enables them to execute malicious JS code on the website and bypass logins. From a developer's point of view, it's really hard to keep track of XSS especially in humongous applications with a lot of features. Due to this, some inbuilt security features are there in cookies, which prevent such attacks even if the attacker is able to execute some code.

You can check out Hack this site basic 10 which demonstrates, what careless use of cookies can lead to.

HttpOnly is an option used by web-server when they set cookies. This option forbids any JavaScript access to the cookie. This is a precautionary measure, to protect from certain attacks.

//server side
const app=require("express")();
app.get("/",(req,res)=>{
    /*can also use res.setHeader() instead of
    res.cookie()*/
    res.cookie("itsSERVERsecure","100",{httpOnly:true});  
    res.send("this is https://localhost:2000/");
});

app.listen(2000,()=>{
    console.log(">2000<");
});

and you'll see a tick mark (✔️) under HttpOnly in the Application tab (developer tools). Try accessing it using JS.

If your cookie contain sensitive content then you may wanna send it over HTTPS. To accomplish this you have to include secure option as shown below.

//client side
document.cookie = "ItsMeSecure=6; secure";

//server side
const app=require("express")();
app.get("/",(req,res)=>{
    /*can also use res.setHeader() instead of
    res.cookie()*/
    res.cookie("itsSERVERsecure","100",{secure:true});  
    res.send("this is https://localhost:2000/");
});

app.listen(2000,()=>{
    console.log(">2000<");
});

samesite SameSite prevents the browser from sending the cookie along with cross-site requests. Possible values are lax, strict or none.

The lax value will send the cookie for all same-site requests and top-level navigation GET requests. This is sufficient for user tracking, but it will prevent many CSRF attacks. This is the default value in modern browsers.

The strict value will prevent the cookie from being sent by the browser to the target site in all cross-site browsing contexts, even when following a regular link.

The none value explicitly states no restrictions will be applied. The cookie will be sent in all requests—both cross-site and same-site.

So make sure that you use cookies wisely 🦉.
Feel free to point out any issues or suggest improvements in the content.

🥳 So it's time to wrap up the post with a quote

"Opportunities don't happen. You create them" -Chris Grosser

Google XSS challenge: Level 3 aka That sinking feeling (detailed walkthrough)

Souvik Kar Mahapatra — Fri, 12 Feb 2021 05:39:07 +0000

Prerequisite

Before getting started one should be familiar with XSS or at least have an idea about it. Here is a good article which you may give a read to understand what is XSS. Read!

Also, I assume that readers are at least familiar with JavaScript. If not then I'll suggest to spend some time with JS and get comfortable with the basics. You can refer to javascript.info and MDN which are extremely helpful.

💡 Also in this whole series we'll not even roll our eyes on Hints and Toggle Code as in real-world bug hunting no one will give you hints or non-obfuscator source code so you have to figure out things yourself.

Mission Description

As you've seen in the previous level, some common JS functions are execution sinks which means that they will cause the browser to execute any scripts that appear in their input. Sometimes this fact is hidden by higher-level APIs which use one of these functions under the hood.

The application on this level is using one such hidden sink.

Mission Objective

As before, inject a script to pop up a JavaScript alert() in the app.

Since you can't enter your payload anywhere in the application, you will have to manually edit the address in the URL bar below.

Breaking In

Let's jump right into it and see what is this application all about. As you click on the tabs Image 1, Image 2 , Image 3 the image changes. Notice anything else as well? Yep! the URL.

If we click on Image 1 the URL is level3/frame#1, Image 2 => level3/frame#2. Looks like the number followed by # is referring to the tab number. We'll try passing some other number to see how it behaves.

level3/frame#100

thing to notice is that what we enter after # in URL gets displayed in the page. There is a possibility that we can insert some script in the page.

Information (so far):

Entry point: URL
Input in URL gets displayed on the page.

Payload : level3/frame#<h1>hello</h1>

which shows Image NaN on the page. Hmm NaN (not a number),usually returned by a function which expects a number as input but here we provided string. There may be a possibility that the code uses ParseInt. Let's give it a search in dev tools.

In the upper frame line number 16, 17, 18 are the star of the show. When we entered a string, it was passed to parseInt which returned NaN at line 16. However there is a flaw. parseInt saved the application from XSS but here the num is still being used in line 17 and this time no parseInt and of course line 18 insects the HTML in the page.

Let's create our payload keeping line 17 in mind.

line 17: html += "<img src='/static/level3/cloud" + num + ".jpg' />";

NOTE: another thing we have to keep in mind that this application uses JQuery and at line 18 .html() is equivalent to innerHTML in vanilla JavaScript, so even if we insert a script it won't work.

so if you have solved level 2 of XSS challenge then you know you can manipulate the onerror attribute of img tag and the best part is at line 17 there is already an img tag so all we need to do is properly inject onerror to the element.

Payload: ' onerror="alert(/xss/)" '

The image tag will look something like this after injecting the payload:

<img src='/static/level3/cloud ' onerror="alert(/xss/)" ' .jpg' />

the first ' in payload closes the string in src which makes it an invalid image URL (/static/level3/cloud) and will certainly lead to an error that triggers onerror and rest you know.

this payload can be further condensed to 'onerror="alert(/xss/)". The above payload was to explain the logic behind it.

Go ahead and look for some other payload and think what else you can do apart from popping an alert.

We are not done yet!! We have 3 more levels of Google XSS challenges to complete so head over to the blog section and check out walkthroughs.

🥳 So it's time to wrap up the post with a quote

“For the things we have to learn before we can do them, we learn by doing them.” ― Aristotle

Hack The Box: Emdee five for life

Souvik Kar Mahapatra — Thu, 11 Feb 2021 10:27:24 +0000

The first challenge under the web and most of the votes are for easy. Let's try it out.

CHALLENGE TITLE: Emdee five for life

CHALLENGE DESCRIPTION: Can you encrypt fast enough?

The only thing that comes to mind after reading the title and description is, MD5. So the task looks pretty easy, all we have to do is encrypt a random string displayed on the website. Then submit the encrypted string.

Head over to md5.cz to encrypt.

oNbzpf0JAXYbMvDTyb8W --> 5db3c17ae9a5326e66af94741d69858c

but wait, on submitting the encrypted sting it mocks us "Too slow!" 🤨 along with a new string to encrypt. So seems like we have to accomplish this as fast as possible. How about automating the process?

and here is the code:

import requests
import hashlib
from bs4 import BeautifulSoup

req=requests.session()
#change URL according to yours
url="http://144.126.196.140:30844/"

get_req=req.get(url)
html=get_req.content

soup = BeautifulSoup(html, 'html.parser')
hash_val=soup.h3.get_text().encode('utf-8')

md5hash=hashlib.md5(hash_val).hexdigest()
data=dict(hash=md5hash)
post_res=req.post(url=url,data=data)
print("flag:",post_res.text)

and we have the flag. See you on the next challenge ✌️.

DEV Community: Souvik Kar Mahapatra

Fan-In Fan-Out Concurrency Pattern in Go: A Comprehensive Guide

Pipeline Concurrency Pattern in Go: A Comprehensive Visual Guide

Souvik Kar Mahapatra ・ Dec 29 '24

Evolution from Pipeline Pattern

Fan-In Fan-Out Pattern

Understanding Fan-out

Understanding Fan-in

Why Use Fan-in Fan-out Pattern?

Real-World Use Cases

Error Handling Principles

Fail Fast: Detect and handle errors early in the pipeline

Isolate Failures: One worker's error shouldn't affect others

Resource Cleanup: Proper cleanup on errors

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20 '24

Pipeline Concurrency Pattern in Go: A Comprehensive Visual Guide

Generator Concurrency Pattern in Go: A Visual Guide

Souvik Kar Mahapatra ・ Dec 25 '24

Pipeline Pattern

Error Handling in Pipelines

Why Use Pipeline Pattern?

Real world use case

Pipeline scaling patterns

Horizontal Scaling (Fan-Out, Fan-In)

Buffered Pipeline

Batched Processing

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20 '24

Generator Concurrency Pattern in Go: A Visual Guide

Understanding and visualizing Goroutines and Channels in Golang

Souvik Kar Mahapatra ・ Dec 20

Generator Pattern

Why Use Generators?

Real-world Use Case

Key Benefits of Generator Pattern:

Common Pitfalls and Solutions

🚀💸 Let's Talk About Open Source Monetization 🚀💸

Understanding and visualizing Goroutines and Channels in Golang

Foundations of Goroutines

Comes the sync.WaitGroup

Channels

Fixing main not waiting for others issue using channel

How two goroutines can communicate?

Program Start (t=0ms)

First Message (t=1ms)

Second Message (t=101ms)

Third Message (t=201ms)

Channel Close (t=301ms)

Completion (t=302-303ms)

Buffered Channels

When to use Buffered channels vs Unbuffered channels

Key takeaways

Arrays vs Slices in Go: Understanding the "under the hood" functioning visually

Arrays: The Fixed-Size Container 📦

Why Array is Copy By Default?

Slices

Slices under the hood

The dynamic mechanism of slice

Let's get a better understanding from usage perspective

Why reference semantics?

Usage patterns and cautions for slice

Testing REST APIs using Jest and Supertest ✅

Installing dependencies

Creating a simple express server

Creating test file

Running Test

The Wardrobe Strategy: How Shopping in Bulk Explains Amortized Cost

What's amortized cost?

But when do we know we need amortized analysis?

Growing Collections

Resource Management

Performance Optimization

Understanding using simple maths

The Long-Term Impact:

Common Misconceptions

Key Takeaways

Know The Web: SOP (Same Origin Policy)

What will happens if

Same Origin Policy

Comes the `sync.WaitGroup`