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(a)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(a)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