Profiling data of decoding EPDAN compressed bitmap

Holger Freyther holger at
Wed Jul 13 09:43:06 UTC 2016

> On 23 Jun 2016, at 16:39, Pravin Kumaravel Manoharan <Pravin.Manoharan at> wrote:

Dear Parvin,

> Following is the profiling results comparison of the decoding algorithms (unit in micro-seconds). Each of the 4 test inputs is decoded 10000 times for getting below data.

> Important summary:
> 1. For few other identified test vectors existing algorithm fails functionally to decode whereas tree based decoding algorithm succeeds.
> 2. Details of these test vectors are in the latest patch available in users/pravin/epdan_profiling at

I used it from the testcase you added on gerrit and re-added osmo_t4_decode to it. More about results later:

> 3. From the above results it shows that Tree based decoding algorithm is better than existing algorithm for the decoding time consumed.
> 4. The max value is not included because it is abnormally high which occurs at very low frequency like once in 10000 iterations.

max. Well without distribution this argument is difficult. With a tree we will "jump" through memory a lot more than with a table. E.g. outside a microbenchmark the numbers might not be that stable.

Anyway on sysmoBTS #1 with nightly build as of today/yesterday and 89ce5adbe881f4292d5bd5bfc85bd142b3fb4151 (from gerrit refs/changes/17/417/2). Modified to disable verification and 100000 iterations. The difference is big enough.

root at sysmobts-v2:~# time ./TbfTest.TREE 

real	0m24.754s
user	0m22.940s
sys	0m1.790s
root at sysmobts-v2:~# time ./TbfTest      

real	1m15.535s
user	1m13.100s
sys	0m1.730s

perf report -i 

 33.00%  TbfTest.TREE  [.] bitvec_set_bit_pos
 20.46%  TbfTest.TREE  TbfTest.TREE          [.] bitvec_write_field(bitvec*, unsigned int&, unsigned long long, unsigned int)
 14.30%  TbfTest.TREE  [.] bitvec_set_bit
  9.94%  TbfTest.TREE  TbfTest.TREE          [.] search_runlen(node*, unsigned char const*, unsigned char, unsigned char*, unsigned short*)
  5.27%  TbfTest.TREE  TbfTest.TREE          [.] Decoding::decompress_crbb(signed char, unsigned char, unsigned char const*, bitvec*)
  4.97%  TbfTest.TREE  [.] 0x0000523c
  4.29%  TbfTest.TREE  TbfTest.TREE          [.] 0x000023a8

perf report -i

 57.51%  TbfTest  [.] osmo_t4_decode
 12.09%  TbfTest  [.] bitvec_shiftl
 10.63%  TbfTest  [.] bitvec_set_bit_pos
  4.49%  TbfTest  [.] bitvec_set_bit
  4.17%  TbfTest  [.] bitvec_fill
  3.62%  TbfTest  [.] 0x00004d88
  2.21%  TbfTest  [.] bitvec_get_int16_msb
  1.60%  TbfTest          [.] memcpy
  0.68%  TbfTest  [kernel.kallsyms]     [k] read_cycles

Conclusions and comments in the next mail.


More information about the osmocom-net-gprs mailing list