setInterval with 0ms delays within Web Workers

The 4ms minimum

Due to browser restrictions, you typically can’t have a setInterval call where the delay is set to 0, from MDN:

In modern browsers, setTimeout()/setInterval() calls are throttled to a minimum of once every 4 ms when successive calls are triggered due to callback nesting (where the nesting level is at least a certain depth), or after certain number of successive intervals.

I confirmed this by testing with the following code in Chrome and Firefox windows:

setInterval(() => { console.log(`now is ${Date.now()}`); }, 0);

In Firefox 72:

Firefox window setInterval with 0ms delay

In Chrome 79:

Chrome window setInterval with 0ms delay

The delay isn’t exact, but you can see that it typically comes out to around 4ms, as expected. However, things are a little different with web workers.

The delay with web workers

To see the timing behavior within a web worker, I used the following code for the worker:

const printNow = function() { console.log(`now is ${Date.now()}`); }; setInterval(printNow, 0); onmessage = function(_req) { };

… and created it via const worker = new Worker('worker.js');.

In Chrome, there’s no surprises, the behavior in the worker was similar to what it was in the window:

Chrome window setInterval with 0ms delay

Things get interesting in Firefox:

Firefox window setInterval with 0ms delay

Firefox starts grouping the log messages (the blue bubbles), as we get multiple calls to the function within the same millisecond. Firefox’s UI becomes unresponsive (which is weird and I didn’t expect as this is on an i7-4790K with 8 logical processors and there’s little interaction between the worker and the parent window), and there’s a very noticeable spike in CPU usage.

Takeaway

setInterval() needs a delay and you shouldn’t depend on the browser to set something reasonable. It would be nice if setInterval(.., 0) would tell the browser to execute as fast as reasonably possible, adjusting for UI responsiveness, power consumption, etc. but that’s clearly not happening here and as such it’s dangerous to have a call like this which may render the user’s browser unresponsive.


Prioritizing Web Worker Requests

Web workers handle incoming request messages via a function declared on the onmessage property of the worker. A, perhaps not so obvious, behavior here is that incoming requests are queued. If you’re doing something intensive within the worker (or the CPU is taxed b/c of other processes) the queuing behavior becomes more obvious, as you need to wait longer for a response from the worker due to the fact that previous requests need to be picked up and handled first. Here’s a simple worker that does some heavy lifting (at least for Chrome 79 on an i7-4790K):

const highLoadWork = function() { let x = 1000; for(let i=0; i<99999999; i++) { if(i % 2 === 0) { x += 1000; } else { x = Math.sqrt(x); } } return `hello, x=${x}`; }; onmessage = function(_req) { const requestNum = _req.data.requestNum; const workResult = highLoadWork(); postMessage( { "response": `responding to request ${requestNum}` } ); };

… and here’s what happens after making 12 requests to it in a loop:

I can’t say that this is a bad thing, this is generally sensible and what you’d expect to happen. That said, there are workloads where you may want to prioritize things differently. GraphPaper was one such case for me. Workers are handling things based on user interactions, the last request represents the current state of the world and is typically the only request that matters (any others from before can be thrown away). Unfortunately, this is no mechanism to interact with or re-prioritize messages in this underlying queue. However, you can offload the requests to a queue that the worker manages internally by itself. The onmessage() function simply puts the request data in a queue and we can use setInterval() to continuously call a function that pulls and processes requests from this queue. Here’s what the modified worker code looks like, where the latest request is prioritized (and previous ones are thrown away):

const highLoadWork = function() { let x = 1000; for(let i=0; i<99999999; i++) { if(i % 2 === 0) { x += 1000; } else { x = Math.sqrt(x); } } return `hello, x=${x}`; }; const requestQueue = []; const processRequestQueue = function() { if(requestQueue.length === 0) { return; } const lastRequest = requestQueue.pop(); requestQueue.length = 0; const requestNum = lastRequest.requestNum; const workResult = highLoadWork(); postMessage( { "response": `responding to request ${requestNum}` } ); }; setInterval(processRequestQueue, 4); onmessage = function(_req) { requestQueue.push(_req.data); };

… and here’s what happens after making 12 requests to it in a loop:

(sometimes, there are also cases where only request 12 was processed)

So this works pretty well, but there there are a few things to be aware of. The time it takes to post a message to the worker, is somewhere between 0ms – 1ms, plus the cost of copying any data that needs to be transferred to the worker. The setInterval() minimum is not really 0ms; the browser sets a reasonable minimum which you can probably expect to be between 4ms – 10ms, and this is in addition to the cost of posting the message to the worker (The code was updated to explicitly specify a 4ms delay, setInterval with a 0ms delay isn’t a good idea). What this means in practice is that there is additional latency before we begin processing a request, but compared to a scenario where we have to factor in waiting on all prior requests to finish processing (which is the point of doing this to begin with), I expect this method to win out in performance.

Finally, here’s a look at a GraphPaper stress test and how prioritizing the last request to the connector routing worker (which is responsible for generating the path between the 2 nodes) allows for a faster/less-laggy update:

No prioritization

Prioritize last request, eliminate prior


Encapsulating Web Workers

Constructing Web Workers

There’s generally 2 ways to construct a Web Worker…

Passing a URL to the Javascript file:

const myWorker = new Worker('worker.js');

Or, creating a URL with the Javascript code (as a string). This is done by creating a Blob from the string and passing the Blob to URL.createObjectURL:

const myWorker = new Worker( URL.createObjectURL(new Blob([...], {type: 'application/javascript'})) );

In Practice

With GraphPaper, I’ve used the former approach for the longest while, depending on the caller to construct and inject the worker into GraphPaper.Canvas:

const canvas = new GraphPaper.Canvas( document.getElementById('paper'), // div to use window, // parent window new Worker('../dist/connector-routing-worker.min.js') // required worker for connector routing );

This technically works but, in practice, there’s 2 issues here:

  • There’s usually a few hoops to go through for the caller to actually get the worker Javascript file in a location that is accessible by the web server. This could mean manually moving the file, additional configuration, additional tooling, etc.
  • GraphPaper.Canvas is responsible for dealing with whether a worker is used or not, which worker, how many workers are used, etc. These aren’t concerns that should bubble up to the caller. You could make a case that caller should have the flexibility to swap in a worker of their choice (a strategy pattern), that’s a fair point, but I’d argue that the strategy here is what the worker is executing not the worker itself and I haven’t figured out a good interface for what that looks like.

So, I worked to figure out how to construct the worker within GraphPaper.Canvas using URL.createObjectURL(), and this is where things got trickier. The GraphPaper codebase is ES6 and uses ES6 modules, I use rollup with babel to produce distribution files the primary ones being minified IIFE bundles (IIFE because browser support for ES6 modules is still very much lacking). One of these bundles is the code for the worker (dist/connector-routing-worker.js), which I’d need to:

  • Encapsulate it into a string that can be referenced within the source
  • Create a Blob from the string
  • Create a URL from the Blob using URL.createObjectURL()
  • Pass the URL to the Worker constructor, new Worker(url)

The latter steps are straightforward function calls, but the first is not clear cut.

Repackaging with Rollup

After producing the “distribution” code for the worker, what I needed was to encapsulate it into a string like this (the “worker-string-wrap”):

const workerStringWrap = ` const ConnectorRoutingWorkerJsString = \` ${workerCode} \`; export { ConnectorRoutingWorkerJsString }` ;

Writing that out to a file, I could then easily import it as just another ES6 module (and use the string to create a URL for the worker), then build and produce the distribution file for GraphPaper.

I first tried doing this with a nodejs script, but creating a rollup plugin proved a more elegant solution. Rollup plugins are aren’t too difficult to create but I did find the documentation a bit convoluted. Simply, rollup will execute certain functions (hooks) at appropriate points during the build process. The hook needed in this scenario is writeBundle, which can be used to get the code of the produced bundle and do something with it (in this case, write it out to a file).

// rollup-plugin-stringify-worker.js const fs = require('fs'); const stringifyWorkerPlugin = function (options) { return { name: 'stringifyWorkerPlugin', writeBundle(bundle) { console.log(`Creating stringified worker...`); // Note: options.srcBundleName and options.dest are expected args from the rollup config const workerCode = bundle[options.srcBundleName].code; const workerStringWrap = `const ConnectorRoutingWorkerJsString = \`${workerCode}\`; export { ConnectorRoutingWorkerJsString }`; fs.writeFile(options.dest, workerStringWrap, function(err) { // ... }); } }; }; export default stringifyWorkerPlugin;

The plugin is setup within a rollup config file:

import stringifyWorker from './build/rollup-plugin-stringify-worker'; // ... { input: 'src/Workers/ConnectorRoutingWorker.js', output: { format: 'iife', file: 'dist/workers/connector-routing-worker.min.js', name: 'ConnectorRoutingWorker', sourcemap: false, }, plugins: [ babel(babelConfig), stringifyWorker( { "srcBundleName": "connector-routing-worker.min.js", "dest": "src/Workers/ConnectorRoutingWorker.string.js" } ) ], }, // ...

Note that addtional config blocks for components that use ConnectorRoutingWorker.string.js (e.g. the GraphPaper distribution files), need to be placed after the block shown above.

The overall process looks like this:

packaging process

Creating the Worker

The worker can now be created within the codebase as follows:

import {ConnectorRoutingWorkerJsString} from './Workers/ConnectorRoutingWorker.string'; // ... const workerUrl = URL.createObjectURL(new Blob([ ConnectorRoutingWorkerJsString ])); const connectorRoutingWorker = new Worker(workerUrl); // ...

The Future

Looking ahead, I don’t really see a good solution here. Better support for ES6 modules in the browser would be a step in the right direction, but what is really needed is a way to declare a web worker as a module and the ability to import and construct a Worker with that module.


Publishing packages with npm and CircleCI

A common workflow

In recent years, I’ve pushed more and more for common, automated, deployment processes. In practice, this has usually meant:

  • Code is managed with Git, and tags are used for releases
  • Tags (and hence releases) are created via GitHub
  • Creating a tag executes everything in the CI pipeline + a few more tasks for the deployments

The result is that all deployments go through the same process (no deploy scripts run on personal machines), in the same environment (the CI container). It eliminates discrepancies in how things are deployed, avoids workflow differences and failures due to environment variance, and flattens the learning curve (developers only need to learn about Git tags).

Here I’ll present how I’ve been approaching this when it comes to publishing npm packages, with deployment tasks handled via CircleCI. The flow will look something like this:

Setting up CircleCI

First things first, we need the CircleCI pipeline to trigger when a tag is created. At the bottom of your circle.yml file, add filter for “deployment.”

version: 2 jobs: build: docker: - image: circleci/node:10.0.0 working_directory: ~/repo steps: - checkout # # Other stuff (run npm install, execute tests, etc.) # ... deployment: trigger_tag: tag: /.*/

Authenticating with the npm registry

Create an npm token and expose it as an environment variable in CircleCI (in this case, I’ve named it NPM_TOKEN). Then, add a step to authenticate with the npm registry in your circle.yml:

version: 2 jobs: build: docker: - image: circleci/node:10.0.0 working_directory: ~/repo steps: - checkout # # Other stuff (run npm install, execute tests, etc.) # ... - run: name: Authenticate with registry command: echo "//registry.npmjs.org/:_authToken=$NPM_TOKEN" > ~/repo/.npmrc deployment: trigger_tag: tag: /.*/

Versioning

Things get a little weird when it comes to versioning. npm expects a version declared in the project’s package.json file. However, this goes against managing releases (and thus versioning) with Git tags. I see two potential solutions here:

  • Manage versions with both Git and npm, with the npm package version mirroring the tag. This would mean updating the version in package.json first, then creating the Git tag.
  • Only update/set the version in package.json within the pipeline, and set it to the version indicated by the Git tag.

I like the latter solution, as forgetting to update the version number in package.json is an annoyance that pops up frequently for me. Also, dealing with version numbers in 2 places, across 2 systems, is an unnecessary bit of complexity and cognitive load. There is one oddity however, you still need a version number in package.json when developing and using the npm tool, as npm requires it and will complain if it’s not there or in an invalid format. I tend to set it to “0.0.0”, indicating a development version; e.g.

{ "name": "paper-plane", "version": "0.0.0", // ... }

In the pipeline, we’ll reference the CIRCLE_TAG environment variable to get the Git tag and use to correctly set the version in package.json. Based on semantic versioning conventions, we expect the tag to have the format “vX.Y.Z”, so we’ll need to strip away the “v” and then we’ll use “X.Y.Z” for the version in package.json. We can use npm version to set the version number:

npm --no-git-tag-version version ${CIRCLE_TAG:1}

Note the –no-git-tag-version flag. This is necessary as the default behavior of npm version is to commit the tag to the git repo.

Publishing

Publishing is simply done via npm publish. Pulling together the CIRCLE_TAG check, applying the version, and publishing into a deploy step, we get something like this:

version: 2 jobs: build: docker: - image: circleci/node:10.0.0 working_directory: ~/repo steps: - checkout # # Other stuff (run npm install, execute tests, etc.) # ... - run: name: Authenticate with registry command: echo "//registry.npmjs.org/:_authToken=$NPM_TOKEN" > ~/repo/.npmrc - deploy: name: Updating version num and publishing command: | if [[ "${CIRCLE_TAG}" =~ v[0-9]+(\.[0-9]+)* ]]; then npm --no-git-tag-version version ${CIRCLE_TAG:1} npm publish fi deployment: trigger_tag: tag: /.*/

… and we’re done 🚀!

For further reference, this circle.yml uses the steps presented above.


Rendering HTML to images with SVG foreignObject

Motivation

For applications that allow users to create visual content, being able to generate images of their work can be important in a number of scenarios: preview/opengraph images, allowing users to display content elsewhere, etc. This popped up as a need for ScratchGraph and led me to research a few possible solutions. Using the SVG <foreignObject> element was one of the more interesting solutions I came across, as all rendering and image creation is done client-side.

<foreignObject> to Image

<foreignObject> is a somewhat strange element. Essentially, it allows you to load and render arbitrary HTML content within SVG. This in and of itself isn’t helpful for generating an image, but we can take advantage of two other aspects of modern browsers to make this a reality:

  • SVG markup can be dynamically loaded into an Image by transforming the markup into a data URL
  • Data URL length limits are no longer a concern. We no longer have the kilobyte-scale limits we were dealing with a few years ago

Sketching it out, the process looks something like this (contentHtml is a string with the HTML content we want to render):

The code for this is pretty straightforward:

// build SVG string
const svg = `
<svg xmlns='http://www.w3.org/2000/svg' width='
${width}' height='${height}'>
<foreignObject x='0' y='0' width='
${width}' height='${height}'>
${contentHtml}
</foreignObject>
</svg>`
;

// convert SVG to data-uri
const dataUri = `data:image/svg+xml;base64,${window.btoa(svg)}`;

Here I’m assuming contentHtml is valid and can be trusted. If that’s not the case, you’ll likely need some pre-processing steps before sticking it into a string like this.

The code above works, to a degree; there’s a few key limitations to be aware of:

  • Cross-origin images served without CORS headers won’t load within <foreignObject>
  • Styles declared via stylesheets do not pass through to the contents of <foreignObject>
  • External resources (images, fonts, etc.) won’t be in the generated Image, as the browser doesn’t wait for these resources to be loaded before rendering out the image

The cross-origin issue may be annoying and unexpected (as the browser does load these images), but it’s a valid security measure and CORS provides the mechanism around it.

Handling stylesheets and external resources are more important concerns, and addressing them allows for a much more robust process.

Handling stylesheets

This isn’t anything too fancy, here are the steps involved:

  • Copy all the style rules, from all the stylesheets, in the parent document
  • Wrap all those rules in a <style> tag
  • Prepend that string to the contentHtml string

The code for this precursor step looks something like this:

const styleSheets = document.styleSheets;
let cssStyles = "";
let urlsFoundInCss = [];

for (let i=0; i<styleSheets.length; i++) {
for(let j=0; j<styleSheets[i].cssRules.length; j++) {
const cssRuleStr = styleSheets[i].cssRules[j].cssText;
cssStyles += cssRuleStr;
}
}

const styleElem = document.createElement("style");
styleElem.innerHTML = cssStyles;
const styleElemString = new XMLSerializer().serializeToString(styleElem);

...

contentHtml = styleElemString + contentHtml;

...

Handling external resources

My solution here is somewhat curd, but it’s functional.

  • Find url values in the CSS code or src attribute values in the HTML code
  • Make XHR requests to get these resources
  • Encode the resources as Base64 and construct data URLs
  • Replace the original URLs (in the CSS url or HTML src) with the new base64 data URLs

The following shows how this is done for the HTML markup (the process is only slightly different for CSS).

const escapeRegExp = function(string) {
return string.replace(/[.*+?^${}()|[\]\\]/g, '\\$&'); // $& means the whole matched string
};

let urlsFoundInHtml = getImageUrlsFromFromHtml(contentHtml);
const fetchedResources = await getMultipleResourcesAsBase64(urlsFoundInHtml);
for(let i=0; i<fetchedResources.length; i++) {
const r = fetchedResources[i];
contentHtml = contentHtml.replace(
new RegExp(escapeRegExp(r.resourceUrl),"g"), r.resourceBase64);
}

The getImageUrlsFromFromHtml() and parseValue() methods that extract the value of src attributes from elements:

/**
*
*
@param {String} str
*
@param {Number} startIndex
*
@param {String} prefixToken
*
@param {String[]} suffixTokens
*
*
@returns {String|null}
*/
const parseValue = function(str, startIndex, prefixToken, suffixTokens) {
const idx = str.indexOf(prefixToken, startIndex);
if(idx === -1) {
return null;
}

let val = '';
for(let i=idx+prefixToken.length; i<str.length; i++) {
if(suffixTokens.indexOf(str[i]) !== -1) {
break;
}

val += str[i];
}

return {
"foundAtIndex": idx,
"value": val
}
};

/**
*
*
@param {String} str
*
@returns {String}
*/
const removeQuotes = function(str) {
return str.replace(/["']/g, "");
};

/**
*
*
@param {String} html
*
@returns {String[]}
*/
const getImageUrlsFromFromHtml = function(html) {
const urlsFound = [];
let searchStartIndex = 0;

while(true) {
const url = parseValue(html, searchStartIndex, 'src=', [' ', '>', '\t']);
if(url === null) {
break;
}

searchStartIndex = url.foundAtIndex + url.value.length;
urlsFound.push(removeQuotes(url.value));
}

return urlsFound;
};

The getMultipleResourcesAsBase64() and getResourceAsBase64() methods responsible for fetching resources:

/**
*
*
@param {String} url
*
@returns {Promise}
*/
const getResourceAsBase64 = function(url) {
return new Promise(function(resolve, reject) {
const xhr = new XMLHttpRequest();
xhr.open(
"GET", url);
xhr.responseType =
'blob';

xhr.onreadystatechange =
async function() {
if(xhr.readyState === 4 && xhr.status === 200) {
const resBase64 = await binaryStringToBase64(xhr.response);
resolve(
{
"resourceUrl": url,
"resourceBase64": resBase64
}
);
}
};

xhr.send(
null);
});
};

/**
*
*
@param {String[]} urls
*
@returns {Promise}
*/
const getMultipleResourcesAsBase64 = function(urls) {
const promises = [];
for(let i=0; i<urls.length; i++) {
promises.push( getResourceAsBase64(urls[i]) );
}
return Promise.all(promises);
};

More code

The code for this experiment is up on Github. Most functionality is encapsulated with the ForeignHtmlRenderer method, which contains the code shown in this post.

Other Approaches

  • Similar (same?) approach with dom-to-image
    This library also uses the <foreignObject> element and an approach similar to what I described in this post. I played around with it briefly and remember running to a few issues, but I didn’t keep the test code around and don’t remember what the errors were.
  • Server-side/headless rendering with puppeteer
    This seems to be the defacto solution and, honestly, it’s a pretty good solution. It’s not too difficult to get it up and running as a service, though there will be an infrastructure cost. Also, I’d be willing to bet this is what services like URL2PNG use on their backend.
  • Client-side rendering with html2canvas
    This is a really cool project that will actually parse the DOM tree + CSS and render the page (it’s a rendering engine done in client-side javascript). Unfortunately, only a subset of CSS is supported and SVG is not supported.


Performance visibility with HTTP Server-Timing

Visibility into the performance of backend components can be invaluable when it comes to spotting and understanding service degradation, debugging failures, and knowing if and where optimization is needed. There’s a host of collection agents, aggregators, and visualization tools to handle metrics, but just breaking down and looking at what happens during an HTTP request can offer a lot of insight into how components are performing. This is why I’m pretty excited about the the HTTP Server-Timing header, it works well as a lightweight mechanism to surface performance metrics, especially now that it’s read and graphed by Chrome Devtools (and, perhaps sometime soon, by Firefox Devtools as well).

An HTTP response with the Server-Timing header

The following code snippet shows an Illuminate/Http/Response from a controller that PUTs an image into an Amazon S3 bucket.

return response()
    ->json(
        [],
        StatusCode::STATUS_OK,
        [
            'Server-Timing' => 's3-io;desc="Image upload to S3";dur=' . calculateTimeToPut(),
        ]
    );

Let’s assume the calculateTimeToPut() function returns 5500 (i.e. 5500 milliseconds to PUT the image onto S3), and the response header looks something like this:

HTTP Server-Timing header parts

Each metric is a group composed of 3 pieces, with each piece delimited by a semicolon:

  • Metric Name (required)
  • Metric Description
  • Metric Value

Multiple metrics can be surfaced by separating each group with a comma.

return response()
    ->json(
        [],
        StatusCode::STATUS_OK,
        [
            'Server-Timing' => 
                's3-io;desc="Image upload to S3";dur=' . calculateTimeToPut() . 
                ',' . 
                'db-io;desc="DB update of entity";dur=' . calculateTimeToUpdate()
        ]
    );

(The above code is a bit simplistic, you’d likely want to better way to store and group metrics, then do a final transformation to construct the Server-Timing string when it’s time to send the HTTP response)

Surfacing in DevTools

Surfacing metrics in an HTTP response is not something terribly complex and I’m sure most could devise other ways to do it, but one reason Server-Timing is a bit more attractive vs a custom solution is the out-of-the-box support within Chrome DevTools.

HTTP Server-Timing in Chrome DevTools

Firefox Devtools will likely follow suit (hopefully?) in the near future.

The PerformanceServerTiming interface

Server-Timing metrics can also be surfaced via the PerformanceServerTiming interface, from MDN:

In addition to having Server-Timing header metrics appear in the developer tools of the browser, the PerformanceServerTiming interface enables tools to automatically collect and process metrics from JavaScript.

This opens up some interesting possibilities as it enables collecting metrics via a frontend script (as is already done for a lot of product metrics via services like Google Analytics), rather than a backend collector mechanism. While not ground-breaking, the standardization around PerformanceServerTiming may allow for greater adoption and acceptance of this collection pattern.


Using feColorMatrix to dynamically recolor icons (part 2, two-color icons)

Previously, I looked at how to use feColorMatrix to dynamically change the color of single-color icons. In this post, we’ll look at using feColorMatrix, feBlend, and feComposite to implement an algorithm that allow for dynamically changing the the colors of an icon with 2 colors.

The Algorithm

With a single color, we could think of the process as being a single step: applying the color transformation matrix with the desired R, G, B values. For two colors, there are multiple steps and matrices involved, so it’s worth having a high-level overview and conceptual understanding of the algorithm before delving into the details.

  • The input icon will have 2 color, black and white; black areas will be changed to colorA and white areas will be changed to colorB
  • Add colorA to the source image (black areas will take on the new color, white areas will remain white), the result is imageA
  • Invert the source image, then add colorB to it (black areas will become white and remain white, white areas will become black and take on the new color), the result is imageB
  • Combine imageA and imageB, such that the alpha component from the source image is preserved, output the result
Dynamically recolor two-color icon

Note that from the above, we see the key operations that are needed:

  • Add
  • Invert
  • Combine

Another look at the color transformation matrix for applying a single-color

Note that the transformation matrix used previously for the single-color case, only preserves the alpha component from the input. The R, G, and B components are thrown away:

[[0, 0, 0, 0, R], [0, 0, 0, 0, G], [0, 0, 0, 0, B], [0, 0, 0, 1, 0]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(R), (G), (B), (A_(src))]

It doesn’t matter what color the input pixel is, applying the transformation matrix will result in those Rsrc Gsrc Bsrc input values being multiplied by zero, before the new/output R, G, B values are added in.

While this is fine for the single-color case, for the two-color algorithm to work, the distinction between the black areas and the white areas need to be kept intact, so we have to work with the Rsrc Gsrc Bsrc values from the input vector and preserve the distinction.

Making Rsrc Gsrc Bsrc part of the transformation

Modifying the transformation matrix to allow Rsrc Gsrc Bsrc to be part of the calculations requires the first 3 diagonal elements of the matrix to be non-zero.

The simplest case of this is the identity matrix:

[[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 0]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(R_(src)), (G_(src)), (B_(src)), (A_(src))]

Let’s look at a few matrices that define transformations needed for the algorithm.

The add colorK matrix:

[[1, 0, 0, 0, R_(k)], [0, 1, 0, 0, G_(k)], [0, 0, 1, 0, B_(k)], [0, 0, 0, 1, 0]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(R_(src) + R_(k)), (G_(src) + G_(k)), (B_(src) + B_(k)), (A_(src))]

The invert matrix:

[[-1, 0, 0, 0, 1], [0, -1, 0, 0, 1], [0, 0, -1, 0, 1], [0, 0, 0, 1, 0]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(-R_(src) + 1), (-G_(src) + 1), (-B_(src) + 1), (A_(src))]

The above can be combined into a single transformation matrix, the invert & add colorK matrix:

[[-1, 0, 0, 0, 1 + R_(k)], [0, -1, 0, 0, 1 + G_(k)], [0, 0, -1, 0, 1 + B_(k)], [0, 0, 0, 1, 0]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(-R_(src) + 1 + R_(k)), (-G_(src) + 1 + G_(k)), (-B_(src) + 1 + B_(k)), (A_(src))]

Putting aside and referencing intermediate results

Note that the algorithm requires us to create 2 independent images (imageA and imageB) and then subsequently combine them.

This can be accomplished by utilizing the result attribute available on SVG filter primitive elements. By specifying a result identifier we are able to apply a transformation and put aside the resultant image.

Combining the intermediate results

Combining intermediate results/images can’t be done with feColorMatrix, it’s simply not an operation that can be constructed as a transformation. To handle this, SVG provides the feBlend element with a number of predefined operations available via the mode attribute. Based on the color transformations done to create imageA and imageB (mainly that the areas that are not of concern, the background, are set to white [1,1,1]), the multiply operation will work to combine the images (not perfectly, there’s one big problem with the alpha channel, but we’ll deal with that in a bit).

image multiply
<feBlend 
    color-interpolation-filters="linearRGB"
    in="imageA" 
    in2="imageB" 
    mode="multiply" 
    result="output" />        

The alpha channel problem

While feBlend seem to accomplish what’s needed, for anything other than a white background you’ll notice a white-ist outline around elements in the image, as you can see below.

alpha channel problems with feBlend

The problem is that for what we’re trying to accomplish we just want to simply preserve the alpha channel, not blend it in any way. However, all feBlend operations will perform a blend of the alpha channel. From the SVG spec:

image multiply

So there’s no way we can really work with feBlend to get a solution for the alpha channel, but we do have an idea of what the solution is: copy the alpha channel from the source image.

Fixing the alpha channel

Fixing the alpha channel will involve 2 steps:

  • For the image outputted by feBlend, get the alpha value to be 1 for every pixel
    (the reason this step will become apparent once we look at how feComposite has to be used)
  • Use feComposite to construct an image with the alpha values from the source image and the R,G,B values from the image outputted by feBlend

The first step is simple. We just need a slight modification to the 2 color transformation matrices used, such that one or both set the alpha channel to 1 for every pixel (note from the alpha blending equation, this will effectively set the alpha value to 1 for every pixel in the output). The modified matrices are shown below and it’s a good point to start showing some code.

The full-alpha add colorK matrix:

[[1, 0, 0, 0, R_(k)], [0, 1, 0, 0, G_(k)], [0, 0, 1, 0, B_(k)], [0, 0, 0, 0, 1]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(R_(src) + R_(k)), (G_(src) + G_(k)), (B_(src) + B_(k)), (1) ]

<feColorMatrix in="SourceGraphic" type="matrix" result="imageA"
    values="1 0 0 0 0
            0 1 0 0 0.68235294117
            0 0 1 0 0.93725490196
            0 0 0 0 1" /> 

The full-alpha invert & add colorK matrix:

[[-1, 0, 0, 0, 1 + R_(k)], [0, -1, 0, 0, 1 + G_(k)], [0, 0, -1, 0, 1 + B_(k)], [0, 0, 0, 0, 1]][(R_(src)), (G_(src)), (B_(src)), (A_(src))] = [(-R_(src) + 1 + R_(k)), (-G_(src) + 1 + G_(k)), (-B_(src) + 1 + B_(k)), (1)]

<feColorMatrix in="SourceGraphic" type="matrix" result="imageA"
    values="-1 0 0 0 1.0784313725
            0 -1 0 0 1.7058823529
            0 0 -1 0 1.2431372549
            0 0 0 0 1" />

For the next and final step, we need to take a look at feComposite.

The feComposite filter primitive allows for more fine-grained operations on pixels using the supported “arithmetic” operation:

feComposite arithmetic operation

As this operation is done on every channel, including the alpha channel, we have way to control what happens to the alpha pixels in a composition of 2 images.

We’re going to make use of this by:

  • Using an feColorMatrix, where the input in the source image, and transforming such that R,G,B is white [1,1,1] and the alpha remains unchanged
  • Using feComposite to do a simple arithmetic multiply (k1=1, k2=0, k3=0, k4=0), between the image constructed above (where R,G,B is [1,1,1] and alpha is the alpha from the source image) and the output from feBlend (where the R,G,B = the values we want for the output and alpha = 1)

Effectively, the source alpha is multiplied by 1 (as the image produced from the feBlend operation has the alpha set to 1 for all pixels) and the R,G,B values from the feBlend output are multiplied by 1 (as the constructed image, in the first step above, sets R,G,B to 1 for every pixel).

<!-- Get and use alpha from source image -->
<feColorMatrix in="SourceGraphic" type="matrix" result="whiteAlpha"
    values="0 0 0 0 1
            0 0 0 0 1
            0 0 0 0 1
            0 0 0 1 0" />     

<feComposite in="whiteAlpha" in2="outputFullAlpha" operator="arithmetic" k1="1" k2="0" k3="0" k4="0" />

Pulling everything together

We now have all the pieces for the filter and here’s what the code looks like:

<svg style="width:0; height:0; margin:0; padding:0; border:none;">
    <filter color-interpolation-filters="sRGB" id="colorTransformFilter">

        <feColorMatrix in="SourceGraphic" type="matrix" result="imageA"
            values="1 0 0 0 0
                    0 1 0 0 0.68235294117
                    0 0 1 0 0.93725490196
                    0 0 0 0 1" /> 

        <feColorMatrix in="SourceGraphic" type="matrix" result="imageB"
            values="-1 0 0 0 1.0784313725
                    0 -1 0 0 1.7058823529
                    0 0 -1 0 1.2431372549
                    0 0 0 0 1" />              
                    
        <feBlend 
            color-interpolation-filters="linearRGB"
            in="imageA" 
            in2="imageB" 
            mode="multiply" 
            result="outputFullAlpha" />        

        <!-- Get and use alpha from source image -->
        <feColorMatrix in="SourceGraphic" type="matrix" result="whiteAlpha"
            values="0 0 0 0 1
                    0 0 0 0 1
                    0 0 0 0 1
                    0 0 0 1 0" />     

        <feComposite in="whiteAlpha" in2="outputFullAlpha" operator="arithmetic" k1="1" k2="0" k3="0" k4="0" />

    </filter>
</svg>

The demo below uses the filter, along with a bit of Javascript to cycle and update the input colors (i.e. dynamically updating the values plugged into the first 2 feColorMatrix elements):

Limitations

We have the same limitations I mentioned in part 1:

  • For icons applied as background-images, the CSS filter property isn’t ideal. CSS filter will effect not only the element it’s applied to, but all child elements as well
  • As is the case with mixing the CSS filter property and the SVG filter element, effects governed by the CSS transition property won’t work

In addition, because of how the alpha channel in treated in regards to feBlend (setting all pixels to have alpha=1), you more than likely won’t get good results if the icon has different-colored adjoining or overlapping elements, as you won’t get a smooth transition at the edges/boundaries.


Using feColorMatrix to dynamically recolor icons (part 1, single-color icons)

I’ve been experimenting with using feColorMatrix as an elegant way to dynamically color/re-color SVG icons. Here I’ll look at working with single-color icons.

Working directly with the SVG markup

Changing the stroke and/or fill colors of the SVG elements directly can be a good solution in many cases, but it requires:

  • Placing the SVG markup into the document to query and modify the appropriate elements when a color update is needed (note that this option isn’t viable if you need to place the icon in an <img> tag or it needs to be placed as a background-image on an element, as you can’t reference the SVG element in such cases)
  • Treating the SVG markup as a templated, Javascript, string to make a data-URI, and re-making it when a color update is needed

By using the color transformation matrix provided by feColorMatrix these restrictions go away and we also get back the flexibility of using external files.

Icon color

Keep in mind, we’re only dealing with single-color icons. What color is used doesn’t technically matter, but black is a nice basis and in an actual project, black is beneficial, as you’re able to open your the icon files in an editor or browser and actually see it.

black colored icon

A black pixel within the icon can then be represented by the following vector:

black pixel as column vector

Note that the alpha component may vary due to antialiasing (to smooth out edges) or some translucency within the icon.

The color transformation matrix

feColorMatrix allows you to define a 5×4 transformation matrix. There’s a lot you can do with that, but note that the last column of the matrix is essentially an additive component for each channel (see matrix-vector multiplication), so in that column we enter the desired R, G, B values from top to bottom, which will be added to the zeros in the input vector. Next, we want to preserve the alpha component from the input vector, so the fourth column of the matrix becomes [0, 0, 0, 1]T and the fourth row of the last column is zero, as we don’t want to add anything to the alpha component.

color transformation matrix, [[0, 0, 0, 0, R], [0, 0, 0, 0, G], [0, 0, 0, 0, B], [0, 0, 0, 1, 0]][(0), (0), (0), (A_(src))] = [(R), (G), (B), (A_(src))]

The matrix-vector multiplication gives a new vector (that defines the output pixel) with the entered R, G, B values and the alpha value from the source pixel.

Representing the matrix within an feColorMatrix element is straightforward…

<feColorMatrix in="SourceGraphic" type="matrix"
values="0 0 0 0 R
0 0 0 0 G
0 0 0 0 B
0 0 0 1 0"
/>

… just plug in values for R, G, B.

Applying the color transformation

The color transformation matrix can be applied to an element by wrapping it in an SVG filter element and referencing the filter via the CSS filter property.

With Javascript, the values attribute of the feColorMatrix element can be updated dynamically. The color change will, in turn, be reflected in any elements referencing the SVG filter.

<!DOCTYPE html>
<html>
<body>
<!--
The values of the color matrix defines the color transformation what will be applied.
Here we just setup the elements and define an identity matrix. We'll modify the matrix via Javascript code
to define an actual color transformation.
-->
<svg style="width:0; height:0; margin:0; padding:0; border:none;">
<filter
color-interpolation-filters="sRGB" id="colorTransformFilter">
<feColorMatrix
in="SourceGraphic" type="matrix"
values="1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0"
/>

</filter>
</svg>

<!--
Element with an SVG icon that we want to colorize
Note: that the color transformation is applied to everything not only to the background, but everything
within the element as well.

Typical solution to to isolate background stuff to it's own div and use another div for contents

-->
<div id="logo-colored"
style="
width:300px;
height:300px;
background-color: transparent;
background-image: url(logo.svg);
background-position: center center;
background-repeat: no-repeat;
background-size: cover;
filter:url(#colorTransformFilter);"
>

<p
style="color:#fff">Testing 1 2 3...</p>
</div>

<script
type="text/javascript">
/**
* A little helper function to update the color transformation matrix
*
* @param {Number} _r
* @param {Number} _g
* @param {Number} _b
*/
const setPrimaryColor = function(_r, _g, _b) {

const rScaled = _r / 255.0;
const gScaled = _g / 255.0;
const bScaled = _b / 255.0;

const feColorMatrixElem = document.getElementById('colorTransformFilter').getElementsByTagName('feColorMatrix')[0];
feColorMatrixElem.setAttribute(
`values`,
`0 0 0 0 ${rScaled}
0 0 0 0 ${gScaled}
0 0 0 0 ${bScaled}
0 0 0 1 0`
);
};

// Set/update color transformation matrix
setPrimaryColor(129, 0, 0);
</script>

</body>
</html>

The code will take a black-colored icon and re-color it to [129, 0, 0], as seen below:

Limitations

This technique provides a lot of flexibility, but it’s not without it’s limits.

  • For icons applied as background-images, the CSS filter property isn’t ideal. CSS filter will effect not only the element it’s applied to, but all child elements as well. Note the “Testing 1 2 3…” paragraph is re-colored in the demo above.
  • As is the case with mixing the CSS filter property and the SVG filter element, effects governed by the CSS transition property won’t work.

Similar techniques

  • For shifting between colors, the hue-rotate() CSS filter function can be a solution. However, in practice, I don’t find this intuitive and color changes are rarely just hue rotations.
  • A more limited case, transitioning a colored icon to white, can be achieved with 2 CSS filter functions, brightness(0) and invert(100%).
  • You can do crazier things by trying to compute and fit a solution to the hue-rotation, saturation, sepia, and invert filter functions; however this is both complex to grasp and produces inexact/approximate color matches.
  • An SVG filter using feComponentTransfer should work, but I don’t find it as intuitive to work with.

Resources

If you want to interactively play around with feColorMatrix, check out SVG Color Filter Playground.


Full-text search with PostgreSQL

I spent some time experimenting with PostgresSQL’s full-text search functionality, which has been available to some degree since v8.3. If Postgres is already being used as a data store, this functionality is attractive as it provides a simple way to implement non-trivial search without the need to build out additional infrastructure and code (e.g. an Elasticsearch cluster + application code to load data into Elasticsearch and keep it up-to-date).

I experimented with basic querying and ranking using the Lexiio database, the definitions table in particular provides a good dataset to work with, containing 604,076 term definitions.

Querying

Below is a sample query where we search for the phrase “to break into small pieces”, rank each item in the result set, and order the results based on their rank.

SELECT id, definition
FROM definitions
WHERE to_tsvector('english', definition) @@ plainto_tsquery('english', 'to break into small pieces')

Understanding this query is mostly about understanding some vendor-specific SQL.

  • The tsvector type represents is a sorted list of lexemes. to_tsvector(…) is a function to convert raw text to a tsvector.
  • The tsquery type represents lexemes to be searched for and the operators combining them. to_tsquery(…) is a function to convert raw text to a tsquery.
  • @@ is the match operator, this is a binary operator which take a tsvector and a tsquery

PostgreSQL full-text search query

To get a better understanding of of these types, it can be helpful to run the conversion functions with a few phrases.

SELECT to_tsvector('english', 'to break into small pieces');

"'break':2 'piec':5 'small':4"
SELECT plainto_tsquery('english', 'to break into small pieces');

"'break' & 'small' & 'piec'"

Ranking

The ranking of a full-text search match can be computed with either ts_rank(…), which provides a standard ranking, or ts_rank_cd(…), which gives a coverage density ranking (where ranking is also based on term proximity and cooccurrence, as described in “Relevance ranking for one to three term queries”).

SELECT
id,
definition,
ts_rank(
to_tsvector('english', definition),
plainto_tsquery('english', 'to break into small pieces')
)
AS rank
FROM definitions
WHERE to_tsvector('english', definition) @@ plainto_tsquery('english', 'to break into small pieces')
ORDER BY rank DESC

Higher rank values correspond to more relevant search results.

Here’s the result set, with rankings, for the query above:

+--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | id | definition | rank | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568352 | # {{transitive}} To [[break]] small pieces from. | 0.26833 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 135231 | # Resistant to chipping (breaking into small pieces). | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 572891 | # {{transitive}} To break into small pieces or fragments. | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568348 | # {{transitive}} To [[break]] into small pieces. | 0.266913 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 176962 | # To break into crumbs or small pieces with the fingers; to [[crumble]]. | 0.25948 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 50744 | # A small piece of [[detailing]] added to break up the [[surface]] of an [[object]] and add [[visual]] interest, particularly in [[movie]] [[special effect]]s. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 568350 | # {{transitive}} To [[break]] open or [[crush]] to small pieces by impact or stress. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 572890 | # {{transitive}} To break into [[fragment]]s or small pieces. | 0.25134 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+ | 547405 | # {{surgery}} The [[operation]] of breaking a [[stone]] in the [[bladder]] into small pieces capable of being [[void]]ed. | 0.221355 | +--------+-----------------------------------------------------------------------------------------------------------------------------------------------------------------+----------+

Indexing

Without an index the above query takes ~5.3 seconds on my local machine (i7-4790K @ 3.7GHz, Intel 730 Series SSD, DDR3 1600 RAM w/ more than enough available to PG).

A Generalized Inverted Index (GIN) is recommended for full-text search. A GIN index can be created directly on a tsvector column or, in this case where there’s an existing text column, an expression index can be created using the to_tsvector() function.

CREATE INDEX ix_def
ON definitions
USING GIN(to_tsvector('english', definition));

With this index, performance improves drastically, with query times ~13 milliseconds.

Is it worth trying?

Maybe. If you’re not using Postgres as the data store for what needs to be searched over (i.e. you’d have to continually ETL data into Postgres), you already have a sophisticated search solution in place, or you’re operating at a scale where you need a clustered solution, probably not. However, if you’re using Postgres, and looking to implement search in an application or move beyond simple substring search, what Postgres is offering is fairly powerful and worth trying out.


Encoding MP4s in the browser

Is this possible?

Given that it’s relatively easy to access a camera and capture frames within a browser, I began wondering it there was a way to encode frames and create a video within the browser as well. I can see a few benefits to doing this, perhaps the biggest being that you can move some very computationally expensive work to front-end, avoiding the need to setup and scale a process to do this server-side.

I searched a bit and first came across Whammy as a potential solution, which take a number of WebP images and creates a WebM video. However, only Chrome will let you easily get data from a canvas element as image/webp (see HTMLCanvasElement.toDataURL docs). The non-easy way is to read the pixel values from the canvas element and encode them as WebP. However, I also couldn’t find any existing JS modules that did this (only a few NodeJS wrappers for the server-side cwebp application) and writing an encoder was a much bigger project that I didn’t want to undertake.

The other option I came across, and used, was ffmpeg.js. This is a really interesting project, it’s a port of ffmpeg via Emscripten to JS code which can be run in browsers that support WebAssembly.

Grabbing frames

My previous post on real-time image processing covers how to setup the video stream, take a snapshot, and render it to a canvas element. To work with ffmpeg.js, you’ll additionally need the frame’s pixels from the canvas element as a JPEG image, represented as bytes in a Uint8Array. This can be done as follows:

var dataUri = canvas.toDataURL("image/jpeg", 1);
var jpegBytes = convertDataURIToBinary(dataUri);

convertDataURIToBinary() is the following method, which will take the data-uri representation of the JPEG data and transform it into a Uint8Array:

function convertDataURIToBinary(dataURI) {
var base64 = dataURI.substring(23);
var raw = window.atob(base64);
var rawLength = raw.length;

var array = new Uint8Array(new ArrayBuffer(rawLength));
for (i = 0; i < rawLength; i++) {
array[i] = raw.charCodeAt(i);
}
return array;
};

FYI, this is just a slight modification of a method I found in this gist.

Note that I did not use PNG images due to an issue in the current version of ffmpeg.js (v3.1.9001).

Working with ffmpeg.js

ffmpeg.js comes with a Web Worker wrapper (ffmpeg-worker-mp4.js), which is really nice as you can run “ffmpeg –whatever” by just posting a message to the worker, and get the status/result via messages posted backed to the caller via Worker.onmessage.

var worker = new Worker("node_modules/ffmpeg.js/ffmpeg-worker-mp4.js");
worker.onmessage =
function (e) {
var msg = e.data;

switch (msg.type) {
case "ready":
console.log(
'mp4 worker ready');
break;
case "stdout":
console.log(msg.data);
break;
case "stderr":
console.log(msg.data);
break;

case "done":
var blob = new Blob([msg.data.MEMFS[0].data], {
type:
"video/mp4"
});

// ...
break;

case "exit":
console.log(
"Process exited with code " + msg.data);
break;
}
};

Input and output of files is handled by MEMFS (one of the virtual file systems supported by Emscripten). On the “done” message from ffmpeg.js, you can access the output files via the msg.data.MEMFS array (shown above). Input files are specified via an array in the call to worker.postMessage (shown below).

worker.postMessage(
{
type:
"run",
TOTAL_MEMORY: 268435456,
MEMFS: [
{
name:
"input.jpeg",
data: jpegBytes
}
],
arguments: [
"-r", "60", "-i", "input.jpeg", "-aspect", "16/9", "-c:v", "libx264", "-crf", "1", "-vf", "scale=1280:720", "-pix_fmt", "yuv420p", "-vb", "20M", "out.mp4"]
}
);

Limitations

With a bunch of frames captured from the video stream, I began pushing them through ffmpeg.js to encode a H.264 MP4 at 720p, and things started to blow up. There were 2 big issues:

  • Video encoding is no doubt a memory intensive operation, but even for a few dozen frames I could never give ffmpeg.js enough. I tried playing around with the TOTAL_MEMORY prop in the worker.postMessage call, but if it’s too low ffmpeg.js runs out of memory and if it’s too high ffmpeg.js fails to allocate memory.
  • Browser support issues. Support issues aren’t surprising here given that WebAssembly is still experimental. The short of it is: things work well in Chrome and Firefox on desktop. For Edge or Chrome on a mobile device, things work for a while before the browser crashes. For iOS there is no support.

Hacking something together

The browser issues were intractable, but support on Chrome and Firefox was good enough more me, and I felt I could work around the memory limitations. Lowering the memory footprint was a matter of either:

  • Reducing the resolution of each frame
  • Reducing the number of frames

I opted for the latter. My plan was to make a small web application to allow someone to easily capture and create time-lapse videos, so I had ffmpeg.js encode just 1 frame to a H.264 MP4, send that MP4 to the server, and then use ffmpeg’s concat demuxer on the server-side to progressively concatenate each individual MP4 file into a single MP4 video. What this enables is for the more costly encoding work to the done client-side and the cheaper concatenation work to be done server-side.

Time Stream was the end result.

Here’s a time-lapse video created using an old laptop and a webcam taped onto my balcony:

This sort of hybrid solution works well. Overall, I’m happy with the results, but would love the eliminate the server-side ffmpeg dependency outright, so I’m looking forward to seeing Web Assembly support expand and improve across browsers.

More generally, it’s interesting to push these types of computationally intensive tasks to the front-end, and I think it presents some interesting possibilities for architecting and scaling web applications.