Posts

Showing posts from July, 2017

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…