4
\$\begingroup\$

Given a heap of pixel data, and a width and height associated with that pixel data, I've written code which will save that data as an image, and it more-or-less works as expected.

//I'm using the FreeImage library.
#include<freeimage.h>

/*Some other, irrelevant code*/

namespace filesystem = std::experimental::filesystem;

//'heap' is an object wrapping around a std::vector<uint8_t> which allows me to query its 
//width and height, as opposed to its "size"
void save_image(filesystem::path path, font_heap const& heap) {
    uint32_t width = heap.get_width(), height = heap.get_height();
    FIBITMAP * image = FreeImage_Allocate(width, height, 8);

    BYTE * bits = (BYTE*)FreeImage_GetBits(image);
    auto it = stdext::make_checked_array_iterator(bits, width * height);
    //BEGIN CONCERNING CODE
    for (size_t y = 0; y < height; y++) {
        it = std::transform(
            heap.begin() + (height - y - 1) * width,
            heap.begin() + (height - y) * width,
            it,
            [](uint8_t val) {return 255 - val; }
        );
    }
    //END CONCERNING CODE

    FIMEMORY * memory = FreeImage_OpenMemory();
    FreeImage_SaveToMemory(FIF_PNG, image, memory);
    BYTE * raw_memory;
    DWORD size;
    FreeImage_AcquireMemory(memory, &raw_memory, &size);
    std::ofstream file(path, std::ios_base::binary);
    file.write(reinterpret_cast<char *>(raw_memory), size);
    FreeImage_CloseMemory(memory);
    FreeImage_Unload(image);
}

But, aside from some trivial optimizations in surrounding parts of the code (which don't concern me because they make up a tiny proportion of CPU time), the code in the for loop is most troubling to me:

auto it = stdext::make_checked_array_iterator(bits, width * height);
for (size_t y = 0; y < height; y++) {
    it = std::transform(
        heap.begin() + (height - y - 1) * width,
        heap.begin() + (height - y) * width,
        it,
        [](uint8_t val) {return 255 - val; }
    );
}

What needs to happen in this code is

  • All the rows need to be swapped, because images are saved x→, y↓, but the data is saved in memory as x→, y↑
  • The colors need to be inverted, because the image is a raw grayscale image, and the image should be black with a white background (but is saved in data as white with a black background).

The code does what I'm expecting, but it requires a rather significant amount of CPU overhead to do it, and I'd like to know if there's a better solution.

  • Are there STL algorithms that I could/should be using instead of std::transform? Maybe stuff to use alongside std::transform?
  • Is there a way to eliminate the surrounding for-loop? I can't use reverse iterators, because the row ordering needs to be reversed, but the column ordering needs to stay the same.
  • Are there FreeImage functions/options I could/should be using to make this code faster? Have I included needlessly redundant steps in my process of saving the image to disk?
  • Can this be multithreaded without the overhead outweighing the performance gains? (Also, this code is meant to be used in an environment where there already exist other threads, and I don't want to introduce significant slowdowns to those other threads)
  • Are there any CUDA/OpenCL/Vulkan Compute solutions that won't add significant overhead to this problem?
\$\endgroup\$
  • \$\begingroup\$ Why not use fipImage.invert and fipImage.flipVertical? \$\endgroup\$ – user650881 Jan 10 '17 at 11:06
  • \$\begingroup\$ @user650881 It's not clear from the documentation: do those functions toggle a flag in the image, which affects how the data is saved to disk, or do they perform the per-pixel transformations? Because if it's the latter, I doubt I'll gain performance from those operations. \$\endgroup\$ – Xirema Jan 10 '17 at 16:29
  • \$\begingroup\$ I shall try same code on intel hd 400 which has 12 compute units. whats the image size? how many bytes per pixel? \$\endgroup\$ – huseyin tugrul buyukisik Feb 20 '17 at 21:27
2
\$\begingroup\$

Here is some OpenCl test on Intel HD Graphics 400 with 12 compute units and using 1-channel 1600 MHz ddr3 ram:

timings include buffer copies. No mapping was used. With memory mapping, it would drop to much lower time.

Edit: fixed the mapped buffer accessing, it is even faster now(laptop battery nearly empty)

  • 1 byte per pixel
  • 1024 x 1024: 4.5 ms (1.52 ms with mapping)

  • 2048 x 2048: 9.7 ms (4.19 ms with mapping)

  • 4096 x 4096: 21 ms (13.93 ms with mapping)

  • 8192 x 8192: 65 ms (55.16 ms with mapping)

kernel code(number of threads are half of total pixels, each thread swap uppermost line's pixel with bottommost line's pixel):

__kernel void test0(__global char *imagebuf)
{
        int i=get_global_id(0);
        int height=8192;
        int width=8192;
        int y=i/width;
        int x=i%width;
        char tmp=255-imagebuf[((height-y)-1)*width+x];
        char tmp2=255-imagebuf[x+y*width];
        imagebuf[x+y*width]=tmp;
        imagebuf[((height-y)-1)*width+x]=tmp2;
}

throughput increases for larger images and minimum latency depends on hardware and opencl wrapper thickness. This example was run on a not-thin wrapper.

One of the pros, cpu can be used for other things when gpu is computing this.

One of the cons, depending on the image size, completion time will have variance.

Kernel has low compute to data ratio so it will not be faster for computers with same pci-e bandiwdth.(just tried with a r7-240, 8k_8k took 67 ms)

\$\endgroup\$
  • \$\begingroup\$ I forgot to add that my opencl wrapper was using 16bit elements instead of chars from host side so it might be even faster.(it was optimized for floats, not chars, my bad) \$\endgroup\$ – huseyin tugrul buyukisik Feb 21 '17 at 17:46
1
\$\begingroup\$

I can see several ways to improve the speed of that loop. While I'm all for using the GPU, there are a bunch of easier more practical things to do before going that far.

memcpy

On most platforms, the C standard library memcpy() function is highly optimized. It will be much faster than copying a single byte at a time. If you have the space for it, it might be faster to make a second memory array and use memcpy to copy each line from the original image into its inverted Y position in the new image. Then run through the new image and invert the colors. Profiling will tell you if it's faster or not.

Work on more at once

Heck, even using a 32-bit or 64-bit data type (careful at the ends!) for doing your copies would be a win. You get 4 to 8x as many copies done in a single instruction.

You can also work on more than one byte at a time when inverting the colors by using SIMD instructions. (On Intel architectures this would be SSE or AVX instructions.)

Parallel processing

Depending on the size of your images, it might make sense to write some multithreaded code to process many sections of the image at a time. For example, if you have 4 cores in your machine, you could have each one work on 1/4th of the image. (This is obviously easier for the color inversion than the Y inversion.)

Don't Do Any Work

The fastest way to get work done is to already have it done. Why are your images inverted (both in color and in space) in the first place? Is there any way you could create them correctly so you don't have to flip them and make a negative? If so, that's probably the right thing to do, but I'm sure there are other considerations.

\$\endgroup\$
  • \$\begingroup\$ avx optimized code would be fast enough, scavenging and altering assembly codes of memcpy. my answer was for just in case no cpu cores available \$\endgroup\$ – huseyin tugrul buyukisik Feb 21 '17 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.