lkml.org 
[lkml]   [1999]   [Jan]   [11]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: tiny patch, reduces kernel memory usage
Stephen Tweedie wrote:
> The unused field needs to go. Fine. The map_nr field is needed to
> avoid a division when we try to find a page number from a struct page.

Um, it's a division by a constant, which GCC optimizes to a multiply.
GCC also knows that the division must have no remainder, so it can do even
better than the usual case.)

For example,
struct x {
unsigned c[13];
};

unsigned foo (struct x *p1, struct x *p2)
{
return p2-p1;
}

On an x86 with egcc -O2 -fomit-frame-pointer produces:
foo:
movl 8(%esp),%eax
subl 4(%esp),%eax
imull $-991146299,%eax,%eax
sarl $2,%eax
ret

A multiply is not a trivial cost, but it's cheaper than a divide.
(And depending on the multiplier, GCC can optimize it further into
a series of shifts and adds.)

Any odd number x has a multiplicative inverse y such that
(x*y) == 1 (mod 2^32). Thus, (k*x)*y == k*(x*y) == k (mod 2^32).hC
and multiplying by y is the same as dividing by x.

And may number at all can be broken down into an odd number and
a power of two, where division is a simple shift.
--
-Colin

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:49    [W:0.020 / U:0.780 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site