rohc team mailing list archive
-
rohc team
-
Mailing list archive
-
Message #00527
Re: Patch to optimize WLSB memory allocation (Was: Support of RFC4996 RoHC-TCP)
Hello Didier,
Attached is a new patch to optimize wlsb.c in the current branch.
I suppress the field "is_used" in the c_window structure, and add the
fields "count" and "window_mask" in the c_wlsb structure to optimize the
code.
Pointers "next" and "oldest" are calculated using the size of the
window, minus 1, as mask. No need of modulo.
I think the code is faster, and more compact.
Hope you enjoy it ...
Best regards,
FWX.
Le 26/05/2012 14:27, Didier Barvaux a écrit :
WBX,
struct c_window
{
+ uint16_t is_used; /**< Whether the window entry is
used or not */ uint16_t sn; /**< The Sequence Number (SN)
associated with the entry (used to acknowledge the entry) */
uint32_t value; /**< The value stored in the window
entry */
- bool is_used; /**< Whether the window entry is used or
not */ };
Why changing the position and the type of is_used?
==> Just to align members of the structure, and compact
the size (16+16+32) rather than (16+(16)+32+32) when not
compacted.
I see your point. I prefer however to keep the bool type for semantic
reasons.
size_t bits;
/// Shift parameter (see 4.5.2 in the RFC 3095)
rohc_lsb_shift_t p;
+
+ /// @brief The window in which numerous previous values of
the encoded value
+ /// are stored to help recreate the value
+ struct c_window window[1];
};
Why not use flexible arrays from ISO C99?
==> Because I am not sure all old compilers understand and support
that, especially older cross-compilers I used. This way is not the
best, but I am sure that it is very easy to compile.
OK. Patch applied on trunk in 2 parts. Thanks for sending it!
See http://bazaar.launchpad.net/~didier-barvaux/rohc/main/revision/354
and http://bazaar.launchpad.net/~didier-barvaux/rohc/main/revision/355
for details.
Regards,
Didier
_______________________________________________
Mailing list: https://launchpad.net/~rohc
Post to : rohc@xxxxxxxxxxxxxxxxxxx
Unsubscribe : https://launchpad.net/~rohc
More help : https://help.launchpad.net/ListHelp
=== modified file 'src/common/wlsb.c'
--- src/common/wlsb.c 2012-05-26 12:09:09 +0000
+++ src/common/wlsb.c 2012-06-19 14:57:22 +0000
@@ -43,7 +43,6 @@
uint16_t sn; /**< The Sequence Number (SN) associated with the entry
(used to acknowledge the entry) */
uint32_t value; /**< The value stored in the window entry */
- bool is_used; /**< Whether the window entry is used or not */
};
@@ -55,11 +54,17 @@
/// The width of the window
size_t window_width;
+ // The size of the window (power of 2) minus 1
+ size_t window_mask;
+
/// A pointer on the oldest entry in the window (change on acknowledgement)
size_t oldest;
/// A pointer on the current entry in the window (change on add and ack)
size_t next;
+ // Count of entries in the window
+ int count;
+
/// The maximal number of bits for representing the value
size_t bits;
/// Shift parameter (see 4.5.2 in the RFC 3095)
@@ -105,10 +110,11 @@
const rohc_lsb_shift_t p)
{
struct c_wlsb *wlsb;
- size_t entry;
assert(bits > 0);
assert(window_width > 0);
+ // window_width must be a power of 2!
+ assert( window_width == 2 || window_width == 4 || window_width == 8 || window_width == 16 );
wlsb = malloc(sizeof(struct c_wlsb) + (window_width - 1) * sizeof(struct c_window));
if(wlsb == NULL)
@@ -119,15 +125,12 @@
wlsb->oldest = 0;
wlsb->next = 0;
+ wlsb->count = 0;
wlsb->window_width = window_width;
+ wlsb->window_mask = window_width - 1;
wlsb->bits = bits;
wlsb->p = p;
- for(entry = 0; entry < window_width; entry++)
- {
- wlsb->window[entry].is_used = false;
- }
-
return wlsb;
error:
@@ -163,15 +166,18 @@
assert(wlsb->next < wlsb->window_width);
/* if window is full, an entry is overwritten */
- if(wlsb->window[wlsb->next].is_used)
- {
- wlsb->oldest = (wlsb->oldest + 1) % wlsb->window_width;
+ if(wlsb->count == wlsb->window_width)
+ {
+ wlsb->oldest = (wlsb->oldest + 1) & wlsb->window_mask;
+ }
+ else
+ {
+ ++wlsb->count;
}
wlsb->window[wlsb->next].sn = sn;
wlsb->window[wlsb->next].value = value;
- wlsb->window[wlsb->next].is_used = true;
- wlsb->next = (wlsb->next + 1) % wlsb->window_width;
+ wlsb->next = (wlsb->next + 1) & wlsb->window_mask;
}
@@ -193,31 +199,28 @@
size_t *const bits_nr)
{
size_t entry;
- bool is_window_valid;
uint16_t min;
uint16_t max;
+ int i;
assert(wlsb != NULL);
assert(wlsb->window != NULL);
/* (value <= 0xffff) always ensured because value is of type uint16_t */
assert(bits_nr != NULL);
+ /* If the window contains no value */
+ if(wlsb->count==0)
+ {
+ /* cannot do anything if the window contains no value */
+ goto error;
+ }
+
min = 0xffff;
max = 0;
- is_window_valid = false;
/* find out the interval in which all the values from the window stand */
- for(entry = 0; entry < wlsb->window_width; entry++)
+ for(i = wlsb->count, entry = wlsb->oldest ; i != 0; i--)
{
- /* skip entry if not in use */
- if(!(wlsb->window[entry].is_used))
- {
- continue;
- }
-
- /* the window contains at least one value */
- is_window_valid = true;
-
/* change the minimal and maximal values if appropriate */
if(wlsb->window[entry].value < min)
{
@@ -227,12 +230,7 @@
{
max = wlsb->window[entry].value;
}
- }
-
- /* cannot do anything if the window contains no value */
- if(!is_window_valid)
- {
- goto error;
+ entry = ( entry + 1 ) & wlsb->window_mask;
}
/* find the minimal number of bits of the value required to be able
@@ -279,31 +277,27 @@
size_t *const bits_nr)
{
size_t entry;
- bool is_window_valid;
uint32_t min;
uint32_t max;
+ int i;
assert(wlsb != NULL);
assert(wlsb->window != NULL);
assert(value <= 0xffffffff);
assert(bits_nr != NULL);
+ /* cannot do anything if the window contains no value */
+ if(wlsb->count==0)
+ {
+ goto error;
+ }
+
min = 0xffffffff;
max = 0;
- is_window_valid = false;
/* find out the interval in which all the values from the window stand */
- for(entry = 0; entry < wlsb->window_width; entry++)
+ for(i = wlsb->count, entry = wlsb->oldest ; i != 0; i--)
{
- /* skip entry if not in use */
- if(!(wlsb->window[entry].is_used))
- {
- continue;
- }
-
- /* the window contains at least one value */
- is_window_valid = true;
-
/* change the minimal and maximal values if appropriate */
if(wlsb->window[entry].value < min)
{
@@ -313,12 +307,7 @@
{
max = wlsb->window[entry].value;
}
- }
-
- /* cannot do anything if the window contains no value */
- if(!is_window_valid)
- {
- goto error;
+ entry = ( entry + 1 ) & wlsb->window_mask;
}
/* find the minimal number of bits of the value required to be able
@@ -357,7 +346,7 @@
*/
void c_ack_sn_wlsb(struct c_wlsb *s, int sn)
{
- int found = 0;
+ size_t entry;
int i;
/* check the W-LSB object validity */
@@ -368,31 +357,15 @@
/* search for the window entry that matches the given SN
* starting from the oldest one */
- for(i = s->oldest; i < s->window_width; i++)
+ for(entry = s->oldest, i = s->count; i != 0; i--)
{
- if(s->window[i].is_used && s->window[i].sn == sn)
+ if(s->window[i].sn == sn)
{
- found = 1;
+ /* remove the window entry if found */
+ c_ack_remove(s, i);
break;
}
- }
-
- if(!found)
- {
- for(i = 0; i < s->oldest; i++)
- {
- if(s->window[i].is_used && s->window[i].sn == sn)
- {
- found = 1;
- break;
- }
- }
- }
-
- /* remove the window entry if found */
- if(found)
- {
- c_ack_remove(s, i);
+ entry = ( entry + 1 ) & s->window_mask;
}
}
@@ -407,15 +380,14 @@
*/
int c_sum_wlsb(struct c_wlsb *s)
{
+ size_t entry;
+ int sum = 0;
int i;
- int sum = 0;
- for(i = 0; i < s->window_width; i++)
+ for(entry = s->oldest, i = s->count; i != 0; i--)
{
- if(s->window[i].is_used)
- {
- sum += s->window[i].value;
- }
+ sum += s->window[entry].value;
+ entry = ( entry + 1 ) & s->window_mask;
}
return sum;
@@ -432,20 +404,22 @@
*/
int c_mean_wlsb(struct c_wlsb *s)
{
+ size_t entry;
+ int sum = 0;
int i;
- int sum = 0;
- int num = 0;
-
- for(i = 0; i < s->window_width; i++)
- {
- if(s->window[i].is_used)
- {
- sum += s->window[i].value;
- num++;
- }
- }
-
- return (num > 0 ? sum / num : 0);
+
+ if( s->count == 0 )
+ {
+ return 0;
+ }
+
+ for(entry = s->oldest, i = s->count; i != 0; i--)
+ {
+ sum += s->window[entry].value;
+ entry = ( entry + 1 ) & s->window_mask;
+ }
+
+ return sum / s->count;
}
@@ -461,7 +435,8 @@
*/
static void c_ack_remove(struct c_wlsb *s, int index)
{
- int j;
+ size_t entry;
+ int i;
/* check the W-LSB object validity */
if(s == NULL)
@@ -471,75 +446,16 @@
rohc_debugf(2, "index is %d\n", index);
- if(s->oldest == index)
- {
- /* remove only the oldest entry */
- s->window[s->oldest].is_used = false;
- }
- else if(s->oldest < index)
- {
- /* remove all entries from oldest to (not including) index */
- for(j = s->oldest; j < index; j++)
- {
- s->window[j].is_used = false;
- }
- }
- else /* s->oldest > index */
- {
- /* remove all entries from oldest to wrap-around and all from start
- * to (excluding) index */
- for(j = s->oldest; j < s->window_width; j++)
- {
- s->window[j].is_used = false;
- }
- for(j = 0; j < index; j++)
- {
- s->window[j].is_used = false;
- }
- }
-
- /* fix the s->oldest pointer */
- if(index >= (s->window_width - 1))
- {
- s->oldest = 0;
- }
- else
- {
- s->oldest = index;
- if(s->oldest >= s->window_width)
- {
- s->oldest = 0;
- }
- }
-
- /* fix the s->next pointer */
- s->next = s->oldest;
- for(j = s->oldest; j < s->window_width; j++)
- {
- if(s->window[j].is_used)
- {
- s->next = (s->next + 1) % s->window_width;
- }
- else
- {
- break;
- }
- }
- for(j = 0; j < s->oldest; j++)
- {
- if(s->window[j].is_used)
- {
- s->next = (s->next + 1) % s->window_width;
- }
- else
- {
- break;
- }
- }
-
- if(s->oldest >= s->window_width)
- {
- s->oldest = 0;
+ for( entry = s->oldest, i = s->count; i != 0 ; i-- )
+ {
+ /* remove this oldest entry */
+ --s->count;
+ s->oldest = ( entry + 1 ) & s->window_mask;
+ if( entry == index )
+ {
+ break;
+ }
+ entry = s->oldest;
}
}
Follow ups
References
