[PATCH 3/3] Decompress the CRBB bitmap using tree based approach
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
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.
> 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...
Size: 819 bytes
Desc: Digital signature
More information about the osmocom-net-gprs