So hanging out at GothamGo this year has been inspirational! I have been able to rub elbows with the best of the best Go engineers in the world.

Last night I was introduced to what I think is..

..finally the solution to generics in Go!

The G Package

So there is an Apache 2 open source licensed package that can be found on GitHub here. ‘

The package is clean, and elegant. So let’s take the package for a spin!

First things first, we need to install the G package. Luckily it using the Go idiomatic installation method go get.

go get github.com/StabbyCutyou/generics

Now we can import the package into our Go program.

import . "github.com/StabbyCutyou/generics"

The Implementation

We can now take ugly and non idiomatic (but flexible) Go code such as the following and implement a much more elegant solution for Generics.

func UglyUnIdiomaticQuoteGenericApproachUnquote(poorexcuse ...interface{}) []interface{}

with the G package now becomes the following

func Excellence(things ...G) []G

Backwards Compatibility

From the G package repository we can read a glorious compatibility statement:

G meets the standard of golang by matching its stance on backwards compatibility. Until a 2.0 release of generics, which may never happen, G will always be 100% Backwards compatible with it’s initial 1.0 release.

Behind The Scenes

The source code for G is simple and elegant, and I encourage all users to take a peak at what is going on behind the scenes. In my eyes it is a clean solution to Generics in Go, and I couldn’t be more pleased with the project.

I hope this helps.

Cheers.

A well written sorting algorithm is hard to replace, and typically the ones that have been battle tested will stand the test of time and stick around for a while. The Go programming language offers a clean abstraction on top of a commonly used sorting algorithm. With the sort  package in the standard library a user can sort arbitrary types in arbitrary ways using a time-proven sorting algorithm.

The way Go has set this up for us is by defining an interface called the sort.Interface. The rule is that as long as a type implements to this interface, it can be sorted.

The sort.Interface interface

type Interface interface {
       // Len is the number of elements in the collection.
       Len() int
       // Less reports whether the element with
       // index i should sort before the element with index j.
       Less(i, j int) bool
       // Swap swaps the elements with indexes i and j.
       Swap(i, j int)
}

The interface definition can be found here. The interface defines 3 functions, all of which are critical to the success of the sort.

Len()

The sort works by dividing the length of a collection by 2. So we need a way to determine a length (or size) of a collection. Think of this like the len() function in Go, and usually the len() function is appropriate to use here.

Less()

This is a function that will receive 2 integer indices from the collection. The algorithm assumes the implementation will perform some logic here and make an assertion. The algorithm will not care if a user actually checks if a value is less than another, as that assertion is completely arbitrary. This is analogous to the function used to compare values in C’s qsort()

Swap()

Go takes the sort abstraction one step further, and also makes the user define a Swap() function. This is called after Less() returns false and the algorithm understands that a change is needed. In Go however, you can make Swap() do whatever you want in this case.

Sorting integers with sort.Sort()

A very basic example of defining a sort.Interface implementation is to create an integer alias in Go, and implement the required functions.

type Integers []int

func (s Integers) Len() int {
	return len(s)
}
func (s Integers) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func (s Integers) Less(i, j int) bool {
	return s[i] < s[j]
}

This implementation can now be passed to sort.Sort() and sorted on. A full working example of an integer sort with sort.Sort() can be found here in the Go playground, or my raw source here on GitHub.

Sorting structs with sort.Sort()

Below is an example of sorting on a collection of custom types, and using the utf8 package to sort on the int32 value of a rune. This is important because it demonstrates how a user might want to sort on a “calculated” value instead of a literal value.

A user can implement any logic they wish in Less() or in Swap() giving the user a powerful opportunity to build quick and efficient sorting program on any type they can dream of. This is useful in situations where the logic for what a user wants to sort on, might be something different than a simple numerical or alphabetical sort.

type Type struct {
	Value string
}

type Types []Type

func (s Types) Len() int {
	return len(s)
}
func (s Types) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}
func (s Types) Less(i, j int) bool {
	iRune, _ := utf8.DecodeRuneInString(s[i].Value)
	jRune, _ := utf8.DecodeRuneInString(s[j].Value)
	return int32(iRune) > int32(jRune)
}

As always you can run the code in Go Playground, and also see the raw source in GitHub.

Conclusion

The Go programming language offers a familiar and clean abstraction for sorting on arbitrary types and with arbitrary logic. The user can implement any logic they wish in regards to what the sort will use to sort on.

By offering the underlying algorithm and defining the sort.Interface the programming language helps us build powerful sorting programs without enforcing a single opinion on what the algorithm should do but rather how to do it.

Thanks!

Thank you for reading my article. As always, I appreciate any feedback from users. So let me know how we could be better.

Follow @kris-nova

So today I decided to take on a fairly complex design pattern in the hopes of demonstrating some more advanced features of concurrency in Go or at least ruffle a few feathers about how to approach digraph processing.

Wikipedia offers a great explanation of graph theory in case you need to brush up!

The goal of this post is to offer a design approach to processing graphs concurrently , where each vertex in the graph represents a processable unit of work .

The graph will be processed concurrently via a `Crawl()` operation, where there are N number of concurrent processors . Each processor will process a stream of vertices procedurally by referencing a function pointer to a `process()` function.

The Graph

The graph is composed of edges and vertices. We start the example off by building a complex graph with an arbitrary child count. Each of the children may or may not have their own children. A child is represented by a vertex.

The Vertices

A vertex represent the intersections of the graph. Where 2 edges intersect, there will be a vertex. The only way to get from one vertex to another is to traverse it’s corresponding edge.

The Edges

Edges are what connect vertices. Every edge has a `to` and a `from` pointer that will point to the two vertices it’s connecting. Because the edge insinuates direction, and only connects in a single direction that makes the graph a directional graph, or a digraph.

The Processors

Processors process vertexes. In this example we simulate some arbitrary work by injecting a random sleep. In a real implementation a processor would actually accomplish some amount of work that a vertex would require. We have N processors so they can operate on vertices concurrently. The more processors, the more vertices we can concurrently operate on, or process.

The Crawler

The crawler will traverse edges to find vertices. As the crawler finds a vertex it will concurrently process each vertex by passing it to a processor. Processors are called cyclically and in order.

For example if we had 10 vertices and 3 processors the call pattern would look like this.

V -- P
------
1 -- 1
2 -- 2
3 -- 3
4 -- 1
5 -- 2
6 -- 3
7 -- 1
8 -- 2
9 -- 3
0 -- 1

The vertices to be processed in unique goroutines, but on shared channels. The channels will buffer and form a queue if the vertex workflow overflows their ability to keep up.

The win

The huge win here is that the graph stays constructed in it’s original form. The crawler can iterate through it’s many (and complex) layers quickly because of the concurrent processing design. A processor could be replaced with any implementation capable of running a workload. This allows the user to structure complex data, while operating on it without any overhead of understanding the data. The processor gets a vertex, and thats it. The processors have no concept of order, and they don’t need to.

Notice how the program is able to calculate the operations by counting the graph, and the graph is actually processed quickly with the same number of operations. Good. Clean. Concurrent processing.

Furthermore a user can turn up the number of iterations and specify how many times to visit each vertex. This is useful in situations were a process is idempotent but could potentially fail. Sending the same request N number of times makes sense and increases the probability of a success.

package main



import (
	"math/rand"
	"time"
	"fmt"
)

const (
	NumberOfConcurrentProcessors = 32
	NumberOfCrawlIterations = 4
)

// DiGraph
//
// This is a directional graph where edges can point in any direction between vertices.
// The graph has 1 root vertex, which is where the Crawl() starts from.
type DiGraph struct {
	RootVertex       *Vertex       // The root vertex of the graph
	Processors       [] *Processor // List of concurrent processors
	ProcessorIndex   int           // The current index of the next processor to use
	Edges            []*Edge       // All directional edges that make up the graph
	Iterations       int           // The total number of times to iterate over the graph
	TotalVertices    int           // Count of the total number of vertices that make up the graph
	ProcessedChannel chan int      // Channel to track processed vertices
	ProcessedCount   int           // Total number of processed vertices
	TotalOperations  int           // Total number of expected operations | [(TotalVertices * Iterations) - Iterations] + 1
}

// Vertex
//
// A single unit that composes the graph. Each vertex has relationships with other vertices,
// and should represent a single entity or unit of work.
type Vertex struct {
	Name   string // Unique name of this Vertex
	Edges  []*Edge
	Status int
}

// Edge
//
// Edges connect vertices together. Edges have a concept of how many times they have been processed
// And a To and From direction
type Edge struct {
	To             *Vertex
	From           *Vertex
	ProcessedCount int
}

// Processor
//
// This represents a single concurrent process that will operate on N number of vertices
type Processor struct {
	Function func(*Vertex) int
	Channel  chan *Vertex
}

// Init the graph with a literal definition
var TheGraph *DiGraph = NewGraph()

func main() {
	TheGraph.Init(NumberOfConcurrentProcessors, NumberOfCrawlIterations)
	TheGraph.Crawl()
}

func (d *DiGraph) Init(n, i int) {
	noProcs := n
	d.TotalVertices = d.RootVertex.recursiveCount()
	d.Iterations = i
	for ; n > 0; n-- {
		p := Processor{Channel: make(chan *Vertex)}
		d.Processors = append(d.Processors, &p)
		p.Function = Process
		go p.Exec()
	}
	d.TotalOperations = (d.TotalVertices * d.Iterations) - d.Iterations + 1 //Math is hard
	fmt.Printf("Total Vertices              : %d\n", d.TotalVertices)
	fmt.Printf("Total Iterations            : %d\n", d.Iterations)
	fmt.Printf("Total Concurrent Processors : %d\n", noProcs)
	fmt.Printf("Total Assumed Operations    : %d\n", d.TotalOperations)
}

func (d *DiGraph) Crawl() {
	d.ProcessedChannel = make(chan int)
	go d.RootVertex.recursiveProcess(d.getProcessor().Channel)
	fmt.Printf("---\n")
	for d.ProcessedCount < d.TotalOperations {
		d.ProcessedCount += <-d.ProcessedChannel
                //o(fmt.Sprintf("%d ", d.ProcessedCount))
	}
	fmt.Printf("\n---\n")
	fmt.Printf("Total Comlpeted Operations  : %d\n", d.ProcessedCount)
}

func (d *DiGraph) getProcessor() *Processor {
	maxIndex := len(d.Processors) - 1
	if d.ProcessorIndex == maxIndex {
		d.ProcessorIndex = 0
	} else {
		d.ProcessorIndex += 1
	}
	return d.Processors[d.ProcessorIndex]
}

func Process(v *Vertex) int {

	// Simulate some work with a random sleep
	rand.Seed(time.Now().Unix())
	sleep := rand.Intn(100 - 0) + 100
	time.Sleep(time.Millisecond * time.Duration(sleep))

        o(fmt.Sprintf("Processing: %s", v.Name))
	// Return a status code
	return 1
}

func (v *Vertex) recursiveProcess(ch chan *Vertex) {
	ch <- v
	for _, e := range v.Edges {
		if e.ProcessedCount < TheGraph.Iterations {
			e.ProcessedCount += 1
			go e.To.recursiveProcess(TheGraph.getProcessor().Channel)
		}
	}
}

func (v *Vertex) recursiveCount() int {
	i := 1
	for _, e := range v.Edges {
		if e.ProcessedCount != 0 {
			e.ProcessedCount = 0
			i += e.To.recursiveCount()
		}
	}
	return i
}

func (v *Vertex) AddVertex(name string) *Vertex {
	newVertex := &Vertex{Name: name}
	newEdge := &Edge{To: newVertex, From: v, ProcessedCount: -1}
	newVertex.Edges = append(newVertex.Edges, newEdge)
	v.Edges = append(v.Edges, newEdge)
	return newVertex
}

func (p *Processor) Exec() {
	for {
		v := <-p.Channel
		v.Status = p.Function(v)
		TheGraph.ProcessedChannel <- 1
	}
}

func NewGraph() *DiGraph {
	rootVertex := &Vertex{Name: "0"}
	v1 := rootVertex.AddVertex("1")
	rootVertex.AddVertex("2")
	rootVertex.AddVertex("3")
	v1.AddVertex("1-1")
	v1.AddVertex("1-2")
	v1_3 := v1.AddVertex("1-3")
	v1_3.AddVertex("1-3-1")
	v1_3.AddVertex("1-3-2")
	v1_3_3 := v1_3.AddVertex("1-3-3")
	v1_3_3.AddVertex("1-3-3-1")
	v1_3_3.AddVertex("1-3-3-2")
	v1_3_3.AddVertex("1-3-3-3")
	v1_3_3.AddVertex("1-3-3-4")
	v1_3_3.AddVertex("1-3-3-5")
	v1_3_3.AddVertex("1-3-3-6")
	v1_3_3.AddVertex("1-3-3-7")
	graph := &DiGraph{}
	graph.RootVertex = rootVertex
	return graph
}

func o(str string) {
	fmt.Println(str)
}

Try it out

You can run the code yourself in the Go playground.

Thanks!

Thank you for reading my article. As always, I appreciate any feedback from users. So let me know how we could be better.

Follow @kris-nova