This is a programming task given to candidates interviewing at Numfum GmbH to complete from home, taking as long as they need. The code is a snippet from Basis Universal (copyright 2019-2021 Binomial LLC, released under an Apache 2.0 license). The original code is extracted from the ETC1S to DXT transcoder and turned into this standalone sample.
The task is to optimise the table generation in create_etc1_to_dxt1_6_conversion_table() (in main.cpp), showing timings before and after. Example timings from the unoptimised code for comparison:
| Machine | OS | CPU | Compiler | Time |
|---|---|---|---|---|
| Mac Pro (Late 2013) | Windows 10 | Intel Xeon E5 | MSVC 19 | 408ms |
| Mac Pro (Late 2013) | macOS Big Sur | Intel Xeon E5 | Clang 13 | 326ms |
| Talos II | Debian Buster | IBM Power9 | GCC 10 | 289ms |
| MacBook Pro (2021) | macOS Monterey | Apple M1 Max | Clang 13 | 158ms |
These numbers should give you an idea of what to expect on different architectures (and also compilers and OSes).
For macOS/Linux build with:
cc -Wall -Wextra -O3 -g0 main.cpp
For Windows, in a Visual Studio Command Prompt, build with:
cl /W3 /wd4576 /Ox main.cpp
For Emscripten build with:
emcc -Wall -Wextra -O3 -g0 -s SINGLE_FILE=1 main.cpp -o out.html
Feel free to tweak the compiler flags, -flto or /GL for example, or target a specific CPU with -mcpu=power9, /arch:AVX2, etc., but both optimised and unoptimised runs should be compared with the same flags.
(The Windows/MSVC warning C4576 is for the initialiser list syntax.)
Alternatively you can use CMake to perform command-line builds for macOS, Linux and Windows:
cmake -B out -DCMAKE_BUILD_TYPE=Release
cmake --build out --config Release
And also Emscripten:
emcmake cmake -B out -DCMAKE_BUILD_TYPE=Release
cmake --build out --config Release
Or generate a Visual Studio solution, for example:
mkdir out
cd out
cmake .. -G "Visual Studio 16 2019"
task-opt1.sln
The following limits are imposed:
- Use a single thread. Whilst the code can be parallelised with ease, the task is to see what optimisations can be applied to the table generation.
- Generate the table. The ultimate unbeatable optimisation is to simply include the pre-generated table, but that defeats the task (BasisU's code already includes the pre-generated table).
- It must compile with Clang/GCC/MSVC. Again, an easy route would be compiling with
ispcor similar SPMD compilers, but this would also defeat the task. It would be interesting to compare the results though. - No using OpenMP's
#pragma omp parallelor similar libraries or preprocessors. - The before and after comparison should be on the same hardware under the same conditions and with the same compiler (otherwise, from the table above, a 2.5x speed-up can simply be had by using a newer machine).
Any SIMD optimisations can be for an architecture of your choice, the interesting point being the before and after timings. We have implementations for SSE4.1, Neon and Wasm. Any questions, feel free to ask.
The original code is a greedy algorithm to determine the best colour matches for a given ETC1S block when transcoding to DXT. In BasisU these matches are generated ahead of time and stored as tables (5- and 6-bit tables for DXT1), so this code is only ever run if the tables need regenerating. When assessing BasisU we looked at various ways of reducing the binary size, and generating the tables at runtime was considered. During the process it became a fun distraction for us in-house as a way of flexing optimisation skills amongst colleagues!