Wednesday, August 13, 2014

Parallel Javascript

ParallelJS started its life as River Trail, a JavaScript language extension for Firefox by Intel. River Trail provides a new constructor, ParallelArray with iteration methods whose callbacks are executed concurrently.
ParallelJS brings the RiverTrail idea to normal arrays and has recently been included in Firefox Nightly. It adds three methods to arrays (binary data will eventually get those methods, too):

These methods work like the traditional array methods map(), filter() and reduce(), but the order in which the elements are processed is undefined (with the non-par versions, you know exactly in which order they are processed). That enables concurrent execution of multiple instances of the callback. However, not all callbacks can be run concurrently. A callback must fulfill certain requirements:
It must not mutate shared data. It can freely change data that it has created, but can only read data from the outside world.
Many host (or “native”) objects can’t be used. That includes the DOM, which may never be supported and regular expressions for which short- to mid-term support is likely. All vanilla JavaScript objects are fine, though.
PJS code is executed like this: It is first run sequentially and observed. The requirements for parallelism are checked. If they are fulfilled, parallel code is produced and run in parallel. If any of the requirements are not fulfilled anymore, then PJS reverts to sequential execution.
The rules for when PJS code can be run concurrently will probably never be standardized, because a PJS standard needs to accomodate a variety of implementation approaches (see below). There will, however, be guidelines and recommendations for what works for most implementations.

Given how difficult it is to predict whether your code can be run concurrently or not, an important part of PJS will be diagnostic tools. They will let you find out when and why code is not parallelizable.

ParallelJS is currently tentatively scheduled for ECMAScript 8. If you are worried that that’s too far into the future: ECMAScript 7 and ECMAScript 8 will be smaller and developed more quickly than ECMAScript 6.

Also checkout Webcl for the work there on Parallel Computing in HTML 5 Browsers.

Tuesday, July 15, 2014

Reactive Manifesto

1. Event Driven via Asynchronous Communication
In an event-driven application, the components interact with each other through the production and consumption of events—discrete pieces of information describing facts. These events are sent and received in an asynchronous and non-blocking fashion. Event-driven systems tend to rely on push rather than pull or poll, i.e. they push data towards consumers when it is available instead of wasting resources by having the consumers continually ask for or wait on the data.

Event-driven systems enable loose coupling between components and subsystems. This level of indirection is, as we will see, one of the prerequisites for scalability and resilience. By removing complex and strong dependencies between components, event-driven applications can be extended with minimal impact on the existing application.

2.  Scalable via Location transparency
The topology of the application becomes a deployment decision which is expressed through configuration and/or adaptive runtime algorithms responding to application usage.

3. Resilient via Fine Grained Error Handling
Application downtime is one of the most damaging issues that can occur to a business. The usual implication is that operations simply stop, leaving a hole in the revenue stream. In the long term it can also lead to unhappy customers and a poor reputation, which will hurt the business more severely. It is surprising that application resilience is a requirement that is largely ignored or retrofitted using ad-hoc techniques. This often means that it is addressed at the wrong level of granularity using tools that are too coarse-grained. A common technique uses application server clustering to recover from runtime and server failures. Unfortunately, server failover is extremely costly and also dangerous—potentially leading to cascading failures taking down a whole cluster. The reason is that this is the wrong level of granularity for failure management which should instead be addressed using fine-grained resilience on the component level.

In a reactive application, resilience is not an afterthought but part of the design from the beginning. Making failure a first class construct in the programming model provides the means to react to and manage it, which leads to applications that are highly tolerant to failure by being able to heal and repair themselves at runtime. Traditional fault handling cannot achieve this because it is defensive in the small and too aggressive in the large—you either handle exceptions right where and when they happen or you initiate a failover of the whole application instance.

Key Building Blocks

In order to manage failure we need a way to isolate it so it doesn’t spread to other healthy components, and to observe it so it can be managed from a safe point outside of the failed context. One pattern that comes to mind is the bulkhead pattern, illustrated by the picture, in which a system is built up from safe compartments so that if one of them fails the other ones are not affected. This prevents the classic problem of cascading failures and allows the management of problems in isolation.

The event-driven model, which enables scalability, also has the necessary primitives to realize this model of failure management. The loose coupling in an event-driven model provides fully isolated components in which failures can be captured together with their context, encapsulated as messages, and sent off to other components that can inspect the error and decide how to respond.

4. Responsive via observable models, event streams, and stateful clients
Observable models enable other systems to receive events when state changes. This can provide a real-time connection between users and systems. For example, when multiple users work concurrently on the same model, changes can be reactively synchronized bi-directionally between them, thus appearing as if the model is shared without the constraints of locking.

Event streams form the basic abstraction on which this connection is built. Keeping them reactive means avoiding blocking and instead allowing asynchronous and non-blocking transformations and communication.

Reactive applications embrace the order of algorithms by employing design patterns and tests to ensure a response event is returned in O(1) or at least O(log n) time regardless of load. The scaling factor can include but is not limited to customers, sessions, products and deals.

They employ a number of strategies to keep response latency consistent regardless of load profile:

Under bursty traffic conditions reactive applications amortize the cost of expensive operations—such as IO and concurrent data exchange—by applying batching combined with an understanding and consideration of the underlying resources to keep latency consistent.
Queues are bounded with appropriate back pressure applied, queue lengths for given response constraints are determined by employing Little’s Law.
Systems are monitored with appropriate capacity planning in place.
Failures are isolated with alternate processing strategies readily available for when circuit breakers are triggered.

Friday, May 2, 2014

Improved Type Inference in C++11: auto, decltype, and the new function declaration syntax

int x = 3;
decltype(x) y = x; // same thing as auto y = x;
You can use decltype for pretty much any expression, including to express the type for a return value from a method. Hmm, that sounds like a familiar problem doesn't it? What if we could write:
decltype( builder.makeObject() )
This would give us the type that is returned from makeObject, allowing us to specify the return value from makeAndProcessObject. We can combine this with the new return value syntax to produce this method:
template <typename Builder>
makeAndProcessObject (const Builder& builder) -> decltype( builder.makeObject() )
    auto val = builder.makeObject();
    // do stuff with val
    return val;

As of this writing, GCC 4.4 and MSVC 10 both support everything I've talked about this article, and I'm used most of these techniques in production code; these aren't theoretical benefits, they're real. So if you're compiling your code with -std=c++0x in GCC or using MSVC 10, you can start using these techniques today. If you're using another compiler, check out this page for details of C++11 compiler support. Since the standard has been ratified, and should be published within weeks, now's the time to start.

Tuesday, December 3, 2013

Structuring Single Page Applications

Knockout js, Require js, Templating

1. I came up with a custom solution to a problem we were having at my job. We needed to be able to add components to the screen and then reuse that screen real estate later. Therefore we wanted to dispose of old components and prevent memory leaks. In the past I had experience with Backbone js and two frameworks written for it, Chaplin and Marionette. I found Marionette's solution to be the best, it had the idea of a Region. A Region represents an area of the screen usually an element. It controls opening and closing a view inside it's area. This allows you to composite the screen up into Regions, also taking care of making sure a parent Region closes any child Regions it knows about.

2. When initially designing the application we wanted to be able to split up the javascript files to make for easy development. In order to make a quicker load in production we wanted to be able to recombine and minify those files into one. Require js allows us to do all of these things easily.

3. Finally we wanted to split up our knockout templates into separate files, I used handlebars, and would use a "View" to apply a knockout viewmodel to a rendered template inside an element. Something like this ko.applyBindings(new BlahViewModel(), this.el);

Final thoughts on this approach and combination of technologies. I found knockout js to be extremely productive and I wasted less time doing simple things by using knockout's expressive templates and great bindings. Dependency tracking proved extremely useful and very versatile as well. Using require js and templating (handlebars in my case) to split up the javascript files and the markup/knockout stuff made the application much more maintainable. Falcon js seems to combine alot of the things I did by hand but I don't see any mention of the idea of Regions.

Backbone js, Marionette js, Require js

Look to my previous articles for a detailed explanation about these technologies. All in all has many of the benefits as the knockout stack above but not nearly as productive as knockout. Knockout has great support for binding html components to javascript viewmodels which saves LOTS of time.

Tuesday, November 19, 2013

Infinite scroll performance with lots of elements

The problem when using infinite scroll with LOTS of elements is the browser gets bogged down.

This guy eloquently gives a great explanation of a solution.

We had to deal with a similar problem on FoldingText. As the document grew larger, more line elements and associated span elements were created. The browser engine just seemed to choke, and so a better solution needed to be found.
Here's what we did, may or may not be useful for your purposes:
Visualize the entire page as a long document, and the browser viewport as the lens for a specific part of the long document. You really only have to show the part within the lens.

So the first part is to calculate the visible view port. (This depends on how your elements are placed, absolute / fixed / default)

var top = document.scrollTop;
var width = window.innerWidth;
var height = window.innerHeight;
Some more resources to find a more cross-browser based viewport:

Second, you need a data structure to know which elements are visible in that area

We already had a balanced binary search tree in place for text editing, so we extended it to manage line heights too, so this part for us was relatively easy. I don't think you'll need a complex data structure for managing your element heights; a simple array or object might do fine. Just make sure you can query heights and dimensions easily on it. Now, how would you get the height data for all your elements. A very simple (but computationally expensive for large amounts of elements!)
var boundingRect = element.getBoundingClientRect()
I'm talking in terms of pure javascript, but if you're using jQuery $.offset$.position, and methods listed here would be quite helpful.
Again, using a data structure is important only as a cache, but if you want, you could do it on the fly (though as I've stated these operations are expensive). Also, beware of changing css styles and calling these methods. These functions force redraw, so you'll see a performance issue.

Lastly, just replace the elements offscreen with a single, say <div> element with calculated height

  • Now, you have heights for all the elements stored in your Data structure, query all the elements that lie before the visible viewport.
  • Create a <div> with css height set (in pixels) to the sum of the element heights
  • Mark it with a class name so that you know its a filler div
  • Remove all the elements from the dom that this div covers
  • insert this newly created div instead
Repeat for elements that lie after the visible viewport.
Look for scroll and resize events. On each scroll, you will need to go back to your data structure, remove the filler divs, create elements that were previously removed from screen, and accordingly add new filler divs.
:) It's a long, complex method, but for large documents it increased our performance by a large margin.


I'm not sure I explained it properly, but the gist of this method is:
  • Know the vertical dimensions of your elements
  • Know the scrolled view port
  • Represent all off-screen elements with a single div (height equal to the sum of all element heights it covers for)
  • You will need two divs in total at any given time, one for elements above the visible viewport, one for elements below.
  • Keep track of the view port by listening for scroll and resize events. Recreate the divs and visible elements accordingly

Great Linkedin demonstation of the problem and solution.

Mobile devices have less memory and CPU power compared to Desktop computers. If you render a very long list in the HTML, you run the risk of crashing the device. This makes it challenging to build large, interactive HTML5 apps for mobile devices. Native technologies provide UITableViewController to build long, infinite scrolling lists. UITableView contains reusable UITableViewCells which are optimized for memory, performance and responsiveness . For HTML5, we did not have any solution. So we set out to build one!

Technique #1: unloading images

Technique #2: hiding pages

Technique #3: removing pages

Technique #4: avoid scaling and box-shadow

Technique #5: minimizing DOM nodes

Grid of elements with variable heights and a sorted order

You have a grid of elements each with a fixed width and a variable height. Example. Images that have fixed width and a variable height because you want to preserve the aspect ratio.

The problem you want to align them into a grid but simple floating them leaves large gaps in vertical space between elements.

Great further explanation of the problem, taken from link below.

"To my knowledge, there's no way to fix this problem with pure CSS (that works in all common browsers):
  • Floats don't work.
  • display: inline-block doesn't work.
  • position: relative with position: absolute requires manual pixel tuning. If you're using a server-side language, and you're working with images (or something with predictable height), you can handle the pixel tuning "automatically" with server-side code.
Instead, use jQuery Masonry."


1. This sorts the elements by height.

            arrange.elements.push(new Array($(this).height(), $(this).clone()));
 for(var i = 0; i < arrange.elements.length; i ++)
          if(arrange.elements[i][0] > current)
              current = arrange.elements[i][0];
              elem = arrange.elements[i][1];
              index = i;

This is pretty slow by the way.

2. Use jquery masonry or isotope

3. Absolute positioning

Jquery Waterfall Plugin

4. Solution we settled on after playing with all of the above techniques.

We organize the elements into their respective sections one for each column, this way we can both insert sorted data into them and preserve reasonable vertical spacing.

So for n columns you would have markup like the following.

<section class="mediaItems overview" data-bind="foreach: columns">
<div class="column-div" data-bind="unveil: $root.everyNthMediaItems($index())">
<img data-bind=" attr: { src: url}" />

We precompute the items that will be in each column to make it faster loading on the dom aka (everyNthMediaItems). That way we start with sorted data and then run everyNthMediaItems to put that data into columns thereby preserving the sorting and keeping vertical spacing correct.


Thursday, October 17, 2013

Make your JQuery plugin loadable with Require.JS

A simple and easy way to make your JQuery plugin work in an AMD and NON-AMD context is the  following snippet. See how it cleverly uses the factory.

(function (factory) {
if (typeof define === 'function' && define.amd) {
    // AMD. Register as an anonymous module.
    define(['jquery'], factory);
} else {
    // Browser globals
}(function ($) {

    $.fn.jqueryPlugin = function () {
        // Put your plugin code here