No description, website, or topics provided.
JavaScript CoffeeScript
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
demo
test
.gitignore
README.md
fast-dom-sorter-1.2.js

README.md

FastDomSorter 1.2

FastDomSorter is designed to solve a very specific problem:

  1. The data you have to sort is in an array of javascript objects uniquely identified by an ID (entities).
  2. You have to sort on the client; you can not go back to the server after you've gotten the collection, more than likely to conserve server and/or network resources.
  3. You have a lot of entities - approximately 10,000+ (See "Dealing with Very Large Collections" below).
  4. The DOM you have to sort could be anything - not just a table or a list, but even complex UI widgets.
  5. You need the browser to do everything from the sort to building the DOM tree as quickly as possible.
  6. You need ways to tune the UI depending on what types of performance optimizations need to be applied in your particular situation.

How it Works

FastDomSorter uses two main techniques to sort large numbers of DOM elements as quickly as possible:

  • It uses ID based sort indexes which can be built up front, on demand, or in the background.
  • It keeps a collection of generated HTML strings in a hash keyed by ID.

When a sort is triggered after the indexes are built, the following happens:

  1. Using the sort index, a single pass is made to concatenate the generated HTML string in the proper sort order - this is very fast even for very large collections.
  2. The HTML string is then added to the DOM tree via innerHTML - the fastest way to add to the DOM tree.
  3. The browser then builds the render tree, which is the most costly part of the entire operation (See "Dealing with Very Large Collections" below).
  4. The browser does a single paint, which is very fast even for very large collections.

Dealing with Very Large Collections

FastDomSorter allows for two UI techniques that dramatically speeds up building the render tree, which is necessary as you get above approximately 10,000 entities, as the delay becomes noticeable to the user:

  1. Pagination - Only append to the DOM tree what the user wants to see.
  2. Infinite Scrolling - Append to the DOM in chunks as the user scrolls.

In addition, while it is convenient to build all of your indexes up front, it is far better to only build the index you need to initial render. You then have two options to build the other indexes:

  • Build the sort index on demand when the user issues a sort action. This index will be cached, so you do not have to rebuild the index every time the user issues the same a sort request.
  • Build the sort index in the background, after the page has initially rendered, in anticipation of a user's sort. An advanced UI might show the sort controls only after the sort index is built. Building each index will block the UI thread, so building each index should be done on a recursive setTimeout loop for optimal user experience.

If you would like the user to interact with the rendered items, there are two techniques to consider:

  1. Event Delegation - Listen to events only on the parent container, making use of Event Bubbling. Binding events to each individual DOM element would be a massive performance hit.
  2. href="javascript://" - This obsolete technique may in some cases be perform better than even Event Delegation.

Demo

Please see demo/simple-table-sort.html for a working example.

NOTE: The class EntityCollectionGenerator is only used to build a test entity collection, and should not be used outside of demos.

Usage

First, you will need a collection of entities (array of javascript objects) that will provide the data for the DOM elements you want to be sortable. An entity is a object with a unique identifier (id), which can be a number or a string. Without an unique id, FastDomSorter will not work:

var collection = [
  {
    id: 147,
    firstName: 'Alex',
    lastName: 'Clemons'
  },
  {
    id: 313,
    firstName: 'Brian',
    lastName: 'Boston'
  },
  {
    id: 958,
    firstName: 'Chris',
    lastName: 'Abram'
  }
];

Second, you will need a function that builds a HTML string using your entities:

var htmlBuilder = function(entity) {
    return '<tr><td>' + entity.firstName + '</td><td>' + entity.lastName + '</td></tr>';
};

Include this in your page to make FastDomSorter a globally available class:

    <script type="text/javascript" src="fast-dom-sorter-1.2.js"></script>

FastDomSorter's API can be used as a DSL through method chaining. The collection and htmlBuilder are passed into the constructor because without them, FastDomSorter cannot work:

window.fastDomSorter = new FastDomSorter(collection, htmlBuilder)
    .defineIndex('firstLastAsc').orderBy('firstName').orderBy('lastName').ascending().buildIndex()
    .defineIndex('lastFirstDesc').orderBy('lastName').orderBy('firstName').descending().buildIndex()
    .createDomStrings()
    .setDomElementIdToReplace('myList')
    .sortByIndex('firstLastAsc');

The objects and methods used in this simple example:

  • FastDomSorter is a globally available class after you include fast-dom-sorter-1.2.js.
  • collection is an array of objects with unique ID's (entities).
  • htmlBuilder is a function that will build an HTML string from the entities in collection.
  • defineIndex creates a new index that you can sort by later.
  • firstLastAsc and lastFirstDesc are the names of the indexes you are setting up. You can pick whatever names you like - your UI will refer to them in order to trigger the appropriate sort.
  • orderBy specifies which of the properties in the objects in the collection should be used to sort by, and in what order by stringing multiple orderBy() calls together. This is similar to how SQL works.
  • ascending and descending specify sort direction. This is also similar to how SQL works.
  • buildIndex creates the index. If this is an expensive operation, it can be done on demand or in the background rather than up front. If entity values change, the index can be rebuilt at any time.
  • createDomStrings loops through collection and creates id-indexed HTML strings using htmlBuilder.
  • setDomElementIdToReplace sets the id of the DOM element to replace.
  • sortByIndex replaces the DOM element with the id defined by setDomElementIdToReplace. Can be called again at any time to apply a new sort.

sortByIndex has additional optional arguments that can be used to implement pagination or infinite scrolling (also see setDomElementIdToAppend in the list of optional methods) :

  1. start - At what position in the sort index should you start listing items.
  2. limit - How many items should be appended to the DOM tree.

Other optional methods:

  • logToConsole can be placed anywhere in the method chain to start logging performance statistics to the browser's console.
  • setEntityIdProperty allows you to change the default property to use as the entity id. Defaults to id.
  • setEntityIdSplitString allows you to change the default string sequence used to separate the concatenated sort string from the entity id. Defaults to ::. Change to something more unique if you think :: will occur in your string properties.
  • rebuildIndex if an item in collection changes, an index can be rebuilt by name at the developers discretion. This simply delegates to buildIndex, and is more for readability.
  • setDomElementIdToAppend - when doing infinite scrolling, you will want to append to the DOM element, rather than replace it.

Performance Statistics

The following configuration was used for while running demo\simple-table-sort.html:

  • Browser: Chrome 22.0.1229.94
  • OS: Windows 7
  • HD: 7200 RPM
  • Video Card: EVGA GeForce GTX 550 1GB PCI Express 2.0
  • RAM: 8 GB DDR3 SDRAM
  • CPU: AMD Phenom II X4 965 3.4GHzQuad-Core

Statistics for 1,000 entities in collection generating ~5,000 DOM elements (NOTE: All times in milliseconds):

firstLastAsc indexing duration: 1
firstLastAsc sort duration: 4
firstLastAsc entity id pluck duration: 1
firstLastAsc total index build duration: 9
lastFirstDesc indexing duration: 0
lastFirstDesc sort duration: 3
lastFirstDesc entity id pluck duration: 0
lastFirstDesc total index build duration: 4
HTML string concatenation duration: 0
innerHTML assignment duration: 7
1000 items added to DOM tree

(NOTE: The browser then has to build the render tree and paint, but is not noticeable)

Statistics for 10,000 entities in collection generating ~50,000 DOM elements:

firstLastAsc indexing duration: 21
firstLastAsc sort duration: 27
firstLastAsc entity id pluck duration: 19
firstLastAsc total index build duration: 71
lastFirstDesc indexing duration: 17
lastFirstDesc sort duration: 26
lastFirstDesc entity id pluck duration: 18
lastFirstDesc total index build duration: 61
HTML string concatenation duration: 1
innerHTML assignment duration: 68
10000 items added to DOM tree

(NOTE: The browser then has to build the render tree and paint, which takes about 1 second)

Statistics for 100,000 entities in collection generating ~500,000 DOM elements (These times vary widely from test run to test run):

firstLastAsc indexing duration: 2123
firstLastAsc sort duration: 371
firstLastAsc entity id pluck duration: 2269
firstLastAsc total index build duration: 4766
lastFirstDesc indexing duration: 11992
lastFirstDesc sort duration: 361
lastFirstDesc entity id pluck duration: 2086
lastFirstDesc total index build duration: 14439
HTML string concatenation duration: 30
innerHTML assignment duration: 716
100000 items added to DOM tree

(NOTE: The browser then has to build the render tree and paint, which takes about 5 seconds if you are not using
pagination or infinite scrolling - which you should be at this number of entities)

ChangeLog

1.2

  • Greatly improved documentation
  • Added start and limit optional arguments to sortByIndex to allow for pagination and infinite scrolling.
  • Added setDomElementIdToAppend to allow for infinite scrolling.
  • Added a live link to the demo

1.1

  • Changed string split method from string.split() to using indexOf() and subString() for a huge performance boost.
  • Changed the way innerHTML is used for a huge performance boost.
  • Added the ability to change the number of elements under test.
  • Performance stats per operation are printed to console.
  • Added more names to randomly generate names from.