Optimizing Deconstructed Image. From art to Analytics (part I)

Background of Deconstructed Image

Many of my contacts and friends are aware of my non-professional activity blending two of my passions: 𝗮𝗿𝘁 and 𝗰𝗼𝗺𝗽𝘂𝘁𝗮𝘁𝗶𝗼𝗻. You might have seen my TEDx talk where I described how I was “pushed” into the area of algorithmic art and Deconstructed Image. After some time developing an open-source 3D virtual gallery I decided months ago to get back to my image deconstruction project. It has been an incredible opportunity to practice one of my best skills: problem solving.

For those of you unaware, my algorithmic art project tries to reorganize the pixels of a digital image based on given loss function. It is a blantly untractable optimization problem, with a number of combinations beyond any reasonble unreasonable number, so it that can only be tackled from meta-heuristics approaches. Getting remarkable solutions imply running billions, trillions, quadrillion iterations. Sky is the limit.

Initial algorithm

Back to the initial algorithm development, done in 𝗠𝗮𝘁𝗹𝗮𝗯, I was happy to reach (hardly) the 1 us per iteration benchmark. In the new develoment I was aiming to reduce the iteration time x10, in order to generate high resolution images. 𝙾̲𝚑̲ ̲𝚋̲𝚘̲𝚢̲,̲ ̲𝚠̲𝚑̲𝚊̲𝚝̲ ̲𝚊̲ ̲𝚓̲𝚘̲𝚞̲𝚛̲𝚗̲𝚎̲𝚢̲. I will develop the story into several posts, but let’s see a high level overview:

• I started redesigning the code completely, still in Matlab, just to realize it was slower than before 😣. At least it created data structures that helped debugging it.
• Moving away from 𝗠𝗮𝘁𝗹𝗮𝗯, I decided to learn 𝗠𝗼𝗷𝗼 (the new compiled high performance Python). It proved me I could go beyond the 0.5 us mark. It is indeed fast but it was extremely frustrating to interpret the compiler errors and when an update changed the definition of pointers, I gave up. It needs to settle down and stabilize the code base.
• After thinking about C, C++, Rust or even good old Fortran, I decided to port the code to 𝗖++. I got close to 0.7 us/iteration. That was not enough so I learnt 𝗺𝘂𝗹𝘁𝗶𝘁𝗵𝗿𝗲𝗮𝗱𝗶𝗻𝗴.
• I faced all the academic issues of multi-threading, from 𝗺𝘂𝘁𝗲𝘅 to 𝘀𝗽𝗶𝗻𝗹𝗼𝗰𝗸𝘀 and the producer-consumer problem. I hit a wall on the 0.4 us. I always thought that this was indeed a non-parallelizable problem and proved to be rather true. When it was not context switching, it was memory bandwidth or atomic variables overhead.
• Finally, I removed all the concurrent access code but kept all the optimizations created in the journey, to realize that the single-thread task could go around the 100 ns mark. Mission accomplished.

𝗢𝘁𝗵𝗲𝗿 𝗸𝗲𝘆 𝗹𝗲𝗮𝗿𝗻𝗶𝗻𝗴𝘀:

1. 𝗣𝗼𝘀𝗶𝘁𝗶𝘃𝗲 𝘀𝘂𝗿𝗽𝗿𝗶𝘀𝗲𝘀: how much C++ has changed, the Tracy profiler (and VTune), CMake and Windows Subsystem Linux.
2. 𝗡𝗲𝗴𝗮𝘁𝗶𝘃𝗲 𝘀𝘂𝗿𝗽𝗿𝗶𝘀𝗲𝘀: how tough is to debug multidimensional data in C++
3. 𝗟𝗟𝗠𝘀 𝗲𝘅𝗽𝗲𝗿𝗶𝗲𝗻𝗰𝗲: for high-end algorithm development, it is not fit for the task. It is not a Phd coder but rather an assistant that does things well when micro-managed. (tbc)

Continue to part 2.