[Tinyos-devel] One should make limited use of the "%" operator

[Michael Newman]

I don't like using hacks like this. I think the proper place for
implementing this is in the compiler's peephole optimization. Using the hack
results in better code only some of the time and depends on knowledge of the
particular build environment to know if it will help or hurt.

The change Phil proposes will typically be better than a call to a service
routine. It also results in safe code most of the time.  There are two
issues:

1) if QUEUE_SIZE is a power of 2 the original code (using the % operator)
generates better, faster and smaller code

2) Phil's strategy is ONLY a good idea if idx is an 8 bit integer. If the
data type is a 16 bit or 32 bit integer this code could result in a loop
that takes an unexpectedly long time to execute.


Whenever hacks like this are installed my practice has always been to
document the hack and why it is used:


// Use a small while loop to avoid an expensive
// library call for the % operator.
#if 0
    idx %= QUEUE_SIZE;
#else
    while (idx > QUEUE_SIZE)
          idx -= QUEUE_SIZE;
#endif


-----Original Message-----
From: tinyos-devel-bounces at millennium.berkeley.edu
[mailto:tinyos-devel-bounces at millennium.berkeley.edu] On Behalf Of Philip
Levis
Sent: Thursday, June 25, 2009 2:36 PM
To: Eric Decker
Cc: TinyOS Development
Subject: Re: [Tinyos-devel] One should make limited use of the "%" operator

On Jun 25, 2009, at 11:30 AM, Eric Decker wrote:

> While perusing the code and paying attention to the kind of code  
> generated I noticed constructs of the form:
>
>   command queue_t Queue.element(uint8_t idx) {
>     idx += head;
>     idx %= QUEUE_SIZE;
>     return queue[idx];
>   }
>
> I'm referring to "idx %= QUEUE_SIZE"
>
>
> The use of the % operator can be expensive and more often than not  
> is.  How is it expensive?  Well what
> it does it generates a call to the math library (which pull that  
> piece in which chews precious rom space) and
> the math code take a bit of time to execute.
>
> The above could might be rewritten as:
>
> command queue_t Queue.element(uint8_t idx) {
>   if (idx > QUEUE_SIZE)
>     return NULL;
>    return queue[idx];
> }
>
> or
>
> while (idx > QUEUE_SIZE)
>    idx -= QUEUE_SIZE;
>
>
> I prefer the former because it is well bounded in time execution and  
> detects odd requests.

Agreed. Except that the former is buggy. The latter is the correct  
approach. I'll check in the fix.

Phil
_______________________________________________
Tinyos-devel mailing list
Tinyos-devel at millennium.berkeley.edu
https://www.millennium.berkeley.edu/cgi-bin/mailman/listinfo/tinyos-devel