It was 2018 when I first wrote a post about bench-marking in GNU Radio. This post will expand on that, focusing on one technology I am experimenting with (eBPF) and a bit hack.
This year I taught a class on High Performance Coding and one of the chapters introduces some bit hacks. Reading the excellent material from MIT 6.172 Performance Engineering of Software Systems, I stumbled upon the modular addition bit hack implementation. Considering that what I did in the previous post was trading a costly idiv operation for an unpredictable branch, I was tempted to test this new implementation.
Prelude: in the meantime I’ve updated, via PyBOMBS, GNU Radio to the 3.8 version that is based on Python 3.0, so some comparison with precedent results may be not straightforward.
Adding the new implementation to the code (src/gnuradio/gr-dtv/lib/dvbt/dvbt_viterbi_decoder_impl.cc) was trivial. Now our critical loop has three versions, the original one, the branch code, and the new bit hack.
// Trace back
for (i = 0, pos = store_pos; i < (ntraceback - 1); i++) {
// Obtain the state from the output bits
// by clocking in the output bits in reverse order.
// The state has only 6 bits
beststate = ppresult[pos][beststate] >> 2;
// original
// pos = (pos - 1 + ntraceback) % ntraceback;
// branch version
/*
pos = (pos - 1 + ntraceback);
if (pos >= ntraceback) {
pos -= ntraceback;
}
*/
// bithaks MIT 6.172 lec3 pg 31
pos = (pos - 1 + ntraceback) -
(ntraceback & -((pos - 1 + ntraceback)>=ntraceback));
}All versions compile without issues and perform the same logical function, but how to measure which one is faster? Last time I had a very complex and useful setup to do that, but now I have no intention to mount it again… So I have decided to play with eBPF and especially with its easy user space interface bpftrace. The basic idea is easy: using user space probes (uprobes) to instrument GNU Radio code dynamically! The practice is a little trickier and here is a guide for a future me about I did it.
For all tests, I always run the same command from the shell:
/usr/bin/python3 -u src/gnuradio/gr-dtv/examples/dvbt_rx_demo_8k.pywith this running, the first issue is discovering which dynamic library is actually used by Python. I did this with
lsof -p $(pgrep -n python3) | grep dtvthe output pointed out to lib64/libgnuradio-dtv.so.3.8.1.0.
Now that we have the library, we have to find the entry point.
nm lib64/libgnuradio-dtv.so.3.8.1.0 | grep sse2
000000000014ecd0 b _ZN2gr3dtv25dvbt_viterbi_decoder_impl16Branchtab27_sse2E
00000000000a7dd0 t _ZN2gr3dtv25dvbt_viterbi_decoder_impl28dvbt_viterbi_butterfly2_sse2EPhPDv2_xS4_S4_S4_
00000000000a8120 t _ZN2gr3dtv25dvbt_viterbi_decoder_impl28dvbt_viterbi_get_output_sse2EPDv2_xS3_iPh
00000000000a7d20 t _ZN2gr3dtv25dvbt_viterbi_decoder_impl29dvbt_viterbi_chunks_init_sse2EPDv2_xS3_gave the symbols I was looking for. Finally, with a short bpftrace script it is possible to instrument the entry and exit of the function and get an histogram of the elapsed time for each function call.
#!/usr/bin/bpftrace
// measure user space code
u:/prefix/2021/lib64/libgnuradio-dtv.so.3.8.1.0:_ZN2gr3dtv25dvbt_viterbi_decoder_impl28dvbt_viterbi_get_output_sse2EPDv2_xS3_iPh
{
@start[tid] = nsecs;
}
ur:/prefix/2021/lib64/libgnuradio-dtv.so.3.8.1.0:_ZN2gr3dtv25dvbt_viterbi_decoder_impl28dvbt_viterbi_get_output_sse2EPDv2_xS3_iPh
{
$duration_ns = (nsecs - @start[tid]);
@ns = lhist($duration_ns, 800, 1100, 10);
delete(@start[tid]);
}The official doc will explain you this script much better than what I can do here.
I compiled and ran the three versions of the code under the monitoring of bpftrace (Warning: times here are really short and probably a better technique should be to cumulate the execution times and count the number of calls, but this gives us a shape of the performance that is by itself interesting).
Original
@ns:
[940, 950) 228 |
[950, 960) 5023 |
[960, 970) 26051 |@@@@
[970, 980) 94472 |@@@@@@@@@@@@@@@@@
[980, 990) 237892 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[990, 1000) 250907 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1000, 1010) 211095 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1010, 1020) 152349 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1020, 1030) 129232 |@@@@@@@@@@@@@@@@@@@@@@@
[1030, 1040) 148754 |@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1040, 1050) 173736 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1050, 1060) 161507 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1060, 1070) 153057 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1070, 1080) 184757 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1080, 1090) 144384 |@@@@@@@@@@@@@@@@@@@@@@@@@@
[1090, 1100) 41826 |@@@@@@@
[1100, ...) 281678 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
Branch
@ns:
[880, 890) 33 |
[890, 900) 3517 |
[900, 910) 57634 |@@@@@@
[910, 920) 261212 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[920, 930) 436206 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[930, 940) 318410 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[940, 950) 228738 |@@@@@@@@@@@@@@@@@@@@@@@@@@@
[950, 960) 201788 |@@@@@@@@@@@@@@@@@@@@@@@@
[960, 970) 230723 |@@@@@@@@@@@@@@@@@@@@@@@@@@@
[970, 980) 265956 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[980, 990) 216438 |@@@@@@@@@@@@@@@@@@@@@@@@@
[990, 1000) 250648 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1000, 1010) 310401 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1010, 1020) 112340 |@@@@@@@@@@@@@
[1020, 1030) 49523 |@@@@@
[1030, 1040) 11963 |@
[1040, 1050) 3035 |
[1050, 1060) 1662 |
[1060, 1070) 1393 |
[1070, 1080) 1182 |
[1080, 1090) 1015 |
[1090, 1100) 725 |
[1100, ...) 191452 |@@@@@@@@@@@@@@@@@@@@@@
Bit Hack
@ns:
[880, 890) 12 |
[890, 900) 2281 |
[900, 910) 41715 |@@@@@
[910, 920) 223091 |@@@@@@@@@@@@@@@@@@@@@@@@@@@
[920, 930) 419862 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|
[930, 940) 292430 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[940, 950) 230511 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[950, 960) 208865 |@@@@@@@@@@@@@@@@@@@@@@@@@
[960, 970) 206896 |@@@@@@@@@@@@@@@@@@@@@@@@@
[970, 980) 275887 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[980, 990) 232744 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[990, 1000) 255698 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1000, 1010) 350489 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
[1010, 1020) 139624 |@@@@@@@@@@@@@@@@@
[1020, 1030) 66628 |@@@@@@@@
[1030, 1040) 20171 |@@
[1040, 1050) 5310 |
[1050, 1060) 2203 |
[1060, 1070) 1669 |
[1070, 1080) 1380 |
[1080, 1090) 1232 |
[1090, 1100) 873 |
[1100, ...) 243205 |@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ Nice to get fast and accurate stats on a so complex piece of software!! As always in performance optimization we are aiming at a moving target, but this tool is nevertheless very interesting and powerful. Without proper statistical analysis I cannot conclude that this optimization is a sure gain, but at least I have the data for doing the math.
