This is merely a historical archive of years 2008-2021, before the migration to mailman3.
A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/osmocom-net-gprs@lists.osmocom.org/.
Neels Hofmeyr nhofmeyr at sysmocom.deOn 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>