[KJ] Re: Log2 all through the kernel?

[KJ] Re: Log2 all through the kernel?

[Oliver Korpilla]

[-- Attachment #1: Type: text/plain, Size: 1758 bytes --]

Am Mittwoch, den 10.08.2005, 16:23 +0300 schrieb Stauros Passas:
> Accurate logarithm algorithms are costly,and I don't think
> are needed from kernel developers, usually a approximation is enough.
> So if u want something realy accurate,
> u must look how it is implemented on libc.

No, I'm pretty find with a bit-shifted implementation - my question is:
Why is there not a single implementation that fits most people's needs?
The way log2 functions and macros are interpersed throughout the kernel
looks very spaghetti to me - everyone brewing his own one.

Wouldn't it be more sensible to supply one portable one, with bit
shifts, and people with a need for O(1) timing could implement it using
an array?

> The easiest(and fastest) way to compute a logarithm
> (with or without base 2) is to make bit shifts.
> 
> >
> > Is this desirable? While it may be some reduction for special cases using a 
> > table (like in the log2_2048 function I found - it computes only a certain of 
> > log2 and multiplies this with 2048), wouldn't a more generic implementation 
> > like ceil_log2 and floor_log2 not be desirable for all platforms?
> 
> U can simply use the functions of bitops.h (of asm-alpha) inline 
> functions, removing the alpha special comands:

Well, I could, but that is not quite my point. That would be a kernel
patch to just my kernel. 

Wouldn't it be more wise to supply a patch providing a single
implementation in the standard kernel and start converting most other
log2 implementations to that one? I don't have a good feeling with
everyone implementing the same, for really minimal gains.

You may say I'm more worried about software engineering practice than a
really quick solution. ;)

Thanks and with kind regards,
Oliver Korpilla


[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

[KJ] Re: Log2 all through the kernel?

[Erik Mouw]

[-- Attachment #1.1: Type: text/plain, Size: 368 bytes --]

On Wed, Aug 10, 2005 at 05:54:44PM +0200, Oliver Korpilla wrote:
> Wouldn't it be more sensible to supply one portable one, with bit
> shifts, and people with a need for O(1) timing could implement it using
> an array?

Send a patch to the linux-kernel mailing list and see what happens.


Erik

-- 
Erik Mouw
J.A.K.Mouw@its.tudelft.nl  mouw@nl.linux.org

[-- Attachment #1.2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

[KJ] Re: Log2 all through the kernel?

[Rene Herman]

[-- Attachment #1: Type: text/plain, Size: 520 bytes --]

Erik Mouw wrote:

> On Wed, Aug 10, 2005 at 05:54:44PM +0200, Oliver Korpilla wrote:
> 
>>Wouldn't it be more sensible to supply one portable one, with bit
>>shifts, and people with a need for O(1) timing could implement it using
>>an array?
> 
> 
> Send a patch to the linux-kernel mailing list and see what happens.

Sticking a few defines in a header somewhere should do, I believe:

#define floor_log2(x) (fls(x) - 1)
#define ceil_log2(x) (fls((x) - 1)

fls() is both defined in the kernel and a gcc builtin.

Rene.

[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors

Re: [KJ] Re: Log2 all through the kernel?

[Alexey Dobriyan]

[-- Attachment #1: Type: text/plain, Size: 574 bytes --]

On Thu, Aug 11, 2005 at 01:03:14AM +0200, Rene Herman wrote:
> Erik Mouw wrote:
> >On Wed, Aug 10, 2005 at 05:54:44PM +0200, Oliver Korpilla wrote:
> >>Wouldn't it be more sensible to supply one portable one, with bit
> >>shifts, and people with a need for O(1) timing could implement it using
> >>an array?
> >
> >Send a patch to the linux-kernel mailing list and see what happens.
> 
> Sticking a few defines in a header somewhere should do, I believe:
> 
> #define floor_log2(x) (fls(x) - 1)
> #define ceil_log2(x) (fls((x) - 1)

IMO, one of them should be just "log2".


[-- Attachment #2: Type: text/plain, Size: 168 bytes --]

_______________________________________________
Kernel-janitors mailing list
Kernel-janitors@lists.osdl.org
https://lists.osdl.org/mailman/listinfo/kernel-janitors