Skip to contentSkip to conversation

include/asm-ARCH/page.h:get_order() Reorganize and optimize

PATCH In review Inaky Perez-Gonzalez 2 participants 2 messages Nov 13, 2002 Sparse checker

lore
Share & tools
lore

Inaky Perez-Gonzalez

author
#0 lore raw

PATCH 1/1 include/asm-ARCH/page.h:get_order() Reorganize and optimize

Hi all

This patch is a reorganization and optimization of the get_order() function.

Currently each architecture defines its version in asm-${ARCH}/page.h, being most of them the same function. I have unified the implementation in asm-generic/page.h, as generic_get_order(). Then each arch can implement it's own version or use the generic one [as the patch stands now, every architecture that had the generic version uses generic_get_oder()].

The optimization is done in the way the generic_get_order() is implemented; currently it is a loop - however, that can be highly optimized by using fls() [available on each architecture or as generic_tls() where not optimized]. On my tests in a tight loop doing repeated get_order() calls (see included test program), I got an aprox average run time of 0.5 seconds for the optimized version, versus an average of 1.45 for the old one. Almost 33% better, not bad.

I was only able to test it and try it in ia32, so I don't know if I broke anything else in other archs; reports welcome.

CAVEATS:

- the #include <asm-generic/page.h> ... I don't know if it is the best way to do it. Any ideas?

- Some arches still define fls() as the generic_fls(), instead of using bit-searching ASM instructions - I lack the knowledge to fix it, though.

Quickie-dirtie-test program:

compile with 'cc -DV# -O2 -g -o test-# test.c', where # is 0 for the original version and 1 for the optimized version.

#include <asm/page.h>
#include <stdio.h>

#ifdef V0
int get_order(unsigned long size)
{
int order;

size = (size-1) >> (PAGE_SHIFT-1);
order = -1;

  do {
    size >>= 1;
    order++;

} while (size);
return order;
}
#endif

#ifdef V1
static __inline__
int fls (int x)

{
	int r;

	__asm__("bsrl %1,%0\n\t"
		"jnz 1f\n\t"
		"movl $-1,%0\n"
		"1:" : "=r" (r) : "g" (x));
	return r+1;
}

#define likely(y) (y)

static __inline__
int get_order (unsigned long s)

{
    int exp;

    s = --s >> PAGE_SHIFT;
    if (s == 0)
      return 0;
    
    exp = fls (s);
    s = 1 << exp;
    if (likely (s) < s)
	exp++;
    return exp;
}

#endif

int main (void)
{
unsigned long cnt, rep;

  unsigned long *pivot, pivots[] = {
    0x00001000, 0x00002000, 0x00004000, 0x00008000,
    0x00010000, 0x00020000, 0x00040000, 0x00080000,
    0x00100000, 0x00200000, 0x00400000, 0x00800000,
    0x01000000, 0x02000000, 0x04000000, 0x08000000,
    0x10000000, 0x20000000, 0x40000000, 0x80000000

};

for (pivot = pivots; pivot < pivots + sizeof (pivots) / sizeof (unsigned long); pivot++)

    for (rep = 0; rep < 400000; rep++)
      for (cnt = *pivot - 10; cnt < *pivot + 10; cnt++)
           cnt += get_order (cnt);

return cnt;
}

This patch is against 2.5.47.

asm-alpha/page.h renamed from asm-alpha/page.h:1.1.1.1 +10 -11
diff -u include/asm-alpha/page.h:1.1.1.1 include/asm-alpha/page.h:1.1.1.1.16.1
@@ -67,18 +67,17 @@
 
 #define PAGE_BUG(page)	BUG()
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
+
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #endif /* !__ASSEMBLY__ */
asm-arm/page.h renamed from asm-arm/page.h:1.1.1.2 +9 -11
diff -u include/asm-arm/page.h:1.1.1.2 include/asm-arm/page.h:1.1.1.2.10.1
@@ -175,18 +175,16 @@
 
 #endif
 
-/* Pure 2^n version of get_order */
-static inline int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #include <asm/memory.h>
asm-generic/page.h new file +27 -0
diff -u /dev/null include/asm-generic/page.h:1.1.2.1
@@ -0,0 +1,27 @@
+#ifndef _GENERIC_PAGE_H
+#define _GENERIC_PAGE_H
+
+#include <asm/bitops.h>
+
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+static __inline__
+int generic_get_order (unsigned long s)
+{
+        int exp;
+
+        s = --s >> PAGE_SHIFT;
+        if (s == 0)
+                return 0;
+    
+        exp = fls (s);
+        s = 1 << exp;
+        if (likely (s) < s)
+                exp++;
+        return exp;
+}
+
+#endif _GENERIC_PAGE_H
+
asm-i386/bitops.h renamed from asm-i386/bitops.h:1.1.1.2 +29 -4
diff -u include/asm-i386/bitops.h:1.1.1.2 include/asm-i386/bitops.h:1.1.1.2.4.1
@@ -414,11 +414,19 @@
 	return word;
 }
 
-/*
- * fls: find last bit set.
+/**
+ * __fls - find last bit in word.
+ * @word: The word to search
+ *
+ * Undefined if no bit exists, so code should check against 0 first.
  */
-
-#define fls(x) generic_fls(x)
+static __inline__ unsigned long __fls(unsigned long word)
+{
+	__asm__("bsrl %1,%0"
+		:"=r" (word)
+		:"rm" (word));
+	return word;
+}
 
 #ifdef __KERNEL__
 

@@ -454,6 +462,23 @@
 	int r;
 
 	__asm__("bsfl %1,%0\n\t"
+		"jnz 1f\n\t"
+		"movl $-1,%0\n"
+		"1:" : "=r" (r) : "g" (x));
+	return r+1;
+}
+
+/**
+ * fls - find last bit set
+ * @x: the word to search
+ *
+ * Check out comments for ffs()
+ */
+static __inline__ int fls(int x)
+{
+	int r;
+
+	__asm__("bsrl %1,%0\n\t"
 		"jnz 1f\n\t"
 		"movl $-1,%0\n"
 		"1:" : "=r" (r) : "g" (x));
asm-i386/page.h renamed from asm-i386/page.h:1.1.1.2 +10 -11
diff -u include/asm-i386/page.h:1.1.1.2 include/asm-i386/page.h:1.1.1.2.10.1
@@ -120,18 +120,17 @@
 	BUG(); \
 } while (0)
 
-/* Pure 2^n version of get_order */
-static __inline__ int get_order(unsigned long size)
-{
-	int order;
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
+
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #endif /* __ASSEMBLY__ */
asm-m68k/page.h renamed from asm-m68k/page.h:1.1.1.2 +10 -11
diff -u include/asm-m68k/page.h:1.1.1.2 include/asm-m68k/page.h:1.1.1.2.4.1
@@ -100,18 +100,17 @@
 /* to align the pointer to the (next) page boundary */
 #define PAGE_ALIGN(addr)	(((addr)+PAGE_SIZE-1)&PAGE_MASK)
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
+
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #endif /* !__ASSEMBLY__ */
asm-m68knommu/page.h renamed from asm-m68knommu/page.h:1.1.2.1 +10 -11
diff -u include/asm-m68knommu/page.h:1.1.2.1 include/asm-m68knommu/page.h:1.1.2.1.4.1
@@ -51,19 +51,18 @@
 /* to align the pointer to the (next) page boundary */
 #define PAGE_ALIGN(addr)	(((addr)+PAGE_SIZE-1)&PAGE_MASK)
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 extern unsigned long memory_start;
 extern unsigned long memory_end;
asm-mips/page.h renamed from asm-mips/page.h:1.1.1.1 +9 -11
diff -u include/asm-mips/page.h:1.1.1.1 include/asm-mips/page.h:1.1.1.1.16.1
@@ -49,18 +49,16 @@
 #define __pgd(x)	((pgd_t) { (x) } )
 #define __pgprot(x)	((pgprot_t) { (x) } )
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #endif /* _LANGUAGE_ASSEMBLY */
asm-parisc/page.h renamed from asm-parisc/page.h:1.1.1.2 +10 -11
diff -u include/asm-parisc/page.h:1.1.1.2 include/asm-parisc/page.h:1.1.1.2.6.1
@@ -53,19 +53,18 @@
 #define __pgd(x)	((pgd_t) { (x) } )
 #define __pgprot(x)	((pgprot_t) { (x) } )
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #ifdef __LP64__
 #define MAX_PHYSMEM_RANGES 8 /* Fix the size for now (current known max is 3) */
asm-ppc64/page.h renamed from asm-ppc64/page.h:1.1.1.1 +10 -11
diff -u include/asm-ppc64/page.h:1.1.1.1 include/asm-ppc64/page.h:1.1.1.1.16.1
@@ -119,19 +119,18 @@
 
 #define PAGE_BUG(page) do { BUG(); } while (0)
 
-/* Pure 2^n version of get_order */
-static inline int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #define __pa(x) ((unsigned long)(x)-PAGE_OFFSET)
asm-s390/page.h renamed from asm-s390/page.h:1.1.1.1 +9 -11
diff -u include/asm-s390/page.h:1.1.1.1 include/asm-s390/page.h:1.1.1.1.16.1
@@ -71,18 +71,16 @@
         BUG(); \
 } while (0)                      
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-        int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-        size = (size-1) >> (PAGE_SHIFT-1);
-        order = -1;
-        do {
-                size >>= 1;
-                order++;
-        } while (size);
-        return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 /*
asm-s390x/page.h renamed from asm-s390x/page.h:1.1.1.1 +9 -11
diff -u include/asm-s390x/page.h:1.1.1.1 include/asm-s390x/page.h:1.1.1.1.16.1
@@ -69,18 +69,16 @@
         BUG(); \
 } while (0)                      
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-        int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-        size = (size-1) >> (PAGE_SHIFT-1);
-        order = -1;
-        do {
-                size >>= 1;
-                order++;
-        } while (size);
-        return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 /*
asm-sh/page.h renamed from asm-sh/page.h:1.1.1.1 +10 -11
diff -u include/asm-sh/page.h:1.1.1.1 include/asm-sh/page.h:1.1.1.1.16.1
@@ -102,19 +102,18 @@
 	BUG(); \
 } while (0)
 
-/* Pure 2^n version of get_order */
-static __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #endif
asm-sparc/page.h renamed from asm-sparc/page.h:1.1.1.1 +10 -11
diff -u include/asm-sparc/page.h:1.1.1.1 include/asm-sparc/page.h:1.1.1.1.16.1
@@ -147,19 +147,18 @@
 
 #define TASK_UNMAPPED_BASE	BTFIXUP_SETHI(sparc_unmapped_base)
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #else /* !(__ASSEMBLY__) */
asm-sparc64/page.h renamed from asm-sparc64/page.h:1.1.1.2 +9 -11
diff -u include/asm-sparc64/page.h:1.1.1.2 include/asm-sparc64/page.h:1.1.1.2.6.1
@@ -161,18 +161,16 @@
 
 extern struct sparc_phys_banks sp_banks[SPARC_PHYS_BANKS];
 
-/* Pure 2^n version of get_order */
-static __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
 
 #endif /* !(__ASSEMBLY__) */
asm-v850/page.h renamed from asm-v850/page.h:1.1.2.1 +10 -11
diff -u include/asm-v850/page.h:1.1.2.1 include/asm-v850/page.h:1.1.2.1.4.1
@@ -98,19 +98,18 @@
 #define BUG()		__bug()
 #define PAGE_BUG(page)	__bug()
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order (unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #endif /* !__ASSEMBLY__ */
asm-x86_64/page.h renamed from asm-x86_64/page.h:1.1.1.2 +10 -11
diff -u include/asm-x86_64/page.h:1.1.1.2 include/asm-x86_64/page.h:1.1.1.2.10.1
@@ -80,19 +80,18 @@
 #define PAGE_BUG(page) BUG()
 void out_of_line_bug(void);
 
-/* Pure 2^n version of get_order */
-extern __inline__ int get_order(unsigned long size)
-{
-	int order;
+/* Return 'n' in how many 2^n pages are needed to store s bytes.
+** (n == 0 for s == 0)
+*/
+
+#include <asm-generic/page.h>
 
-	size = (size-1) >> (PAGE_SHIFT-1);
-	order = -1;
-	do {
-		size >>= 1;
-		order++;
-	} while (size);
-	return order;
+static __inline__
+int get_order (unsigned long s)
+{
+        return generic_get_order (s);
 }
+
 
 #endif /* __ASSEMBLY__ */
Signature · 1 line
Inaky Perez-Gonzalez -- Not speaking for Intel - opinions are my own [or my fault]
#1 lore raw
Quoted 1 line · Inaky Perez-Gonzalez
    s = --s >> PAGE_SHIFT;

This code has undefined behaviour.

Quoted 1 line
    if (likely (s) < s)

What is that supposed to do?

BTW, I just noticed

#define likely(x) __builtin_expect((x),1)

I think this should rather be

#define likely(x) __builtin_expect((x)!=0,1)

So people can write

if (likely(pointer))

and indeed some people seem to assume that already.

include/linux/compiler.h 2002-11-13 12:44:05.000000000 +0100 renamed from include/linux/compiler.h~ 2002-11-11 04:28:25.000000000 +0100 +1 -1
@@ -10,7 +10,7 @@
 #define __builtin_expect(x, expected_value) (x)
 #endif
 
-#define likely(x)      __builtin_expect((x),1)
+#define likely(x)      __builtin_expect((x)!=0,1)
 #define unlikely(x)    __builtin_expect((x),0)
 
 /* This macro obfuscates arithmetic on a variable address so that gcc
Signature · 1 line
	Falk