Skip to contentSkip to conversation

a fast fls also for 2.6?

parisc-linux Grant Grundler 2 participants 4 messages Sep 5, 2003 2 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): [email protected]

Grant Grundler

author
#2 lore raw
Quoted 2 lines · Joel Soete

remember me that I also suggest a __fls() in:
<http://lists.parisc-linux.org/pipermail/parisc-linux/2003-August/020628.html>

sorry - I missed that.

Quoted 2 lines

Without any remark, I don't know if you could also be interested to include it in 2.6.

no - becuase fls() and ffs() return the same values for given input. (I see comments in include/asm-ppc/bitops.h to that effect).

parisc __ffs costs the same number of cycles regardless of input. (2 cycles per 3 instructions about on PA 2.0 machines). ie there is no advantage to "searching from the top" vs "searching from the bottom" which is what I think the intent of fls() vs ffs(). For generic implementations, this intent is important.

What we could do is redefine fls() to also use ffs() and add my comment above. Patch appended. Please test/review and tell me if that should be committed. I haven't tested it yet and the comments in PPC bitops.h could be wrong.

thanks,
grant

Index: include/asm-parisc/bitops.h
===================================================================
RCS file: /var/cvs/linux-2.6/include/asm-parisc/bitops.h,v retrieving revision 1.2

asm-parisc/bitops.h +6 -1
diff -u -p -r1.2 bitops.h
@@ -281,9 +281,14 @@ static __inline__ int ffs(int x)
 
 /*
  * fls: find last bit set.
+ *
+ * parisc __ffs costs the same number of cycles regardless of input.
+ * A similar implementation for __fls() would have no advantage.
+ * ie there is no advantage to "searching from the top" vs "searching 
+ * from the bottom" which is the intent of fls() vs ffs().
  */
 
-#define fls(x) generic_fls(x)
+#define fls(x) ffs(x)
 
 /*
  * hweightN: returns the hamming weight (i.e. the number
#3 lore raw
Quoted 49 lines · Grant Grundler
Quoted 3 lines · Joel Soete

remember me that I also suggest a __fls() in: <http://lists.parisc-linux.org/pipermail/parisc-linux/2003-August/020628.html>

sorry - I missed that.

Quoted 3 lines

Without any remark, I don't know if you could also be interested to include it in 2.6.

no - becuase fls() and ffs() return the same values for given input. (I see comments in include/asm-ppc/bitops.h to that effect).

parisc __ffs costs the same number of cycles regardless of input. (2 cycles per 3 instructions about on PA 2.0 machines). ie there is no advantage to "searching from the top" vs "searching from the bottom" which is what I think the intent of fls() vs ffs(). For generic implementations, this intent is important.

What we could do is redefine fls() to also use ffs() and add my comment above. Patch appended. Please test/review and tell me if that should be committed. I haven't tested it yet and the comments in PPC bitops.h could be wrong.

thanks,
grant

Index: include/asm-parisc/bitops.h
===================================================================
RCS file: /var/cvs/linux-2.6/include/asm-parisc/bitops.h,v retrieving revision 1.2
diff -u -p -r1.2 bitops.h

asm-parisc/bitops.h +2 -0
@@ -281,9 +281,14 @@ static __inline__ int ffs(int x)
 
 /*
 * fls: find last bit set.
+ *
+ * parisc __ffs costs the same number of cycles regardless of input.

asm-parisc/bitops.h static __inline__ int ffs(int x) · line 294

Quoted 10 lines
asm-parisc/bitops.h +4 -1
+ * A similar implementation for __fls() would have no advantage.
+ * ie there is no advantage to "searching from the top" vs "searching 
+ * from the bottom" which is the intent of fls() vs ffs().
 */
 
-#define fls(x) generic_fls(x)
+#define fls(x) ffs(x)
 
 /*
 * hweightN: returns the hamming weight (i.e. the number

My bad, I undurstand that ffs return the index of the first bit set otc fls returning the the index of the last bit set (ie for 1010: ffs would return 2 and fls would return 4)?

Sorry for confusion. It was never the less a good exercice ;)

Thanks,
Joel

author
#4 lore raw
In reply to Grant Grundler
Quoted 5 lines · Grant Grundler
Quoted 2 lines

Without any remark, I don't know if you could also be interested to include it in 2.6.

no - becuase fls() and ffs() return the same values for given input. (I see comments in include/asm-ppc/bitops.h to that effect).

James Bottomley privately corrected me. fls() != ffs(). fls() returns most significant bit set.

The examples provided:
* Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.

have the same value for ffs() and fls(). I didn't read the rest. Good examples for showing bit numbering though.

I'll work on adding 64-bit support to your __fls() and commit that.

sorry for the confusion,
grant

#5 lore raw
Quoted 14 lines · Grant Grundler
Quoted 7 lines · Grant Grundler
Quoted 3 lines

Without any remark, I don't know if you could also be interested to include it in 2.6.

no - becuase fls() and ffs() return the same values for given input. (I see comments in include/asm-ppc/bitops.h to that effect).

James Bottomley privately corrected me. fls() != ffs(). fls() returns most significant bit set.

Quoted 8 lines

The examples provided:
* Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32.

have the same value for ffs() and fls(). I didn't read the rest. Good examples for showing bit numbering though.

I'll work on adding 64-bit support to your __fls() and commit that.

Thanks a lot :) (it just make me happy to be usefull)

Quoted 3 lines

sorry for the confusion,

Please, don't be sorry, I am frequently the first confusing thought ;)

Cheers,
Joel