Announcement

Tuesday, June 18, 2013

Book Review : Beautiful Code – Leading Programmers Explain How They Think

As programmer I am always looking for improving myself. One of the ways to improve is to study ‘the masters’. This is a norm for artists, architects etc. A new painter studies how other past master painters done their work. Initially they mimic their style and later develop their own. The mathematical equations, science concepts, programming have their own beauty. For a software developer, a really well written piece of software has its own ‘elegance’. It is a ‘work of art’. It is ‘beautiful’. But it is hard to describe that beauty to someone who is not a programmer. So this is book for software developers to understand the beauty in software.

This book gives you examples from master programmers and what they think about their work or about other master programmers work. It’s a great way to gain insights on how master programmers think about a particular problem.  This book has articles written by masters like Brian Kernighan (Inventor of C), Karl Fogel (lead developer of Subversion), Tim Bray (inventor of Web), Charles Petzold (Famous Windows programmer and book writer), Sanjay Ghemat (of Google), Yuihiro Matsumoto (inventor of Ruby) etc. It also has articles from diverse domains regular expressions, version control, language development (Ruby, Python),  numerical programming, bioinformatics, Web and search, etc.

One of most interesting article is by Arun Mehta on how he developed the hardware and software so that Prof. Stephen Hawking can interact with the world. The spec given was ‘Prof. Hawking can only press one button’. This article explains in detail how they developed the actual specs from the one liner. He explains basic design models, input interface, simple typing, word prediction, scrolling/editing/searching/macros etc. This software was developed in VB. Imagine you have given this ‘one line’ spec, what you will do? How you will proceed? It’s fascinating to understand thoughts behind all these ideas and design decisions.

First article is from Kernighan about ‘regular expression’ matcher that Rob Pike wrote for book ‘Practice of Programming’. It is truly ‘Beautiful code’. Small, powerful, elegant, does its job well.  I am really tempted to show you the code.
    /* match: search for regexp anywhere in text */
    int match(char *regexp, char *text)
    {
        if (regexp[0] == '^')
            return matchhere(regexp+1, text);
        do {    /* must look even if string is empty */
            if (matchhere(regexp, text))
                return 1;
        } while (*text++ != '\0');
        return 0;
    }

    /* matchhere: search for regexp at beginning of text */
    int matchhere(char *regexp, char *text)
    {
        if (regexp[0] == '\0')
            return 1;
        if (regexp[1] == '*')
            return matchstar(regexp[0], regexp+2, text);
        if (regexp[0] == '$' && regexp[1] == '\0')
            return *text == '\0';
        if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
            return matchhere(regexp+1, text+1);
        return 0;
    }

    /* matchstar: search for c*regexp at beginning of text */
    int matchstar(int c, char *regexp, char *text)
    {
        do {    /* a * matches zero or more instances */
            if (matchhere(regexp, text))
                return 1;
        } while (*text != '\0' && (*text++ == c || c == '.'));
        return 0;
    }

Just three small functions handle following regular expression constructs
c              matches any literal character c
.               matches any single character
^             matches the beginning of the input string
$              matches the end of the input string
*             matches zero or more occurrences of the previous character

I am always fascinated by small, powerful code. In 30 lines, this is one of most powerful code that I have seen. Here is the online version of this article

Personally I also like following articles,
  1.  Subversion’s delta editor By Karl Fogel.
    It helped me in understanding how subversion works behind scene. It also helped in developing versioning/delta storage scheme for a project. 
  2.  Framework for integrated Test : Beauty through Fragility by Michael Feathers
    Here Feathers talks about design of FIT (Framework for Integrated Test) framework by Ward Cunningham. (NOTE : Ward Cunningham is inventor of Wiki). FIT framework is just 3 classes. 
  3. Distributed Programming with MapReduce by Jeffery Dean and Sanjay Ghemavat
    This article explains the concepts and infrastructure ideas that drive the Google search. Hadoop project implements these concepts and brings it to open source world. 
  4. Linux Kernel Driver Model : The benefits of working together by Greg Kroah-Hartman
    Linux operating systems runs on everything from your mobile phone (Android OS is a derivative of Linux), to desktop, to servers to supercomputers. The driver model has to support diverse hardware requirements and various memory scales.
This is a book where you go back every few months, read different articles again and gain new insights. Enjoy.

Here are some links about the book.


Wednesday, March 20, 2013

Software Performance Optimization - A Different Skill

For almost every project I worked on in last 18 years, required performance optimization. Now I have become somewhat of an expert in Performance Optimization in various domains. I have worked on optimizing performance in CAD/CAM algorithms, database queries, caching. I have considered alternative algorithms, alternative data structure usage, impact of page faults, impact of caching etc etc.

In every domain few things are different but some basics remain constant. First rule of optimization is "Don't depend on your gut feel about the location of the performance bottleneck". 99% of times Your gut feel is wrong. So you need to use tools to locate the performance bottleneck. Essentially the process boils down to 
  1. Identify appropriate tool to generate the performance data. Usually this will be a 'profiler'. But sometimes other tools are required (e.g. for analyzing database queries which are taking long time).
  2. Generate the performance data using the tool.
  3. Interpret the data and locate the performance bottleneck. This requires some practice (and guidance if available)
  4. Study the bottleneck code and find out a way to eliminate bottleneck with least amount of code changes. It is important to ensure that code changes are minimum. Large amount of code change can result in new bugs.
  5. Make code changes and test.
  6. Generate the new performance data and ensure the bottleneck is fixed. If not, revert the changes.
  7. If performance is improved keep the changes and commit it.
  8. Analyze the performance data again for the next bottleneck.
  9. Repeat the steps 3-8.
For most projects 5 to 10 times speed ups are possible. However, usually project teams find it hard to believe. Recently I worked with SigmaTEK Systems India team for improving the performance of their Tube Nesting product. Together we were able improve the performance of  their Tube Nesting product by more than 5 times.

It was a real pleasure to work with Nitin on several projects, especially related to performance development.

Nitin came on board at a typical situation, where the customer was unhappy about the speed of the algorithm, and there was lot of pressure to improve it significantly more than the current speed.

Nitin showed us how to systematically analyze code using simplest tools possible (emphasis was always on understanding, never too much on tools). His inputs and ideas on how to improve the performance, without having to compromise with the quality of the results, very extremely valuable. In addition to just code optimization using performance metrics, Nitin was very keen on evaluating the algorithm techniques as well, and provided us several alternatives right down to the core level, on alternative approaches to evaluate for performance improvement.

This experience has been a real eye opener for us, and although it sounded cliché, when Nitin mentioned the very first time, that he has been involved in several projects with optimization improvements of 5X are more, it was extremely satisfying to see that he guided us using his systematic methods and principles, to performance gains of 5X + in our project as well.



Thursday, September 06, 2012

'shortcut' binding for KnockoutJS

[NOTE : This post was originally published on  BootStrapToday blog as "Shortcut binding for Knockoutjs"]

Now that we have BootStrapToday V3 based on KnockoutJS in production, we are working on various enhancements to improve user experience. One of the enhancement we have added in this release, is Keyboard shortcuts for various operations (Ctrl+Enter for form submit, Esc for cancel and various other shortcuts). However, implementing shortcuts is tricky. Basically we wanted to do the following
  • Simulate A 'click' on some attached html element when user presses the shortcut key.
  • The shortcuts can contain the modifier keys like 'ctrl or meta', 'alt' and special keys like 'enter' or 'escape'.
  • Since we dynamically 'load' various pages, different shortcuts will be available at different points, or same shortcut will behave differently on different pages. For example, when 'e' is pressed when Ticket view is visible, will open the ticket edit form, same key will open 'milestone' edit when milestone view is visible. Hence any event handler attached has to be removed and new handler need to be added when the context changes.
  • Different browsers behave slightly differently. For example, 'ctrl+enter'  will trigger 'keydown' event but not the 'keypress' event in some browsers. Chrome capture Ctrl+F and Alt+F, so we cannot use some combinations.
  • Consider a situation, where shortcut key is 'n'. I  added an 'event handler' to handle the keypress. Now if form is open and focus is on form input field, if user presses 'n', shortcut will be triggered. Obviously this is not expected. So shortcuts without modifiers have to be ignored, when focus is on some form input field.
  • Sometimes the element is not visible (for example, drop down menus). In such cases, click should be triggered only when the element is visible.
There are lots of complications involved. Since every page requires some shortcuts to be defined, it was time for a custom knockout binding. So I am going to show you how I developed the shortcut binding handling all the complexities mentioned above. It's not perfect and may require more tweaks.

Version 1:

I started with a simple approach of adding a jquery event handler for the 'keypress' event. The event handler is added to 'body' tag so that it works whatever element has focus. I used a regex to handle 'ctrl' modifier. The binding triggers a 'click' on the element attached to it.

 /*short cut binding handler. Defines a keyboard short for 'click' event */  
 ko.bindingHandlers.shortcut = {  
   init: function(element, valueAccessor, allBindingsAccessor,viewModel) {      
     var key = valueAccessor();      
     var regx = /ctrl\+/gi;  
     key = key.replace(regx,'');  
     var handler = function(event) {  
       if((event.metaKey || event.ctrlKey) && event.charCode == key.charCodeAt(0)) {      
         event.preventDefault();      
         event.stopPropagation();  
         $(element).click();  
         return false;    
       }  
       return true;  
     }  
     $('body').on('keypress', handler);  
   }  
 }  

Version 2:

This version handles 'alt' modifier as well. Sometimes the element is not visible (for example, drop down menus). In such cases, click should be triggered only when the element is visible. Hence I added a check to ensure that element is visible.

 ko.bindingHandlers.shortcut = {  
   init: function(element, valueAccessor, allBindingsAccessor,viewModel) {  
     var key = valueAccessor();  
     key = key.toLowerCase();  
     var match = key.match(/ctrl\+/gi);  
     var ctrl_modifier = (match && match.length > 0);  
     match = key.match(/alt\+/gi);  
     var alt_modifier = (match && match.length > 0);  
     key = key.replace(/(alt\+|ctrl\+)/gi,'');  
     key = key.charCodeAt(0);  
     var handler = function(event) {  
       //first check if the element is visible. Do not trigger clicks  
       // on invisible elements. This way I can add short cuts on  
       // drop down menus.  
       if($(element).is(':visible')) {  
         var modifier_match = ( ctrl_modifier && (event.metaKey || event.ctrlKey))  
           || ( alt_modifier && event.altKey );  
         if( modifier_match &&event.charCode == key) {        
           event.preventDefault();  
           event.stopPropagation();  
           $(element).click();  
           return false;  
         }  
       }  
       return true;  
     }    
     $('body').on('keypress', handler);  
   }  
 }  

Version 3:

Still the special keys like 'enter' and 'escape' are not handled. Also Safari/Chrome do not trigger 'keypress' event for special keys like 'escape'. So based on if shortcut is an alpha numeric key or special key, 'keypress' or 'keydown' event is used.

 var special_key_map = { 'enter': 13, 'esc': 27}  
 ko.bindingHandlers.shortcut = {  
   init: function(element, valueAccessor, allBindingsAccessor,viewModel) {  
     var key = valueAccessor();  
     key = key.toLowerCase();  
     var match = key.match(/ctrl\+/gi);  
     var ctrl_modifier = Boolean(match && match.length > 0);  
     match = key.match(/alt\+/gi);  
     var alt_modifier = Boolean(match && match.length > 0);  
     key = key.replace(/(alt\+|ctrl\+)/gi,'');  
     var keycode = null;      
     if( key in special_key_map) {      
       keycode = special_key_map[key];      
     }else {    
       keycode = key.charCodeAt(0);  
     }  
     var handler = function(event) {  
       //first check if the element is visible. Do not trigger clicks      
       // on invisible elements. This way I can add short cuts on      
       // drop down menus. if($(element).is(':visible')){  
       var modifier_match = ( ctrl_modifier == (event.metaKey || event.ctrlKey))  
         && ( alt_modifier == event.altKey );  
       if( modifier_match && (event.charCode == keycode || event.keyCode == keycode)) {  
         event.preventDefault();  
         event.stopPropagation();  
         $(element).click();  
         return false;    
       }  
       return true;  
     }  
     if( key in special_key_map) {  
       $('body').on('keydown', handler);  
     }else {  
       $('body').on('keypress', handler);  
     }  
   }  
 }  

Version 4:

Now shortcuts like just 'n' has to be ignored if the focus is on a form input field. However, shortcut like 'escape' or 'ctrl+n' (i.e. special key or with modifier) should work even when the focus is on form input. So lets add that condition as well.

 var special_key_map = { 'enter': 13, 'esc': 27}  
 ko.bindingHandlers.shortcut = {  
   init: function(element, valueAccessor, allBindingsAccessor,viewModel) {  
     var key = valueAccessor();      
     key = key.toLowerCase();  
     var match = key.match(/ctrl\+/gi);      
     var ctrl_modifier = Boolean(match && match.length > 0);  
     match = key.match(/alt\+/gi);      
     var alt_modifier = Boolean(match && match.length > 0);  
     key = key.replace(/(alt\+|ctrl\+)/gi,'');  
     var keycode = null;  
     if( key in special_key_map) {  
       keycode = special_key_map[key];   
     }else {  
       keycode = key.charCodeAt(0);  
     }  
     // if no modifiers are specified in the shortcut (.e.g shortcut is just 'n')  
     // in such cases, do not trigger the shortcut if the focus is on  
     // form field.  
     // if modifier are specified, then even if focus is on form field  
     // trigger the shortcut (e.g. ctrl+enter)  
     var ignore_form_input=Boolean(ctrl_modifier || alt_modifier || key in special_key_map);  
     var handler = function(event) {  
       //first check if the element is visible. Do not trigger clicks  
       // on invisible elements. This way I can add short cuts on  
       // drop down menus.  
       var $element = $(element);        
       var $target = $(event.target);  
       var is_forminput = Boolean($target.is('button')==false && $target.is(':input')==true);  
       if($element.is(':visible') && (ignore_form_input==true || is_forminput==false)) {  
         var modifier_match = ( ctrl_modifier == (event.metaKey || event.ctrlKey))  
           && ( alt_modifier == event.altKey );  
         if( modifier_match && (event.charCode == keycode || event.keyCode == keycode)) {  
           event.preventDefault();  
           event.stopPropagation();  
           $element.click();  
           return false;  
         }  
       }  
     return true;  
     }  
     if( key in special_key_map) {  
       $('body').on('keydown', handler);  
     }else {  
       $('body').on('keypress', handler);  
     }  
   }  
 }  

Version 5 (Final):

So far we are not removing the attached event handlers. Obviously it's not a good idea especially if binding get evaluated multiple times and event handler gets attached multiple times. To remove the event handler, we have to define a 'dispose' callback which gets called, whenever the element (to which the binding is attached) is disposed/deleted from the DOM.

 /*  
 * Copyright 2012 Sensible Softwares Pvt. Ltd, India. (http://bootstraptoday.com)  
 *  
 * Licensed under the MIT License. (http://opensource.org/licenses/mit-license.php)  
 *  
 */  
 var special_key_map = { 'enter': 13, 'esc': 27}  
 ko.bindingHandlers.shortcut = {  
   init: function(element, valueAccessor, allBindingsAccessor,viewModel) {  
     var key = valueAccessor();  
     key = key.toLowerCase();  
     var match = key.match(/ctrl\+/gi);    
     var ctrl_modifier = Boolean(match && match.length > 0);  
     match = key.match(/alt\+/gi);  
     var alt_modifier = Boolean(match && match.length > 0);  
     key = key.replace(/(alt\+|ctrl\+)/gi,'');  
     var keycode = null;  
     if( key in special_key_map) {  
       keycode = special_key_map[key];  
     }else {  
       keycode = key.charCodeAt(0);  
     }  
     // if no modifiers are specified in the shortcut (.e.g shortcut is just 'n')  
     // in such cases, do not trigger the shortcut if the focus is on  
     // form field.  
     // if modifier are specified, then even if focus is on form field  
     // trigger the shortcut (e.g. ctrl+enter)  
     var ignore_form_input=Boolean(ctrl_modifier || alt_modifier || key in special_key_map);  
     var handler = function(event) {  
       //first check if the element is visible. Do not trigger clicks  
       // on invisible elements. This way I can add short cuts on  
       // drop down menus.  
       var $element = $(element);  
       var $target = $(event.target);  
       var is_forminput = Boolean($target.is('button')==false && $target.is(':input')==true)  
       if($element.is(':visible') && (ignore_form_input==true || is_forminput==false)) {  
         var modifier_match = ( ctrl_modifier == (event.metaKey || event.ctrlKey))  
           && ( alt_modifier == event.altKey );  
          if( modifier_match && (event.charCode == keycode || event.keyCode == keycode)) {  
           event.preventDefault();   
           event.stopPropagation();  
           $element.click();  
           // event is handled so return false so that any further propagation is stopped.  
           return false;    
         }  
       }  
       // event is not handled. Hence return true so that propagation continues.  
       return true;  
     }  
     var eventname='keypress';  
     if( key in special_key_map) {    
       eventname = 'keydown';  
     }  
     $('body').on(eventname, handler);  
     var removeHandlerCallback = function() {    
       $('body').off(eventname, handler);  
     }  
     // Now add a callback on the element so that when the element is 'disposed'  
     // we can remove the event handler from the 'body'  
     ko.utils.domNodeDisposal.addDisposeCallback(element, removeHandlerCallback);    
   }  
 }  

That's the final version. So far it's working out very nicely in BootStrapToday. If we find any bugs or enhancements we will update here. Please feel free to suggest improvements.

You can check live by signing up for free from here.

License : Shortcut binding code above is licensed under MIT License.Same as KnockoutJS. So feel free to use it anyway that you want.