How to Optimize execution time for RGB to HSL conversion function?

Question

I've created this function to convert RGB color to HSL color. It works perfect.

But I need to make it run faster, because it's used to replace colors on a canvas, and I need to reduce the time of replacement. Since the image contains 360k pixels (600x600px) anything can make it faster.

That's my current implementation:

/**
 * Convert RGB Color to HSL Color
 * @param {{R: integer, G: integer, B: integer}} rgb
 * @returns {{H: number, S: number, L: number}}
 */
Colorize.prototype.rgbToHsl = function(rgb) {
    var R = rgb.R/255;
    var G = rgb.G/255;
    var B = rgb.B/255;
    var Cmax = Math.max(R,G,B);
    var Cmin = Math.min(R,G,B);
    var delta = Cmax - Cmin;
    var L = (Cmax + Cmin) / 2;
    var S = 0;
    var H = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2*L) - 1));

        switch (Cmax) {
            case R:
                H = ((G - B) / delta) % 6;
                break;
            case G:
                H = ((B - R) / delta) + 2;
                break;
            case B:
                H = ((R - G) / delta) + 4;
                break;
        }
        H *= 60;
    }

    // Convert negative angles from Hue
    while (H < 0) {
        H += 360;
    }

    return {
        H: H,
        S: S,
        L: L
    };
};

Answer 1

tl;dr

• Define everything, before calculations
• Switch is bad for performance
• Loops are bad
• Use Closure Compiler for automated optimizations
• MEMOIZE! (this one is not available in the benchmark because it uses only one color at the time)
• Compare pairs in Math.max and Math.min (if-else works better for bigger numbers as far as I can see)

Benchmark

The benchmark is quite basic; I'm generating a random RGB color every time and use it for the test suit.

The same color for all implementations of a converter.

I'm currently using a fast computer, so your numbers may differ.

At this point it is hard to optimize further, because performance differs, depending on the data.

Optimisations

Define the object for the result value at the very beginning. Allocating memory for the objects upfront somehow improves the performance.

var res = {
    H: 0,
    S: 0,
    L: L
}
// ...
return res;

Not using switch will yield easy performance improvement.

if (delta !== 0) {
    S = delta / (1 - Math.abs((2 * L) - 1));

    if (Cmax === R) {
        H = ((G - B) / delta) % 6;
    } else if (Cmax === G) {
        H = ((B - R) / delta) + 2;
    } else if (Cmax === B) {
        H = ((R - G) / delta) + 4;
    }
    H *= 60;
}

While loop is easily removable by:

if (H < 0) {
    remainder = H % 360;

    if (remainder !== 0) {
        H = remainder + 360;
    }
}

I have also applied Closure Compiler to remove redundant operations inside of the code.

You should memoize the results!

Consider refactoring the function to use three arguments so it's possible to have a multi-dimensional hash-map for memozing cache. Alternatively you can try using WeakMap, but the performance of this solution is unknown.

See the article Faster JavaScript Memoization For Improved Application Performance

Results

Node.js

The best one is rgbToHslOptimizedClosure.

node -v
v6.5.0

rgbToHsl x 16,468,872 ops/sec ±1.64% (85 runs sampled)
rgbToHsl_ x 15,795,460 ops/sec ±1.28% (84 runs sampled)
rgbToHslIfElse x 16,091,606 ops/sec ±1.41% (85 runs sampled)
rgbToHslOptimized x 22,147,449 ops/sec ±1.96% (81 runs sampled)
rgbToHslOptimizedClosure x 46,493,753 ops/sec ±1.55% (85 runs sampled)
rgbToHslOptimizedIfElse x 21,825,646 ops/sec ±2.93% (85 runs sampled)
rgbToHslOptimizedClosureIfElse x 38,346,283 ops/sec ±9.02% (73 runs sampled)
rgbToHslOptimizedIfElseConstant x 30,461,643 ops/sec ±2.68% (81 runs sampled)
rgbToHslOptimizedIfElseConstantClosure x 40,625,530 ops/sec ±2.70% (73 runs sampled)

Fastest is rgbToHslOptimizedClosure
Slowest is rgbToHsl_

Browser

Chrome Version 55.0.2883.95 (64-bit)

rgbToHsl x 18,456,955 ops/sec ±0.78% (62 runs sampled)
rgbToHsl_ x 16,629,042 ops/sec ±2.34% (63 runs sampled)
rgbToHslIfElse x 17,177,059 ops/sec ±3.85% (59 runs sampled)
rgbToHslOptimized x 27,552,325 ops/sec ±0.95% (62 runs sampled)
rgbToHslOptimizedClosure x 47,659,771 ops/sec ±3.24% (47 runs sampled)
rgbToHslOptimizedIfElse x 26,033,751 ops/sec ±2.63% (61 runs sampled)
rgbToHslOptimizedClosureIfElse x 43,430,875 ops/sec ±3.55% (59 runs sampled)
rgbToHslOptimizedIfElseConstant x 33,696,558 ops/sec ±3.97% (58 runs sampled)
rgbToHslOptimizedIfElseConstantClosure x 44,529,209 ops/sec ±3.56% (60 runs sampled)

Fastest is rgbToHslOptimizedClosure
Slowest is rgbToHsl_

Run the benchmark yourself

Note, that browser will freeze for a moment.

function getRandomInt(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

var RGB = { R: getRandomInt(0, 255), G: getRandomInt(0, 255), B: getRandomInt(0, 255) }

// http://axonflux.com/handy-rgb-to-hsl-and-rgb-to-hsv-color-model-c

/**
 * Converts an RGB color value to HSL. Conversion formula
 * adapted from http://en.wikipedia.org/wiki/HSL_color_space.
 * Assumes r, g, and b are contained in the set [0, 255] and
 * returns h, s, and l in the set [0, 1].
 *
 * @param   {number}  r       The red color value
 * @param   {number}  g       The green color value
 * @param   {number}  b       The blue color value
 * @return  {Array}           The HSL representation
 */
function rgbToHsl_(r, g, b) {
    r /= 255, g /= 255, b /= 255;
    var max = Math.max(r, g, b), min = Math.min(r, g, b);
    var h, s, l = (max + min) / 2;

    if (max == min) {
        h = s = 0; // achromatic
    } else {
        var d = max - min;
        s = l > 0.5 ? d / (2 - max - min) : d / (max + min);
        switch (max) {
            case r:
                h = (g - b) / d + (g < b ? 6 : 0);
                break;
            case g:
                h = (b - r) / d + 2;
                break;
            case b:
                h = (r - g) / d + 4;
                break;
        }
        h /= 6;
    }

    return [ h, s, l ];
}

function rgbToHsl(rgb) {
    var R = rgb.R / 255;
    var G = rgb.G / 255;
    var B = rgb.B / 255;
    var Cmax = Math.max(R, G, B);
    var Cmin = Math.min(R, G, B);
    var delta = Cmax - Cmin;
    var L = (Cmax + Cmin) / 2;
    var S = 0;
    var H = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2 * L) - 1));

        switch (Cmax) {
            case R:
                H = ((G - B) / delta) % 6;
                break;
            case G:
                H = ((B - R) / delta) + 2;
                break;
            case B:
                H = ((R - G) / delta) + 4;
                break;
        }
        H *= 60;
    }

    // Convert negative angles from Hue
    while (H < 0) {
        H += 360;
    }

    return {
        H: H,
        S: S,
        L: L
    };
};

function rgbToHslIfElse(rgb) {
    var R = rgb.R / 255;
    var G = rgb.G / 255;
    var B = rgb.B / 255;
    var Cmax = Math.max(R, G, B);
    var Cmin = Math.min(R, G, B);
    var delta = Cmax - Cmin;
    var L = (Cmax + Cmin) / 2;
    var S = 0;
    var H = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2 * L) - 1));

        if (Cmax === R) {
            H = ((G - B) / delta) % 6;
        } else if (Cmax === G) {
            H = ((B - R) / delta) + 2;
        } else if (Cmax === B) {
            H = ((R - G) / delta) + 4;
        }
        H *= 60;
    }

    // Convert negative angles from Hue
    while (H < 0) {
        H += 360;
    }

    return {
        H: H,
        S: S,
        L: L
    };
};

function rgbToHslOptimized(rgb) {
    var R = rgb.R / 255;
    var G = rgb.G / 255;
    var B = rgb.B / 255;
    var Cmax = Math.max(Math.max(R, G), B);
    var Cmin = Math.min(Math.min(R, G), B);
    var delta = Cmax - Cmin;
    var S = 0;
    var H = 0;
    var L = (Cmax + Cmin) / 2;
    var res = {
        H: 0,
        S: 0,
        L: L
    }
    var remainder = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2 * L) - 1));

        switch (Cmax) {
            case R:
                H = ((G - B) / delta) % 6;
                break;
            case G:
                H = ((B - R) / delta) + 2;
                break;
            case B:
                H = ((R - G) / delta) + 4;
                break;
        }
        H *= 60;
    }

    if (H < 0) {
        remainder = H % 360;

        if (remainder !== 0) {
            H = remainder + 360;
        }
    }

    res.H = H;
    res.S = S;

    return res;
}

function rgbToHslOptimizedIfElse(rgb) {
    var R = rgb.R / 255;
    var G = rgb.G / 255;
    var B = rgb.B / 255;
    var Cmax = Math.max(Math.max(R, G), B);
    var Cmin = Math.min(Math.min(R, G), B);
    var delta = Cmax - Cmin;
    var S = 0;
    var H = 0;
    var L = (Cmax + Cmin) / 2;
    var res = {
        H: 0,
        S: 0,
        L: L
    }
    var remainder = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2 * L) - 1));

        if (Cmax === R) {
            H = ((G - B) / delta) % 6;
        } else if (Cmax === G) {
            H = ((B - R) / delta) + 2;
        } else if (Cmax === B) {
            H = ((R - G) / delta) + 4;
        }
        H *= 60;
    }

    if (H < 0) {
        remainder = H % 360;

        if (remainder !== 0) {
            H = remainder + 360;
        }
    }

    res.H = H;
    res.S = S;

    return res;
}

function rgbToHslOptimizedIfElseConstant(rgb) {
    var R = rgb.R * 0.00392156862745;
    var G = rgb.G * 0.00392156862745;
    var B = rgb.B * 0.00392156862745;
    var Cmax = Math.max(Math.max(R, G), B);
    var Cmin = Math.min(Math.min(R, G), B);
    var delta = Cmax - Cmin;
    var S = 0;
    var H = 0;
    var L = (Cmax + Cmin) * 0.5;
    var res = {
        H: 0,
        S: 0,
        L: L
    }
    var remainder = 0;

    if (delta !== 0) {
        S = delta / (1 - Math.abs((2 * L) - 1));

        if (Cmax === R) {
            H = ((G - B) / delta) % 6;
        } else if (Cmax === G) {
            H = ((B - R) / delta) + 2;
        } else if (Cmax === B) {
            H = ((R - G) / delta) + 4;
        }
        H *= 60;
    }

    if (H < 0) {
        remainder = H % 360;

        if (remainder !== 0) {
            H = remainder + 360;
        }
    }

    res.H = H;
    res.S = S;

    return res;
}

function rgbToHslOptimizedIfElseConstantClosure(c) {
    var a = .00392156862745 * c.h, e = .00392156862745 * c.f, f = .00392156862745 * c.c, g = Math.max(Math.max(a, e), f), d = Math.min(Math.min(a, e), f), h = g - d, b = c = 0, k = (g + d) / 2, d = {
        a: 0,
        b: 0,
        g: k
    };
    0 !== h && (c = h / (1 - Math.abs(2 * k - 1)), g === a ? b = (e - f) / h % 6 : g === e ? b = (f - a) / h + 2 : g === f && (b = (a - e) / h + 4), b *= 60);
    0 > b && (a = b % 360, 0 !== a && (b = a + 360));
    d.a = b;
    d.b = c;
    return d;
};

function rgbToHslOptimizedClosure(c) {
    var a = c.f / 255, e = c.b / 255, f = c.a / 255, k = Math.max(Math.max(a, e), f), d = Math.min(Math.min(a, e), f), g = k - d, b = c = 0, l = (k + d) / 2, d = {
        c: 0,
        g: 0,
        h: l
    };
    if (0 !== g) {
        c = g / (1 - Math.abs(2 * l - 1));
        switch (k) {
            case a:
                b = (e - f) / g % 6;
                break;
            case e:
                b = (f - a) / g + 2;
                break;
            case f:
                b = (a - e) / g + 4;
        }
        b *= 60;
    }
    0 > b && (a = b % 360, 0 !== a && (b = a + 360));
    d.c = b;
    d.g = c;
    return d;
}

function rgbToHslOptimizedClosureIfElse(c) {
    var a = c.f / 255, e = c.b / 255, f = c.a / 255, g = Math.max(Math.max(a, e), f), d = Math.min(Math.min(a, e), f), h = g - d, b = c = 0, l = (g + d) / 2, d = {
        c: 0,
        g: 0,
        h: l
    };
    0 !== h && (c = h / (1 - Math.abs(2 * l - 1)), g === a ? b = (e - f) / h % 6 : g === e ? b = (f - a) / h + 2 : g === f && (b = (a - e) / h + 4), b *= 60);
    0 > b && (a = b % 360, 0 !== a && (b = a + 360));
    d.c = b;
    d.g = c;
    return d;
}

new Benchmark.Suite()
    .add('rgbToHsl', function () {
        rgbToHsl(RGB);
    })
    .add('rgbToHsl_', function () {
        rgbToHsl_(RGB.R, RGB.G, RGB.B);
    })
    .add('rgbToHslIfElse', function () {
        rgbToHslIfElse(RGB);
    })
    .add('rgbToHslOptimized', function () {
        rgbToHslOptimized(RGB);
    })
    .add('rgbToHslOptimizedClosure', function () {
        rgbToHslOptimizedClosure(RGB);
    })
    .add('rgbToHslOptimizedIfElse', function () {
        rgbToHslOptimizedIfElse(RGB);
    })
    .add('rgbToHslOptimizedClosureIfElse', function () {
        rgbToHslOptimizedClosureIfElse(RGB);
    })
    .add('rgbToHslOptimizedIfElseConstant', function () {
        rgbToHslOptimizedIfElseConstant(RGB);
    })
    .add('rgbToHslOptimizedIfElseConstantClosure', function () {
        rgbToHslOptimizedIfElseConstantClosure(RGB);
    })
    // add listeners
    .on('cycle', function (event) {
        console.log(String(event.target));
    })
    .on('complete', function () {
        console.log('Fastest is ' + this.filter('fastest').map('name'));
        console.log('Slowest is ' + this.filter('slowest').map('name'));
    })
    // run async
    .run({ 'async': false });

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.11/lodash.min.js"></script>
<script src="https://cdn.rawgit.com/bestiejs/benchmark.js/master/benchmark.js"></script>

Answer 2

Avoid the divisions by all means. You can probably eliminate a few by rescaling the relevant variables and constants.

You can also avoid divisions by using a lookup-table of inverses.

I don't think that the switch case is very efficient. I would advise to replace the max/min/switch by a single discussion using a triply nested if where you compare the RGB components, ending in the 6 possible orderings and applying ad-hoc processing to each.

Answer 3

Use a rough approximation instead:

third = Math.PI * 2 / 3;
ctx.fillStyle = 'rgb('+ [
    127 + 127 * Math.cos(time - third),
    127 + 127 * Math.cos(time),
    127 + 127 * Math.cos(time + third)
] +')';

Based on:

• http://www.p01.org/artjs_at_ffconf/
• http://www.p01.org/artjs_at_ffconf/talk.html