How to avoid premature optimization

Three simple rules to develop by if you really want to avoid falling into the trap of premature performance optimization.

eternityA common quote linked with Donald E. Knuth of TeX fame is “premature optimization is the root of all evil”. While this might sound a bit harsh, it holds a lot of truth.

Performance as an asset

If you consider software performance as an asset, you can determine its characteristics and derive your decisions about whether to work on it from them. For example, you will discover that while a good performance is paramount, there is a certain threshold when further optimizations are worthless from the asset’s point of view. If you happen to develop a game, you only need to draw as much frames as the monitor can handle. If you process sensor data in real time, there is no need for a prolonged pause between data packets, because computers don’t grow tired.
If you treat performance as an asset, you can also apply a worth to every optimization you want to make and contrast it to the cost of the work you expect to have to invest. This divides the possible optimizations into a group of lucrative and a (probably larger) group of unprofitable investments.

Simple rules

Treating performance as an asset gives you the mental tools to make profound decisions about when and what to optimize. But there are also three simple rules you can apply if you don’t want to write a business plan every time you think “if I just change this line, the code will run much smoother”.

First rule: Don’t

The first rule of performance optimization with a tendency to avoid premature optimization is to just don’t care. You ask yourself if a LinkedList is faster than an ArrayList for a given use case? The short (and ignorant) answer is: both will be fast enough. Is it better to explicitly set all references to null after usage? Why bother when the garbage collector won’t slow you down anyway. Following this rule, you deliberately act dumber than you are with the goal to delay action.

There is a disclaimer, though. There are two different kinds of performance optimization: The first one was referenced in the examples above and deals with actual, but rather local code changes. The second and more important type of performance consideration deals with complexity theory (the one with big O notation) and isn’t measured in milliseconds, but in scalability. You don’t want to be ignorant of the latter type because it will always ruin your runtime behaviour regardless of any optimization of the former type if you implement an exponential or even factorial algorithm. You can be ignorant of “real performance tuning”, but should always be aware of the complexity category your algorithm is living in.

Second rule: Not Yet

There will be a moment when you clearly see an opportunity to improve the runtime performance of your code with just this very small (and very clever) modification. This is when you are ready to break the first rule. Now you should adhere to the second rule: If the cost is as marginal as you say and the gain is profound, go for it – but not now. Performance tuning isn’t a time limited sale that you are only offered right now or never. You can make the same change and reap the same advantages next week or next month. You doubt that you will remember the details? Write an issue or insert some code comment about it. You probably have another task on your todo list that is more important than speeding up the functionality at hand.

The goal of the first rule was to delay action, and that’s the goal of the second rule, too. You’ve probably guessed it already: you avoid premature optimization best by not optimizing at all or at least not optimizing too early. You need to be sure about the value of an optimization before you implement it. As a result of the second rule, your code will be enriched with possibilities for performance improvement. And if you actually need to improve your performance, you can orient yourself along these possibilities or find them then. You want to invest in the tuning business as late as possible, for it is highly speculative.

Third rule: Measure

If you cannot hold on to the first two rules, for example when a real performance issue is reported, you need to take action. But as you are going to invest work into performance optimization, you can as well invest it efficiently. In most applications, there is a 90/10 rule in effect, stating that 90 percent of the runtime is spent in just 10 percent of the code. If you don’t know exactly where your performance bottleneck is, find it using a profiler and remember the 90/10 rule. It’s not efficient nor effective to improve the 90 percent of your code that doesn’t matter in regard to performance.

If you have identified the piece of code that most likely slows your application down, you should remember the second part of the third rule: Never make performance optimizations without a meaningful benchmark that you can run beforehand and afterwards. All to often, the clever performance trick you remember from long ago is actually hurting your performance now. A meaningful benchmark will tell you if you did good. To make a benchmark “meaningful”, you really need to read up on benchmarking in your target platform. In Java, for example, you need to know about proper warm-up of the VM and perform enough cycles to not include one-time effects in your numbers. If you’ve written such a benchmark, keep it! Try to fully automate it and let it be the cornerstone of your growing performance test suite. There might come the day when this test/benchmark tells you that your formerly clever optimization is now obsolete due to internal platform changes.

Conclusion

If you follow these three simple rules, you won’t automatically write high performance software. But you will spend your valuable time fixing real performance issues instead of tinkering with your code to no effect. You definitely won’t optimize prematurely and steer clear of this “root of all evil”.

Using Rails with a legacy database schema

Rails is known for its convention over configuration design paradigm. For example, database table and column names are automatically derived and generated from the model classes. This is very convenient, but when you want to build a new application upon an existing (“legacy”) database schema you have to explore the configuration side of this paradigm.

The most basic operation for dealing with a legacy schema in Rails is to explicitly set the table_names and the primary_keys of model classes:

class User < ActiveRecord::Base
  self.table_name = 'benutzer'
  self.primary_key = 'benutzer_nr'
  # ...
end

Additionally you might want to define aliases for your column names, which are mapped by ActiveRecord to attributes:

class Article < ActiveRecord::Base
  # ...
  alias_attribute :author_id, :autor_nr
  alias_attribute :title, :titel
  alias_attribute :date, :datum
end

This automatically generates getter, setter and query methods for the new alias names. For associations like belongs_to, has_one, has_many you can explicitly specify the foreign_key:

class Article < ActiveRecord::Base
  # ...
  belongs_to :author, class_name: 'User', foreign_key: :autor_nr
end

Here you have to repeat the original name. You can’t use the previously defined alias attribute name. Another place where you have to live with the legacy names are SQL queries:

q = "%#{query.downcase}%"
Article.where('lower(titel) LIKE ?', q).order('datum')

While the usual attribute based finders such as find_by_* are aware of ActiveRecord aliases, Arel queries aren’t:

articles = Article.arel_table
Article.where(articles[:titel].matches("%#{query}%"))

And lastly, the YML files with test fixture data must be named after the database table name, not after the model name. So for the example above the fixture file name would be benutzer.yml, not user.yml.

Conclusion

If you step outside the well-trodden path of convention be prepared for some inconveniences.

Next part: Primary key schema definition and value generation

CMake as a project model

One thing I actually like about Maven is its attempt to create a project model, conventions and a basic project structure. It allows easy integration IDEs, build servers and so on. For projects in C/C++ I find CMake an attractive way to specify the project model.

Despite its name CMake is not really a build system but more of a cross-platform project description with an integrated build system generator. Cross-platform means not only operating system (OS) here but development environment in general. CMake thus can generate project files for MS Visual Studio 20xx, Eclipse CDT, Code::Blocks, KDevelop and the like. QtCreator can even import a CMake-based project natively which brings you up to speed in almost no time.

CMake allows you organise your project in modules and manage your external dependencies. It does not impose as strict rules as Maven does and lacks an own artifact repository infrastructure but you can use the CMake package definitions or pkg-config information many projects provide.

Packaging and deployment with CPack allows you to deliver releases of your project the way your user would expect it: Depending on the target platform you can package your software as a Windows installer executable (using NSIS), several options for Mac OS X (like Package Maker or Bundle) and the popular DEB and RPM package formats for Linux Distributions.

Conclusion

CMake is more than just another build system. It is a flexible tool to define your project and integrate it with your favorite development tools. It can support the whole project lifecyle from initial creation and normal development to deployment and delivery of your software to the user.

Solution for ng-quiz #1: LetterCrush

The solution for ng-quiz #1 using Angularjs with services, controllers and the File API.

In this solution for the first ng-quiz you learn about Angularjs in general using controller and services. Also you learn about using the HTML File API. You can download the source at my GitHub repository.

The HTML for this solution is pretty straightforward: (we omit the CSS here)

<!DOCTYPE html>
<html>
  <head>
    <script type="text/javascript" src="https://ajax.googleapis.com/ajax/libs/angularjs/1.2.11/angular.min.js"></script>
    <script type="text/javascript" src="lettercrush.js"></script>

    <link rel="stylesheet" href="http://netdna.bootstrapcdn.com/bootstrap/3.1.0/css/bootstrap.min.css">
    <link rel="stylesheet" href="http://netdna.bootstrapcdn.com/bootstrap/3.1.0/css/bootstrap-theme.min.css">
    <link rel="stylesheet" href="lettercrush.css">
  </head>
  <body>
    <div ng-app="LetterCrush" class="container">
      <div ng-controller="LetterCrush" class="col-md-9">
        <div class="jumbotron">
          <h1>Letter Crush</h1>
          <p>Fun with words</p>
        </div>
        <div class="col-md-7">
          <div class="form-group">
            <label for="dictionary" class="control-label">Please choose a dictionary to play with (one word per line)</label>
            <input type="file" id="dictionary" ng-model="file">
          </div>
        </div>
        <div class="col-md-5">
          <form ng-submit="testWord()">
            <div class="form-group">
              <label for="score" class="control-label">Your score</label>
              <span class="form-control-static"><big>{{score}}</big></span>
            </div>
            <div class="form-group">
              <label for="word" class="control-label">Your word</label>
              <input ng-model="word" type="text" id="word">
            </div>
          </form>
        </div>
        <div class="col-md-12">
          <table class="table">
            <tr ng-repeat="row in board.content track by $index"><td ng-repeat="cell in row track by $index">{{cell}}</td></tr>
          </table>
        </div>
    </div>
  </body>
</html>

The bits you should take a deeper look at are the attributes starting with ng (called Angularjs directives) and the variables enclosed in double curly braces. Directives are the glue between JavaScript and the DOM. The first important ng attribute is ng-app in line 12. The value of the ng-app attribute is the name of the module used inside the JavaScript.

var module = angular.module("LetterCrush", []);

Everything inside this div is treated specially by Angularjs. So you can use references like {{score}}. These references enclose expressions which evaluate properties defined on the Angularjs $scope object. For bundling functionality you can use controllers. Controllers are used by setting ng-controller. In line 13 we declare a controller named LetterCrush. This controller is defined inside the JavaScript like

module.controller('LetterCrush', ['$scope', 'board', 'dictionary', 'util',
                  function ($scope, board, dictionary, util) {
}]);

The strings in the array are the dependencies which should be injected. Every declared dependency needs to be a parameter in the function which implements the functionality of the controller. Angularjs’ own objects are prefixed with $ as you see with $scope. All other ones are defined by us using a concept called services. These services are defined similar to controllers but with a factory.

// with no special dependencies, just jQueryLite $q and log
module.factory('fileReader', function($q, $log) {
});

// with our own dependencies
module.factory('board', ['letterGenerator', 'wordFinder', function(letterGenerator, wordFinder) {
}]);

The factory returns an object. Services are singletons and are commonly used for backend access, service like functionality or model like objects. Services can be injected into other services, directives or controllers.

All expressions enclosed in double curly braces or as value of a ng-model directive are used for two way data binding. These expressions are evaluated on the $scope object and all changes either from the DOM or via JavaScript are reflected on the other side. This means when the user enters text into the input in line 32 $scope.word is updated with the value. Also if the code updates $scope.word the value of the input is updated accordingly.

In this solution we use two other directives: ng-submit and ng-repeat. ng-submit just calls a function when the form is submitted and ng-repeat repeats the enclosed DOM subtree for every item in the passed array. Note here the track by in line 38. Normally Angularjs tracks the item by its value but since we can have the same letter more than once we need a different tracking mechanisms, so we use the index of the array here.

Accessing local files can only be done when they are inside a file input. We adapted a solution from ode to code for handling the details of the file API.

// FileReader service
// adapted from http://odetocode.com/blogs/scott/archive/2013/07/03/building-a-filereader-service-for-angularjs-the-service.aspx
module.factory('fileReader', function($q, $log) {
  var onLoad = function(reader, deferred, scope) {
    return function () {
      scope.$apply(function () {
        deferred.resolve(reader.result);
      });
    };
  };
  var onError = function (reader, deferred, scope) {
    return function () {
      scope.$apply(function () {
        deferred.reject(reader.result);
      });
    };
  };
  var onProgress = function(reader, scope) {
    return function (event) {
      scope.$broadcast("fileProgress", {
                        total: event.total,
                        loaded: event.loaded
                      });
    };
  };
  var getReader = function(deferred, scope) {
    var reader = new FileReader();
    reader.onload = onLoad(reader, deferred, scope);
    reader.onerror = onError(reader, deferred, scope);
    reader.onprogress = onProgress(reader, scope);
    return reader;
  };
  var readAsText = function (file, scope) {
    var deferred = $q.defer();
            
    var reader = getReader(deferred, scope);         
    reader.readAsText(file);
            
    return deferred.promise;
  };

  return {readAsText: readAsText};
});

We can then use this service to read out the file. Therefore we need to listen to changes of the input and then read out the content:

module.factory('dictionary', ['fileReader', 'util', function(fileReader, util) {
  var dictionary = [];
  var init = function(scope) {
    var getFile = function (evt) {
      fileReader.readAsText(evt.target.files[0], scope).then(function(result) {
        dictionary = result.split("\n");
      });
    };
    document.getElementById('dictionary').addEventListener('change', getFile, false);
  };
  var containsWord = function(w) {
    return util.containsIgnoreCase(dictionary, w);
  };
  var isEmpty = function() {
    return dictionary.length === 0;
  };
  return {init: init, containsWord: containsWord, isEmpty: isEmpty};
}]);

The fibonacci sequence for calculating the score and the random letter generation are pretty straightforward.

module.factory('util', function($q, $log) {
  var containsIgnoreCase = function(array, e) {
    for (var i = 0; i < array.length; i++) {
      if (e.toUpperCase() === array[i].toUpperCase()) {
        return true;
      }
    }
  return false;                        
  };
  var fib = function(n) {
    if (n === 0) {
      return 0;
    }
    if (n === 1) {
      return 1;
    }
    return fib(n - 1) + fib(n - 2);
  };
  return {containsIgnoreCase: containsIgnoreCase, fib: fib};
});

module.factory('letterGenerator', function($q, $log) {
    var frequencies = [8.167,1.492,2.782,4.253,12.702,2.228,2.015,6.094,6.966,0.153,0.772,4.025,2.406,6.749,7.507,1.929,0.095,5.987,6.327,9.056,2.758,0.978,2.360,0.150,1.974,0.074];
    var codeA = 65;
    var newLetter = function() {
        var frequency = Math.random() * 100;
        for (var i = 0; i < frequencies.length; i++) {
            frequency -= frequencies[i];
            if (frequency <= 0) {
                return String.fromCharCode(codeA + i);
            }
        }
        return 'Z';
    };
    return {newLetter: newLetter};
});

One slightly more difficult piece is the algorithm for finding the word on the board. Here we used a depth first search and represent the neighbours as an array instead of two loops which improves the readability of the algorithm.

module.factory('wordFinder', function($q, $log) {
  var insideBoard = function(board, row, column) {
    return row >= 0 && column >= 0 && row < board.length && column < board[row].length;
  };
  var neighboursOf = function(cell) {
    return [
      [cell[0] - 1, cell[1] - 1], [cell[0] - 1, cell[1]], [cell[0] - 1, cell[1] + 1],
      [cell[0],     cell[1] - 1],                         [cell[0],     cell[1] + 1],
      [cell[0] + 1, cell[1] - 1], [cell[0] + 1, cell[1]], [cell[0] + 1, cell[1] + 1]
    ];
  };
  var contains = function(array, e) {
    for (var i = 0; i < array.length; i++) {
      if (e[0] === array[i][0] && e[1] === array[i][1]) {
        return true;
      }
    }
    return false;                        
  };
  var findNextLetter = function(board, word, path) {
    if (word.length === 0) {
      return path;
    }
    var position = path[path.length - 1];
    var neighbours = neighboursOf(position);
    for (var i = 0; i < neighbours.length; i++) {
      var neighbour = neighbours[i];
      if (!insideBoard(board, neighbour[0], neighbour[1])) {
        continue;
      }
      if (contains(path, neighbour)) {
        continue;
      }
      if (word.charAt(0).toUpperCase() === board[neighbour[0]][neighbour[1]]) {
        var foundPath = findNextLetter(board, word.slice(1), path.concat([neighbour]));
        if (foundPath) {
          return foundPath;
        }
      }
    }
    return null;
  };
  var find = function(board, word) {
    var foundPath;
    angular.forEach(board, function(row, i) {
      angular.forEach(row, function(column, j) {
        if (word.charAt(0).toUpperCase() === column) {
          var path = findNextLetter(board, word.slice(1), [[i, j]]);
          if (path) {
            foundPath = path;
          }
        }
      });
    });
    return foundPath;
  };

  return {find: find};
});

For the board we use an Angularjs service and encapsulate the letters as a two dimensional array, the word finding algorithm, the letter generation and the logic for clearing and falling of letters.

module.factory('board', ['letterGenerator', 'wordFinder', function(letterGenerator, wordFinder) {
  var content = [];
  var init = function(boardSize) {
    for (var lineNo = 0; lineNo < boardSize; lineNo++) {
      var line = [];
      for (var count = 0; count < boardSize; count++) {
        line.push(letterGenerator.newLetter());
      }
      content.push(line);
    }
  };
  var fall = function() {
    for (var i = content.length - 1; i > 0; i--) {
      for (var j = 0; j < content[i].length; j++) {
        if (content[i][j] === '') {
          for (var k = i - 1; k >= 0; k--) {
            if (content[k][j] !== '') {
              content[i][j] = content[k][j];
              content[k][j] = '';
              break;
            }
          }
        }
      }
    }
  };
  var fillEmpty = function() {
    angular.forEach(content, function(row, i) {
      angular.forEach(row, function(column, j) {
        if (column === '') {
          content[i][j] = letterGenerator.newLetter();
        }
      });
    });
  };
  var clear = function(path) {
    angular.forEach(path, function(pos, i) {
      content[pos[0]][pos[1]] = '';
    });
    fall();
    fillEmpty();
  };
  var find = function(word) {
    return wordFinder.find(content, word);
  };
  return {content: content, init: init, clear: clear, find: find};
}]);

Finally we glue everything together inside the controller:

module.controller('LetterCrush', ['$scope', 'board', 'dictionary', 'util',
                  function ($scope, board, dictionary, util) {
    var penalty = 1;

    $scope.score = 0;
    $scope.board = board;
    board.init(5);
    
    dictionary.init($scope);
    
    $scope.testWord = function() {
      if (dictionary.isEmpty()) {
        alert('Please specify a dictionary file.');
        return;
      }
      if (!dictionary.containsWord($scope.word)) {
        $scope.score -= penalty;
        alert($scope.word + ' is no word.');
        $scope.word = '';
        return;
      }
      var found = $scope.board.find($scope.word);
      if (!found) {
        $scope.score -= penalty;
        alert($scope.word + ' is not on the board.');
        $scope.word = '';
        return;
      }
      $scope.score += $scope.calculateScore(found.length);
      $scope.word = '';
      $scope.board.clear(found);
    };
    $scope.calculateScore = function(len) {
        return util.fib(len);
    };
}]);

This concludes our first ng-quiz. We hope you had fun and learned something along the way. If you have questions or improvements please don’t hesitate to comment. In the next ng-quiz we tackle a smaller piece of functionality since this first one seemed a bit too big.

Three essential developer values

We reflected on the inner values of our team and came up with a short list that might sound trivial to you, but is honest in its motivation.

value-coinThere is the notion of “professional attitude” in software development. In the recent years, the agile movement, the craftsmanship philosophy, the pragmatic approach and the clean code developer initiative all tried (and certainly kind of accomplished) to install a set of values in developers. Most of these values are important and probably self-evident to those of us that can transcribe them into actual work decisions. It just feels right to do certain things or do something a certain way.

Local values

But what if you are challenged to articulate your own core values without using a common template like “the values of the clean code developer”? Let’s say that recurring conflicts force you to spell out the (in your view) most self-evident things to be able to describe the root of your unease. Every group of collaborators shares a set of “unspoken laws” and common beliefs that lay below the threshold of conscious application and are hard to describe to outsiders. We reflected on these core values in the last time and came up with a set of “local values” that are important to us. This blog post tries to explain them.

Probably trivialities

Before I list our three essential developer values, I want to damp your expectation about a great revelation and a whole new set of values that nobody’s ever thought about. All the value set templates listed above had and still have a great influence on us and are explored in our daily work. So you’ve probably already heard about every thought we could come up with. And our results are probably trivialities to most of you. That’s great! We didn’t set out to research something new, we tried to articulate our most mundane motivations and standards.

The three values

The following list is ordered. I start with the least of the three values and end with the most important one. That’s not to say that this list includes all values of ours, it just lists the three most important ones to adhere to the spirit of brevity (and relevance).

Efficiency

Yes, efficiency is the third most important skill to master when working with us. It’s a platitude in the sense that “you should be efficient” – of course you should. But we defined some aspects of efficiency that are vital to our work culture. Our developers need a heightened capability of self-inspection in regard of “being stuck”. You know that feeling when your work breaks apart into an overwhelming amount of tedious little steps? Or when you always feel like success is right around the corner, but always just out of reach? That’s just two of many aspects of getting stuck. We expect our developers to raise their hands and ask for help as soon as they sense the faintest amount of “stuckness” in their work. It takes a lot of self-confidence to admit that the task at hand is too much to handle alone, at least right now. We don’t count your report of being stuck as a personal failure, but a team-wide possibility to gain efficiency by reducing waste (wasted time in this case).
To avoid getting overwhelmed by a task in the first place, we expect our developers to assess their abilities and “readiness” towards a specific task and give an honest evaluation if they think to be “the right one for the task”. There again, pride and over-confidence can prove utterly destructive and diminish overall efficiency.

Communication

While communication itself is a tool, not a value, we rely on the proper application of this tool enough to value it our second most important trait to master. The most important question to ask is “has anybody done something similar yet?”. There is no point in re-inventing the wheel or re-learning the same lessons again and again. Don’t make assumptions – ask for specific details if necessary. Don’t be afraid to appear dumb – you’ll look even dumber if you didn’t ask and screw up. There are many aspects to communication that can go wrong.
In accordance with the efficiency value, we also expect you to be proactive to report problems or even uncertainty. Every failure contains a failure in communication. Even if you can just announce that everything goes smoothly up to this point, this is an information worth noting. After each waypoint or iteration in your current task, make a commit and leave a comment in your issue. Stay in touch with your team and don’t retreat into a “me against the world” kind of solitude. In short, we expect our developers to be open, honest and proactive in their communication.

Reliability

Our most important value is reliability in the sense of trustworthiness. We want and need to trust our developers, their estimations and commitments and the repeatability of their successes. There is no benefit in “faking it” or taking credit for something you achieved by pure luck. We try to have a working atmosphere were we can rely on another, trust another and also be open with our shortcomings. There is no need to pretend, for we will ultimately see through the ruse. We want our developers to contribute to the team, not to groom their ego. In a reliable work relation, you can trust the other to deliver what was mutually agreed upon or report problems at the first moment possible. And you can expect to be valued and commended for “just doing your job”. There is a lot of the craftsman ideology in this approach and it ultimately resolves to the commandments of egoless programming. The result is a fearless, positive environment for everybody to develop their unique abilities and strength. And don’t you worry about your weak points – the team got you covered.

Epilogue

I hope that my shortcomings with the english language didn’t stop you from grasping the core concepts of our local value set. We mostly apply it subconsciously and definitely aren’t perfect in any aspect. But just to articulate our deeper motives helped a lot to dissect certain conflicts and gain a broader understanding exactly why we do certain things. I don’t suggest you should adopt our values, that wouldn’t probably work out. But I encourage you and your team to invest some time to reflect on your local value set and try to find a mutually understood verbalization of them. If you can share your insights on this topic, please leave a comment! We would love to hear from you.

Introducing ng-quiz – a JavaScript / Angular quiz: #1 Letter Crush

Learning a new language or framework can be quite daunting. It helps me when I have small tasks which motivate me to explore my chosen field further and in a fun and goal driven way. So in the spirit of the Ruby quiz I introduce ng-quiz, a quiz for learning Angularjs.

Learning a new language or framework can be quite daunting. It helps me when I have small tasks which motivate me to explore my chosen field further and in a fun and goal driven way. So in the spirit of the Ruby quiz I introduce ng-quiz, a quiz for learning Angularjs. Every month I post a small task which should be solved in a short time and helps you to learn and deepen your Angularjs and JavaScript skills. It will touch different areas and explores other JavaScript libraries. You can post your solutions (as a link to a jsfiddle or github) as a comment. Two weeks later I will update the post with the solutions.

ng-quiz #1: Letter Crush

In the first quiz you will implement a simple game named ‘Letter Crush’. In ‘Letter Crush’ a player tries to find letters forming a word in a random letter ‘soup’. The board consists of nxn quadratic cells containing a random letter.

A	G	H	M	I
T	C	O	U	E
F	E	P	R	Q
K	D	S	A	N
V	L	F	T	Y

The player can enter a word. This word must be in an english dictionary and needs to be found without overlapping. If both criteria are satisified, the word is removed from the board, the letters above the empty cells fall down and the top most empty cells are filled with new random letters.

Example

A	G	H	M	I
T	C	O	U	E
F	E	P	R	Q
K	D	S	A	N
V	L	F	T	Y

If the player enters the word ‘test’ (case insensitive) and since it is a real word the letters are removed from the board.

A	G	H	M	I
 	C	O	U	E
F	 	P	R	Q
K	D	 	A	N
V	L	F	 	Y

Now the letters above fall down.

 	 	 	 	I
A	G	H	M	E
F	C	O	U	Q
K	D	P	R	N
V	L	F	A	Y

The top most empty cells are filled again.

I	W	S	T	I
A	G	H	M	E
F	C	O	U	Q
K	D	P	R	N
V	L	F	A	Y

Now the next turn begins and the player could enter RUN, ACORN, MOURN, THORN or GO or others.

Letter Generation

To not fill the board with garbage letters, the new letters need to be generated taking the relative frequency of letters in the english language.

A B C D E F G
8.167 1.492 2.782 4.253 12.702 2.228 2.015
H I J K L M N
6.094 6.966 0.153 0.772 4.025 2.406 6.749
O P Q R S T U
7.507 1.929 0.095 5.987 6.327 9.056 2.758
V W X Y Z
0.978 2.360 0.150 1.974 0.074

Words

Entering a word could be done via the mouse or the keyboard. To form a valid word the letters need to be direct or diagonal adjacent. Every letter can be used only once.

Score

The player starts with a score of 0. A wrong input reduces the score by 1. A valid word is scored by its length and according to the following fibonacci sequence:

Length 1 2 3 4 5 6 7
Score 1 1 2 3 5 8 13

Optional fun: special fields

The above version of ‘Letter Crush’ is playable but if the task is too small for you or you want to explore it further, you can implement some special fields.

Duplication – lower case letter

A duplication field consists of a lower case letter and doubles the score of the word. It has a frequency of 5 percent.

Wildcard – ?

A wild card can be used as any letter and is represented as a question mark. It should be generated with 0.5 percent.

Extension – +

An extension field just lengthen a word if it is adjacent to the last letter. A plus sign marks the field and is generated with a relative frequency of 1 percent.

Bomb – *

An asterisk shows a bomb and is produced every 0.25 percent. A bomb detonates when the chosen word is adjacent to it. Every letter which is not part of the word but adjacent to the bomb is also removed.

Example:

B	M	A	S
O	R	B	*
N	B	T	B
E	U	O	L

The player chooses the word bomb and the bomb detonates. So after the removal but before the filling it looks like:


	R		
N	B		
E	U	O	L

P.S. if you are new in JavaScript and coming from a Java background you might find our JavaScript for Java developers post helpful.

Testing C++ code with OpenCV dependencies

This is a documentation of a problem I ran into when I wrote C++ tests for a simple function, inclusive workaround.

The story:

Pushing for more quality and stability we integrate google test into our existing projects or extend test coverage. One of such cases was the creation of tests to document and verify a bugfix. They called a single function and checked the fields of the returned cv::Scalar.

TEST(ScalarTest, SingleValue) {
  ...
  cv::Scalar actual = target.compute();
  ASSERT_DOUBLE_EQ(90, actual[0]);
  ASSERT_DOUBLE_EQ(0, actual[1]);
  ASSERT_DOUBLE_EQ(0, actual[2]);
  ASSERT_DOUBLE_EQ(0, actual[3]);
}

Because this was the first test using OpenCV, the CMakeLists.txt also had to be modified:

target_link_libraries(
  ...
  ${OpenCV_LIBS}
  ...
)

Unfortunately, the test didn’t run through: it ended either with a core dump or a segmentation fault. The analysis of the called function showed that it used no pointers and all variables were referenced while still in scope. What did gdb say to the segmentation fault?

(gdb) bt
#0  0x00007ffff426bd25 in raise () from /lib64/libc.so.6
#1  0x00007ffff426d1a8 in abort () from /lib64/libc.so.6
#2  0x00007ffff42a9fbb in __libc_message () from /lib64/libc.so.6
#3  0x00007ffff42afb56 in malloc_printerr () from /lib64/libc.so.6
#4  0x00007ffff54d5135 in void std::_Destroy_aux&amp;lt;false&amp;gt;::__destroy&amp;lt;testing::internal::String*&amp;gt;(testing::internal::String*, testing::internal::String*) () from /usr/lib64/libopencv_ts.so.2.4
#5  0x00007ffff54d5168 in std::vector&amp;lt;testing::internal::String, std::allocator&amp;lt;testing::internal::String&amp;gt; &amp;gt;::~vector() ()
from /usr/lib64/libopencv_ts.so.2.4
#6  0x00007ffff426ec4f in __cxa_finalize () from /lib64/libc.so.6
#7  0x00007ffff54a6a33 in ?? () from /usr/lib64/libopencv_ts.so.2.4
#8  0x00007fffffffe110 in ?? ()
#9  0x00007ffff7de9ddf in _dl_fini () from /lib64/ld-linux-x86-64.so.2
Backtrace stopped: frame did not save the PC

Apparently my test had problems at the end of the test, at the time of object destruction. So I started to eliminate every statement until the problem vanished or no statements were left. The result:

#include &quot;gtest/gtest.h&quot;
TEST(DemoTest, FailsBadly) {
  ASSERT_EQ(1, 0);
}

And it still crashed! So the code under test wasn’t the culprit. Another change introduced previously was the addition of OpenCV libs to the linker call. An incompatibility between OpenCV and google test? A quick search spitted out posts from users experiencing the same problems, eventually leading to the entry in OpenCVs bug tracker: http://code.opencv.org/issues/1608 or http://code.opencv.org/issues/3225. The opencv_ts library which appeared in the stack trace, exports symbols that conflict with google test version we link against. Since we didn’t need opencv_ts library, the solution was to clean up our linker dependencies:

Before:

find_package(OpenCV)

 

/usr/bin/c++ CMakeFiles/demo_tests.dir/DemoTests.cpp.o -o demo_tests -rdynamic ../gtest-1.7.0/libgtest_main.a -lopencv_calib3d -lopencv_contrib -lopencv_core -lopencv_features2d -lopencv_flann -lopencv_gpu -lopencv_highgui -lopencv_imgproc -lopencv_legacy -lopencv_ml -lopencv_nonfree -lopencv_objdetect -lopencv_photo -lopencv_stitching -lopencv_ts -lopencv_video -lopencv_videostab ../gtest-1.7.0/libgtest.a -lpthread -lopencv_calib3d -lopencv_contrib -lopencv_core -lopencv_features2d -lopencv_flann -lopencv_gpu -lopencv_highgui -lopencv_imgproc -lopencv_legacy -lopencv_ml -lopencv_nonfree -lopencv_objdetect -lopencv_photo -lopencv_stitching -lopencv_ts -lopencv_video -lopencv_videostab

After:


find_package(OpenCV REQUIRED core highgui)

 

/usr/bin/c++ CMakeFiles/demo_tests.dir/DemoTests.cpp.o -o demo_tests -rdynamic ../gtest-1.7.0/libgtest_main.a -lopencv_highgui -lopencv_core ../gtest-1.7.0/libgtest.a -lpthread

Lessons learned:

Know what you really want to depend on and explicitly name it. Ignorance or trust in build tools’ black magic is a recipe for blog posts.

Integrating googletest in CMake-based projects and Jenkins

In my – admittedly limited – perception unit testing in C++ projects does not seem as widespread as in Java or the dynamic languages like Ruby or Python. Therefore I would like to show how easy it can be to integrate unit testing in a CMake-based project and a continuous integration (CI) server. I will briefly cover why we picked googletest, adding unit testing to the build process and publishing the results.

Why we chose googletest

There are a plethora of unit testing frameworks for C++ making it difficult to choose the right one for your needs. Here are our reasons for googletest:

  • Easy publishing of result because of JUnit-compatible XML output. Many other frameworks need either a Jenkins-plugin or a XSLT-script to make that work.
  • Moderate compiler requirements and cross-platform support. This rules out xUnit++ and to a certain degree boost.test because they need quite modern compilers.
  • Easy to use and integrate. Since our projects use CMake as a build system googletest really shines here. CppUnit fails because of its verbose syntax and manual test registration.
  • No external dependencies. It is recommended to put googletest into your source tree and build it together with your project. This kind of self-containment is really what we love. With many of the other frameworks it is not as easy, CxxTest even requiring a Perl interpreter.

Integrating googletest into CMake project

  1. Putting googletest into your source tree
  2. Adding googletest to your toplevel CMakeLists.txt to build it as part of your project:
    add_subdirectory(gtest-1.7.0)
  3. Adding the directory with your (future) tests to your toplevel CMakeLists.txt:
    add_subdirectory(test)
  4. Creating a CMakeLists.txt for the test executables:
    include_directories(${gtest_SOURCE_DIR}/include)
    set(test_sources
    # files containing the actual tests
    )
    add_executable(sample_tests ${test_sources})
    target_link_libraries(sample_tests gtest_main)
    
  5. Implementing the actual tests like so (@see examples):
    #include "gtest/gtest.h"
    
    TEST(SampleTest, AssertionTrue) {
        ASSERT_EQ(1, 1);
    }
    

Integrating test execution and result publishing in Jenkins

  1. Additional build step with shell execution containing something like:
    cd build_dir && test/sample_tests --gtest_output="xml:testresults.xml"
  2. Activate “Publish JUnit test results” post-build action.

Conclusion

The setup of a unit testing environment for a C++ project is easier than many developers think. Using CMake, googletest and Jenkins makes it very similar to unit testing in Java projects.

Learning JavaScript: Great libraries

After taking a look at JavaScript as a language we continue with some interesting and helpful libraries for web development.

After taking a look at JavaScript as a language we continue with some interesting and helpful libraries for web development.

underscore – going the functional route

What: Underscore has a lot of utility functions for helping with collections, arrays, objects, functions and even some templating.

How: Just a glimpse at the many, many functions provided (taken from the examples at underscorejs.org)

_.map([1, 2, 3], function(num){ return num * 3; });
=> [3, 6, 9]

_.map({one: 1, two: 2, three: 3}, function(num, key){ return num * 3; });
=> [3, 6, 9]

_.every([true, 1, null, 'yes'], _.identity);
=> false

_.groupBy([1.3, 2.1, 2.4], function(num){ return Math.floor(num); });
=> {1: [1.3], 2: [2.1, 2.4]}

_.escape('Curly, Larry & Moe');
=> "Curly, Larry &amp; Moe"

var compiled = _.template("hello: <%= name %>");
compiled({name: 'moe'});
=> "hello: moe"

Why: JavaScript is a functional language but its standard libraries miss a lot of the functional goodies we are used to from other languages. Here underscore comes to the rescue.

when.js – lightweight concurrency

What: When.js is a lightweight implementation of the promise concurrency model.

How:

var when = require('when');
var rest = require('rest');

when.reduce(when.map(getRemoteNumberList(), times10), sum)
    .done(function(result) {
        console.log(result);
    });

function getRemoteNumberList() {
    // Get a remote array [1, 2, 3, 4, 5]
    return rest('http://example.com/numbers').then(JSON.parse);
}

function sum(x, y) { return x + y; }
function times10(x) {return x * 10; }

Why: Concurrency is hard. Callbacks can get out of hand pretty quickly even more so when they are nested. Promises make writing and reading concurrency code simpler.

require.js – modules (re)loaded

What: Require.js uses a common module format (AMD – Asynchronous Module Definition) and helps you loading them.

How: You include your module loading file as a data-main attribute on the script tag.

<script data-main="js/app.js" src="js/require.js"></script>

Inside your module loading file you define the modules you want to load and where they are located.

requirejs.config({
    baseUrl: 'js/lib',
    paths: {
        app: '../app'
    }
});

requirejs(['jquery', 'canvas', 'app/sub'],
function   ($,        canvas,   sub) {
    //jQuery, canvas and the app/sub module are all
    //loaded and can be used here now.
});

Why: Your scripts need to be in modules, cleanly separated from each other. If you don’t have an asset pipeline want to load your modules asynchronously or just want to manage your modules from your JavaScript require.js is for you.

bower – packages managed

What: Bower lets you define your dependencies.

How: Just define a bower.json file and run bower install

{
	"name": "My project",
	"version": "0.1.0",
	"dependencies": {
		"jquery": "1.9",
		"underscore": "latest",
		"requirejs": "latest"
	}
}

Why: Proper dependency management is a tough nut to crack and it is even harder to be pleasantly used (I am looking at you, maven).

grunt – the worker

What: Grunt is a task runner or build tool much like Java’s Ant.

How: Create a GruntFile and start automating:

module.exports = function(grunt) {

  grunt.initConfig({
    pkg: grunt.file.readJSON('package.json'),
    uglify: {
      options: {
        banner: '/*! <%= pkg.name %> <%= grunt.template.today("yyyy-mm-dd") %> */\n'
      },
      build: {
        src: 'src/<%= pkg.name %>.js',
        dest: 'build/<%= pkg.name %>.min.js'
      }
    }
  });

  grunt.loadNpmTasks('grunt-contrib-uglify');
  grunt.registerTask('default', ['uglify']);
};

Why: Repetitive tasks need to be automated. If you plan to use grunt and bower consider using yeoman which combines both into a workflow.

d3 – visualizations

What: d3 – data driven documents, a library for manipulating the DOM based on data using HTML, CSS and SVG.

How: There are many, many examples on d3js.org but to get a glimpse on how d3 works, here a small example.

Why: There are tons of chart or visualization libraries out there but d3 takes a more general approach. It defines a way of thinking, a way of manipulating the document based on data and data alone. It treats the DOM as part of your web application. Your visualization is a part of your document and not just a component you can forget about after creating it. This general approach allows you to create arbitrary visualizations not just charts.

last but not least: jQuery

What: jQuery is more of a collection of libraries then a single one, It features AJAX, effects, events, concurrency, DOM manipulation and general utility functions for collections, functions and objects.

How: Here we can just take a very quick overview because jQuery is so big.

// DOM querying and manipulation
$('.cssclass').each(function (index, element) {
  $(element).attr('name') = 'new name';
});

// AJAX calls
$.get('/blog/posts', function(data) {
  $('.posts').html(data);
});

// events
$( document ).ready(function() {
  console.log('DOM loaded');
});

// deferred objects aka promises
$.when(asyncEvent()).then(
  function( status ) {
    // done
  },
  function( status ) {
    // fail
  },
  function( status ) {
    // progress
  }
);

// utilities
var object = $.extend({}, object1, object2);

$('li').each(function(index) {
  console.log(index + ": " + $(this).text());
});

Why: jQuery is almost ubiquitous and this is not by chance. It provides a great foundation and helps in many common scenarios.

Others

There are many more libraries out there and I would appreciate a pointer to a great library. This article can only give a short glimpse so please take a further look at their respective homepages. A word on testing or test runners: these will get an additional blog post.

Our recruitment process

We are a small company that doesn’t hire often. But when we do, we try to make the process as effective and pleasant for everybody involved as possible. Here’s what we do.

huerdenlaufWe are a small company with a focus on delivering high quality software to our customers. Therefore every developer represents a substantial share of our organization. Every time we hire, we need to make sure that the decision in favor or against a new employee is profound. So we established a recruitment process that tries to evaluate and communicate both our requirements and the possibilities of the candidate. Without going into details, this is how we will interact with you if you apply for a job.

First contact

The first contact is usually an application including a curriculum vitae sent to us by the candidate. We will read your application and look for possible matches with our required skill set. If there is a chance to work together in the future, we will answer back with an invitation for a first talk, usually done via telephone.

The first talk is mostly a getting to know each other on a communicative level. We might ask some questions about your curriculum or past jobs, but the main purpose is to establish a mutual understanding. We probably end the talk with an appointment for a first meeting.

First meeting

We really want to know who you are, not only what you can offer on a professional level. Remember that you will represent our company substantially if we hire you. Both sides need to be sure that they understand what they commit to. Because it always is a real commitment and a substantial investment for us to hire a new developer.

The first meeting will be rather short and kept on a casual level. We don’t want to build up pressure, we don’t want to judge your abilities as a developer, we want to get a first impression of you in person. And you will get a full tour of our company and get to know the whole development team, also as a first impression. If you like what you see, we will make an appointment for a second meeting that will go into the details.

Detailed meeting

The second meeting will be much longer and more stressful than the first meeting. The goal of this meeting is the examination of your professional skills. Most companies use trick questions or “how to approach this?” tasks to challenge your abilities to solve difficult problems and deduce your skills from that. We decided not to do that.

We want to see your performance in a normal work situation – as normal as it can be under the circumstances. So you will have to program a non-trivial assignment, with the help of the whole team. The assignment doesn’t contain any “tricks” or common pitfalls that you can fall into and a lot of different solutions are possible without us wanting to see exactly one (the “best”). If you are an experienced developer, you will feel at ease with the task.

Another important skill of every developer is the quick assessment of existing code in regard to bugs, security risks and bad practices. We have prepared a piece of code riddled with all kinds of quirks and will review it with you. None of us finds them all, too.

We orient our work around a set of core values that are very congruent with the values of the Clean Code Developer Initiative. So it helps tremendously if you are firm with the practices of a clean code developer. But we also want to know if you can convey the ideas and principles behind the actual practices, so you will have to explain some of them to us.

These are the three parts that we want to see of your professional skills:

  • Programming
  • Analysis
  • Introspection

After this meeting, we will have a fairly detailed picture of your abilities and you will know a lot about the level of skill that we require for daily work. If we come to the conclusion that everything matches, we will invite you to the last official step of our recruitment process, the recruitment internship or probationary work.

Internship

In the previous steps of our recruitment process, it was mostly us that examined your skills. Now, after we are sure that you might complete us, it’s time that you get a chance to examine us. So we invite you to accompany us for several days in our normal work. You can team up with whoever you want and join in his (or her) development task. You can ask questions. You can just watch. You can complete your picture of us. You can make sure that you will feel comfortable when joining us.

Welcome aboard

If you’ve seen nothing that scares you during your internship, we will discuss the details of your employment, but that’s a topic for another blog post.

Inspirational source

We don’t hire very often and couldn’t sustain the process for a large number of applicants because the effort required from everyone involved is substantial. But we wanted to make sure that we don’t hire blind and don’t torture our applicants. We compiled our process from a lot of sources, mostly blog posts around the internet and one noteworthy book by Johanna Rothman: “Hiring The Best Knowledge Workers, Techies & Nerds”. That’s exactly what we set out to do!