Microarchitecture rpm macros

During Hackweek 20 at SUSE I created some rpm macros to create packages easily that use the glibc-hwcaps feature. There’s a post with the journal from the hackweek in case you want to read it. Here I’ll just explain how to use the new macros I created.

The package definition

First you have to add a BuildRequires to use the macros:

BuildRequires:  microarch-rpm-macros

Then before the %description section, you have to add a line like:

%microarch_subpackage -n %{libname}

The %microarch_subpackage macro is used to generate the subpackage sections. It’s important that the parameter passed to it is the same as the parameter passed to the %package section that defines the library package. It’ll also generate the %files section with the same contents as the %files section in the library package but with the directory adapted to the microarchitecture of each subpackage.

The %build section

Let’s consider the following code in the build section:

autoreconf -fiv
%configure \
   --with-pic \
   --disable-static
make %{?_smp_mflags} CFLAGS="%{optflags}"

We will replace that with:

autoreconf -fiv
%{microarch_build %$configure \
  --with-pic \
  --disable-static
  make %{?_smp_mflags} CFLAGS="%{$optflags}"
}

The %microarch_build macro will take care of executing 4 times the code within to build the baseline version of the package and then the x86-64-v2, x86-64-v3 and x86-64-v4 versions, each in a different directory and with different %optflags values which include the respective -march and -mtune parameters in each case as well as different %_libdir values so the library is installed to the right place later in %install.

Note that %configure was replaced with %$configure and %{optflags} was replaced with %{$optflags}. This is done so that they’re not expanded before passing the arguments to %microarch_build .

Also note that the autoreconf execution was left out of the macro. This is so that the configure script is generated in the root source directory. Then the %microarch_build macro can generate build.x86-64-vN directories and put there the build files.

In my test with the bzip2 package I had a special case. If the %do_profiling boolean is set then code is built, the tests are executed and then the code is built again with the generated profiling information. The %build section used was:

%configure \
  --with-pic \
  --disable-static
%if 0%{?do_profiling}
  make %{?_smp_mflags} CFLAGS="%{optflags} %{cflags_profile_generate}"
  make %{?_smp_mflags} CFLAGS="%{optflags} %{cflags_profile_generate}" test
  make %{?_smp_mflags} clean
  make %{?_smp_mflags} CFLAGS="%{optflags} %{cflags_profile_feedback}"
%else
  make %{?_smp_mflags} CFLAGS="%{optflags}"
%endif

And I replaced that with:

%{microarch_build %$configure \
  --with-pic \
  --disable-static
%if 0%{?do_profiling} && "%{$microarch_current_flavor}" == "x86-64"
  make %{?_smp_mflags} CFLAGS="%{$optflags} %{cflags_profile_generate}"
  make %{?_smp_mflags} CFLAGS="%{$optflags} %{cflags_profile_generate}" test
  make %{?_smp_mflags} clean
  make %{?_smp_mflags} CFLAGS="%{$optflags} %{cflags_profile_feedback}"
%else
  make %{?_smp_mflags} CFLAGS="%{$optflags}"
%endif
}

Note that here again I used a $ within %{$microarch_current_flavor} so it can be replaced in each flavor with the right value.

The %install section

%install sections usually consist on running something like %make_install and then maybe installing some files manually. In this case, we would replace this:

%make_install pkgconfigdir=%{_libdir}/pkgconfig
install -Dpm 0755 foo %{buildroot}%{_bindir}/foo
install -m 0644 %{SOURCE2} %{buildroot}%{_mandir}/man1

with:

%microarch_install %make_install pkgconfigdir=%{_libdir}/pkgconfig
install -Dpm 0755 foo %{buildroot}%{_bindir}/foo
install -m 0644 %{SOURCE2} %{buildroot}%{_mandir}/man1

%microarch_install will run the argument passed to it 4 times but first it’ll run the microarch flavors and the baseline flavor will be run last.

Note that after the flavors are installed and before the baseline installation is done, it’ll remove all *.so files within the glibc-hwcaps directories since we don’t want development files in there.

The %check section

In the %check section packages usually run the generated binaries to test they work as expected. Note that we can’t do that for all flavors since we may not have a recent enough CPU to run them. Because of this, I opted to just check the baseline flavor.

Just replace

make %{?_smp_mflags} test

or anything you have to run from the build directory in %check with:

pushd %microarch_baseline_builddir
make %{?_smp_mflags} test
popd

And that should be enough for the simple case of bzip2 and similar packages.

Please note that this is work in progress and currently using the macros with %cmake or %meson will fail and is not supported yet. Check the conclusions on the previous post for information about what’s still missing.

Hackweek 20: glibc-hwcaps in openSUSE

This week we’ve held Hackweek 20 in SUSE so I’ll try to explain here what I’ve worked on. I recently noticed glibc 2.33 introduced hwcaps support which means it’s now possible to install libraries using an expanded cpu instruction set from recent CPUs in addition to the regularly compiled libraries and glibc will automatically choose the version optimized for the current cpu in use. This sounded very nice so I thought I’d try to work on that for my hackweek project.

My plan was to work at the package building level: Add/modify rpm macros to make it easy to build packages so that subpackages optimized for the different microarchitectures are (semi-)automatically generated and SUSE/openSUSE users can easily install those packages with optimizations for the specific cpu in use.

The preliminary tests

I began by creating a home:alarrosa:branches:hackweek:glibc-hwcaps project in obs to force gcc-11 to be used by default to build every package I wanted to test and then added a home:alarrosa:branches:hackweek:glibc-hwcaps:baseline subproject where I’d build baseline versions of packages and a home:alarrosa:branches:hackweek:glibc-hwcaps:x86-64-v3 project where I’d build the packages using `-march=x86-64-v3 -mtune=skylake` so they’re optimized for my cpu and I can measure the speed improvement.

I first thought I’d benchmark converting an x264 file to x265 using ffmpeg, so I built fdk-aac, libx264, x265 and ffmpeg-4 in both projects (baseline and x86-64-v3). The results were practically the same with both versions but that was partly expected since ffmpeg and most video libraries usually already contain code to check the current cpu and run code specifically optimized for it in assembly.

So I thought I should try a C/C++ library that’s not video-related, which brought me to building baseline and x86-64-v3 versions of libpng16, poppler, cairo and freetype2 libraries.

I then executed the following command to render png files for each page of a large pdf file using both sets of libraries:

time pdftocairo asio.pdf -png

The results were:

  • 325.618 seconds (mean over 3 runs with 1.235 seconds of difference between the min and max results) for the baseline version.
  • 336.672 seconds (mean over 4 runs with 0.664 seconds of difference between the min and max results) for the x86-64-v3 version

Yes, you read that right. Unexpectedly, the optimized version was noticeably slower. I got a bit frustrated with that result but still thought that it might be related to problems with the current version of the compiler that might be fixed in the future, so it might be worth to continue working on the project.

A quick test for glibc-hwcaps

I created a really small libbar dynamic library with a function that prints a message on the screen, built it three times with three different messages and put each of them into /usr/lib64, /usr/lib64/glibc-hwcaps/x86-64-v2 and /usr/lib64/glibc-hwcaps/x86-64-v3 . I then did a small foo binary that linked to libbar and called that function. Making only some of the libraries available worked as expected so I confirmed that glibc-hwcaps support worked as expected.

The microarch rpm macros

At this point (it was already wednesday afternoon), I could start working on the rpm macros. In order to test them, I created yet another project at home:alarrosa:branches:hackweek:glibc-hwcaps:test . In there I created a new package microarch-rpm-macros that would install … well… the rpm macros 🙂 and then another package called microarch that would be used on one hand to generate a microarch-filesystem package that owns the new directories /usr/lib64/glibc-hwcaps and /usr/lib64/glibc-hwcaps/x86-64-v[234] and 3 other packages (microarch-x86-64-v2, microarch-x86-64-v3 and microarch-x86-64-v4) that you’ll see in a moment what they’re used for.

I worked on the rpm macros and these packages on Thursday and Friday and by 19:00 on Friday I got everything working.

I’ll explain the rpm macros I created on my next post so that it can be used as a reference without having all the explanations in this post about the story to develop them.

The rpm macros built the package four times with different optimization flags, generated all three subpackages with the optimized versions, put the library files in place and then adding the repository from the test obs project I could do:

sudo zypper in microarch-x86-64-v3
Loading repository data…
Reading installed packages…
Resolving package dependencies…

The following 2 NEW packages are going to be installed:
 libbz2-1-x86-64-v3 microarch-x86-64-v3

2 new packages to install.
Overall download size: 52.6 KiB. Already cached: 0 B. After the operation, additional 74.4 KiB will be used.
Continue? [y/n/v/…? shows all options] (y):

So just installing the microarch-x86-64-v3 package pulls in all optimized packages for that microarchitecture automatically.

Conclusions

I consider the hackweek project was a partial success. I did what I wanted in the original plan and it works well. There’s still work to do of course:

  • The rpm macros need to be polished (a lot) before submitting them to Factory.
  • More packages apart from bzip2 should be adapted to use them.
  • The macros will need to be adapted to more use cases. For example, using cmake or meson to build a package with the %microarch* macros is not tested and I have no doubts it’ll fail. Fortunately, now that the main work is done I think this will be easy to implement.
  • I need to provide NOOP versions of the macros for other architectures since currently they just fail to build packages on anything different than x86-64 (does glibc-hwcaps support microarchitectures for other architectures?)

And then, even if I work on all points above there’s still the main issue of the optimized libraries being slower than the baseline ones. In any case, once this issue is solved, all this should bring some benefits to our distributions. And the project was also useful to have a confirmation that using optimization flags doesn’t always means that the generated code will be faster.

Before ending I’d like to thank Florian Weimer, Michael Matz, Dario Faggioli, Albert Astals and Dan Čermák for their valuable input on this project as well as Matěj Cepl, Ben Greiner and the rest of the authors of the great openSUSE python singlespec macros which are the inspiration of this project.

Optimizing a Python application with C++ code

I’ve been working lately in a command line application called Bard which is a music manager for your local music collection. Bard does an acoustic fingerprinting of your songs (using acoustid) and stores all song metadata in a sqlite database. With this, you can do queries and find song duplicates easily even if the songs are not correctly tagged. I’ll talk in another post more about Bard and its features, but here I wanted to talk about the algorithm to find song duplicates and how I optimized it to run around 8000 times faster.

The algorithm

To find out if two songs are similar, you have to compare their acoustic fingerprints. That seems easy (and in fact, it is), but it’s not as straightforward as it seems. A fingerprint (as acoustid calculates it) is not just a number, but an array of numbers, or better said, an array of bits, so you can’t just compare the numbers themselves, but you have to compare the bits in those numbers. If all bits are exactly the same, the songs are considered the same, if 99% of bits are the same then that means there’s a 99% chance it’s the same tune, maybe differing because of encoding issues (like one song being encoded as mp3 with 192 kbits/s and the other with 128 kbits/s).

But there are more things to have in mind when comparing songs. Sometimes they have different silence lengths at the beginning or end, so the bits that we compare are not correctly aligned and they don’t match as they are calculated, but could match if we shifted one of the fingerprints a bit.

This means that to compare two songs, we don’t just have to compare the two fingerprints, but then we have to simulate increasing/decreasing silence lengths at the beginning of a song by shifting its fingerprint and calculate the match level for each shift to see if we improve/worsen the similarity percentage.  Right now, Bard shiftes the array by 100 positions in one direction and then another 100 positions in the other direction, this means that for each song we have to compare the two fingerprints 200 times.

Then, if we want to compare all of the songs in a collection to find duplicates, we need to compare the songs with ID 1 and 2, then we need to compare the song with ID 3 with IDs 1 and 2, and in general, each song with all previous ones. This means for a collection with 1000 songs we need to compare 1000*1001/2 = 500500 songs (or 100100000 fingerprints).

The initial python implementation

Bard is written in python, so my first implementation used a python list to store the array of integers from the fingerprint. For each iteration in which I have to shift the array numbers I prepend a 0 to one fingerprint array and then iterate over them comparing each element. To do this comparison, I xor the two elements and then use a standard good known algorithm to count the bits which are set in a integer:

def count_bits_set(i):
    i = i – ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

Let’s use the speed of this implementation as a reference and call it 1x.

First improvement

As a first improvement I tried replacing that bit counting algorithm with gmpy.popcount which was faster and also improved the algorithm by introducing a canceling threshold. This new algorithm stops comparing two fingerprints as soon as it’s mathematically impossible to have a match over the canceling threshold. So for example, if we are iterating the fingerprints and we calculate that even if all remaining bits would match we wouldn’t get at least a 55% match between songs, we just return “different songs” (but we still need to shift songs and try again, just in case).

With these improvements (commit) the comparisons ran at nearly an exact 2x speed.

Enter C++17

At that time,  I thought that this code wouldn’t scale nicely with a large music collection, so I thought Bard needed a much better implementation. Modifying memory is slow and C/C++ allows for much fine grained low-level optimizations, but I didn’t want to rewrite the application in C++ so I used Boost.Python to implement just this algorithm in C++ and call it from the python application. I should say that I found really easy to integrate methods in C++ with Python and I absolutely recommend Boost.Python .

With the new implementation in C++ (commit) I used STL’s vector to store the fingerprints and I added the maximum offsets in advance so I didn’t need to modify the vector elements during the algorithm and I access elements by simulating the shifting offsets. I also use STL’s map to store all fingerprints indexed on a song ID. Finally, I also added another important optimization which is using the CPU’s instructions to calculate bits set by using gcc’s __builtin_popcount.

The best part of this algorithm is that during the comparison algorithm itself, no fingerprint is copied or modified, which translated in a speed of 126.47x . At this point I started calculating another measure: songs compared per second (remember we’re doing 200 fingerprints comparison for each pair of songs). This algorithm gave an average speed of 580 songs/second. Or put another way, to compare our example collection of 1000 songs, this would take 14 min 22 sec (note that we can calculate the original implementation in Python would take approximately 1 day, 6 hours, 16 minutes and 57 seconds).

First try to parallelize the algorithm

I use an i7 CPU to run Bard and I always thought it was a pity that it only used one CPU. Since the algorithm that compares two songs doesn’t modify their data anymore, I thought it might be interesting to parallelize it to allow it to run in all 8 cores at the same time and just coalesce the result of each independent iterations. So I wondered how to do it and noticed that when I compare each song with all previous ones, this is done using a for loop that iterates over a std::map containing all songs that are already processed. Wouldn’t it be nice to have a for-each loop implementation that runs each iteration on a different thread? Well, there is! std::for_each in C++17 allows to specify an ExecutionPolicy with which you can tell it to run the iterations in different threads. Now the bad news: This part of the standard is not completely supported by gcc yet.

So I searched for a for_each implementation and found this stackoverflow question which included one. The problem is that the question mentions the implementation was copied from the C++ Concurrency in Action book and I’m not sure of the license of that code, so I can’t just copy it into Bard. But I can make some tests with it just for measurements purposes.

This increased the speed to 1897x or ~8700 songs/second (1000 songs would be processed in 57 seconds). Impressive, isn’t it? Well… keep reading 🙂

Second parallelization try

So I needed to find a parallelized for_each version I could use. Fortunately I kept looking and found out that gcc includes an experimental parallel implementation of some algorithms in the C++ standard library which includes __gnu_parallel::for_each (there are more parallelized algorithms documented in that page). You just need to link to the openmp library.

So I ran to change the code to use it and hit a problem: I used __gnu_parallel::for_each but every time I tested, it only ran sequentially! It took me a while to find out what was happening, but after reading the gcc implementation of __gnu_parallel::for_each I noticed it required a random access iterator, but I’m iterating on a std::map and maps have a bidirectional iterator, not a random-access one.

So I changed the code (commit) to first copy the fingerprints from the std::map<int, std::vector<int>> to a std::vector<std::pair<int,std::vector<int>>> and with just that, the same __gnu_parallel::for_each line ran using a pool of 8 threads.

The gcc implementation proved to be faster than the implementation in the stackoverflow question, with a speed of 2442x , ~11200 songs/second and 44 seconds.

The obvious but important improvement I forgot about

While looking at the compiler build Bard I noticed I wasn’t using compiler flags to optimize for speed! So I tested adding -Ofast -march=native -mtune=native -funroll-loops to the compiler (commit). Just that. Guess what happened…

The speed raised to a very nice  6552x, ~30050 songs/second and 16 seconds.

The Tumbleweed improvement I got for free

I’m running openSUSE Tumbleweed in the system I use to develop which as you probably know, is a (very nice) rolling release distribution. One day, while doing these tests, Tumbleweed updated the compiler from gcc 7.3 to using gcc 8.1 by default. So I thought that deserved another measurements.

Just changing the compiler to the newer version increased the speed to 7714x, 35380 songs/second and 14 seconds.

The final optimization

An obvious improvement I didn’t do yet was replacing the map with a vector so I don’t have to convert it before each for_each call. Also, vectors allow to reserve space in advance, and since I know the final size the vector will have at the end of the whole algorithm, I changed to code to use reserve wisely.

This commit gave the last increase of speed, to 7998x, 36680 songs/second and would fully process a music collection of 1000 songs in just 13 seconds.

Conclusion

Just some notes I think are important to keep in mind from this experience:

  • Spend some time thinking how to optimize your code. It’s worth it.
  • If you use C++ and can afford to use a modern compiler, use C++17, it allows you to make MUCH better/nicer code, more efficiently. Lambdas, structured bindings, constexpr, etc. are really worth the time spent reading about them.
  • Allow the compiler to do stuff for you. It can optimize your code without any effort from your side.
  • Copy/Move data as little as possible. It’s slow and many times it can be avoided just by thinking a bit on data structures before starting developing.
  • Use threads whenever possible.
  • And probably the most important note: Measure everything. You can’t improve what you can’t measure (well, technically you can, but you won’t know for sure).