Tic Tacs Toe

script.js

function evaluateBoard(data) {
  /*
   *  Setup
   */
  // Don't want to keep calling .charAt, so save all the values with easier-to-use names up front
  var topLeft = data.charAt(0);
  var topMiddle = data.charAt(1);
  var topRight = data.charAt(2);
  var centerLeft = data.charAt(3);
  var centerMiddle = data.charAt(4);
  var centerRight = data.charAt(5);
  var bottomLeft = data.charAt(6);
  var bottomMiddle = data.charAt(7);
  var bottomRight = data.charAt(8);
  
  // Ways to win: Rows
  var topRow = [topLeft, topMiddle, topRight];
  var centerRow = [centerLeft, centerMiddle, centerRight];
  var bottomRow = [bottomLeft, bottomMiddle, bottomRight];
  
  // Ways to win: Columns
  var leftColumn = [topLeft, centerLeft, bottomLeft];
  var middleColumn = [topMiddle, centerMiddle, bottomMiddle];
  var rightColumn = [topRight, centerRight, bottomRight];
  
  // Ways to win: Diagonals
  var firstDiagonal = [topLeft, centerMiddle, bottomRight];
  var secondDiagonal = [bottomLeft, centerMiddle, topRight];
  
  // Put all the ways to win together in an array of "ways to win"
  var waysToWin = [topRow, centerRow, bottomRow, leftColumn, middleColumn, rightColumn, firstDiagonal, secondDiagonal];
  
  /*
   *  Start actual algorithm to evaluate the board
   */
  // Is there a winner?  Go through each way to win and see if either side won that way
  var isWinner = false;
  var winningSide = null;
  for (var wayToWinIndex = 0; wayToWinIndex < waysToWin.length; wayToWinIndex++) {
    // Which group are we testing in this iteration?
    var targetGroup = waysToWin[wayToWinIndex];
    
    // Test the group to see if it's a winner
    isWinner = groupIsWinner(targetGroup);
    
    // did someone win?
    if (isWinner) {
      // Which side won?
      winningSide = targetGroup[0]; // x or o
      break; // don't have to keep going
    }
  }
  
  // If we have a winner, declare it!
  if (isWinner) {
    return winningSide + ' wins!';
  }
  else { // we don't have a winner
    // is the game incomplete or tie?
    
    // If it's a tie, there won't be any empty squares
    if (data.indexOf('-') === -1) {
      // No empty squares, it's a tie
      return 'The game is a tie';
    }
    else { // there are empty sqaures.  Game is incomplete
      return 'The game is still in progress';
    }
  }
}

function groupIsWinner (group) {
  // Only a winner if the three spaces match and they're not empty
  return group[0] !== '-' &&
         group[0] === group[1] &&
         group[1] === group[2];
}

Tic Tacs Toe.markdown

Tic Tacs Toe

A Pen by Andy Terranova on CodePen.

License.

Okay I spent about an hour. I can chat to you off line / in thread / whenever about these results and why they are the way they are:
http://jsperf.com/andy-s-candygram-2

I've had extremely little exposure to JS, why is there such a performance gain for both removing the function and changing the setup order?

@kmckinley It would be the same in any language. It's a fallacy that in Javascript there is no control over memory, garbage collection etc.
The function is an easy win. Unless it is inlined (which some of the browsers do with enough hints) then you are saving allocation of a stack and a branch. It takes time and effort to do all that.
The setup follows the heuristic that you can use in any managed language (C#, Java, Javascript, etc) in that what is allocated close together in time is close together in space. In a compacting allocator like C# they can only ever get closer in space.
Reading things from memory is expensive, and can only be done in chunks in to the cache - the fastest part of all the memory. By keeping stuff in that short term memory you are avoiding blocking on slow memory reads so you get a ton of performance. Even in Javascript!
Cache is tiny, so the more you can pack in close together the better the performance.

I just converted my C++ answer to JS (actually was mostly a copy and paste job, not many changes needed). It converts things in to 32 bit number first. Now Javascript engines tend to work in 64 bit numbers exclusively, but it is possible for an engine to infer a smaller number. Or if I used one of the webgl type structures. Didn't bother with any of that though.

http://jsperf.com/andy-s-candygram-2/2
( http://codepen.io/paulevans/pen/eNaWxN if you want to play )

You will see that it is a lot faster than any of the previous answers (the original is about 75% slower on Chrome + Mac). It's all about the data!

@supernova-at - should I reply to the email with this or just keep it on the thread?

@paulevans I see. I'm use to the compiler inlining the code (if it thinks it can) for me. Obviously I find breaking out to functions more readable and maintainable. In swift the default behavior is to try to inline, but you can force inlining or outlining by using the @inline(__always) and @inline(never) annotations.

When do you feel readability/maintainability is worth the perf hit? And why not relay on the compile to do this?

Of course JS isn't a compiled language, so maybe that's where I'm getting hung up over this.

@kmckinley I only see a reason to split up a function if it really is going to be used in more than one place. To me theirs a value of being able to read a function top to bottom too rather than jumping around the file constantly for stuff that is only used in that one place anyway.
Plus if it can be reused then you have to rely it will be reused - meaning you are actually adding to the maintenance cost - you have more functions to maintain and cannot change their ins and outs without causing a cascade change.

I am not defending the monolyth function here - I just believe that if you add complexity of the namespace (class, global, whatever) there should be a good reason to do so. Personally I did not find that function compelling enough for ~35% hit on performance. I do not believe that having the function made the code 35% better to read.

Any compiler runs on heuristics - here I know enough about Javascript virtual machines to trigger off some performance ones. So in a sense I am relying on the (just in time) compiler.

The compiler can only reason about a very, very proportion about your code. It really is not that intelligent, it cannot guess your intention. And it often assumes the worst case. You might think of it as an SQL database that will use that primary key index, but you must write your SQL Query in a way that will use that index rather than a full lookup.

Also although inlining is often a good thing, it can also make performance worse. There's an instruction cache and a data cache separately in many architectures - and it is again read in chunks and tiny. So if lots of inlining causes memory reads instead of branching to an instruction already in the cache, then you get a penalty waiting for the next instruction to be read from memory. So inlining all the things is also not a necessarily good thing. Though if the memory access pattern is predictable you may get lucky and have that section pre-read for you (even in Javascript)... as you are sharing that cache with other applications on the same machine that advantage can be lost if you are relying on monopolising the cache.

If readabilty of the performance code is tougher, I would try and educate my teammates so it was more readable for them, should they be interested. After all at one point or another we cannot read language x very easily (in my case Swift), but with enough exposure it becomes second nature.

Awesome thanks. My question my have seemed a little out of context here, I was thinking more of my swift solution since I have three main test functions that are called multiple times.

Also, just to clarify, I wasn't suggesting that this function shouldn't be inline.

@kmckinley I'm not even sure how you would profile swift! I'm such a Mac newbie. I have no idea if it would inline it because there is quite a bit of state and a few branches in there (for loop + if). If you know how to compile it to assembly or some kind of readable intermediate language I'm sure we could figure it out. That's a ton of effort though! With Swift + Mac, I don't even know where to tell you to begin.

@paulevans, awesome! Just getting a chance to read through this now - I'd say keep it here for now, if you want to generalize into something more easily digestible for the thread though, that would be awesome.