17 Mar
2016
17 Mar
'16
4:43 p.m.
Hello,
In current master code base 5 different arrays are used for compression as described
below,
* Two dimensional array is used to store terminating code words for 1's length
code and 0's length code.
* Two dimensional array is used to keep size of each codeword
* Two dimensional array is used to store make up code words
* Two dimensional array is used to keep size of each codeword of makeup code
words
* one array for each code word to return corresponding value for makeup code
words
We are proposing following modification for above,
* Array of strings shall be used for 1's run length code word
* Array of strings shall be used for 0's run length code word
These two arrays will have code words of both terminating codes and make up codes
together.
In this approach two trees (i.e ones list and zero list) shall be introduced and entire
code word traversing shall be done in respective tree in single traversal.
With this approach we can avoid multiple array usage.
The above changes will be sent in my next patch
Regards,
Sangamesh
18 Mar
18 Mar
11:28 a.m.
On Thu, Mar 17, 2016 at 03:43:36PM +0000, Sangamesh Sajjan wrote:
We are proposing following modification for above,
* Array of strings shall be used for 1's run length code word
* Array of strings shall be used for 0's run length code word
These two arrays will have code words of both terminating codes and make up codes
together.
In this approach two trees (i.e ones list and zero list) shall be introduced and entire
code word traversing shall be done in respective tree in single traversal.
With this approach we can avoid multiple array usage.
Hi Sangamesh,
though I'm not entirely familiar with the compression algorithm, I'm
pretty sure that using an array of strings to store bits will make the
code less efficient by magnitudes.
If I have bits in a primitive like an int, I can compare them to other
bits with a single CPU clock cycle. Even if they are shifted/fragmented to
a different bit position, using shl or shr (<< or >>) and comparing
int-wise will be extremely faster than iterating an array of chars of '1'
and '0' and interpreting those as 1 and 0.
I do see that it might make the code arrays easier to read and understand
for humans, but that wouldn't make up for the humungous performance loss
you're inflicting at the same time.
Please correct me if I'm missing something, but my guess is that you're on
the verge of an abyss here ;)
~Neels
--
- 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
22 Mar
22 Mar
11:22 a.m.
Hi Neels,
Thanks for the suggestions.
On Friday, March 18, 2016 3:59 PM, Neels Hofmeyr wrote:
though I'm not entirely familiar with the
compression algorithm, I'm pretty sure that using an array of strings to store bits
will make the code less efficient by magnitudes.
The proposed structures are being used in following scenario.
1. System Init (i.e. During system bootup)
* Array of strings are used to form a tree, it is used only once during system bootup ,
hence it should not impact the performance. Let me know your opinion on this ?
2. Decoding of EGPRS packet downlink Ack/Nack
* While decoding there is no string comparison involved, we read every bit from the
bitmap and traverse tree generated in init, hence only bit operation involved in
decoding.
3. Encoding of packet uplink Ack/Nack
* While encoding, first find the number of one's/zero's (i.e. run length of
one's or zero's) consecutively and find the corresponding code word by referring
to the code word list
* This involves string comparison to find the code word, but based on your feedback we
are planning to avoid string operations
and adopt existing (i.e. master ) approach to find the code word by using respective
tables.
Hence to summarize, the tree based approach is more significant during the decoding of
bitmap.
In current master code for decoding, the function t4_rle_term is used to find the run
length for each received code word,
There could be multiple code words in the received bitmap and each require multiple
iterations(i.e. maximum of 64 iterations) to find run length.
Instead if tree based approach is used multiple iterations can be avoided to find run
length.
Patches for the above modification will be sent further.
Thanks,
Sangamesh
5 p.m.
Hi Sangamesh,
I should probably also read all of the code involved, properly, which I
must admit I haven't, but based on general knowledge, my replies are:
On Tue, Mar 22, 2016 at 10:22:59AM +0000, Sangamesh Sajjan wrote:
The proposed structures are being used in following
scenario.
1. System Init (i.e. During system bootup)
* Array of strings are used to form a tree, it is used only once during system bootup ,
hence it should not impact the performance. Let me know your opinion on this ?
Ok, for once-upon-boot a string approach sounds fair enough.
2. Decoding of EGPRS packet downlink Ack/Nack
* While decoding there is no string comparison involved, we read every bit from the
bitmap and traverse tree generated in init, hence only bit operation involved in decoding.
sounds good
3. Encoding of packet uplink Ack/Nack
* While encoding, first find the number of one's/zero's (i.e. run length of
one's or zero's) consecutively and find the corresponding code word by referring
to the code word list
* This involves string comparison to find the code word,
Ick! :)
but based on your feedback we are planning to
avoid string operations
and adopt existing (i.e. master ) approach to find the code word by using respective
tables.
Sounds much better, yes.
In current master code for decoding, the function
t4_rle_term is used to find the run length for each received code word,
There could be multiple code words in the received bitmap and each require multiple
iterations(i.e. maximum of 64 iterations) to find run length.
Instead if tree based approach is used multiple iterations can be avoided to find run
length.
Is this a separate suggestion to introduce a binary tree search? Beware of
too heavy / premature optimizations, but your trajectory sounds way better
now.
Anyway, looking forward to the patches, and I hope to read the patch
context properly, then. Thanks!
~Neels
--
- 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
2981
days inactive
2986
days old
osmocom-net-gprs@lists.osmocom.org
3 comments
2 participants
participants (2)
-
Neels Hofmeyr -
Sangamesh Sajjan