Recently I stumbled upon a question on stackoverflow, which asked how to vectorize computing symmetric difference of two sorted int32 arrays using AVX2. I decided to try doing it myself, and this post is about what I achieved. Of course, the best way to compute symmetric difference of sorted sets is by running ordinary merge algorithm (e.g. with std::merge) for the arrays plus some simple postprocessing. I'll concentrate only on the generic merging algorithm here.

I'll handle 32-bit integer keys only. Having keys of larger size would reduce significantly the efficiency of the algorithm (as usual with vectorization). Using 32-bit floating point keys is not much different from using integer keys; moreover, sorting 32-bit floats can be easily reduced to sorting 32-bit integers, which is often used to run radix sort on floating point data (see this and that). Also I'll briefly discuss the case when 32-bit values are attached to 32-bit keys (sorting without values is pretty useless in practice).

read more

Although Doom 3 was released 13 years ago, there is still of lot of interesting stuff to find in it. The main reason for that is: it was developed in the time of changes. The ID software team had just moved from C to C++ (using Visual C++ 6). Graphic cards were moving from fixed pipeline to programming pipeline, CPUs were getting SIMD extensions. All of this caused a lot of diversity in the code: crazy mix of C++/C/asm code, several renderer backends, code acceleration for MMX/SSE/AltiVec (yeah, Macs used PowerPC at that time). Not to mention tons of scripts and defs, including C++-like scripting language, and in-game GUI system.

I have to deal with Doom 3 engine in the context of The Dark Mod (TDM for short).

This article is about memory debugging configuration in Doom 3 SDK (more precisely, "Debug with inlines and memory log").

read more