Benchmark color conversion

[JeremyAnsel]

Hello, I've run a few benchmark to compare lookup vs compute color conversion.

Here is the result;

compare 5 OK
compare 6 OK
bench_lookup: 28.2832 ms        4286578691 41943043 4286578688 41943043
bench_compute: 41.4348 ms       4286578691 41943043 4286578688 41943043
bench_compute_simd: 24.7041 ms  4286578691 41943043 4286578688 41943043
bench_colorkey: 16.5983 ms      4286578691 41943043 4286578688 4267704323
bench_colorkey_simd: 14.2981 ms 4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_lookup: 26.9225 ms  4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_compute: 38.8146 ms 4286578691 41943043 4286578688 4267704323

I've used this code:

#include <iostream>
#include <string>
#include <chrono>

const int g_loopCount = 0x1000000 + 3;

unsigned short g_srcArray16[g_loopCount];
unsigned int g_srcArray32[g_loopCount];
unsigned short g_dstArray16[g_loopCount];
unsigned int g_dstArray32[g_loopCount];

void initGlobalArray()
{
    for (int i = 0; i < g_loopCount; i++)
    {
        g_srcArray16[i] = (unsigned short)i;
        g_srcArray32[i] = (unsigned int)i;
        g_dstArray16[i] = (unsigned short)i;
        g_dstArray32[i] = (unsigned int)i;
    }
}

void sumGlobalArray()
{
    unsigned int sumSrc16 = 0;
    unsigned int sumSrc32 = 0;
    unsigned int sumDst16 = 0;
    unsigned int sumDst32 = 0;

    for (int i = 0; i < g_loopCount; i++)
    {
        sumSrc16 += g_srcArray16[i];
        sumSrc32 += g_srcArray32[i];
        sumDst16 += g_dstArray16[i];
        sumDst32 += g_dstArray32[i];
    }

    std::cout << "\t" << sumSrc16 << " " << sumSrc32 << " " << sumDst16 << " " << sumDst32 << std::endl;
}

void measure(const char* name, void(*fct)())
{
    auto start = std::chrono::high_resolution_clock::now();

    if (fct)
    {
        fct();
    }

    auto end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double, std::milli> ellapsed = end - start;

    std::cout << name << ": " << ellapsed.count() << " ms";
}

unsigned char convertColorB8G8R8X8toB5G6R5_15(unsigned char c)
{
    return (c * (0x1F * 2) + 0xFF) / (0xFF * 2);
}

unsigned char convertColorB8G8R8X8toB5G6R5_16(unsigned char c)
{
    return (c * (0x3F * 2) + 0xFF) / (0xFF * 2);
}

unsigned char convertColorB8G8R8X8toB5G6R5_25(unsigned char c)
{
    return (c * 7967 + 32768) >> 16;
}

unsigned char convertColorB8G8R8X8toB5G6R5_26(unsigned char c)
{
    return (c * 16191 + 32768) >> 16;
}

void compare5()
{
    std::cout << "compare 5";

    bool error = false;

    for (int i = 0; i < 256; i++)
    {
        unsigned char c = (unsigned char)i;

        unsigned char c1 = convertColorB8G8R8X8toB5G6R5_15(c);
        unsigned char c2 = convertColorB8G8R8X8toB5G6R5_25(c);

        if (c1 != c2)
        {
            error = true;
            break;
        }
    }

    std::cout << (error ? " ERROR" : " OK") << std::endl;
}

void compare6()
{
    std::cout << "compare 6";

    bool error = false;

    for (int i = 0; i < 256; i++)
    {
        unsigned char c = (unsigned char)i;

        unsigned char c1 = convertColorB8G8R8X8toB5G6R5_16(c);
        unsigned char c2 = convertColorB8G8R8X8toB5G6R5_26(c);

        if (c1 != c2)
        {
            error = true;
            break;
        }
    }

    std::cout << (error ? " ERROR" : " OK") << std::endl;
}

class ColorConverterTables
{
public:
    ColorConverterTables()
    {
        // X8toX5, X8toX6
        for (unsigned int c = 0; c < 0x100; c++)
        {
            this->X8toX5[c] = (c * (0x1F * 2) + 0xFF) / (0xFF * 2);
            this->X8toX6[c] = (c * (0x3F * 2) + 0xFF) / (0xFF * 2);
        }
    }

    unsigned char X8toX5[0x100];
    unsigned char X8toX6[0x100];
};

ColorConverterTables g_colorConverterTables;

unsigned short convert32to16_lookup(unsigned int color32)
{
    unsigned int red = (color32 & 0xFF0000) >> 16;
    unsigned int green = (color32 & 0xFF00) >> 8;
    unsigned int blue = color32 & 0xFF;

    red = g_colorConverterTables.X8toX5[red];
    green = g_colorConverterTables.X8toX6[green];
    blue = g_colorConverterTables.X8toX5[blue];

    unsigned short color16 = (red << 11) | (green << 5) | blue;
    return color16;
}

void bench_lookup()
{
    unsigned short* dst = g_dstArray16;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color32 = src[i];

        unsigned char red = (unsigned char)((color32 & 0xFF0000) >> 16);
        unsigned char green = (unsigned char)((color32 & 0xFF00) >> 8);
        unsigned char blue = (unsigned char)(color32 & 0xFF);

        red = g_colorConverterTables.X8toX5[red];
        green = g_colorConverterTables.X8toX6[green];
        blue = g_colorConverterTables.X8toX5[blue];

        unsigned int color16 = (red << 11) | (green << 5) | blue;

        dst[i] = color16;
    }
}

void bench_compute()
{
    unsigned short* dst = g_dstArray16;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color32 = src[i];

        unsigned char red = (unsigned char)((color32 & 0xFF0000) >> 16);
        unsigned char green = (unsigned char)((color32 & 0xFF00) >> 8);
        unsigned char blue = (unsigned char)(color32 & 0xFF);

        red = (red * 7967 + 32768) >> 16;
        green = (green * 16191 + 32768) >> 16;
        blue = (blue * 7967 + 32768) >> 16;

        unsigned int color16 = (red << 11) | (green << 5) | blue;

        dst[i] = color16;
    }
}

unsigned short convert32to16_compute(unsigned int color32)
{
    unsigned int red = (color32 & 0xFF0000) >> 16;
    unsigned int green = (color32 & 0xFF00) >> 8;
    unsigned int blue = color32 & 0xFF;

    red = (red * 7967 + 32768) >> 16;
    green = (green * 16191 + 32768) >> 16;
    blue = (blue * 7967 + 32768) >> 16;

    unsigned short color16 = (red << 11) | (green << 5) | blue;
    return color16;
}

void bench_compute_simd()
{
    unsigned short* dst = g_dstArray16;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        dst[i] = convert32to16_compute(src[i]);
    }
}

void bench_colorkey()
{
    unsigned int* dst = g_dstArray32;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color32 = src[i];

        if (color32 == 0x200000)
        {
            dst[i] = 0xff000000;
        }
        else
        {
            dst[i] = color32 & 0xffffff;
        }
    }
}

unsigned int convert32Colorkey(unsigned int color32)
{
    if (color32 == 0x200000)
    {
        color32 = 0xff000000;
    }
    else
    {
        color32 = color32 & 0xffffff;
    }

    return color32;
}

void bench_colorkey_simd()
{
    unsigned int* dst = g_dstArray32;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        dst[i] = convert32Colorkey(src[i]);
    }
}

void bench_colorkey_skip_lookup()
{
    unsigned short* dst = g_dstArray16;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color32 = src[i];

        if (color32 == 0x200000)
            continue;

        dst[i] = convert32to16_lookup(color32);
    }
}

void bench_colorkey_skip_compute()
{
    unsigned short* dst = g_dstArray16;
    unsigned int* src = g_srcArray32;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color32 = src[i];

        if (color32 == 0x200000)
            continue;

        dst[i] = convert32to16_compute(color32);
    }
}

#define BENCH(fct) measure(#fct, (fct)); sumGlobalArray();

void main()
{
    compare5();
    compare6();

    initGlobalArray();

    BENCH(bench_lookup);
    BENCH(bench_compute);
    BENCH(bench_compute_simd);
    BENCH(bench_colorkey);
    BENCH(bench_colorkey_simd);
    BENCH(bench_colorkey_skip_lookup);
    BENCH(bench_colorkey_skip_compute);
}

It seems that compute is faster than lookup when SIMD is used, and lookup is faster than compute when SIMD is not used.

[rdoeffinger]

I got similar results, though I was much less thorough. But there is some risk that the lookup result is affected by not having realistic content. If one wanted to be really certain it might make sense to have a source image if all identical values and one initialized with random values to see the effect of cache hit rate. As for the SIMD case I suspect that I chose the constants poorly, as SSE2 has an instruction that does a*b>>16 which has double the throughput of a a*b that goes from 16 to 32 bit. Which means that for example (((red * 7967 * 2) >> 16) + 1) >> 1; might be significantly faster (unless the compiler already figures that out). Though I am not sure if there actually is a point in optimizing this, I admit I mostly changed the code because MSVC had warnings about the LUT and in general runtime-initialized global variables always come with the risk of falling into the undefined initialization order trap.

[rdoeffinger]

Here's an alternative SSE2 version not relying on SIMD. It is a bit wasteful though since it really could do 2 pixels for almost the same price as doing 1:

unsigned short convert32to16_sse2(unsigned int color32)
{
    __m128i in = _mm_setr_epi32(color32, 0, 0, 0);
    __m128i in16 = _mm_unpacklo_epi8(in, _mm_setzero_si128());
    __m128i scaled = _mm_mulhi_epu16(in16, _mm_setr_epi16(7967*2, 16191*2, 7967*2, 0, 0, 0, 0, 0));
    __m128i rounded = _mm_avg_epu16(scaled, _mm_setzero_si128());
    __m128i shifted = _mm_madd_epi16(rounded, _mm_setr_epi16(1, 32, 32*64, 0, 0, 0, 0, 0));
    return _mm_extract_epi16(shifted, 0) | _mm_extract_epi16(shifted, 2);
}

[rdoeffinger]

With that function I get:

compare 5 OK
compare 6 OK
bench_lookup: 22.834 ms 4286578691 41943043 4286578688 41943043
bench_compute: 37.7886 ms       4286578691 41943043 4286578688 41943043
bench_compute_simd: 20.393 ms   4286578691 41943043 4286578688 41943043
bench_compute_sse2: 22.9526 ms  4286578691 41943043 4286578688 41943043
bench_colorkey: 13.9993 ms      4286578691 41943043 4286578688 4267704323
bench_colorkey_simd: 10.1302 ms 4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_lookup: 25.5961 ms  4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_compute: 43.5716 ms 4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_sse2: 25.8467 ms    4286578691 41943043 4286578688 4267704323

But the results are not very stable.

[rdoeffinger]

EDIT: sorry forget all that is written below, it's buggy. Fixed version is still faster, but not as much. Unfortunately I am not getting consistent results for bench_compute_simd at all, anything from 15 to 25 ms... EDIT END

Another variant:

unsigned short convert32to16_sse2_double(unsigned int color32, unsigned color32_2)
{
    __m128i in = _mm_setr_epi32(color32, color32_2, 0, 0);
    __m128i in16 = _mm_unpacklo_epi8(in, _mm_setzero_si128());
    __m128i scaled = _mm_mulhi_epu16(in16, _mm_setr_epi16(7967 * 2, 16191 * 2, 7967 * 2, 0, 7967 * 2, 16191 * 2, 7967 * 2, 0));
    __m128i rounded = _mm_avg_epu16(scaled, _mm_setzero_si128());
    __m128i shifted = _mm_madd_epi16(rounded, _mm_setr_epi16(1, 32, 32 * 64, 0, 1, 32, 32 * 64, 0));
    return _mm_extract_epi16(shifted, 0) | _mm_extract_epi16(shifted, 2) | ((_mm_extract_epi16(shifted, 4) | _mm_extract_epi16(shifted, 6)) << 16);
}

Which gives a good speedup when it can be used:

compare 5 OK
compare 6 OK
bench_lookup: 22.8618 ms        4286578691 41943043 4286578688 41943043
bench_compute: 37.8927 ms       4286578691 41943043 4286578688 41943043
bench_compute_simd: 24.5239 ms  4286578691 41943043 4286578688 41943043
bench_compute_sse2: 22.9949 ms  4286578691 41943043 4286578688 41943043
bench_compute_sse2_double: 13.0858 ms   4286578691 41943043 4290248704 41943043
bench_colorkey: 13.8535 ms      4286578691 41943043 4290248704 4267704323
bench_colorkey_simd: 10.665 ms  4286578691 41943043 4290248704 4267704323
bench_colorkey_skip_lookup: 25.4881 ms  4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_compute: 43.5247 ms 4286578691 41943043 4286578688 4267704323
bench_colorkey_skip_sse2: 30.657 ms     4286578691 41943043 4286578688 4267704323

I think the only pretty clear result is that the only thing that really works well is to write the whole inner loop in SSE2... But as far as I know that is already done for anything that actually appears as a hotspot, so in a way performance of this function should not really matter.

[JeremyAnsel]

I think the return type of convert32to16_sse2_double should be unsigned int instead of unsigned short.

[JeremyAnsel]

unsigned int convertColorB5G6R5toB8G8R8X8_1(unsigned short color16)
{
    unsigned int red = (color16 >> 11) & 0x1f;
    unsigned int green = (color16 >> 5) & 0x3f;
    unsigned int blue = color16 & 0x1f;

    red = (red * (0xFF * 2) + 0x1F) / (0x1F * 2);
    green = (green * (0xFF * 2) + 0x3F) / (0x3F * 2);
    blue = (blue * (0xFF * 2) + 0x1F) / (0x1F * 2);

    unsigned int color32 = (red << 16) | (green << 8) | blue;
    return color32;
}

unsigned int convertColorB5G6R5toB8G8R8X8_2(unsigned short color16)
{
    unsigned int red = (color16 >> 11) & 0x1f;
    unsigned int green = (color16 >> 5) & 0x3f;
    unsigned int blue = color16 & 0x1f;

    red = (red * 539086 + 32768) >> 16;
    green = (green * 265264 + 32768) >> 16;
    blue = (blue * 539086 + 32768) >> 16;

    unsigned int color32 = (red << 16) | (green << 8) | blue;
    return color32;
}

unsigned int convertColorB5G6R5toB8G8R8X8_reimar(unsigned short color16)
{
    unsigned red = color16 >> 11;
    red |= red << 5;
    red >>= 2;
    unsigned green = (color16 >> 5) & 0x3f;
    green |= green << 6;
    green >>= 4;
    unsigned blue = color16 & 0x1f;
    blue |= blue << 5;
    blue >>= 2;
    return (red << 16) | (green << 8) | blue;
}

void compare_B5G6R5toB8G8R8X8()
{
    std::cout << "compare B5G6R5 to B8G8R8X8";

    bool error = false;

    for (int i = 0; i < 0x10000; i++)
    {
        unsigned short c = (unsigned short)i;

        unsigned int c1 = convertColorB5G6R5toB8G8R8X8_1(c);
        unsigned int c2 = convertColorB5G6R5toB8G8R8X8_2(c);

        if (c1 != c2)
        {
            error = true;
            break;
        }
    }

    std::cout << (error ? " ERROR" : " OK") << std::endl;
}

void compare_B5G6R5toB8G8R8X8_reimar()
{
    std::cout << "compare B5G6R5 to B8G8R8X8 Reimar";

    bool error = false;

    for (int i = 0; i < 0x10000; i++)
    {
        unsigned short c = (unsigned short)i;

        unsigned int c1 = convertColorB5G6R5toB8G8R8X8_1(c);
        unsigned int c2 = convertColorB5G6R5toB8G8R8X8_reimar(c);

        if (c1 != c2)
        {
            error = true;
            break;
        }
    }

    std::cout << (error ? " ERROR" : " OK") << std::endl;
}

I get:

compare B5G6R5 to B8G8R8X8 OK
compare B5G6R5 to B8G8R8X8 Reimar ERROR

void bench_B5G6R5toB8G8R8X8_lookup()
{
    unsigned int* dst = g_dstArray32;
    unsigned short* src = g_srcArray16;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        unsigned int color16 = src[i];

        dst[i] = g_colorConverterTables.B5G6R5toB8G8R8X8[color16];
    }
}

void bench_B5G6R5toB8G8R8X8_compute_1()
{
    unsigned int* dst = g_dstArray32;
    unsigned short* src = g_srcArray16;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        dst[i] = convertColorB5G6R5toB8G8R8X8_1(src[i]);
    }
}

void bench_B5G6R5toB8G8R8X8_compute_2()
{
    unsigned int* dst = g_dstArray32;
    unsigned short* src = g_srcArray16;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        dst[i] = convertColorB5G6R5toB8G8R8X8_2(src[i]);
    }
}

void bench_B5G6R5toB8G8R8X8_compute_reimar()
{
    unsigned int* dst = g_dstArray32;
    unsigned short* src = g_srcArray16;
    int size = g_loopCount;

    for (int i = 0; i < size; i++)
    {
        dst[i] = convertColorB5G6R5toB8G8R8X8_reimar(src[i]);
    }
}

I get:

bench_B5G6R5toB8G8R8X8_lookup: 15.5249 ms       4267165611 10566150 80301439 3598571874
bench_B5G6R5toB8G8R8X8_compute_1: 76.5755 ms    4267165611 10566150 80301439 3598571874
bench_B5G6R5toB8G8R8X8_compute_2: 15.4619 ms    4267165611 10566150 80301439 3598571874
bench_B5G6R5toB8G8R8X8_compute_reimar: 17.0034 ms       4267165611 10566150 80301439 3447264098

[rdoeffinger]

Yes, my replacement for the 565 to 8888 code was not meant to be bit-exact. It is the standard method other programs like FFmpeg etc. use though. It has a < 1 ULP rounding error, which I didn't consider relevant. It might also not be very impressive performance-wise in its C form, but it is relatively easy to convert into SIMD, and more specifically into SSE2 SIMD operating on 8 pixels at once. I do admit I have not checked if the fixed-point multiplication algorithm could give similar SIMD performance though, but at least the constants you selected would not allow for 16x16->high 16 bit multiplication to be used without dropping the rounding. I also admit that when it comes to optimization I tend to be stuck in the past and assume CPUs that are much faster at shifts than multiplies, which is not really true anymore. But the SSE2 code worked for eliminating that function from the profile at least, that much I actually tested :) (the SSE2 code to do colorkeying and conversion is approximately 21 instructions for converting 8 pixels, which even with some loop overhead comes out below 3 instructions per pixel) With the 64kB LUT at least I also think that the input array with values always incrementing by 1 shows it in an unrealistically positive light, since that LUT no longer fits in the L1 cache. But I admit that will depend a lot on the exact image content and CPU used.