Author Archives: Christian Harms

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

Problem

In the 2009 qualification round there was a simple problem with a nice background story:

After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.

Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.

A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.

solution with regexp

We have a set of correct words and patterns which should match the words. How many words are matched by every pattern?

words = [“abc”, “bca”, “dac”, “dbc”, “cba”]

The first pattern “(ab)(bc)(ca)” means, that the first character can be “a” or “b”, the second “b” or “c” and the third “c” or “a”.

The solution should print out how many words in the alien language match the pattern. After so many “match” and “pattern” you know the solution: regular expression! One pattern can be converted into a regular expression:

searchStr = line.replace(“(“, “[“).replace(“)”,”]”)

Here the complete solution uses the filter function again (read more about the functional part of python) to shrink the code:

import sys, re
fp = file(sys.argv[1])

#read params
(l, d, n) = [int(x) for x in fp.next().split()]

#read words
words = [fp.next() for x in range(d)]

#read pattern
for i in range(1, n+1):
    searchStr = fp.next().replace("(","[").replace(")","]")
    searchIt = re.compile(searchStr).search
    print "Case #%d: %d" % (i, len(filter(searchIt, words)))
fp.close()

timing

25 words with 10 characters and 10 patterns to check:

time python alien.py alien_small.in > alien_small.out

real	0m0.120s
user	0m0.108s
sys	0m0.012s

5000 words with 15 characters and 500 patterns to check:

time python alien.py alien_large.in > alien_large.out

real	0m13.398s
user	0m12.821s
sys	0m0.316s

other solutions

I found (longer) solutions in other programming languages, feel free to read and comment them or offer an alternative or even better solution – we will link your article.

• the regexp solution in a long perl version: www.technicalypto.com
• Java/C++ and C# at necessaryandsufficient.net
• typical algorithm can find it in num_chars*num_words*strlen(testcase); at intellitures.com
• my regexp solution in java: anuj-mehta.blogspot.com

The rotate example nico last week reported was funny to solve: No rotating needed! Read the complete problem description in nicos article or in the google code contest page. Here my complete python solution with file handling and solution printing.

import sys
from re import search

fp = file(sys.argv[1])
for case in range(1, 1+int(fp.next())):
    n, k = [int(x) for x in fp.next().split()]
    lines = [fp.next() for x in range(n)]
    
    #right-gravitation and joining to one line (delim is a line)
    s = "#".join(map(lambda x:"%%%ds"%n%(x.strip().replace(".","")), lines))
    result = 0

    #find one of the 4 variants: horiz, verti, slash, backslash for Blue
    reB = "(B.{%%d}){%d}B" % (k-1)
    if search(k*"B", s) or search(reB%(n-1), s) or search(reB%n, s) or search(reB%(n+1), s):
        result+=1

    #find one of the 4 variants: horiz, verti, slash, backslash for Red
    reR = "(R.{%%d}){%d}R" % (k-1)
    if search(k*"R", s) or search(reR%(n-1), s) or search(reR%n, s) or search(reR%(n+1), s):
        result= result+2
    print "Case #%d: %s" % (case, ["Neither", "Blue", "Red", "Both"][result])

There are 15 effective lines of code for the solution. And some lines are used for imports or reading from the input file (comments and spacer not counted) – cool?

handling the gravitation

To understand the code read the problem description in nicos article or in the google code contest page. I will describe now the two steps for the solution. First the play field have to sorted like a gravitation to the right. All dot character are handled like spaces and the capital letters goes to the right border.

We start with a n by n matrix:

..R          ..R
.R.   ->     ..R  
R.B          .RB

To remove the dots simple replace it with nothing as a standard string manipulatin method. To fill it from the left use the common used string formating well know from printf.

newLine = “%3s” % lin.replace(“.”, “”)

To do this with the length n use this obscure-looking multi step format string:

newLine = “%%%ds” % n % line.replace(“.”, “”)

And to do this with a complete list of lines use a list comprehension (read more about functional programming in python).

lines = map(lambda x:"%%%ds"%n%(x.replace(".","")), lines)

This is done in line 10 in the example (with joining to one string).

find the winner

Second part is to find the k=4 characters in a line:

RBBBB
_RBBB   -> "RBBBB#_RBBB#__RBB#___RB"
__RBB
___RB

I concat all lines to one string to find the four different directions with regular expressions: “RBBBB-_RBBB-__RBB-___RB”

• The horizontal line is easy:

  /BBBB/

  or with k:

  /B{4}/

• the vertical line can found by 4 B’s and n characters (one line up):

  /B.{5}B.{5}B.{5}B/

  or shorter:

  /(B.{5}){3}B/

• the backslash line is the same like the vertical line, only with n+1 spaces
• the slash line is the same like the vertical line, only with n-1 spaces

I prepared the regular pattern with k:

reB = "(B.{%%d}){%d}B" % (k-1)

and used the multi step format string for the different pattern strings (see example above in line 15).

That’s all!

I am running a IP-Geo-location demo in my App Engine. After many silent months I got some traffic on it (and hitting the daily CPU limit). Some one would kick the “traffic monster”, after all it’s starts only as a demo, other ones (like me) will try to optimize the GEO-location script.

When you read the message “This Google App Engine application is temporarily over its serving quota. Please try it again later” (or simply a HTTP-Status 503) you can activate the App Engine billing option. Or it’s time to start caching in the different application levels:

• cache external resources – they are slow and unpredictable
• cache internal resources – lookups to database and rendering the output can be cached
• use the browser cache – webservices can be cached with basic http usage

introduction for the caching article

other articles about the geo location

• the tutorial how to use ip to geolocation provider api
• the free usage ip to geolocation aggregator script
• the php stand alone implementation
• the python Google App Engine implementation

The described caching steps works perfectly if you do not need to invalidate your cache. This detailed example only reads from external resources and can use long caching times. After some improvements I got a speed up of factor 10! Or in other words: from 50.000 requests/day I increased the App Engine capacity to 500.000 requests/day (and hitting the cpu limit again …) All logged times come from the logfiles and profiling with Appstats helps with the sequence diagrams (generated live).

The profiling images are examples of the google Appstats tool in the App Engine and show live examples of requests. Its slow down your engine up to 10% (on high load) and saves all statistics in memcache. There are different values in the graphics:

• blue cpu time: time “wasted” in my own python code
• red api cpu time: time needed by the services (memcache, database, fetch and many more)
• requests total time: time for the request, can stopped in the browser

What we have to optimize

The basic webservice requests have to do the following steps:

1. accept a GET request (param is the calling IP) on a javascript-url
2. ask up to 4 web-service for data
3. generate resultString as javascript code
4. return the resultString

The result is a dynamically generated javascript wich contains only the data. A second static script with functionality over this values is added as a static file and google does all the caching stuff for static content. There are functions for finding the next city in a given set or calculate the distance of the visitors home and your given location.

var com = com||{};  
com.unitedCoders = com.unitedCoders||{};  
com.unitedCoders.geo = com.unitedCoders.geo||{};  
com.unitedCoders.geo.ll = [{"lat": -21.78330, "city": "Araraquara", "name": "maxmind", "long": -48.16670, "country": "Brazil"}];

Costs: every request results in 4 calls to webservices
• not much cpu, no local storage, long running (depend on slowest webservice)
• worst case: up to 2 seconds, but on average 100 ms cpu-time

cache external resources

Notes: Not every used webservice will give results for every called IP and the free daily amount of web-service-calls are limited. Second the assignment between IP and location will rarely change – an ideal setup for caching on application side. A long time cache like a local database with timestamp is a good choice for saving requests to the webservices and a short time cache for faster lookups.

1. accept an GET request (param is the calling IP) as a javascript-url
2. check if result is in local database
3. otherwise ask up to 4 web-service for data
4. save the results in the local database
5. generate resultString
6. return the resultString

The profiling image shows the result. It tests if the IP is in the local database – this is implemented as a keyname call (in sql syntax a request to the primary index) and very fast. If not it starts 4 parallel requests to the webservices and transforms the results. Then it saves it in the database and returns the result. This does require expensive resources and can have long request time (depending on the webservices).

Personal experiences: After running this with many visitors, my database filled with known values and the count to call the webservices will go down. I got after 10 million requests (from one site in brazil) an 97% hit chance (this will highly depend on the calling visitors and the saved data!!!) in my database!

Cost: 3% of requests fetch from 4 webservice and writing into database
• longtime usage on the storage
• real=642ms cpu=700ms api=273ms overhead=1ms (8 RPCs)

If the result is in the local database the request can use the saved result and therefore is fast. I used a keyname (like primary index on sql databases) to find the record for the called IP. The time for finding the result is nearly constant for the first 100.000 records I tested in my App Engine instance.

97% of requests reads from database
• normal time, some cpu, many memory
• real=59ms cpu=67ms api=8ms

cache internal resources

Using local caching or the fast memcached is the classic way – every call to a database can be cached in memory too. Saving data in the memcache is fast and can be made asynchronous – no waiting time. The memCacheD is a standard service in the App Engine and should be faster than the distributed bigtable.

1. accept an GET request (param is the calling IP) as a javascript-url
2. check if calling IP in memcache -> return it
3. check if result is in local database-> return it
4. otherwise ask up to 4 web-service for data
5. save the results in the lcoal database
6. generate the resultString
7. dump the resultString in memcached
8. return the resultString

The complete and worst case request is only a little bit more expensive than the basic call. It is asking the memcache and than the local database. If no data is found calling all 4 webservices. The result has to be transformed and saved in local database (saving is not asynchronous in the App Engine) and memcache.

If the request found a hit in the memcache all is very fast!

If the script found the record in the database, it has to save it in memcache and return the result. See here for some python code lines for doing this in the App Engine. The function computeData tries to read the record from the database. If not found start the webservice calls, saving into database and returning the record.

def get(request, response):
     resultCacheKey = "geo_data(%s)" % request.get("ip")
     resultStr = memcache.get(resultCacheKey)
     if resultStr:
         response.out.write(resultStr)
         return
     #some code
     result = computeData()
     resultStr = self.pageTemplate.render(Context(result))
     memcache.set(resultCacheKey, resultStr)
     response.out.write(resultStr) 
#get

Cost:
• 3% requests to 4 webservices
• 67% hit rate in database (long-time cache)
• 30% hit rate in memcache (short-time cache)
• fast, minimal cpu, some memory
• real=6ms cpu=39ms api=0ms

Tip: Don’t cache the database result directly (with wrapper or annotations). Try to dump the webservice result in memcache as late as possible. You next memcache hit does not need to convert the result data.

use the browser cache

Some calling browser/IPs (not only anonymous proxies with the same IP) come several times an hour – I don’t know why. The result depends on the calling IP – not by the url – it can’t be cached for all caller transparently. I defined in the http response header one hour as the private cache time – in this period the location should not change dramaticaly and the browser should load the script from his browser cache.

Cache-Control: max-age=3600, private

After one hour the second identifier would be the IP itself, transported as etag header. If the IP did not change since the last call the status code will return 304 (s. rfc 2616) “Not Modified”. In this case the webservice has nothing to do – the browser cache is valid. The request answer means: your cache is valid – use it (since the last call with the given etag).

response.headers["Cache-Control"] = "max-age=3600, private" 
response.headers.add_header("Etag",  request.get("ip")) 
if request.headers.get("If-None-Match", "") == request.get("ip"):
     response.set_status(304)
     return

The activated cache-control option decreased the request count by 30% and increased the capacity for the app! The cpu load did not dramatically change because the old requests were caught by etag check or by memcache cache hits.

Requests with an adequate etag will only cost checking the header and is reported with the minimum cpu ms (19ms) in the log files. After active cache-control settings every 20 requests an etag logline appeared. The example with the Etag matching can also be used on url-parameters or cookie-values.

Check your webservice with the cache header test tool from Resource Expert Droid or read more caching hints in http://mnot.net/cache_docs/.

Request rate before and after optimization

Here you can see the daily statistic on the App Engine dashboard with a 2 requests/seconds maximum and 50.000 requests/day. I got some more traffic and the result was the Overload screen (started with this image in the article).

With the prior noted improvements the free and basic Google App Engine runs with up 20 requests/second. The daily traffic of 400.000 requests/day can now be handled. Altering my App Engine code was fun and it was exciting to see if I can stay below the daily 6.5 hour cpu limit, or if the cpu limit was ok but the bandwidth limit will become the new challenge.

Consumption

I hope this helps to find optimization options for your webservice on the server and client side! If you have more tips or questions, ask for it. If you want to check your website try out the yahoos yslow or google page speed plugins for basic client checks or the profiling tools Appstats on google app engine.

Yoda was a great teacher except for his word sequence. For programmer exists the yoda condition :

if (value == 42) { 
    ...
}

As yoda condition written:

if (42 == value) { 
    ...
}

I found some discussions on stackoverflow.com and collected pro and contras.

prevent an assignment

if (value = 42) { 
   ...
}

If you make this typo in javascript the condition is true and value is changed. In C your compiler would give you an warning, as yoda condition this would not work and your compiler will throw a compiler error.

if (42 = value) { 
    ...
}

null checks

if (myString != null && myString.equals(“yes”)) { 
    ...
}

This typical double check in java is tiring and will be shorter as yoda condition:

if (“yes”.equals(myString)) { 
   ...
}

in-operator

With javascript the in-operator can find an attribute in myObject:

myObject = {name: "Christian Harms" };
if ("name" in myObject) { 
    ...
}

The variant using value as first part is ok. A more object oriented variant will ask the container if the attribute is true.

if (myObject["name"]) { 
    ...
}

The same example in python with a list (because the example wont work with javascript Array):

myList = [1, 2, 3]
if 1 in myList: 
    ...

The yoda condition can used with a list method:

myList = [1, 2, 3]
if myList.count(1): 
    ...

conclusion

yoda says: “Try not. Do or do not, there is no try.”

The object access benchmarks last weeks was not surprising but a factor 5 between access “obj.a” and “obj.getA()” is interesting. In this second part I check the access time for properties on objects, created with ECMAScript 3 getter/setter and with the ECMAScript 5 Object.defineProperty variant (works on IE8+, FF3.7+, newest Webkit and Chrome 5) – see more on ECMAScript 5 compatibility table. Oliver asked to add getter tests – and the results produce differences with factor 15-100.

1. JavaScript property with get

Since ECMAScript 3 (works in FF, Safari 3+, Opera 9.5+, Chrome and IE8) we can define properties with getter and setter instead building manually with functions. John Resig has explained the getter syntax in 2007.

 
var obj = { 
  get a() { return 1; },
  get b() { return 1; },  
  get c() { return 1; },
  get d() { return 1; },
  get e() { return 1; },
};

JSLitmus.test("ObjectPropertyConstantGet", function()
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

The example object is only readable, returns the constant 1 and no setter are defined.

2. JavaScript getter and setter in prototype

Instead of defining it directly in the object the getter and setter can defined in the prototype of the object and the value of a public property will saved in a (per convention private) variable with evil underbar.

function Data() {
    this.a=1, this.b=1, this.c=1, this.d=1, this.e=1;
};
Data.prototype = {
    get a()  { return this._a; }, 
    get b()  { return this._b; },
    get c()  { return this._c; }, 
    get d()  { return this._d; },
    get e()  { return this._e; }, 
    set a(v) { this._a=v; },
    set b(v) { this._b=v; },
    set c(v) { this._c=v; },
    set d(v) { this._d=v; },
    set e(v) { this._e=v; }
};
var obj = new Data();

JSLitmus.test("ObjectPropertySetGet", function()
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

This getter and setter constructs work like a normal function so the benchmarks should be the same.

3. JavaScript defineProperty

An upgraded property definition looks in ECMAScript 5 like this. First I defined only the three attributes to false – if you more interested read the longer article from John Resig.

• Writable. If false, the value of the property can not be changed.
• Configurable. If false, any attempts to delete the property or change its attributes (Writable, Configurable, or Enumerable) will fail.
• Enumerable. If true, the property will be iterated over when a user does “for (var prop in obj){}” (or similar).

var obj = {};
Object.defineProperty(obj, "a", 
       { value: 1, writeable: false, enumerable: false, configurable:false});
Object.defineProperty(obj, "b", 
       { value: 1, writeable: false, enumerable: false, configurable:false});
Object.defineProperty(obj, "c", 
       { value: 1, writeable: false, enumerable: false, configurable:false});
Object.defineProperty(obj, "d", 
       { value: 1, writeable: false, enumerable: false, configurable:false});
Object.defineProperty(obj, "e", 
       { value: 1, writeable: false, enumerable: false, configurable:false});

JSLitmus.test("ObjectDescriptor", function()
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

With all attributes set to false it should be fast than plain objects. My experiments with try out all the variants of false and true has the same results.

4. JavaScript defineProperty with getter/setter

The last example can expanded with getter. It works like example 2.

var obj = {};
var a=1, b=1, c=1, d=1, e=1;
Object.defineProperty(obj, "a", { get: function() { return a; }, set: function(v) { a=v; } });
Object.defineProperty(obj, "b", { get: function() { return b; }, set: function(v) { b=v; } });
Object.defineProperty(obj, "c", { get: function() { return c; }, set: function(v) { c=v; } });
Object.defineProperty(obj, "d", { get: function() { return d; }, set: function(v) { d=v; } });
Object.defineProperty(obj, "e", { get: function() { return e; }, set: function(v) { e=v; } });

JSLitmus.test("ObjectDescriptorGet", function()
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

Test it in your browser

If you own a compatible browser start your own benchmarks!

The Results

The results for the plain javascript object access started in the first article with the first 8 tests.

All tests with active getter function (ObjectPropertyConstantGet, ObjectPropertySetGet, ObjectDescriptorGet) are terrible slow!

The middle graph is the Firefox Developer Preview 3.7a4, the Opera is version 10.10. All benchmarks are stopped on a eeeBox with Intel Atom N270.

After getting the tip to use JSLitmus for JavaScript microbenchmarks I grabbed my old “How to access JavaScript Object” code and build some tests with JSLitmus. The following question was sometimes very religious and only benchmarks can solve the problem:

The question is simple: what is faster?

obj = {a:1};

//variant 1
result = obj.a;

//variant 2
result = obj['a'];

//variant 3 - build an object with getter function:
result = obj.getA();

I build some variants and run the benchmarks on different browsers on my Intel Atom N270 eeeBox. The examples show the single function call with JSLitmus for better readability, the benchmarks are made with the function-count-parameter.

Live demo

You can start it here with your browser – some tests will result “Infinity” because the tests can be fast on modern Intel Core cpus. That’s one of the reason to use a netbook/netbook with a slow standard Atom cpu. If it run fast on this machine its fast enough for the normal web visitor.

A: Accessing with Dot Notation to a plain Object.

The simple direct access to an JavaScript Object used as key-value data object.

var obj = {a: 1, b: 1, c:1, d:1, e:1};

JSLitmus.test("ObjectAccessWithDot", function() 
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

B: Accessing with Key Notation to a plain Object.

The access with the name as key to an JavaScript Object used as key-value data object. This should be the same like Case B.

var obj = {a: 1, b: 1, c:1, d:1, e:1};

JSLitmus.test("ObjectAccessWithKey", function() 
  { sum = obj['a'] + obj['b'] + obj['c'] + obj['d'] + obj['e']; }
);

If the key is constant a optimizer can convert the code to the dot notation. The second example use local variables for the keys.

var obj = {a: 1, b: 1, c:1, d:1, e:1};
var a='a', b='b', c='c', d='d', e='e';
 
JSLitmus.test("ObjectAccessWithKey", function() 
  { sum = obj[a] + obj[b] + obj[c] + obj[d] + obj[e]; }
);

C/D: Building a constructor, accessing with Dot or Key notation

Plain JavaScript Objects are fine, but we build more complex object and we need contructors. Build an constructor with the five members and get an instance of it for accessing. This should be the same than Case A because type(obj)==”object”.

var Data = function() { this.a=1; this.b=1; this.c=1; this.d=1; this.e=1;};
var obj = new Data();

JSLitmus.test("ConstructorAccessWithDot", function() 
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

JSLitmus.test("ConstructorAccessWithKey", function() 
  { sum = obj['a'] + obj['b'] + obj['c'] + obj['d'] + obj['e']; }
);

E/F: Accessing with getter function to public or private members

The first examples use only direct access to the member variables. Variant E/F use the more java-like getter functions to access to the integers and it should dramaticly slower (function call overhead).

var Data = function() {
     this.a=1; this.b=1; this.c=1; this.d=1; this.e=1;
     this.getA = function() { return this.a; }
     this.getB = function() { return this.b; }
     this.getC = function() { return this.c; }
     this.getD = function() { return this.d; }
     this.getE = function() { return this.e; }
  };
var obj = new Data();

JSLitmus.test("testConstructorAccessWithGetter", function() 
  { sum = obj.getA() + obj.getB() + obj.getC() + obj.getD() + obj.getE(); }
);

Real private members can be generated in the constructor as local variables. They are only accessable with functions defined in the same variable scope. The benchmark will test if the access to the local scope is more expensive than to public members.

var Data = function() {
     var a=1, b=1, c=1, d=1, e=1;
     this.getA = function() { return a; }
     this.getB = function() { return b; }
     this.getC = function() { return c; }
     this.getD = function() { return d; }
     this.getE = function() { return e; }
  };
var obj = new Data();

JSLitmus.test("testConstructorAccessWithPrivateGetter", function() 
  { sum = obj.getA() + obj.getB() + obj.getC() + obj.getD() + obj.getE();} 
);

G. Accessing members over the prototype chain

The DataProto contructor defines the five member and the Data constructor will inheritance it. While accessing to the member variables it has to hop to the prototype DataProto to get the values. It should be slower than Case A or Case C.

var DataProto = function() { 
   this.a=1; this.b=1; this.c=1; this.d=1; this.e=1;
};
var Data = function() {};
Data.prototype = new DataProto();
var obj = new Data();

JSLitmus.test("ConstructorAccessWithDot", function() 
  { sum = obj.a + obj.b + obj.c + obj.d + obj.e; }
);

The results

Funny! If you access to many members use plain JavaScript objects with dot notation. Charts shows loops/second – higher is better!

The Opera 9.80 was a Opera 10.10, the last one is from the Konqueror 4.3.2:

I dont test the IE because it is not a browser for JavaScript Programmers (ECMA5) and I dont run it on ubuntu … If any one will post benchmarks for windows (on an netbook with Intel Atom N270) as tinyurl make a comment!