Rethinking Single Loop Optimization to Enable Modular Design

It’s not uncommon to hear that you can make a program more efficient by combining loops. The idea is “why loop over something three times when you can loop over it once?”. However there is danger in this idea as a blanket assumption. Furthermore it impedes patterns that can be quite scalable and powerful.

//Setup
var l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function funcOne(i) { /*...*/ }
function funcTwo(i) { /*...*/ }
function funcThree(i) { /*...*/ }

//First way
_.each(l, funcOne);
_.each(l, funcTwo);
_.each(l, funcThree);

//"Optimized" way
_.each(l, function (i) {
  funcOne(i);
  funcTwo(i);
  funcThree(i);
});

When This Assumption is Correct

The more I though about this the harder this statement became to justify. In an academically absolute circumstance each loop creates some over head. So, in that case it is correct to cluster the operations on each item. In cases when the list or collection that you will loop over is extremely large that overhead could be crippling. The classic example is reading a very large file from disk. Keeping the data in memory was problematic in the past. However now modern programming patterns have reduced this problem or removed it all together by using streams and iterators.

Thinking Modular

If we let go of the first assumption and look at this another way we can lay the foundation for some very powerful patterns. So lets look again at our first example and make a minor logical jump.

//If the "Optimized" way
_.each(l, function (i) {
  funcOne(i);
  funcTwo(i);
  funcThree(i);
});
//Is equivalent to 
//First way
_.each(l, funcOne);
_.each(l, funcTwo);
_.each(l, funcThree);
//What would the benefit be instead of working on one element
//in the set the function took the set instead?
funcOne(l);
funcTwo(l);
funcThree(l);

The power from this assumption is that if the function takes a set instead of just an element from it each function now entirely wraps a step or possibly a feature. The other advantage to this is that you could store your steps in their own set or collection that you could programmatic add and remove items. This is how Express in Node.js works. Every time you add a module it gets added to a list. When a request comes into the server it walks down the chain of modules with each one processing data is it goes. This is very powerful architecturally.

//A list of modules
var m = [modOne, modTwo, modThree];
//We can now just iterate over our modules 
_.each(m, function (f) { f(l); });

Getting the path of a script file during execution

Recently I was looking at a script in an Angular.js controller that used a template. An absolute path was being used to reference the template from the controller in each as this was the way the pattern we were using for modules. Though it seemed like a good way to isolate concerns and organize the code having hard coded strings always bothers me. So I started looking into if it was possible in JavaScript to get the file location of a script during execution. As it turns out there are a couple of ways and here is how I ended up at my solution.

arguments.callee()

There were some suggestions that you could build a call stack with arguments.callee() by getting the function that was scoped and calling .toString() to get its name. First off this requires access to the whole call stack and secondly in ‘strict mode’ it is no longer allowed. So this was not really ever an option for me.

document script tag inspection

The second approach I found that was popular was in a script to inspect the DOM and get the “src” attribute of the last script tag. The assumption is that since the scripts are parsed in order that as the code was executed that it would be the current and last script in the document before the next was added and run.

//Select the "last" script tag, the one that currently being interpreted
//at least that's the assumption.
$('script[src]').last();

The problem with this approach was that it was based on alot of assumptions. It also would not work with lazy loading or any script tag with an async attribute. Lastly, if we are going to be picky it would be ideal if we could programmatically call and return the path of the file we are in at any time.

Inspecting the call-stack of an exception

This method was the most reliable of the three if not the least convenient to extract the final information from. This method works on try / catch / throw in JavaScript and the Error() object. By creating and throwing an error the exception can then be caught and the location of the file that caused it inspected from the call stack. This can also be done at any time during script loading and as many times as one would need/want. The specifics are commented in the code and the full reference can be found in the project it is apart of on my GitHub account.

    function ScriptPath() {
      var scriptPath = '';
      try {
        //Throw an error to generate a stack trace
        throw new Error();
      }
      catch(e) {
        //Split the stack trace into each line
        var stackLines = e.stack.split('n');
        var callerIndex = 0;
        //Now walk though each line until we find a path reference
        for(var i in stackLines){
          if(!stackLines[i].match(/http[s]?:///)) continue;
          //We skipped all the lines with out an http so we now have a script reference
          //This one is the class constructor, the next is the getScriptPath() call
          //The one after that is the user code requesting the path info (so offset by 2)
          callerIndex = Number(i) + 2;
          break;
        }
        //Now parse the string for each section we want to return
        pathParts = stackLines[callerIndex].match(/((http[s]?://.+/)([^/]+.js)):/);
      }

      this.fullPath = function() {
        return pathParts[1];
      };

      this.path = function() {
        return pathParts[2];
      };

      this.file = function() {
        return pathParts[3];
      };

      this.fileNoExt = function() {
        var parts = this.file().split('.');
        parts.length = parts.length != 1 ? parts.length - 1 : 1;
        return parts.join('.');
      };
    }

Angualr.js $apply, $digest, Thread Blocking and Preemption

It’s been a week since I gave a talk about Angular.js and someone mentioned the importance of not calling $apply during a $digest cycle. I have read this too, but it struck me at the time that this could even be possible given that script execution in the browser is single threaded. This single threaded-ness is also the principle behind Node.js and it’s asynchronous architecture. So I decided to follow up on my own.

The Browser Update Cycle

A browser splits it time between two phases. The first is rendering the page by reading the markup and applying styles. The second is to execute any scripts that have been queued to run. Then it renders any changes to the page and executes the next script that has been queued. This is actually where the practice of using

setTimeout(fn(), 0)

to allow UI updates comes from. This creates a time out with no delay and fn() is pushed on the end of the script queue. Once the current script scope, the entirety of the call stack, is finished the script engine yields to the render cycle and in the next script cycle fn() is called. If you use Underscore.js (_) the short hand function is _.defer(fn()). Node.js does the same thing though with out the render cycle and because all interaction outside of the main thread is pushed you callbacks the process never waits, and efficiently processes the next function that was queued.

Thread Blocking and Preemption

The rules for execution is that the queue takes functions and each function is executed to its completion. In this process there is no preemption in the execution of code. No matter how deep the call stack may be when a time out or event fires it is put on the end of the script queue and serviced in order of arrival. In this way a complex or poorly written loop can block the execution of the code that is in the queue, and essentially blocks execution.

The issue with $apply and $digest

So with the theory of what we know, how is it possible to call an $apply during a $digest? Angular has it’s own event loop, and one of the things it does is observes any changes to the data in the $apply cycle. This happens automatically for models that are updated inside controllers, scopes, or ng- events, and manually by calling $apply directly. The next step is for angular to call $digest to apply these changes to the scope. Now from what know $apply can’t preempt or interrupt the execution of $digest so what cause the error. The issue is that Angular knows that $digest has been put on the process queue and that calling $apply will interfere with cycle. Angular tracks this by setting the $$phase in the root scope.

The Proof

Theory is sound but I feel better when I have examples that prove it. So I created two examples to illustrate the point of blocking and the absence of preemption.

Blocking Code

This code shows that the interval wont fire until it has a chance to execute after the current block of code has finished. It is interesting to note that not only do only just one of the intervals fire but if the clearInterval() is called in the first code block and not from a timeout the interval never gets a chance to fire at all.

console.clear();
function blockingLoop (delay) {
  var start = new Date();
  while((new Date() - start) <= delay){
    // noprotect
    // ^^^^^^^^^ this stops jsbin from exiting the loop.
    // if you modify this, beware!
  }
  //This will show up formatted on a native console
  console.log('Delayed for %sms', (new Date()) - start);
}

var delay = 500;
var numberOfIntervals = 4;

var intervalId = setInterval(function () {
  console.log('Interval Called');
}, delay / numberOfIntervals);

blockingLoop(delay);

//We expect to see "numberOfIntervals" notifications
//But we only get one, since is executed after the script block

//If you call "clearInterval" outside of this time out the
//interval will never be called...
setTimeout(function () {clearInterval(intervalId);}, 0);

Live Example

No Preemption

This example shows that no matter where the time out is set that they will not execute until after the current code block and call stack is finished. The timeouts also execute in order of their placement in the queue, as any proper queue should function. :p

/*
  To use press run in the console window
*/
console.clear();
console.log('--- Start Script Scope ---');
var timeoutId = 0,
    theTimeout = function (id) {
      /*
        We return a function with the id in a closure
        so that we can assign a number to it and see
        the order in which they were called
      */
      return function () {
        console.log('--- Callback ' + id + ' Called ---');
      };
    },
    one = function () {
      console.log('enter one -->');
      two();
      console.log('exit one <--');
    },
    two = function () {
      console.log('enter two -->');
      three();
      console.log('exit two <--');
    },
    three = function () {
      console.log('enter three -->');
      //Set the time out to zero so it will be next on the queue
      setTimeout(theTimeout(++timeoutId), 0);
      console.log('exit three <--');
    };

console.log('Call Function Chain');
one();

console.log('Call Function Chain Again');
one();

console.log('--- End of Script Scope ---');

Live Example

Hitting the Ground Running with Angular.js

I recently gave a talk on Angular.js and the fundamentals of how it works. My hope was to provide many examples of how to use directives to annotate the markup of the page and explain the subtleties of what was going on along the way. The group was very knowledgeable and we had a great discussion though out. Here are the the links that came along with the slides.

TypeScript and My Fat Arrow Folly

I recently started working in TypeScript. It was really easy to pick it up, because if you know JavaScript, then you know TypeScript. So it was not long before I was converting all of my old helper code into TypeScript as well. However I ran into a problem with the string formatter I had writen for JavaScript. It seemed easy enough but despite everything I tried, the code would not compile. This is where I started:

interface String {
    showString: () => string;
}

String.prototype.format = () : string {
    var formatted = this;
    for (var i = 0; i < arguments.length; i++) {
        formatted = formatted.replace(
            RegExp("\{" + i + "\}", 'g'), arguments[i].toString());
    }
    return formatted;
}; 

Yet no matter what I tried I could not get it to work. Every time I would get an error stating “_this is not defined…”. The issue ends up to be very simple so let’s start at the top with “this”. In JavaScript a function references the scope that it executes in with “this”. That usually means the instance of the object the function is called in, or it means the window when not encapsulated. This can can also be changed by calling a function with f.call() or f.apply(). It can take some understanding to know what “this” actually represents in the context so in TypeScript functions were given a fat arrow syntax to have them perform like functions in C, Java, and C#.

Take a look at:

var f = function (postFix) {return this + postFix};

To add TypeScript syntax you would define types

var f = function (postFix: string): string {return this + postFix};

In both of these cases this refers to the scope of the function just like classic JavaScript. However, things change when we do this…

var f = (postFix: string): string {return this + postFix};
//or more correctly
var f = (postFix: string): string => {return this + postFix};

When you remove the function from in front of the parameters then it is no longer a classic function. It becomes a “Fat Arrow” function, apparently even with out using the “=>” syntax. In the examples above “this” now refers to the class that the function exists in like in C#.

In my attempt to assign a function to the prototype of string I omitted the function keyword so it was interpreted as a “Fat Arrow” function and tries to bind this to the scope of the class. However the function dose not exist in a class and causes the error “_this is not defined”.

When I add the “function” keyword, the function is interpreted as I intended and works correctly.

interface String {
    format: () => string;
}

String.prototype.format = function () : string {
    var formatted = this;
    for (var i = 0; i < arguments.length; i++) {
        formatted = formatted.replace(
            RegExp("\{" + i + "\}", 'g'), arguments[i].toString());
    }
    return formatted;
};

Simple Rot13 Function

For Communeicator I had to write a encoding algorithm that would work to encode and decode a message. There is an algorithm that does just such a thing, and it’s not hard to explain or implement. When I was finished I was very pleased at how simple and elegant it was. Here is it in its entirety.

console.clear();
console.log('encode');

var s = 'this is a test';

function encode(s){
  return _.map(s, function (d) {
    if(!(/[a-zA-Z]/.test(d))) return d;
    var lowerCaseOffset = 'a'.charCodeAt(0),
        upperCaseOffset = 'A'.charCodeAt(0);
    
    var offset = /[a-z]/.test(d) ?
        lowerCaseOffset : 
        upperCaseOffset;
    
    var baseVal = d.charCodeAt(0) - offset,
        shiftVal = baseVal + 13,
        newBase = shiftVal % 26,
        newVal = newBase + offset;
    return String.fromCharCode(newVal);
    
  }).join('');
}

console.log(encode(s));
console.log(encode(encode(s)));

Working example at jsBin.com

Communeicator.com – The Free, Private, Secret Message Encoder.

How it came to be

I started a side project to use some of the libraries I’ve been getting more experience with. I came up with the idea of a site that could encode messages and then decode them all in a single page application. Once you entered the text in it would be encoded and be added to the end of the address of the part of the app that would decode it. I made a quick demo and then after some quick updates and some polish I’ve finished the first release of Communicator.com!

What it does, and does well

Communicator is an app that lets you encode a secret message and send it to someone to read. The way it works is you type a message, preview the encryption and save a link to your secret message. The site stores nothing and there is no record of who created the message. Give the link to the recipient and they can watch it decode before their eyes. So give it a shot if you want to send a middle of the day affirmation to someone special or need to setup a clandestine meetup for undisclosed intentions. The site stores no messages at all. The only trace is from the URL shortening service that is used to make sharing the message easier and they produce no public records. They, is.gd, are also an “Ethical” url shortener meaning they intend to keep the site free and are carbon neutral. So give it a spin.

Why I’m excited about it as a programmer

Well I’m glad you asked. This app uses Angular.js and it’s template, routing, and http helper classes to enable the foundation for the site. The layout is done using a minimalist CSS grid system called Purecss. The decoding animation is done using D3, Data Driven Design, to mind the text and transition between the words once the text is decoded. The url shortening is done using JSONP and the underscore.js library glues any left over architecture together. The site is also hosted on the Amazon Simple Storage Service as it is ideal for a single page application and uses Amazon to manage the name servers for the domain instead of the registry that was used for the domain. I found this a fun project because of all the disperse parts that needed to be strung together, styled, and implemented correctly while not being a total monster. So take it for a spin and enjoy.

Build a Better Bar Chart Using SVG and HTML

How to Build a Better Bar Chart

NOTICE: Your browser must be able to render SVG for you to see the examples on this page.

Most people looking at SVG are trying to do some sort of charting. Starting off it looks simple but quickly quarks start piling up till your trivial task is slightly more convoluted. Looking over these examples of how you probably progressed I have a final example that allows you to remove some of the bss aackward ness from the process.

Starting with Intuition

You first try probably looked like this. I have actually seed this setup as example code for some D3 tutorials. No, they don’t leave it like this either. This is because it was decided that the layout would follow a screen scanning approach where the upper left corner is the start of the coordinate system. Unlike in Math where graphing starts in the lower left and positive values are up not down, but thats not going to get changed now…

Adjusting for Computer Science

This is where most other examples stop. You have solved the problem though computation. You spend some time thinking about it and come up with a way to calculate the way to place the columns on the bottom of the view. Offset each column by 100% minus its height and you get its correct position. We, however, can do better.

The Solution / Easy Fix

Thinking about what we did in step one, our problem was that the bars were flipped from the way we expected it. There is a transform for that but that’s not our entire solution. If we just flip the bars over the y axis then we will not be able to see them. We instead have to translate the chart down to the bottom of the viewport. After our scale and transform the chart looks like we expect and we don’t have to calculate any offsets and our heights are positive values. A win indeed.

Clean JavaScript consol.log() Shortcut

A while ago I posted a article about how to do something like string.Format() in C# .net. Recently I started using it more frequently for logging and had the idea to extend string again to save time when writing output to the console.

To review the original code looked like this.

String.prototype.format = function () {
    var formatted = this;
    for (var i = 0; i < arguments.length; i++) {
        formatted = formatted.replace(
            RegExp('\{' + i + '\}', 'g'), arguments[i]);
    }
    return formatted;
};

You use the code by using curly brackets to define where the parameters will replaced in the string.

//You can fill one value in multiple places
var s = 'This {1} is #{0} !!!{0}!'.format(1, 'blog');
//produces: This blog is #1 !!!1!

I know the mustache library can also do replacement and that _.template (underscore) does similar things. My reason for using this over them is that I don’t always want to pass a full object and seed the keys in my string. This syntax is a little more DRY (Don’t repeat yourself).

So once you have use the above code to extended the prototype for string you can use this next block of code to do the same syntax for logging.

String.prototype.log = function () {
    console.log(this.format.apply(this, arguments));
};

Now logging values out to the console is as easy as…

//Same syntax, just ends up on ur console
'Value of something: {0} / or this {1}'.log(a, b);

Try it for your self on JSBin.com

Personal project updates, github dump.

I’m a professional developer. I’m lucky enough that my job is also my hobby and as such I have tinkered with many side projects. Some of those are merely proof of concepts. Others develop into functioning programs. Those other projects come up from time to time in conversation so I finally figured that I would post them online. Now, besides being proof that they actually exists, I can also get comments on how they were designed and implemented.

SmithWiki

https://github.com/QueueHammer/SmithWiki

A JavaScript based Wiki. Built using jQuery, Underscore, Backbone, Mustache, and Amplify.

In the past I had used javascript wiki called TiddlyWiki. However modern browsers add restrictions to local file modification, disabling any permanent changes to TiddlyWiki. Looking at the idea of making my own I realized that a number of frameworks had been created to make developing such an app easier. Specifically jQuery to clean up working with the DOM, Backbone for managing Views / Local Routes, Mustache for templating, and Amplify for persistent storage.

CC-MineLib

https://github.com/QueueHammer/CC-MineLib

My friend hosts a Minecraft server. Over Christmas one year he convinced me to look into the Turtles Mod. It basically lets you program a block that can move left, right, up, down, forward, and backward to perform tasks. Watching how people were using the “Turtles” i came up with some utility function that I build into a library between Christmas and New Years.

My favorite programs is “atn” or Advanced Turtle Notation. This program took a string of characters to drive the Turtle based on the keys used in first person games; asdw. So to have the Turtle go forward 3 and turn left and go backward 2 your would type “atn wwwass”. Now, that was a big improvement of having to write a custom program for that or call different programs for forward and turn, but it could be better. That’s where the advanced part of the Turtle notation comes in. I made it so you could queue up commands and that it was fully recursive. To go in a circle 4 times you could just write “atn 4(4(wd))”. With the ability to dig and place blocks added in its uses were endless, endless.

Other good programs were fuel, and consume.

Fuel was designed to refuel and display the current fuel of a Turtle. I like it cause of its simple interface. Type the command “fuel” and you see the fuel level, pass in a parameter for where the fuel is in the inventory and it would consume it to refuel the Turtle.

Consume was fun because it leverages the functional nature of Lua. Its not exceptionally hard to write a program to recursively search out the next touching block and consume it, even in three space, but to to it with calls to an function that is a template for an action and pass the steps in as a function was a challenge. I honestly look at it and laugh sometimes as I remember how it works.

WPF 3D Hex Grid

https://github.com/QueueHammer/WPF3DGrid

A WPF 3D demo I made to try out ray tracing to a background element. When you click the tile will change to an inverse color scheme. The tiles are hexes and require that they be laid in an offset pattern. Most WPF / Silverlight examples the view is almost entirely done in markup this I built though code at runtime. I was really excited about property assignment at construction and lambdas at the time so I attempted to make the code look as if C# was a functional language.

Arduino 3×8 Pixel Scroller

https://github.com/QueueHammer/Arduino3x8PixelScroller

The source to a 3×8 pixel LED scroller. Full design and write up is here on this blog!