On Tuesday 06 March 2007 17:28, H. Peter Anvin wrote:
> Eric Dumazet wrote:
> > For epoll, I suspect this is harmless : Programs dont allocate epolls fd
> > every milli second, but at startup only.
> >
> > For pipes/sockets, using a 64 bits would be problematic, because
> > sprintf() uses a divide for each digit. And a divide is slow. Ten
> > divides are *very* slow.
>
> That's true for *any* sprintf(), though. sprintf() converts all its
> arguments to 64 bits.
>
> However, this could be optimized. I think right now sprintf() uses a
> generic divide-by-base, but a divide by 8 and 16 can of course be
> handled with a shift, and divide by 10 can be replaced with a
> multiplication by 0x1999999999999999ULL on most architectures.
Or maybe just use reciprocal division, to keep the 35 bases available in
number()
Something like :
[PATCH] : Use reciprocal divides in sprintf()
pipe() syscalls spend a noticeable amount of time in sprintf() to format their
dentry name. One name may want to print 9 or 10 digits, using one divide per
digit.
Using reciprocal divides permits to change each divide by two multiplies, less
expensive on current CPUS.
Signed-off-by: Eric Dumazet <[EMAIL PROTECTED]>
diff --git a/include/linux/reciprocal_div.h b/include/linux/reciprocal_div.h
index f9c90b3..55a79e0 100644
--- a/include/linux/reciprocal_div.h
+++ b/include/linux/reciprocal_div.h
@@ -23,7 +23,10 @@ #include <linux/types.h>
* or else the performance is slower than a normal divide.
*/
extern u32 reciprocal_value(u32 B);
-
+/*
+ * precomputed reciprocal values of integers from 0 to 36
+ */
+extern const u32 reciprocal_values[36 + 1];
static inline u32 reciprocal_divide(u32 A, u32 R)
{
diff --git a/lib/reciprocal_div.c b/lib/reciprocal_div.c
index 6a3bd48..2dcea45 100644
--- a/lib/reciprocal_div.c
+++ b/lib/reciprocal_div.c
@@ -1,6 +1,31 @@
#include <asm/div64.h>
#include <linux/reciprocal_div.h>
+#define CONSTANT_RECIPROCAL_VALUE(k) \
+ (u32)(((1LL << 32) + (k - 1)) / k)
+
+const u32 reciprocal_values[36 + 1] = {
+ 0,
+ CONSTANT_RECIPROCAL_VALUE(1), CONSTANT_RECIPROCAL_VALUE(2),
+ CONSTANT_RECIPROCAL_VALUE(3), CONSTANT_RECIPROCAL_VALUE(4),
+ CONSTANT_RECIPROCAL_VALUE(5), CONSTANT_RECIPROCAL_VALUE(6),
+ CONSTANT_RECIPROCAL_VALUE(7), CONSTANT_RECIPROCAL_VALUE(8),
+ CONSTANT_RECIPROCAL_VALUE(9), CONSTANT_RECIPROCAL_VALUE(10),
+ CONSTANT_RECIPROCAL_VALUE(11), CONSTANT_RECIPROCAL_VALUE(12),
+ CONSTANT_RECIPROCAL_VALUE(13), CONSTANT_RECIPROCAL_VALUE(14),
+ CONSTANT_RECIPROCAL_VALUE(15), CONSTANT_RECIPROCAL_VALUE(16),
+ CONSTANT_RECIPROCAL_VALUE(17), CONSTANT_RECIPROCAL_VALUE(18),
+ CONSTANT_RECIPROCAL_VALUE(19), CONSTANT_RECIPROCAL_VALUE(20),
+ CONSTANT_RECIPROCAL_VALUE(21), CONSTANT_RECIPROCAL_VALUE(22),
+ CONSTANT_RECIPROCAL_VALUE(23), CONSTANT_RECIPROCAL_VALUE(24),
+ CONSTANT_RECIPROCAL_VALUE(25), CONSTANT_RECIPROCAL_VALUE(26),
+ CONSTANT_RECIPROCAL_VALUE(27), CONSTANT_RECIPROCAL_VALUE(28),
+ CONSTANT_RECIPROCAL_VALUE(29), CONSTANT_RECIPROCAL_VALUE(30),
+ CONSTANT_RECIPROCAL_VALUE(31), CONSTANT_RECIPROCAL_VALUE(32),
+ CONSTANT_RECIPROCAL_VALUE(33), CONSTANT_RECIPROCAL_VALUE(34),
+ CONSTANT_RECIPROCAL_VALUE(35), CONSTANT_RECIPROCAL_VALUE(36),
+};
+
u32 reciprocal_value(u32 k)
{
u64 val = (1LL << 32) + (k - 1);
diff --git a/lib/vsprintf.c b/lib/vsprintf.c
index b025864..9c98cc4 100644
--- a/lib/vsprintf.c
+++ b/lib/vsprintf.c
@@ -22,6 +22,7 @@ #include <linux/types.h>
#include <linux/string.h>
#include <linux/ctype.h>
#include <linux/kernel.h>
+#include <linux/reciprocal_div.h>
#include <asm/page.h> /* for PAGE_SIZE */
#include <asm/div64.h>
@@ -180,8 +181,16 @@ static char * number(char * buf, char *
i = 0;
if (num == 0)
tmp[i++]='0';
- else while (num != 0)
- tmp[i++] = digits[do_div(num,base)];
+ else {
+ while (num >> 32)
+ tmp[i++] = digits[do_div(num,base)];
+ while (num != 0) {
+ u32 next = reciprocal_divide((u32)num,
+ reciprocal_values[base]);
+ tmp[i++] = digits[num - next*base];
+ num = next;
+ }
+ }
if (i > precision)
precision = i;
size -= precision;
