Azundo Design

Musings and Makings

Introducing Dj-timelinejs

I’ve been working on packaging up some components from my work with Engineers Without Borders. One really great Knowledge Management Tool we use is buildling timelines with TimelineJS. Our custom KM site is written in Django and wanted an easy way to integrate timelines with the site, so I created dj-timelinejs.

The package is pip-installable with pip install dj-timelinejs and provides admin-interface access to created timelines and a bunch of class-based views for viewing and importing existing timelines that you may have hosted in Google Spreadsheets. Documentation is in the README.

An Optimal Fox AI Using State Machines

I’ve really enjoyed thinking about the puzzles at http://gurmeet.net/puzzles/, especially looking for ways to solve them or get hints as to how to solve them using visualization without knowing the answers. Last Time I explored puzzle 11, Treasure Island, and this time I’ll look at puzzle 5, Fox in a Hole.

The Puzzle

Here is the wording from http://gurmeet.net/puzzles/:

Consider five holes in a line. One of them is occupied by a fox. Each night,
the fox moves to a neighboring hole, either to the left or to the right. Each
morning, you get to inspect a hole of your choice. What strategy would ensure
that the fox is eventually caught?

The Challenge

The question I asked was, can we, without knowledge of a working strategy, create a fox that plays optimally against us so we can be sure we’ve come up with a strategy that will work? We could simulate a fox that chooses to move left or right randomly, but we would never be sure that our strategy is fool proof. Can we make sure our fox plays hard to get if we don’t even know how to catch it? Turns out we can. Try out the demo of my solution and see if you can both figure out how to catch the fox and understand why a strategy works. Implementation details are below the demo. Code is at https://gist.github.com/azundo/5941503.

Instructions

Click on a hole to select it for inspection. You win if the fox has nowhere
left to hide. If you give up, click the button and one possible path the fox
could have taken to avoid your inspections will be shown.

A Quantum Fox

Instead of modeling our fox as being in one concrete location, we’ll keep track of all possible holes the fox could be in at any given time without getting caught, depending on which holes we have inspected in the past. We’ll use a finite-state machine to keep track of which holes the fox could be in. If we ever get to the state where the fox couldn’t be in any holes without being caught, we know our strategy is a good one. We don’t require any knowledge of the best path for the fox to choose, or a winning strategy.

Our State Space

Each state in our state space will consist of all of the possible holes the fox could be in at any one time. There are 5 holes and each hole has two states: it is either possible for the fox to be in that hole, or not possible. This gives us a state space of size 2^5 = 32. We could model this as a bit vector with 5 bits, but for clarity I will use a simple array. If it is possible for the fox to be in hole i, then our state array will contain i. We’ll number our holes 0, 1, 2, 3, 4.

For example, before we check any holes, our state would be [0, 1, 2, 3, 4]. The fox could be in any hole. If we check hole 2, then our state would move to [0, 1, 3, 4]. In the case where there is no possible hole for our fox to be in without catching him at some point, our state is an empty array [].

State Transitions

The key implementation detail when using a state machine is our state transitions. How do we decide which state we move to next? In our case our next state is dependent on two things, our previous state (the set of possible holes the fox could have been in yesterday) and our selection of which hole to check.

To start let’s forget about the action of checking a hole. How can we determine what holes the fox can be in based on what holes it could have been in yesterday? If it was possible for the fox to be in hole i yesterday, then it is possible for the fox to be in any hole beside i today. If we iterate over all of the holes that the fox could have been in yesterday then we’ll get the set of holes it could be in today.

We’ll use a very simple adjacency list to make our lives easy. If we access element i of the adjacency list we will get back an array containing all of the holes next to i.

1
2
3
4
5
6
7
8
9
10

var ADJACENCY_LIST = [
    // hole 0 is next to hole 1
    [1],
    // hole 1 is next to hole 0 and hole 2
    [0, 2],
    // etc.
    [1, 3],
    [2, 4],
    [3]
];

This adjacency list defines a very simple graph where each hole is a node connected by edges to each of its adjacent holes. The first and last holes only have one adjacent hole (and thus one edge) while the others have two.

Accessing element 0 of our ADJACENCY_LIST tells us which holes are next to hole 0. If we want to know the set of possible future holes, we take the set of possible past holes and add all of the adjacent holes. Simple enough.

Lastly we don’t include the hole that we chose to inspect since the fox would get caught if he ended up there. Hence, our transition function looks like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

  function nextState(pastState, guess) {
    /*
     * Calculates our next state based on the past state and
     * the next hole to be inspected.
     */
    var next = [], i, j, possiblePastHole, possibleNextHoles, possibleNextHole;
    for (i = 0; i < pastState.length; i++) {
      // any value in our pastState represents a hole that
      // the fox was possibly in yesterday
      possiblePastHole = pastState[i];

      // look up holes next to the possiblePastHole in our ADJACENCY_LIST
      possibleNextHoles = ADJACENCY_LIST[possiblePastHole];
      for (j = 0; j < possibleNextHoles.length; j++) {
        // any holes that are ajacent to a possible hole
        // from the pastState are valid holes for the fox in
        // the next state, provided that hole wasn't
        // inspected.  Note that the fox cannot stay in the
        // same hole, it has to move to an adjacent hole.
        possibleNextHole = possibleNextHoles[j]
        // don't add holes that are already in the next
        // state array since our state is the set of
        // possible holes
        if (possibleNextHole !== guess && next.indexOf(possibleNextHole) === -1) {
          next.push(possibleNextHole);
        }
      }
    }
    return next;
  }

If we ever end up with an empty state, the fox has nowhere to go. We must have caught it at some point, no matter where it started and how it decided to move.

Every time we select a hole to inspect, we’ll update our state and push a copy of it onto an array to keep track of what states we’ve been through in the past. We’ll use that later.

1
2
3
4
5
6
7
8
9
10
11

  function selectHole(selection) {
      // update state information
      state = nextState(state, selection);
      stateHistory.push(state.slice());
      // if there are no possible holes for the fox to be in, we caught him!
      if (state.length === 0) {
        foxCaught(selection);
      } else {
        advanceOneDay(selection);
      }
  }

Reconstructing the Fox’s Moves

If we save each state we reach, we can reconstruct a possible path the fox could have taken to get to the current state. Let’s choose any arbitrary hole from the current state, and work backwards by looking for adjacent holes in the previous state. We are guaranteed to find a backwards path since every hole in our current state must be possible. Here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

  function getPossibleSequence() {
    // only depends on stateHistory, an array of our past states
    var i, finalState, stateToDetermine, possibleHoles, possibleHole, seq = [];
    if (stateHistory.length === 0) {
      return seq;
    }
    finalState = stateHistory.pop();
    // pick whatever hole happens to be listed first in the
    // final state to end our sequence.
    seq.unshift(finalState[0]);
    // work backwards through the state history, picking a
    // valid state from each entry and unshifting it onto
    // the front of the sequence
    while (stateHistory.length > 0) {
      stateToDetermine = stateHistory.pop();
      // find a hole beside the hole at the front of our
      // sequence since our 'graph' is not directed, we can
      // safely use the same adjacency values to move
      // backwards through the state list
      possibleHoles = ADJACENCY_LIST[seq[0]];
      for (i = 0; i < possibleHoles.length; i++) {
        possibleHole = possibleHoles[i];
        // if the possible hole is in our stateToDetermine, use it.
        if (stateToDetermine.indexOf(possibleHole) !== -1){
          seq.unshift(possibleHole);
          break;
        }
      }
    }
    return seq;
  }

Demo and Further Steps

Throwing this together with some d3.js drawing and we get the demo from above. The full code is in a gist at https://gist.github.com/azundo/5941503 and viewable on bl.ocks.org at http://bl.ocks.org/azundo/5941503.

You could also make solving the puzzle a bit easier if you showed all possible holes the fox could be in as you go along, instead of only showing one possible path at the end. Feel free to fork and implement this as a good exercise in d3 basics.

Now can you catch the fox?

Attributions

Using D3.js to Brute Force the Pirate Puzzle

SPOILER ALERT. This post contains an answer to puzzle 11 Treasure Island from http://gurmeet.net/puzzles which appeared on Hacker News recently. If you want to solve it yourself first, check it out over there before reading on, or just don’t read too far down the page.

The Puzzle

Here is the wording of the puzzle:

An old parchment has directions to a treasure chest buried in an island:

There is an unmarked grave and two tall oak trees. Walk from the grave to the
left tree, counting the number of steps. Upon reaching the left tree, turn left
by 90 degrees and walk the same number of steps. Mark the point with a flag.
Return to the grave. Now, walk towards the right tree, counting the number of
steps. Upon reaching the right tree, turn right by 90 degrees and walk the same
number of steps. Mark this point with another flag. The treasure lies at the
midpoint of the two flags.

A party of sailors reached the island. They find a pair of tall oak trees
merrily swaying in the wind. However, the unmarked grave is nowhere to be
found. They are planning to dig up the entire island. It'll take a month. Can
they do any better?

My high school geometry is a little fuzzy so I thought I’d do a little empirical playing around with d3.js to get a sense of the answer before trying to work out the math. Almost a sort of graphical brute force method. If you’re new to d3.js this should hopefully act as a good introduction as well.

If you want to skip ahead, the full gist is at https://gist.github.com/azundo/5928203 and you can use Mike Bostock’s bl.ocks.org to view it at http://bl.ocks.org/azundo/5928203.

Brute Forcing

Set up

We’ll start with a little bit of d3 boilerplate to set things up. There are a few g elements to get our layers working properly but hopefully the comments in the code make things clear.

1
2
3
4
5
6
7
8
9
10

var width = 960,
  height = 600,
  // our svg container
  svg = d3.select('body').append('svg')
  .attr('width', width)
  .attr('height', height),
  // a group within our container that will hold our map features
  features = svg.append('g'),
  // a group within our features group that will show some of the underlying geometry
  geometries = features.append('g');

Next lets set up some parameters for our treasure island.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var islandRadius = 300,
  // size of the features we are plotting on the map
  featureLength = 30,
  // a magic number for placing our trees. Feel free to play around with this number.
  treeOffset = 210,
  // an array of tree objects with x and y properties
  // our trees will have the same y coordinate and x coordinates centered
  // around the middle of the island.
  trees = [
      {
        x: treeOffset,
        y: treeOffset
    },
    {
        x: islandRadius*2 - treeOffset,
        y: treeOffset
    }],
  // an arbitrary initial point for our grave, we'll easily change it later through the graphic.
  grave = {x: islandRadius, y: islandRadius};

Plotting the Static Features

Now we’re ready to plot the static component of our map - the island and the trees.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// create the island on top of everything. If we draw our features "over top"
// of the island then they will interfere with our event handling. Appending to
// the end of the svg container will put the island last in the svg hierarchy
// so it will always be on top. We'll give it a transparent fill so we can see
// through it.
svg.append('circle')
  .attr('r', islandRadius)
  .attr('cx', islandRadius)
  .attr('cy', islandRadius)
  .classed('island', true);


// create the trees - these are static so only draw them once
features.selectAll('.tree')
  .data(trees)
  .enter().append('image')
    .attr('xlink:href', 'images/tree.svg')
    .attr('width', featureLength)
    .attr('height', featureLength)
    // getX and getY are simple helper functions to return properly offset x
    // and y coords for our square features
    .attr('x', getX)
    .attr('y', getY)
    .classed('tree', true);

If we fire this code up you’ll see the following:

Looking good. A couple of trees. Time to get plotting our flags and ultimately the treasure chest location.

Adding Flags

The tricky part here is getting the geometry right when calculating the location of the flags for a given location of the grave. By filling in a couple of extra triangles it becomes clear how we can do it. Here’s a quick diagram for the left tree:

Remembering that the y-coordinate values increase downwards on our svg canvas, we can see a couple of equivalent triangles marked by the red, blue and black lines. The black lines are the path our pirate would mark out, the red is the y-difference between the grave and the tree, and and the blue is the x-difference between the grave and the tree. The coordinates of the left flag are then given by:

If we swap the grave and the flag in the above diagram, we can work out the case for the right tree, turning to the right instead of the left:

So we end up with the following function for calculating our flag placements:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// calculate the positions of the flags
function getFlagPositions(treePositions, gravePosition) {
  var leftTree, rightTree, rise, run, leftFlag, rightFlag;

  leftTree = treePositions[0];
  rightTree = treePositions[1];

  // get left flag position
  rise = gravePosition.y - leftTree.y;
  run = gravePosition.x - leftTree.x;
  // turn 90 to the left
  leftFlag = {
    x: leftTree.x - rise,
    y: leftTree.y + run
  };
  // get right flag position
  rise = gravePosition.y - rightTree.y;
  run = gravePosition.x - rightTree.x;
  // turn 90 to the right
  rightFlag = {
    x: rightTree.x + rise,
    y: rightTree.y - run
  };
  return [leftFlag, rightFlag];
}

We’ll need to dynamically update the positions of these flags so lets create a draw function and call it. At the same time we’ll draw our grave in as well as the triangles that show the walking directions for illustrative purposes. Check out the final version of the code to see the full getPathPoints function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

function draw() {
  // calculate positions
  var flags = getFlagPositions(trees, grave),
      paths = getPathPoints(trees, flags, grave);


  // draw the grave
  features.selectAll('.grave')
    .data([grave])
      .attr('x', getX)
      .attr('y', getY)
    .enter().append('image')
      .attr('xlink:href', 'img/grave.svg')
      .classed('grave', true)
      .attr('height', featureLength)
      .attr('width', featureLength)
      .attr('x', getX)
      .attr('y', getY);


  // draw the flags
  features.selectAll('.flag')
    .data(flags)
      .attr('x', getX)
      .attr('y', getY)
    .enter().append('image')
      .attr('xlink:href', 'img/flag.svg')
      .classed('flag', true)
      .attr('height', featureLength)
      .attr('width', featureLength)
      .attr('x', getX)
      .attr('y', getY);

  // draw triangles showing the flag calculations
  // these are in the geometries group so they appear underneath the other features
  geometries.selectAll('.flag-path')
    .data(paths)
      .attr('d', line)
    .enter().append('path')
      .classed('flag-path', true)
      .attr('d', line);
}
draw();

We’re getting somewhere. Now lets connect our mouse position to the grave position and watch our flags dance around.

Making the Flags Move

1
2
3
4
5
6
7
8
9

// move grave location to wherever the mouse is
svg.select('.island')
  .on('mousemove', function() {
      // 8 is a magic number to make things look nice, on my screen at least.
      var mousePosition = d3.mouse(this);
      grave.x = mousePosition[0] - 8;
      grave.y = mousePosition[1] - 8;
      draw();
  });

Can you guess the answer to the riddle yet? Let’s add a calculation of the flags’ midpoint and plot our treasure chest on the map.

The Chest

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// modified draw function
function draw() {
  ...
  var treasure = getTreasurePosition(flags);
  // draw the treasure location
  features.selectAll('.treasure')
    .data([treasure])
      .attr('x', getX)
      .attr('y', getY)
    .enter().append('image')
      .attr('xlink:href', 'img/treasure_chest.svg')
      .classed('treasure', true)
      .attr('height', featureLength)
      .attr('width', featureLength)
      .attr('x', getX)
      .attr('y', getY);
    ...
}

function getTreasurePosition(flagPositions) {
  // averages the x and y values of the two flag positions
  return {
    x: (flagPositions[0].x + flagPositions[1].x) / 2,
    y: (flagPositions[0].y + flagPositions[1].y) / 2
  }
}

Success! We’ve now got a clear answer - there’s only a single location where the chest could be. If you play around with the grave position it becomes obvious that the chest’s x-coordinate is the midpoint of the two trees’ x-coordinates and the y coordinate is simply that same midpoint distance added to the y-coordinate of the trees. Here we’re assuming the trees are at the same y-coordinate and remember that y increases in the downward direction on our screen. (The y-coordinate assumption is ok because we could always redraw our coordinate system so that the two trees are level in the y direction.)

The Math

Now that we’ve played around with getting the example to work and seen that it is a single point solution (not a line or other area function) we can take a more informed approach to the math.

The X-coordinate

We’ll use the trick that our x and y coordinates are independent. Lets work in the x-direction first. We know our final x-coordinate is the average of our two flags’ x-coordinates. Lets start with the left tree’s flag. Here we use as the left tree’s x-coordinate, as the left flag’s x-coordinate, as the grave’s x-coordinate and (since X marks the spot) as the chest’s x-coordinate. Going back to our earlier formulas:

Averaging these two we can see that our $g_{y}$ term cancels out.

In our case where we get as the average of and , not dependent on the graveyard location, as we saw in our brute force method.

The Y-coordinate

Now we can do the same for the y-coordinate.

In the case where then , the result we saw earlier in the brute force method.

One More Thing

We actually don’t have it quite right yet, there is an omission. In the cases where the grave lies above the trees (from our vantage point looking down at the map of the island) the left and right trees are actually reversed. Here’s the final implementation accounting for this possibility. Check out the gist at https://gist.github.com/azundo/5928203 for the full final version.

Conclusion

So that’s it. A quick prototype in D3 to brute force our solution so we’ve got some intution on how to go about solving the geometry. Great practice in getting simple things done using d3.js and jogging the old geometry proofs portion of the brain.

Attributions

Thanks to the folks over at The Noun Project for their svg icon sets. Here are the attributions:

  • Tree James Keunning from The Noun Project
  • Grave Alex Fuller from The Noun Project
  • Flag The Noun Project
  • Chest Victor N. Escorsin da silva from The Noun Project

Concurrent Qsort in Go - Part II

After my past attempt at writing a concurrent Qsort algorithm I had a few more thoughts about how to change the architecture.

Instead of creating new channels to pass to every recursively-called goroutine and then blocking on them until they return, I wanted to create only a single channel for communication and find a way to return from goroutines immediately. The solution I came up with is to send back the integer value of the number of elements in their sorted position when a goroutine returns. In the naive case, this is when the list is 0 or 1 elements long, leaving this fairly simple code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

func Cqsort2(s []int) {
    // this channel will collect the number of sorted elements
	returnChannel := make(chan int)
	go cqsort2(s, returnChannel)
    // sum up the number of sorted elements until they equal
    // the length of our original slice
	for sortedElements := 0; sortedElements < len(s); {
		sortedElements += <-returnChannel
	}
	return
}

func cqsort2(s []int, done chan int) {
	if len(s) <= 1 {
	    // report the number of sorted elements to the
        // communication channel
		done <-len(s)
		return
	}

	pivotIdx := partition(s)

	go cqsort2(s[:pivotIdx+1], done)
	go cqsort2(s[pivotIdx+1:], done)
    // this goroutine should now return immediately and
    // doesn't have to block on the child calls
	return
}

This still creates too many goroutines and uses too much memory. So taking a page from most quicksort implementations, lets use a selection sort for the last few elements. Empirically I found a value of about 75 to be ok. Our overall architecture doesn’t have to change, just add the selection sort call in the termination condition of our qsort2 function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

func cqsort2(s []int, done chan int) {
	if len(s) <= 75 {
        // run a selection sort when s is small
        selectionSort(s)
	    // report the number of sorted elements to the
        // communication channel
		done <-len(s)
		return
	}

	pivotIdx := partition(s)

	go cqsort2(s[:pivotIdx+1], done)
	go cqsort2(s[pivotIdx+1:], done)
    // this goroutine should now return immediately and
    // doesn't have to block on the child calls
	return
}

Finally when using GOMAXPROCS=2 I got a better running time for the concurrent version over the non-concurrent Qsort from my last post. This isn’t quite a fair comparison though because I wasn’t using the selectionSort trick in Qsort. Adding it in to Qsort and our previous Cqsort brings all three implementations to about 7s to sort 1 milllion elements. So still no improvements over a sequential implementation despite using both of my cores at 100% in the concurrent cases. Memory and communication overhead still provide too much of a slow down. I’m hoping to get my hands on a computer with 4 cores to see if the concurrent version will see a speedup when doubling the core count again, or if communication overhead is still too high.

Again, all of the code and some benchmarking is in a github repository at https://github.com/azundo/cqsort.git.

Concurrent Quicksort in Go

I’ve been playing around with Go to get some experience in a systems programming language before applying for applying jobs. I’ve never done concurrent/parallel programming so I thought I’d try to learn about some of Go’s concurrency tools by implementing quicksort concurrently.

I started by writing a simple in-place quicksort implementation. The majority of the algorithm happens in a partition function which picks a random pivot and then does in-place swapping to partition around the pivot. With this in place the sequential algorithm falls into place easily.

1
2
3
4
5
6
7
8
9

func Qsort(s []int) {
    if len(s) <= 1 {
        return
    }
    pivotIdx := partition(s)
    Qsort(s[:pivotIdx+1])
    Qsort(s[pivotIdx+1:])
    return
}

Since the divide and conquer nature of quicksort means the recursive calls to Qsort don’t touch the same memory, this should be a decent candidate for concurrency.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func Cqsort(s []int) {
    d := make(chan int)
    go cqsort(s, d)
    <-d
    return
}

func cqsort(s []int, done chan int) {
    // termination condition
    if len(s) <= 1 {
        done <- 1
        return
    }
    // where the work happens
    pivotIdx := partition(s)

    // communication channel
    childChan := make(chan int)
    go cqsort(s[:pivotIdx+1], childChan)
    go cqsort(s[pivotIdx+1:], childChan)

    // block until both concurrent children finish
    for i := 0; i < 2; i++ {
        <-childChan
    }
    // tell our caller we are done
    done <- 1
    return
}

This works but is incredibly slow. Goroutines are cheap but not free. For large s this program spends most of its time in garbage collection as too many goroutines are created.

We need to limit the number of goroutines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

func Cqsort(s []int) {
	if len(s) <= 1 {
		return
	}
	workers := make(chan int, MAXGOROUTINES - 1)
	for i := 0; i < (MAXGOROUTINES-1); i++ {
		workers <- 1
	}
	cqsort(s, nil, workers)
}

func cqsort(s []int, done chan int, workers chan int) {
	// report to caller that we're finished
	if done != nil {
		defer func() { done <- 1 }()
	}

	if len(s) <= 1 {
		return
	}
	// since we may use the doneChannel synchronously
	// we need to buffer it so the synchronous code will
	// continue executing and not block waiting for a read
	doneChannel := make(chan int, 1)

	pivotIdx := partition(s)

	select {
	case <-workers:
		// if we have spare workers, use a goroutine
		// for parallelization
		go cqsort(s[:pivotIdx+1], doneChannel, workers)
	default:
		// if no spare workers, sort synchronously
		cqsort(s[:pivotIdx+1], nil, workers)
		// calling this here as opposed to using the defer
		doneChannel <- 1
	}
	// use the existing goroutine to sort above the pivot
	cqsort(s[pivotIdx+1:], nil, workers)
	// if we used a goroutine we'll need to wait for
	// the async signal on this channel, if not there
	// will already be a value in the channel and it shouldn't block
	<-doneChannel
	return
}

Setting MAXGOROUTINES limits the number of goroutines that ever get created by switching to a synchronous model once the workers channel is exhausted.

This performs much better than before. Benchmarking puts it at about the same speed as the built-in sort.Ints, but still slower than our basic Qsort implementation for a shuffled slice of 1 million elements created by math/rand.Perm. Playing around with MAXGOROUTINES I seemed to get slight variations when using numbers anywhere from 2 to 10000 (make sure you have the GOMAXPROCS environment variable set to the number of cores you want to use so that goroutines are executed in parallel). Above 10000 and performance starts to degrade.

This use of Go’s concurrency features purely for the purpose of parallelizing code goes against Rob Pike’s “Concurrency is not Parallelism” talk, so I’m not surprised that I don’t see a significant speedup when trying to parallelize this concurrent code against the sequential version. I am surprised that I don’t get similar speeds to the sequential version when setting MAXGOROUTINES to 1 as the code is essentially executing sequentially in this case. Perhaps the few extra statements and branches are enough to slow things down considerably. In any case it was a good experiment in writing concurrent Go that also forced me to dive into profiling with pprof and using Go’s support for writing benchmarks in test code.

Code is all up on github at (https://github.com/azundo/cqsort).

Introducing the Azundo Blog

A new day and a new blog. As I transition from my past role as a Market Development Specialist with Engineers Without Borders Canada toward a more technically focused time, I thought it might be useful to start a more technical blog. At one point I had intended to write about technical things over at http://theborrowedbicycle.ca but I’ll keep that for thoughts on personal and human development instead of design and engineering.

The intention of this blog is to keep track of what I’m learning and thinking about as I get my coding chops back to re-enter the technical world. Right now my goal is to simply use this blog to record my progress and learnings for myself and to continue to work on my writing skills and technical communication. I’ve got a few projects that I hope to blog about as I work on them over the summer, aiming to land a job as a software engineer starting in September.