[PATCH 3/3] Decompress the CRBB bitmap using tree based approach

Neels Hofmeyr nhofmeyr at sysmocom.de
Thu Mar 31 13:51:23 UTC 2016


On Thu, Mar 31, 2016 at 01:04:36PM +0200, Max wrote:
> Hi and thanks for detailed write-up.
> 
> So the code do exactly the same thing just more efficiently under the
> assumption that gcc optimization is not working.

Correct me if I'm wrong, but I firmly assume gcc optimization wouldn't
implement a tree search algorithm for looking up items in a struct, when
our code walks the struct linearly.

> Is there a way to quantify this potential difference?

Hard besides timing, I guess, and we know how flaky timing based
assumptions in a test suite can be. We'd have to count comparisons or
something, i.e. add code just to prove efficiency. Let's not.

> More specifically - is there a test-case which could demonstrate that
> this difference actually matters in practice?
> 
> I mean if the code in question constitute, for example, 10% of cpu time
> spent by osmo-pcu and the replacement would shrink it to 2% it's one thing.
> If it's 0.1% and 0.001% it's another: the relative gain in the latter
> case is bigger but I'm not sure it justifies allegedly higher code
> complexity.

I'm with Sangamesh here: if 176 comparisons reduce to 4 comparisons
(factor 44!), and assuming a compression algorithm would do this for a
whole stream of message bits, IMHO this justifies code complexity. Right?

I must reserve the fact that I still haven't read the entire code in
detail, I'm just arguing theoretically.

~Neels

> 
> On 03/31/2016 12:51 PM, Sangamesh Sajjan wrote:
> > Hello Max,
> >
> > On Wednesday, March 30, 2016 9:05 PM, Max Suraev wrote:
> >
> >> Thank you for your contribution. Could you clarify - what's the advantage of this approach over existing osmo_t4_decode() function?
> > To highlight the difference between osmo_t4_decode and Tree based approach consider the example below,
> >  
> > if the received code word from the bitmap is “0111” and 0’s color code, then following steps involved to find run length using osmo_t4_decode
> > 1.	Initially it finds the number of bits based on the color code ( i.e if it is 0 color code, then read 2 bits  or  4 bits if it is 1 color code )
> > 2.	Since it is 0’s color code, read 2 bits from the  received encoded bitmap
> > 3.	Check whether received 2 bits matches to any of the table entry ( i.e Makeup or  Terminating table), if it doesn’t match then increment one more bit.
> > o	This will require loop of 15 followed by 64, So total of 79 comparison 
> > 4.	Repeat the 3rd step if there is no matching code word
> >
> > Hence to find 0111 code word from the table, osmo_t4_decode would require
> > Two iterations of makeup table ( i.e 15 times each ) and terminating table ( i.e 64 times each) = ((15 + 64 )* 2 ) = 158
> > Third iteration where in exact match of code word is found in terminating table 3rd  position = 15+3  
> >  So total 176 comparisons required to find the run length.
> >
> >  Usually there will be multiple code words in the received bitmap and each require multiple iterations to find run length as explained above.
> >
> > Whereas In tree based approach two trees (i.e. ones list and zero list ) are used and entire code word traversing shall be done in respective tree in single traversal based on color code.
> > •	Read every bit from the received encoded bitmap and traverse the tree generated in init, If the bit is 0 traverse left and if it is 1 traverse right, Repeat this procedure till we find valid run length.
> > •	In example above for “0111” only 4 comparisons are required 
> >
> > Hence we see advantage in using tree based approach for CRBB decoding.
> >
> >> Is there some test case which works for one but not the other?
> > Currently we don’t have this specific test.
> >  
> > Regards,
> > Sangamesh
> >
> 
> -- 
> Max Suraev <msuraev at sysmocom.de> http://www.sysmocom.de/
> ======================================================================= 
> * sysmocom - systems for mobile communications GmbH
> * Alt-Moabit 93 
> * 10559 Berlin, Germany
> * Sitz / Registered office: Berlin, HRB 134158 B 
> * Geschaeftsfuehrer / Managing Directors: Holger Freyther, Harald Welte 
> 

-- 
- Neels Hofmeyr <nhofmeyr at sysmocom.de>          http://www.sysmocom.de/
=======================================================================
* sysmocom - systems for mobile communications GmbH
* Alt-Moabit 93
* 10559 Berlin, Germany
* Sitz / Registered office: Berlin, HRB 134158 B
* Geschäftsführer / Managing Directors: Holger Freyther, Harald Welte
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: Digital signature
URL: <http://lists.osmocom.org/pipermail/osmocom-net-gprs/attachments/20160331/17b1a084/attachment.bin>


More information about the osmocom-net-gprs mailing list