aboutsummaryrefslogtreecommitdiff
path: root/lib/vsprintf.c
AgeCommit message (Collapse)Author
2007-07-16vsprintf.c: optimizing, part 2: base 10 conversion speedup, v2Denis Vlasenko
Optimize integer-to-string conversion in vsprintf.c for base 10. This is by far the most used conversion, and in some use cases it impacts performance. For example, top reads /proc/$PID/stat for every process, and with 4000 processes decimal conversion alone takes noticeable time. Using code from http://www.cs.uiowa.edu/~jones/bcd/decimal.html (with permission from the author, Douglas W. Jones) binary-to-decimal-string conversion is done in groups of five digits at once, using only additions/subtractions/shifts (with -O2; -Os throws in some multiply instructions). On i386 arch gcc 4.1.2 -O2 generates ~500 bytes of code. This patch is run tested. Userspace benchmark/test is also attached. I tested it on PIII and AMD64 and new code is generally ~2.5 times faster. On AMD64: # ./vsprintf_verify-O2 Original decimal conv: .......... 151 ns per iteration Patched decimal conv: .......... 62 ns per iteration Testing correctness 12895992590592 ok... [Ctrl-C] # ./vsprintf_verify-O2 Original decimal conv: .......... 151 ns per iteration Patched decimal conv: .......... 62 ns per iteration Testing correctness 26025406464 ok... [Ctrl-C] More realistic test: top from busybox project was modified to report how many us it took to scan /proc (this does not account any processing done after that, like sorting process list), and then I test it with 4000 processes: #!/bin/sh i=4000 while test $i != 0; do sleep 30 & let i-- done busybox top -b -n3 >/dev/null on unpatched kernel: top: 4120 processes took 102864 microseconds to scan top: 4120 processes took 91757 microseconds to scan top: 4120 processes took 92517 microseconds to scan top: 4120 processes took 92581 microseconds to scan on patched kernel: top: 4120 processes took 75460 microseconds to scan top: 4120 processes took 66451 microseconds to scan top: 4120 processes took 67267 microseconds to scan top: 4120 processes took 67618 microseconds to scan The speedup comes from much faster generation of /proc/PID/stat by sprintf() calls inside the kernel. Signed-off-by: Douglas W Jones <jones@cs.uiowa.edu> Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-07-16vsprintf.c: optimizing, part 1 (easy and obvious stuff)Denis Vlasenko
* There is no point in having full "0...9a...z" constant vector, if we use only "0...9a...f" (and "x" for "0x"). * Post-decrement usually needs a few more instructions, so use pre decrement instead where makes sense: -       while (i < precision--) { +       while (i <= --precision) { * if base != 10 (=> base 8 or 16), we can avoid using division in a loop and use mask/shift, obtaining much faster conversion. (More complex optimization for base 10 case is in the second patch). Overall, size vsprintf.o shows ~80 bytes smaller text section with this patch applied. Signed-off-by: Douglas W Jones <jones@cs.uiowa.edu> Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-05-08fix sscanf %n match at end of input stringJohannes Berg
I was playing with some code that sometimes got a string where a %n match should have been done where the input string ended, for example like this: sscanf("abc123", "abc%d%n", &a, &n); /* doesn't work */ sscanf("abc123a", "abc%d%n", &a, &n); /* works */ However, the scanf function in the kernel doesn't convert the %n in that case because it has already matched the complete input after %d and just completely stops matching then. This patch fixes that. [akpm@linux-foundation.org: cleanups] Signed-off-by: Johannes Berg <johannes@sipsolutions.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-04-30Add kvasprintf()Jeremy Fitzhardinge
Add a kvasprintf() function to complement kasprintf(). No in-tree users yet, but I have some coming up. [akpm@linux-foundation.org: EXPORT it] Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Cc: Andrew Morton <akpm@linux-foundation.org> Cc: Keir Fraser <keir@xensource.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-02-12[PATCH] scnprintf(): fix a commentMartin Peschke
The return value of scnprintf() never exceeds @size. Signed-off-by: Martin Peschke <mp3@de.ibm.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2007-02-11[PATCH] Numerous fixes to kernel-doc info in source files.Robert P. J. Day
A variety of (mostly) innocuous fixes to the embedded kernel-doc content in source files, including: * make multi-line initial descriptions single line * denote some function names, constants and structs as such * change erroneous opening '/*' to '/**' in a few places * reword some text for clarity Signed-off-by: Robert P. J. Day <rpjday@mindspring.com> Cc: "Randy.Dunlap" <rdunlap@xenotime.net> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
2006-06-28Fix vsnprintf off-by-one bugLinus Torvalds
The recent vsnprintf() fix introduced an off-by-one, and it's now possible to overrun the target buffer by one byte. The "end" pointer points to past the end of the buffer, so if we have to truncate the result, it needs to be done though "end[-1]". [ This is just an alternate and simpler patch to one proposed by Andrew and Jeremy, who actually noticed the problem ] Acked-by: Andrew Morton <akpm@osdl.org> Acked-by: Jeremy Fitzhardinge <jeremy@goop.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] Implement kasprintfJeremy Fitzhardinge
Implement kasprintf, a kernel version of asprintf. This allocates the memory required for the formatted string, including the trailing '\0'. Returns NULL on allocation failure. Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Signed-off-by: Chris Wright <chrisw@sous-sol.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2006-06-25[PATCH] Fix bounds check in vsnprintf, to allow for a 0 size and NULL bufferJeremy Fitzhardinge
This change allows callers to use a 0-byte buffer and a NULL buffer pointer with vsnprintf, so it can be used to determine how large the resulting formatted string will be. Previously the code effectively treated a size of 0 as a size of 4G (on 32-bit systems), with other checks preventing it from actually trying to emit the string - but the terminal \0 would still be written, which would crash if the buffer is NULL. This change changes the boundary check so that 'end' points to the putative location of the terminal '\0', which is only written if size > 0. vsnprintf still allows the buffer size to be set very large, to allow unbounded buffer sizes (to implement sprintf, etc). [akpm@osdl.org: fix long-vs-longlong confusion] Signed-off-by: Jeremy Fitzhardinge <jeremy@xensource.com> Signed-off-by: Chris Wright <chrisw@sous-sol.org> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-10-30[PATCH] fix missing includesTim Schmielau
I recently picked up my older work to remove unnecessary #includes of sched.h, starting from a patch by Dave Jones to not include sched.h from module.h. This reduces the number of indirect includes of sched.h by ~300. Another ~400 pointless direct includes can be removed after this disentangling (patch to follow later). However, quite a few indirect includes need to be fixed up for this. In order to feed the patches through -mm with as little disturbance as possible, I've split out the fixes I accumulated up to now (complete for i386 and x86_64, more archs to follow later) and post them before the real patch. This way this large part of the patch is kept simple with only adding #includes, and all hunks are independent of each other. So if any hunk rejects or gets in the way of other patches, just drop it. My scripts will pick it up again in the next round. Signed-off-by: Tim Schmielau <tim@physik3.uni-rostock.de> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-08-23[PATCH] %t... in vsnprintfAl Viro
handling of %t... (ptrdiff_t) in vsnprintf Signed-off-by: Al Viro <viro@parcelfarce.linux.theplanet.co.uk> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
2005-04-16Linux-2.6.12-rc2Linus Torvalds
Initial git repository build. I'm not bothering with the full history, even though we have it. We can create a separate "historical" git archive of that later if we want to, and in the meantime it's about 3.2GB when imported into git - space that would just make the early git days unnecessarily complicated, when we don't have a lot of good infrastructure for it. Let it rip!