This is not a Git howto, it just describes where our team had trouble when starting our current project in Git.

Git is not SVN

Just forget everything you know about SVN. Start over with a fresh mind. Ok checking out and commiting are still similar, but when working with branches and tags, it’s a whole new world.
Take a look at the Git cheatsheet: https://Git.wiki.kernel.org/index.php/GitCheatSheet
Don’t get confused by the many commands, you’ll get there. Starting Git is not that complicated.

Play around

You don’t need much give Git a spin. Install it, work with it in a local repository. There is plenty of information out which will show you how to do so. Try everything you need to do in your daily work life. Merge, branch, tag …..
The only important thing is: work on the command line. After you got everything figured out you can use your IDE as an aide.

Watch out, branches

Here’s the first thing i stumbled on. I was working on two branches, both not too different. Let’s call the brA and brB.
So after creating to files in brA, I switch to brB to test something. I was wondering, why brB did have the same files and modifications I just did in brA.
Long story short. Never switch away from a dirty state, unless you know what you’re doing.
What happened? Before switching away from brA, I had my repo in a “dirty state”. That means, I had changes I did not commit to my working tree. These files will “follow” me to whereever I go.
This is actually very useful, if you want to test if a fix or change you made works in different scenarios before you commit it. But sometimes you do not want this behavior. So there are two options to avoid it. If you’re sure you want the code in the branch, commit it. Otherwise stash it. There’s a nice post to stashing on ariejan’s site.

Mastering your branches

The next idea i had to learn is how to deal with branches and the master. So in our environment we support one version of the product, which is on the market. This versions has its own branch and tags. The master is the recent cutting edge version with all the features. So if there’s a bugfix in the current release, you have to make sure, that the release is fixed and the change makes its way into the master.
There are to ways to do so. The one i like more is to go to the branch, do the fix and then cherry pick or merge the change to the master. Cherry picking is very useful if you can do the fix in one commit. If not, merging is the better choice. Of course you can also go the other way. Fix it in the master. But then make sure you cherry pick it into the branch, otherwise, when you merge, you will end up having new features in your branch.

Pushing and Pulling

As Git is a distributed version system, all your committing is done locally. So if you want to “store” your changes in a remote repo, you have to push them. It’s a good idea to have a common master, in which every developer pushes and pulls her changes. The extra kick is, you can use different locations to push and pull code. So if you feel you want to get some changes from a fork somebody else is hosting somewhere (maybe Github?) you can provide a destinations for the operations.

Setting up Architecture

There’s not much you need. But a central repo is a good idea. As I’m a big fan of JIRA, you can use the JIRA Git plugin. Another option is Gitosis, especially if you use it as an addon. It runs well with redmine, so user creation and permissions can be done via the web. Git is getting so big, almost every Bugtracking/Codetracking site has a plugin for it.

Personal Conclusion

We are working with Git for about 8 weeks now. I do not want to go back to subversion. Especially if your team is more than two people sitting next to each other. Code control is so much easier with Git.

Our little programming contest was fun and we can learn something about best practices in javascript algorithm performance. I have prepared some micro benchmarks for common code sniplets to find the best variant. After the section with the micro benchmarks you can find the best-performed solution by running the JSLitmus test and browse through the javascript code. And yes – our co-author Matthias had the best solution with factor 20-35 faster than the clean code variant. No solution is close with the performance to Matthias’ solution!

Knowing some javascript performance hints are importend. The different javascript interpreter with Just-In-Time-Optimizer can offer some surprise in the following basic code examples.

• Adding Numbers to an Array
• Using code in loop-header or Body
• Round down a Number
• Using linear Array or Object (=hashmap) for caching Numbers
• Find a substring in a String

Adding Numbers to a Array

The clean code solution forced you to use the push-method to add a number to the Array. Is this the best way?

benchArrayPush = function(count) {
    var a = [];
    while (count--) a.push(count);
};
benchArrayLength = function(count) {
    var a = [];
    while (count--) a[a.length] = count;
};
benchArrayLocal = function(count) {
    var a=[], l=0;
    while (count--) a[l++] = count;
};
benchArrayFixedLocal = function(count) {
    var a=new Array(count), l=0;
    while (count--) a[l++] = count;
};

• Array.push

  is only in Chrome faster than the other variants

• Using a local variable as index instead of the

  Array.length

  attribute is in opera and FF 3.6 faster

• Why is defining a Array with the end length slower than

  Array.push

  in Chome?

conclusion: The variant with using

Array.length

has good performance and dont need an extra variable. One point for clean code!

Using code in loop-header

Instead of call all operation in the body of a loop, you can put simple operation in the head of a loop. This is not clean code, but all operation can seperated by a “,”. Is there an optimizer who accept this coding style as performant?

benchLoopHeader = function(count) {
    var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
    for (j=10;j;j--)
        for (i=count; i; i1++,i2++,i3++,i4++,i5++,i6++,i7++,i8++,i9++,i--)
            sum++;
};
benchLoopBody = function(count) {
    var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
    for (j=10;j;j--)
        for (i=count; i; i--) {
            i1++;
            i2++;
            i3++;
            i4++;
            i5++;
            i6++;
            i7++;
            i8++;
            i9++;
            sum++;
        }
};
benchLoopLine = function(count) {
    var i,j,i1=0,i2=0,i3=0,i4=0,i5=0,i6=0,i7=0,i8=0,i9=0, sum=0;
    for (j=10;j;j--)
        for (i=count; i; i--) {
            i1++;i2++;i3++;i4++;i5++;i6++;i7++;i8++;i9++;sum++;
        }
};

conclusion: The loop body solution has no performance problems comparing with the other variants. You can use the clean coding style – second point !

Round down a Number

The

Math.floor

function is defined to round down and

Math.ceil

for rounding up. But are these function the best choice?

benchIntegerFloor = function(count) {
    var i = 7.7, r;
    while (count--) r = Math.floor(i);
};
benchIntegerParseInt = function(count) {
    var i = 7.7, r;
    while(count--) r = parseInt(i);
};
benchIntegerParse10 = function(count) {
    var i = 7.7, r;
    while(count--) r = parseInt(i, 10);
};
benchIntegerBinaryOr = function(count) {
    var i = 7.7, r;
    while(count--) r = i|0;
};

• Using

  parseInt

  force the javascript interpreter to cast the Number to a String before parsing – this is slow!

• If you use the bitwise OR all browser are very fast to convert it into an 32 bit integer. If your Number is greater than 2^32 the OR-variant will fail.

Conclusion: if your Number range use only 32-bit values (like in the contest) bitwise OR is the fast option, but not clean code. 1 point against clean-code.

Using Array or Object for caching Number results

For the pre-calculated results is an Array the right container as Cache – or is the standard JavaScript Object better?

benchCacheArray = function(count) {
    var a=[], i, j, c;
    for (i=count/2; i; i--) a[i]=i;
    for (i=count/2; i; i--) c = a[i];
};
benchCacheObject = function(count) {
    var a={}, i, j, c;
    for (i=count/2; i; i--) a[i]=i;
    for (i=count/2; i; i--) c = a[i];
};

• Opera / Chrome are factor 6 faster than FF while accessing Object or Array!
• There is no better performance from FF 3.6 to FF 4
• Chrome has optimized the Array access with Numbers

conclusion: Using an Array for cached Number results is Ok, but the hashmap/Object variant is fast, too! Next point for clean code!

Find a substring in a String

What is the fastest method to find a substring in an given String? Many commentators used the

String.indexOf

-method, only one anonymous writer used the

RegExp("7")

constructor.

benchStringMatch = function(count) {
    var seven = "12734", res;
    while (count--) res = seven.match(/7/);
};
benchStringRegExTest = function(count) {
    var seven = "12734", res, hasSeven = new RegExp("7");
    while (count--) res = hasSeven.test(seven);
};
benchStringIndexOf = function(count) {
    var seven = "12734", res;
    while (count--) res = seven.indexOf("7")!==1;
};

• String.match

  is factor 3 -10 slower than a predefined

  RegExp

  Object.

• the

  String.indexOf

  method is in both Firefox very fast

• to find one substring in many Strings the RegExp Object is in Opera / Chrome faster than

  String.indexOf

conclusion: Find the best variant for your usage. Or use browser-optimized code between FF/Chrome – one point against clean code.

Check the best solution for the game of forfeit

Tipp: Maximize your browser because the javascript code has fixed font width.

clean code in JavaScript

Good news for JavaScript number cruncher. Your performance depends on your algorithm and not on cryptic hacks in JavaScript!

I found two ALGOL sniplets for the forfeit game contest. My ALGOL 60 programming book (happy birthday for the ALGOL programming language) offer for every problem the question, a problem analysis, a code structure chart, the code solution and the executing time for the ZUSE 23 computer (see a very similar Z22 on wikipedia). I converted the fast solution for the game of forfeit from ALGOL to javascript without optimizations and benchmarked it.

Opera 10.63 vs. Chrome 7/8 vs. Firefox 3.6.12/4b7

I will start with the results from the converted ALGOL solution. The new javascript engine Jägermonkey with the firefox 4b7 is a real competitor for other fast javascript engines! And the ALGOL version is (mostly) better than the clean code version. The absolute numbers are generated on my own mini-pc and used for comparing with the clean code solution.

The 1:1 conversion of the ALGOL code runs on my Intel Atom N270 3.5 million times faster than on the original ZUSE Z23.

get ALGOL working on your box

How can I start ALGOL code on my local ubuntu? And not the more popular ALGOL 68? There is only one working interpreter: the NASE A60 interpreter from Erik Schoenfelder. Extract the archive, run

./configure

and start your algol code directly.

More background to the z23 on egge.net:

The 1961 Zuse Z-23 was his eighth model, being a transistorised version of the 1956 valve based Z22. His previous computers had used relays! A typical Z22 had 14 words of 38-bit core RAM, 8192 word (38 KB) magnetic drum, punched card I/O, it ran at just 3 KiloHz!! And – oh wonders – by 1958 there was an ALGOL 58 compiler for it !!!

fastest solution

This solution from H.Lehr was the fastest solution. Its not working for all number ranges and there is no defined break. It needs 6 minuts and 17 seconds for calculating and printing on the original hardware. If you are not familiar with ALGOL 60 some tips:

• ENTIER

  function rounds down a floating number to an integer

• all keywords are wrapped by single quotes, variable names not
• code blocks start with

  BEGIN

  and end with

  END

  instead of { and }

• A:

  is a label and you can direct jump to the line with the

  GOTO

  keyword.

The usage of multiple for-loops to check each digit of the number with 7, instead of generating a string, is a limited but a creative solution. And the sum of all digits is directly accessable! The next interessting point: The maximal value for the sum of digits for example

n=1.000.000

is

54

– we dont need complex checks for this number. In the ALGOL example only

X1

to

X4

are used for these checks.

Converting ALGOL to javascript

This works fine and I converted it to javascript (without changes), but it doesn’t perform like excepted. But this code can be an inspiration to get better performance boost for the solution of the forfeits game contest.

function forfeits(n) {
	var k=6, x1, x2, x3, x4, q, z=-1, s, t, result=[];
	for (var a9=0; a9<10; a9++)
	for (var a8=0; a8<10; a8++)
	for (var a7=0; a7<10; a7++)
	for (var a6=0; a6<10; a6++)
	for (var a5=0; a5<10; a5++)
	for (var a4=0; a4<10; a4++)
	for (var a3=0; a3<10; a3++)
	for (var a2=0; a2<10; a2++)
        for (var a1=0; a1<10; a1++) {
	    z++; 
	    k++;
	    x1 = 7 * entier(k/7);
	    k = k - x1;
	    q = (a1+a2+a3+a4+a5+a6+a7+a8+a9);
	    s = q/7;
	    x2 = 7+sign(s-entier(s));
	    t = q/10;
	    x3 = entier(t);
	    x4 = q-10*entier(t);
	    if (x1!==7 && x2!==7 && x3!==7 && x4!==7 && 
		a1!==7 && a2!==7 && a3!==7 && a4!==7 && a5!==7 &&
		a6!==7 && a7!==7 && a8!==7 && a9!==7) result.push(z);

	    if (z === n) return result;
	}

	//transfers an expression of real type to one of integer type, and assigns 
	//to it the value which is the largest integer not greater than the value of E
	function entier(e) {
	    return Math.floor(e);
	}
	//the sign of the value of E (+1 for E < 0, 0 for E=0, -1 for E < 0).
	function sign(e) {
	    return (e<0)?1:(e>0)?-1:0;
	}
    }

Simple test it in your browser:

elegant solution

The second solution printed in the book is from R. Wagner and the calculating/printing time was 7 minuts and 53 seconds.

This doen’ t work with the a60 interpreter and I have no idea what’s is wrong. Feel free to get it running in the a60 interpreter or use the exmaple for a javascript version.

Yesterday it was a very long day starting at 7 o’clock on the M.U.C in munich (ends 8 pm) – here only the first visual impressions from the google developer day 2010 in munich. Later I will give some written impressions to the talks and I try to collect all links to the shared documents (or help with comments).

Funny example for the new channel API on google app engine – talk with Fred Sauer

The game of forfeits is a simple game and one of the classic programming examples since 50 years. I found it in a ALGOL 60 exercise book from 1963: Count the numbers up to 100, but skip all numbers if one of the condition matches:

• number is divisible by seven
• number contains a seven
• sum of digits is divisible by seven
• sum of digits contains a seven

Develop a function which calculates all numbers based on the given conditions. The only one parameter for the function is the range and the function should return the Array of all valid numbers. Hint: You must not cheat while returning a sliced constant result array. The result of the function with max=100 is: [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 15, 18, 19, 20, 22, 23, 24, 26, 29, 30, 31, 32, 33, 36, 38, 39, 40, 41, 44, 45, 46, 48, 50, 51, 53, 54, 55, 58, 60, 62, 64, 65, 66, 69, 80, 81, 82, 83, 85, 88, 90, 92, 93, 94, 96, 99, 100].

clean code variant

Matthia’s has delivered a clean code variant for the problem and it will be used as the reference for this coding contest. It’s not the fastest solution but offers a direct implementation of the problem. Matthias uses an extra function for every condition and put it together in the main loop.

function cleanCodeSolution(n){
	for (var i=0, res=[]; i <= n; i++) {
	    if (!(containsSeven(i) || isMultipleOfSeven(i) ||
		  sumContainsSeven(i) || sumIsMultipleOfSeven(i))) {
		res.push(i);
	    }
	}
	return res;

        //all helper functions defined in local scope
	function containsSeven (n) {
	    return String(n).indexOf("7") !== -1;
	};
	function isMultipleOfSeven (n) {
	    return n % 7 === 0;
	};
	function sumContainsSeven (n) {
	    return containsSeven(sumOfDigits(n));
	};
	function sumIsMultipleOfSeven (n) {
	    return isMultipleOfSeven(sumOfDigits(n));
	} ; 
	function sumOfDigits (n) {
	    var sum = 0;
	    while (n > 0) {
		sum += n % 10;
		n = Math.floor(n / 10);
	    }
	    return sum;
	};
}

If you are surprised about using the helper function before defining, read more about function defining the the In-depth guide to javascript functions.

Testing your solution

In the following textbox you can test your solution by pasting your javascript function body direct into it. It will be compared to Matthias’ clean code version and a performance optimized short clean code version, which works without functions.

/* game of forfeits
   var number {n} numbers to check
   return list of number
*/
function mySolution(n) {

// enter your code here

};

You can include my javascript test suite and add your solution. The benchmark will test your function only with

n=100

.

<script src="http://unitedcoderscom.appspot.com/sites/default/files/JSLitmus.js.txt" type="text/javascript"></script>
<script src="http://unitedcoderscom.appspot.com/sites/default/files/forfeits.js.txt" type="text/javascript"></script>
<script type="text/javascript">
  JSLitmus.test("clean code version", com.unitedCoders.forfeits.testClean);
  JSLitmus.test("short version", com.unitedCoders.forfeits.testShort);
  if (com.unitedCoders.forfeits.runTest(myFunction) {
    JSLitmus.test("your version", function() { myFunction(100); } );
  }

more sultions

In older articles (javascript lotto generator or articles with code puzzles tag), here on unitedcoderscom.appspot.com we linked articles and got comments with solutions in other languages. Feel free to comment or use our tackbacks, but only javascript have the possibility to run directly in the browser.

I will post in the second article the original ALGOL 60 solutions and my 1:1 migration to the javascript variant to benchmark it with today's coding skills. If we got some interesting solutions the third article will comment, link and benchmark all.

Intro: A little excursion to code more functional with javascript. It contain examples with the classic for-loop-code, the more functional variant with Underscore.js and the HTML5 functional enhancements. It does not explain the basic idea of functional programming – it shows the differences in code examples.

motivation

Last week I got access on the address book from Matthias’ well known entry Jennifer. But I had no time to scan all the other girls addresses. With many lines of source code filled with for-loop-code – no way. I have to find a smarter coding way to scan the address book.

Anonymized address book data looks like this – containing many female and male addresses.

addressbook = [  {gender: "female", nickName: "Jenny1"},
                 {gender: "male",   firstName: "Chris"} 
              ];

It’s time to code more functional with javascript (last year’s entry was about functional programming with python). First I will show the normal loop-variant. After the old variant I will show the functional variant with modern browser (only internet explorer doesn’t support it now, IE9 will). Or if you use more recent browser you can use the examples I made in Underscore.js (the global object is a _ ). Functional code is shorter, but does it perform? I added the micro benchmarks for all examples created with Jslitmus.js with some surprising results. All benchmark times are generated on my old ASUS eeeBox with an Intel Atom N270 CPU.

Are there matching objects?

The first addresses in the list contains only girls: I want to find out if at least one male address is in the address book. The functional helper is called “isMale(address)”.

function isMale(adr) {
    return (adr.gender === "male");
}

function findMan_Loop() {
    var i=0, len=addresses.length;
    for (;i<len; i++) {
        if (isMale(addresses[i])) {
            return true;
        }
    }
    return false;
}

If one of the function call of isMale returns true, the result of function findMan_Loop is true. A little bit more functional with ECMAScript 5 or Underscore.js looks smarter and produce the same result. You have to read the line like "return true if any of isMale-call with an item from addresses returns true".

function findMan_some() {
    return addresses.some(isMale);
}

function findMan_Underscore() {
    return _.any(addresses, isMale);
}

The normal loop is faster than the functional variants - browser optimize simple loops more than the function variant.

Check every entry

The other check would be: Does the addressbook contain any women?

function onlyWomen() {
    var i=0, l=addresses.length, result=true;

    for (;i<l && result;i++) {
        result &= isFemale(addresses[i]);
    }
    return result;
}

With this variant I have to check every entry. If every call of the function isFemale is true the result should be true. You have to read it as "return true if all isFemale calls with the items from addresses return true".

function onlyWomen_every() {
    return addresses.every(isFemale);
}

function onlyWomen_Underscore() {
    return _.all(addresses, isFemale);
}

Same performance like the first example.

Get all entries with given filter

But how to get all the women out of the address book? I have to check for every entry and copy the matching entries in a new result array.

function getWomans_Loop() {
    var i=0; l=addresses.length, res = [];
    for (;i<l;i++) {
        if (isFemale(addresses[i])) {
            res.push(addresses[i]);
        }
    }
    return res;
}

The functional variant is named filter and the code is shorter:

function getWomans_filter() {
    return addresses.filter(isFemale);
}

function getWomans_Underscore() {
    return _.filter(addresses, isFemale);
}

I love browser optimizations and micro benchmarks. Chrome is 2x faster with the loop and array.push, Firefox is 2x faster with filter. And my old Opera (10.10 - not 9.80 like his UserAgentString) is 50x times slower than Chrome!

Expand the data with map

Matthias has described how to generate the display name from the different attributes. I want to expand the address book with the new attribute. The function should iterate over all elements, expand every entry with the attribute displayName and return a new array.

function copyDisplayName(adr) {
  return { firstName: adr.firstName,
           nickName: adr.nickName,
           gender: adr.gender,
           displayName: displayName(adr)
  };
}

function copyBookWithDisplayName_Loop() {
    var i=0; len=addresses.length, res =  new Array(len);
    for (; i<len; i++) {
        res[i] = copyDisplayName(addresses[i]);
    }
    return res;    
}

The result is a new array with all entries and the attribute displayName. The functional variant call the function copyDisplayName for every item and return a new array.

function copyBookWithDisplayName_map() {
    return addresses.map(copyDisplayName);
}

function copyBookWithDisplayName_Underscore() {
    return _.map(addresses, copyDisplayName);
}

One performance error is in the last example: I dont need to copy the complete array the original list can manipulated.

Expand the data with forEach

In this last test I created an new Array. Now I will add the displayName member directly in the address book.

function setDisplayName(adr) {
  adr.displayName = displayName(adr);
}

function setDisplayName_Loop() {
    var i=0; len=addresses.length;
    for (; i<len; i++) {
        setDisplayName(addresses[i]);
    }
}

The functional variant is shorter and more elegant. It call the setDisplayName to modify the given object in the array directly.

function setDisplayName_forEach() {
    addresses.forEach(setDisplayName);
}

function setDisplayName_Underscore() {
    _.each(addresses, setDisplayName);
}

Now the loop is slower than the functional variants - fine.

conclusion

Have fun with running the benchmarks in your browser - all the slow timings are made in my ASUS eeeBox with the Intel Atom N270 and Ubuntu!

If you (and your coworkers) like the functional coding style and using an javascript environment supporting it - use it. With performance issues you should try it which variant works better!

links

• definitive Slides to EcmaScript 5 by David Flanagan
• the ECMAScript 5 compatibility table
• Download the ECMAScript 5 as pdf
• ECMAScript 5 support in Mozilla
• Web specifications supported in Opera Presto 2.4 for ECMAScript 5