Parallel Merge Sort using Fork and Join

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class MergeSortForkJoin {
    public static class MergeSortTask extends RecursiveAction {
        private static final long serialVersionUID = 1L;
        private final List<Integer> list;
        private final int lo;
        private final int hi;
        
        public MergeSortTask(List<Integer> list, int lo, int hi) {
            this.list = list;
            this.lo = lo;
            this.hi = hi;
        }
        
        @Override
        protected void compute() {
            if (lo >= hi) {
                return;
            } else {
                int mid = (lo + hi) / 2;
                MergeSortTask task1 = new MergeSortTask(list, lo, mid);
                MergeSortTask task2 = new MergeSortTask(list, mid+1, hi);

                invokeAll(task1, task2);

                merge(list, lo, mid, hi);
            }
        }
        
        private void merge(List<Integer> list, int lo, int mid, int hi) {
            List<Integer> tmp = new ArrayList<>();
            for (int i : list) {
                tmp.add(i);
            }
            int left = lo;
            int right = mid + 1;
            int idx = lo;
            while (left <= mid && right <= hi) {
                if (tmp.get(left) <= tmp.get(right)) {
                    Integer element = tmp.get(left);
                    list.set(idx, element);
                    left++;
                    idx++;
                } else {
                    Integer element = tmp.get(right);
                    list.set(idx, element);
                    right++;
                    idx++;
                }
            }
            while (left <= mid) {
                Integer element = tmp.get(left);
                list.set(idx, element);
                idx++;
                left++;
            }
            while (right <= hi) {
                Integer element = tmp.get(right);
                list.set(idx, element);
                idx++;
                right++;
            }
        }
    }
    
    public static void main(String[] args) throws Exception {
        ForkJoinPool pool = new ForkJoinPool();
        List<Integer> list = Arrays.asList(4, 9, 1, 5, 8, 0, 7, 6, 3, 2);
        System.out.println("Unsorted: " + list);
        MergeSortTask task = new MergeSortTask(list, 0, list.size()-1);
        try {
            do {
                pool.execute(task);
            } while (!task.isDone());
        } finally {
            pool.shutdown();
        }
        System.out.println("Sorted:   " + list);
    }
}

How to Organize a Go Project

The official has a good information on how to structure your Go code. In this blog, I am going to explain a little bit more about it. Let's say we want to create a Go project containing a command and a package.

workspace1/
|-- build.sh
`-- src
    `-- mylib
        |-- hello
        |   `-- hello.go (package)
        `-- main.go (command)

hello.go

package hello

import "fmt"

func SayHello() {
    fmt.Println("Hello")
}

main.go

package main

import "mylib/hello"

func main() {
    hello.SayHello()
}

build.sh

#!/bin/bash

export GOPATH=`pwd`
go install mylib/hello
go install mylib

Calling build.sh will create this structure.

workspace1/
|-- bin
|   `-- mylib (executable)
|-- build.sh
|-- pkg
|   `-- linux_amd64
|       `-- mylib
|           `-- hello.a (library)
`-- src
    `-- mylib
        |-- hello
        |   `-- hello.go (package)
        `-- main.go (command)

In order to make mylib project go-gettable, let's make it into a Git project. Take a note that we will be creating a Git project in the mylib directory and not in the workspace1 directory.

1. cd workspace1/src/mylib
2. git init
3. git add .
4. git commit -m "Initial commit"
5. Push this repository to the remote URL

Now let's create another project that uses mylib. This new project is a simple project that uses mylib.

workspace2/
|-- build.sh
`-- src
    `-- myapp
        `-- app
            `-- app.go (command)

1. cd workspace2
2. git init
3. git add submodule [mylib_git_url] src/mydomain/user/mylib (the src/mydomain/user is just a convention, you can also set the path to src/mylib)

After the submodule addition, we will have this structure.

workspace2/
|-- build.sh
`-- src
    |-- myapp
    |   `-- app
    |       `-- app.go (command)
    `-- mydomain
        `-- user
            `-- mylib
                |-- hello
                |   `-- hello.go (package)
                `-- main.go (command)

app.go

package main

import (
    "fmt"
    "mydomain/user/mylib/hello"
)

func main() {
    fmt.Println("Do something")
    hello.SayHello()
}

build.sh

#!/bin/bash

export GOPATH=`pwd`
go install mydomain/user/mylib/hello
go install myapp/app

Calling build.sh will create this structure.

workspace2/
|-- bin
|   `-- app (executable)
|-- build.sh
|-- pkg
|   `-- linux_amd64
|       `-- mydomain
|           `-- user
|               `-- mylib
|                   `-- hello.a (library)
`-- src
    |-- myapp
    |   `-- app
    |       `-- app.go (command)
    `-- mydomain
        `-- user
            `-- mylib
                |-- hello
                |   `-- hello.go (package)
                `-- main.go (command - not used)

How to Create a Simple REST Server in Go

Below is an example on how to create a simple REST server in Go.

package main

import (
    "encoding/json"
    "log"
    "net/http"
    "strconv"
)

type Hello struct {
    Message string `json:"message"`
}

func HelloServer(w http.ResponseWriter, req *http.Request) {
    log.Println("Received a request from ", req.RemoteAddr)
    w.Header().Set("Content-Type", "application/json")
    if req.Method == "GET" {
        encoder := json.NewEncoder(w)
        hello := Hello{"Hello World"}
        encoder.Encode(hello)
    }
}

func main() {
    port := 8080
    // serve static content
    http.Handle("/", http.FileServer(http.Dir("html")))
    http.HandleFunc("/hello/", HelloServer)
    log.Println("Starting HTTP server at", port)
    err := http.ListenAndServe(":"+strconv.Itoa(port), nil)
    if err != nil {
        log.Fatal("Unable to start the server: ", err)
    }
}

How to Cross Compile Go Programs

If you download the Go binary for a particular platform, most likely that go binary distribution does not come with support for cross-compiling.

cd myapp
GOOS=windows GOARCH=amd64 go build

go build runtime: windows/amd64 must be bootstrapped using make.bash

In order to add support for cross-compiling in your Go distribution, you need to do the following.

cd $GOROOT/src
GOOS=windows GOARCH=amd64 ./make.bash --no-clean

In this example I am adding cross-compile support to target Windows 64-bit.

cd myapp
GOOS=windows GOARCH=amd64 go build

Now you can easily build Windows 64-bit binaries on a Linux.