Saturday, September 10, 2016

How I made text-clipper.js the fastest HTML clipping library

Update: Redditor /u/ugwe43to874nf4 gave another interesting insight in response to this blog. In short, he suggested the final performance improvement might be more due to skipping large blocks in one go, rather than the fact I was doing so using regular expressions. This prompted me to a little bit more investigation, which you can find below...

tl;dr: Regular expressions will pretty much always outperform you, but if you have to evaluate single characters use charCodeAt() rather than charAt().

When I started working on text-clipper a few weeks back, my main focus was on correctness. I wanted to be very sure the library would work correctly no matter what HTML you threw at it, provided it was valid according to the HTML5 spec. Of course there were already some clipping/trimming/truncating libraries for HTML out there, but they all seemed to rely on regular expressions to parse the HTML and well, HTML is just a little more complicated than regular expressions can handle, which meant they all would miss certain edge cases the HTML5 spec said are valid.

But I also had a secondary concern, which is that I wanted text-clipper to be bloody fast. The fastest, if possible. Surely a minimal state machine that evaluates the text to clip only once could be faster than a soup of regular expressions, right? Sure, my state machine is written in JavaScript, while regular expressions are optimized in C, so it would be an interesting testament to the performance of the JIT compiler, but at least on face value it seems my state machine would have to perform less work. So, after my initial implementation, I ran a little benchmark:

text-clipper x 35,338 ops/sec ±4.25% (53 runs sampled)
html-truncate x 95,116 ops/sec ±4.39% (55 runs sampled)
trim-html x 40,879 ops/sec ±2.69% (49 runs sampled)
truncate-html x 1,177 ops/sec ±5.83% (53 runs sampled)
Fastest is html-truncate

So the performance was similar to trim-html, but still 2.5 times slower than html-truncate. At least it was much faster than truncate-html, which uses jQuery internally and involves actual DOM parsing to do the work.

Now, html-truncate uses regular expressions to find the HTML tags relatively efficiently, so it explains its good score, but to be honest I was a little disappointed text-clipper wasn't any faster than trim-html which runs a whole bunch of regular expressions on the entire string and then splits it all into an array which is traversed next. I knew regular expressions were very fast, but are they so fast you can do 3 global searches over the input string and split it into an array and still come out (slightly) ahead against a minimal state machine that evaluates every character once in JavaScript? It appears so...

So yesterday I spent some time trying to optimize text-clipper, and with a little experimentation and some common sense, I realized I had made one big mistake: I used string.charAt(index) to take the characters from the string and evaluated them one by one. Even if inline strings can be used, this will give some overhead and every time I compare that character against another, the JS engine has to assume I'm doing a comparison between two random strings. So I switched the implementation to use string.charCodeAt(index) instead, and I instantly achieved a >75% performance improvement (commit):

text-clipper x 62,848 ops/sec ±3.56% (52 runs sampled)
html-truncate x 88,262 ops/sec ±2.39% (50 runs sampled)
trim-html x 43,259 ops/sec ±2.42% (50 runs sampled)
truncate-html x 1,173 ops/sec ±3.87% (55 runs sampled)
Fastest is html-truncate

Note that different runs of the benchmark unfortunately are not always consistent. I had closed Chrome, but maybe there are still some background processes interfering, so please be aware the fluctuation may be more than benchmark.js reported. When validating my results, I always re-ran the benchmark a few times to make sure I wasn't looking at a random outlier.

Okay, so now trim-html was comfortably left behind, and if I could pull a similar feat, I might be able to beat html-truncate as well. So I went on...

After that I came up with a few smaller optimizations, that basically resolved around doing fewer comparisons in the main loop or making the comparisons cheaper. I won a few percent moving one block of code so that its if-statement didn't have to be evaluated for every character and replacing two range checks with a single bitmasked check (commit). Another ~10% was won by no longer keeping track of good places to break the string (text-clipper prefers to not break in the middle of a word), but doing a little backtrack for that at the end (commit). Finally, I created two specialized inline loops for processing HTML entities (commit) and one for processing HTML tags (commit) which yielded roughly 5% and 10% performance gains, respectively.

text-clipper x 81,248 ops/sec ±3.36% (55 runs sampled)
html-truncate x 91,289 ops/sec ±2.94% (50 runs sampled)
trim-html x 38,015 ops/sec ±0.86% (72 runs sampled)
truncate-html x 1,042 ops/sec ±5.01% (51 runs sampled)
Fastest is html-truncate

At this point text-clipper had almost caught up with truncate-html. But I had another realization. I had been focusing rather heavily on one specific input string that did contain a lot of different HTML tags. This was an intentional decision  in the beginning because it would be more indicative of a worst-case input, but that wouldn't be very typical input. So how were the results if I used an input string with only a few HTML tags?

text-clipper x 191,700 ops/sec ±3.13% (54 runs sampled)
html-truncate x 142,627 ops/sec ±3.87% (52 runs sampled)
trim-html x 55,776 ops/sec ±1.75% (49 runs sampled)
truncate-html x 1,337 ops/sec ±4.92% (49 runs sampled)
Fastest is text-clipper

Okay, great. So text-clipper is already ahead in those cases. But I had one more idea that I wanted to try out. As we learned in the beginning, regular expressions are bloody fast. The other libraries relying on them are having pretty good performance, without having to care too much about performance for the rest. So could we use a regular expression in text-clipper, not for the parsing, but for finding the first interesting character the parser is looking for? So I made one final commit, and the results were impressive...

First with the original, bad-case string:

text-clipper x 89,645 ops/sec ±2.84% (54 runs sampled)
html-truncate x 90,654 ops/sec ±4.57% (49 runs sampled)
trim-html x 36,977 ops/sec ±1.55% (77 runs sampled)
truncate-html x 1,107 ops/sec ±6.15% (47 runs sampled)
Fastest is text-clipper,html-truncate

Okay, so text-clipper and html-truncate are now within margin of error of each other (and multiple runs confirm they are pretty much tied there), but the biggest difference was with a more typical string:

text-clipper x 426,806 ops/sec ±4.33% (48 runs sampled)
html-truncate x 146,281 ops/sec ±3.40% (53 runs sampled)
trim-html x 55,098 ops/sec ±3.05% (50 runs sampled)
truncate-html x 1,503 ops/sec ±3.62% (48 runs sampled)
Fastest is text-clipper

More than twice as fast as the previous commit, and almost triple the performance of html-truncate! I think that's as good as it's going to get for now :) I thought that was the most of it, but once another redditor pointed out I had skipped one important step in my conclusion, I investigated a bit further...

In the previous step I saw a large performance gain, but was it because of the regular expression I was now using, or was it simply because I wasn't concatenating the result string one character after another anymore? So I had another close look, and quickly it became obvious I had still left quite some room for improvement: Why was I even building the result as I went along at all? It became apparent I only need to search for the position where to clip, and then do the clipping if and where necessary and no more. So I first removed all the building of the result string and ran the benchmark again:

Bad-case input:

text-clipper x 106,197 ops/sec ±3.53% (48 runs sampled)
html-truncate x 87,662 ops/sec ±3.14% (49 runs sampled)
trim-html x 43,243 ops/sec ±2.86% (50 runs sampled)
truncate-html x 1,198 ops/sec ±4.66% (50 runs sampled)
Fastest is text-clipper

More typical input:

text-clipper x 589,891 ops/sec ±3.35% (55 runs sampled)
html-truncate x 148,986 ops/sec ±2.32% (49 runs sampled)
trim-html x 51,572 ops/sec ±2.63% (54 runs sampled)
truncate-html x 1,423 ops/sec ±4.05% (51 runs sampled)
Fastest is text-clipper

Another roughly 20-40% improvement depending on the input. Okay, but how does this compare to when we remove the regular expression and iterate manually again?

Bad-case input:

text-clipper x 105,661 ops/sec ±3.36% (55 runs sampled)
html-truncate x 87,098 ops/sec ±3.62% (51 runs sampled)
trim-html x 40,277 ops/sec ±2.77% (53 runs sampled)
truncate-html x 1,161 ops/sec ±4.89% (50 runs sampled)
Fastest is text-clipper

More typical input:

text-clipper x 346,503 ops/sec ±3.69% (53 runs sampled)
html-truncate x 154,289 ops/sec ±2.26% (49 runs sampled)
trim-html x 53,631 ops/sec ±3.19% (55 runs sampled)
truncate-html x 1,402 ops/sec ±4.73% (56 runs sampled)
Fastest is text-clipper

Pretty much no difference for the bad-case input, but the typical case got significantly worse.

But, there's one advantage to not using a regular expression that might be important to some. If the input string is very long, you might want to break early once you discover maxLength characters, but the regular expression I'm using can't do that. By definition, the algorithm scales linearly with the input string, but if you don't use the regular expression, you can cap it to a constant. So how do both variations perform with an input string of 1 million uninteresting characters?

With regular expression:

text-clipper x 575 ops/sec ±2.52% (48 runs sampled)
(html-truncate didn't complete)
trim-html x 60.38 ops/sec ±4.44% (46 runs sampled)
truncate-html x 59.80 ops/sec ±3.64% (46 runs sampled)
Fastest is text-clipper

Without regular expression:

text-clipper x 336,121 ops/sec ±3.42% (53 runs sampled)
(html-truncate didn't complete)
trim-html x 57.67 ops/sec ±3.43% (48 runs sampled)
truncate-html x 60.11 ops/sec ±2.78% (43 runs sampled)
Fastest is text-clipper

As you can see, all the algorithms slow down to quite an extent. Html-truncate, that otherwise did so well, doesn't even complete anymore within 5 minutes or so before I killed it. The happy exception is text-clipper without regular expression which seems hardly affected because it can break early.

Now this does leave me in a bit of a tough spot. Do I sacrifice typical performance for the worst-case or the other way around? For now I've decided to let the regular expression in and have the best average performance. After all, strings with a million characters are very unlikely, and even the occasional newline character would be enough to prevent that worst case from happening. And even if it does occur, at a million characters text-clipper can still handle over 500 such strings in a second, so it just seems the potential for a DOS is really small.

So to sum it up:
  • Using charCodeAt() instead of charAt() provides a very big gain if you're writing a parser.
  • By carefully optimizing how many if-statements you're doing you can shave off tens of percents from a hot loop.
  • Don't underestimate the performance of regular expressions (but be aware of their limitations).
  • And finally: Share your results and learn from others' insights :)

Thursday, August 4, 2016

Selectivity v3 adds React support

From the start, Selectivity has been developed as a jQuery plugin. It used jQuery internally as well as exposed a typical jQuery plugin API. But given that my own use cases involve more and more React, I wanted to bring Selectivity along into a world where using jQuery is no longer a given. The past few months I've gradually rewritten the Selectivity internals so they became independent of jQuery. It was quite a bit of work, with nothing really to show for it...

But today I released Selectivity v3.0.0-beta1 with the official React API! When you download this latest release, you can simply choose to use the jQuery bundle or the React bundle and each comes with its appropriate API and plugins. If you're adventurous, you can even use the VanillaJS bundle that depends on neither library. I have updated the Selectivity homepage to (hopefully) make it clear how to use each API.

Also new (or at least: finally usable) is the NPM release. I have added extensive instructions on how to use the NPM release on the GitHub project page. I have to admit having a triple-API model certainly makes things more complicated in that area. But then again, the alternative would be to create separate projects for each API and each plugin, and I would be stuck with 13 projects to maintain. I guess it would certainly be more in the spirit of NPM, but I hope I struck a good balance here :)

I'd be happy to receive bug reports and suggestions for improvements (not in the least when it comes to the documentation!). Cheers!

Thursday, May 14, 2015

Selectivity.js v1.1.0 improves keyboard support, adds Ruby Gem

Today I'm proud to announce the release of Selectivity.js v1.1.0. Selectivity.js is a library for displaying rich select boxes. It is intended to be lightweight and flexible and has a modular design, a build system for creating custom builds and a proper test suite.

The new version comes with a few notable changes:
  • Shortly after version v1.0.0 was release the project has been officially renamed from Select3 to Selectivity. If you are still using the project under the Select3 name, this will be a breaking change as all symbols have been renamed accordingly. Anyone who jumped in after the name change should not have to deal with any API changes.
  • Keyboard support has been vastly improved. All Selectivity inputs can now be navigated to using the Tab key. Submenus can now be navigated with the keyboard, and submenus can be closed using Backspace. Backspace can also be used to clear a selected input if the allowClear option is enabled. And finally, some annoying page scrolling issues have been fixed when using keyboard navigation to scroll through a longer list of results.
  • Compatibility with web forms has been improved so values selected in a Selectivity.js instance can be submitted back to a server using regular HTML form submission.
  • A Ruby on Rails Gem has been created to facilitate users wanting to use Selectivity.js in their Ruby application.
  • Many bugs have been fixed.
Special thanks go to Konrad Jurkowski without whom this release would've been significantly less impressive. Specifically, he's developed the web forms compatibility and the Ruby on Rails gem for which there is a separate project page: As part of this work he has also set up our Sass support that we now use to generate our stylesheets. And last but not least, he's contributed several bugfixes as well.

Additional thanks go to everyone who has submitted Pull Requests or reported issues on GitHub!

You can install the new version through Bower, Component, the new Ruby Gem or just download the release right here:


Tuesday, March 10, 2015

Selectivity v1.0 released

Update: This post mentioned the release of Select3 v1.0. The project has since been renamed to Selectivity.js and all references in this post have been updated.

After a little over two months of development, I'm proud to announce the first stable release of Selectivity.js. This release follows shortly after we have started using Selectivity in production at Speakap, meaning we believe it is stable enough to expose our users to it :)

Selectivity.js is a library for displaying rich select boxes. It is intended to be lightweight and flexible and has a modular design, a build system for creating custom builds and a proper test suite.

New Features

Some noteworthy features have been added to the library over the past month:

  • Support for submenus, as described in a previous blog post.
  • An AJAX module, for conveniently performing AJAX requests to fetch remote data.
  • An async module, which detects out-of-order responses to requests and discards those that are no longer relevant. This is especially useful in combination with the AJAX module, but can also be used independently.
  • Selectivity.js now automatically fetches more results when the user scrolls to the "Load more" link a dropdown.
  • Dropdowns now detect whether there is enough room to be displayed at the bottom of the screen and expand upwards if necessary.

What's Next?

Now that Selectivity has been released with its first stable release, it is expected the development of additional features will settle down. Maintenance will continue in the form of bug fixes. Some minor features and accessibility enhancements are to be expected, but nothing that will break the API short-term.

Instead, I intend to shift focus to extending the ecosystem around Selectivity.js. For example, I expect to shortly start working on a React.js Component for working with Selectivity. Also some specific customizations will be released in the form of plugins or add-on modules. Such work will be performed in separate repositories and not in the Selectivity.js repository however.

Questions and Suggestions

If you have any questions about working with Selectivity.js, feel free to post them on Stack Overflow using the "Selectivity" tag. Features requests and other suggestions are welcome in the GitHub issue tracker.


Tuesday, February 10, 2015

Creating submenus with Selectivity.js

Update: This post originally mentioned Select3. The project has since been renamed to Selectivity.js and all references in this post have been updated.

tl;dr: Selectivity.js now supports submenus.

Do you know the feeling when you've built some awesome code that's super-flexible and extensible and everything, opening endless possibilities and unimaginable scenarios, only to realize in hindsight that all this over-engineering was wasted effort and all this true potential of the code never materialized because it simply wasn't what you actually needed? It's a very common trap that I think pretty much every software engineer has fallen into at least once in his career... Which is why it's fun to write about when the opposite happens.

Recently I took it upon myself to create a new library called Selectivity. It was originally called Select3 because it's actually a reimplementation of the popular Select2 library. The main reason I decided to go my own way and make a from-scratch reimplementation was because I needed more flexibility and had to facilitate some use cases involving highly customized dropdowns that Select2 just wouldn't cooperate on. So I made it flexible and modular and everything. Then I integrated it into our product and implemented our use cases and all seemed said and done.

Until last week some requirements fell upon my plate and my colleague jokingly said, "that's a nice job for your Selectivity". I scratched my beard a bit, gave it a thought, then gave it a shot. As obvious as it is now, this was actually a use-case I hadn't anticipated in advance. All that was needed was the ability to open submenus from the main dropdown and the submenus should contain a search input to be able to search among the results as shown in this example. And all that was needed to implement it was another Selectivity module and some minor tweaks.

Now, for those using Selectivity.js, let me explain how you can create your own select input with submenus. All the results from which the user can select an item are specified as objects with id and text properties. These are either set on the Selectivity instance using the items option (to set a static array of result items) or through the query function (to fetch a dynamic set of result items based on search terms). Now, if you want to attach a submenu to a result item, all you need to do is set a submenu property on the item. This submenu property should be another object and in it you can again specifiy an items array or a query function like you did for the main Selectivity instance. Optionally, you can also specify the showSearchInput option (whether or not the submenu should contain its own search input) and/or the positionDropdown function (to customize the positioning of the submenu's dropdown; this method has the same signature as the positionDropdown function you can specify for the Selectivity instance).

Example code from the example linked above:

$('#example-4').selectivity({ allowClear: true, items: [{ id: '+00:00', text: 'Western European Time Zone', submenu: { items: [ { id: 4, text: 'Barcelona' } /*, ...*/ ], showSearchInput: true } } /*, ...*/], placeholder: 'No city selected' });

That's all!

Saturday, June 7, 2014

How to speed up resource loading when using Require.js

If you're building a single-page AJAX application using Require.js, odds are your boot sequence for loading the application on production looks something like this:
  • First, your index.html gets loaded.
  • At the head of your index.html you link CSS resources which get loaded.
  • There's a script tag referencing Require.js, then some inline script for configuring it and finally you kick it off by specifying which modules should be loaded.
This is pretty much what booting our application at Speakap looks like and it results in the following graph for loading resources:

Here you see the index.html getting loaded at the top from The CSS gets loaded next and require.js is fetched in parallel because both are referenced straight from the index.html (please note all static files are padded with an MD5 hash for versioning in the graph above). The file nr-411.min.js can be ignored in this discussion as it's used for performance analysis and error reporting by New Relic, but it's not actually a module of our own application. Then finally we see our two modules - app.js and libs.js - that are getting loaded by Require.js.

This is not everything that is happening during boot, but it's the main part and with the resources you saw above, the application is able to render its skeleton and from a user's perspective, the application has loaded and is visible, though data fetching has still to occur. This all happens in under a second for a typical DSL connection (the graph above is measured from my home connection). It's certainly not bad, but it is up for improvement.

The most obvious way to improve the boot time is to improve the parallelization of the loading of resources. Unfortunately, in the current setup the inline script which configures Require.js and tells it which modules to load is blocked by both the loading of the CSS (see here if you want to know why) and the loading of Require.js itself. Because of this, app.js and libs.js cannot be loaded by Require.js until after these two files have been loaded. Fortunately, the workaround is easy; who says these two modules have to be loaded by Require.js? We already know upfront these two modules will be loaded, so why not just reference them straight from the HTML with a good old script tag, preferably with an async attribute.

This is exactly what I did, and the result is that app.js and libs.js are now fetched in parallel with the CSS and require.js. In a development setup (no latency) this saved me about 80ms, or about 15%, in total page load time. In the common case where latency is an issue the savings are even larger.

Before all is said and done however, there is one important caveat that will ruin the plan if you're using a vanilla Require.js library. Require.js expects to be in full control of the loaded libraries and will happily ignore the fact the modules it is instructed to load are already being loaded from a plain script tag. The result being we end up with two script tags for the same module, and depending on the order in which they are actually loaded, global state may be overwritten causing inconsistent JavaScript errors. The fix to this problem is a rather simple check to make Require.js aware of the already existing script tags, and re-use those when applicable. In hopes this might be useful to others, I have created a Pull Request for Require.js, which adds this fix. I hope it gets merged into Require.js proper, but until then, feel free to try it out!

Monday, February 3, 2014

C.I. Joe 0.0.3 "United We Stand" released

After a month of intense work and a big redesign — both mechanically and aesthetically — the time has come to release C.I. Joe 0.0.3 "United We Stand".

New in this release is a great C.I. Joe themed redesign created by my colleague Dennis de Jong (any possible remaining styling issues are due to my lack of CSS skills, not Dennis' design):

In addition, the concept of campaigns has been introduced as seen above. Campaigns provide an easy-to-use mechanism for scheduling multiple missions at once, to be executed one after another or in parallel.

Finally, I've made a beginning writing the in-application Help manual.

As with previous releases, you should be aware this is an alpha release and far from feature complete. But for those wanting to try it out, you can download the new release here:

Join or follow the contribute on GitHub: