Posts

Having fun with Go slices

Image
The fun

Go offers precious few data structures that can be generically typed: queue, map, and slice (including array).  This often leaves developers using slices, particularly ordered slices, for all sorts of use cases.  I thought it might be fun to create some utilities for slice manipulation, starting with a faster stable sort. I hope in Go 2 we can get generics so data structures like binary trees will be safer.

For those that aren't aware, a stable sort is a sort where two elements with the same key retain their same relative positions as they had in the input.  There are several sorting algorithms that support stable sorting, including merge sorts, insertion sorts, and bubble sorts.  Efficient implementations of the ever-popular quicksort are not stable.

I've had several use cases for a stable sort in the past so I thought it might be fun to take the stable sort from the standard library and attempt to make it concurrent to improve performance.  The standard library's so…

Engineering for Offline Workflows

Image
Mobile devices have revolutionized how people use the internet.  Pulling some numbers from Smart Insights' mobile marketing statistics, we see that more minutes are spent on mobile devices than traditional desktop devices when measured globally.  The following image is telling:



However, growing up in a rural-ish area, I've noticed that data coverage is not necessarily commensurate with data requirements.  Even when it is, the cost of the data is often unaffordable.  Even in relatively wealthy countries with modern infrastructure, such as the United States, data rates can be quite high.

This introduces an interesting and important problem for those engineers trying to build applications that target the mobile space.  Users strongly desire to use their applications on mobile devices and using those devices as they were intended to be used is often impossible or unaffordable.  The challenge for the engineer is creating a solution that allows users to seamlessly use these applicatio…

Adventures in bit arrays/SIMD (Go)

Image
Introduction

I've been fortunate enough to have a career where I've been free to explore new technologies and techniques to support a business need.  One of the problems I was once tasked with solving was graph traversal on a rather large scale.  It was not uncommon for a graph in our system to have hundreds of millions of edges, or for a large portion of that graph to be traversed.

However, traversal in our use-case was not path finding as much as node visitation in a particular order, aka, a cyclic dependency graph.  As long as ordering was correct, we didn't necessarily need to know how traversal got to any individual node.

Performance in this use-case was also paramount, so this particular traversal process was going to be done in-memory.  So, to summarize, I needed a way to maintain hundreds of millions of edges and to run a process in the correct order in the dependency graph.  IE, if B relied on A, A needed to be processed first.  To throw a little wrinkle into the fab…