LKML Archive on lore.kernel.org
 help / color / Atom feed
From: Alexey Dobriyan <adobriyan@gmail.com>
To: akpm@linux-foundation.org
Cc: linux-kernel@vger.kernel.org, Alexey Dobriyan <adobriyan@gmail.com>
Subject: [PATCH 05/13] proc: new and improved way to print decimals
Date: Tue, 28 Aug 2018 02:14:55 +0300
Message-ID: <20180827231503.26899-5-adobriyan@gmail.com> (raw)
In-Reply-To: <20180827231503.26899-1-adobriyan@gmail.com>

C lacks a capable preprocess to turn

	snprintf(buf, sizeof(buf), "%u", x);

into

	print_integer_u32(buf, x);

so vsnprintf() is forced to have a million branches.
Benchmark anything which uses /proc and look for format_decode().

This unfortunate situation was partially fixed by seq_put_decimal_ull()
function which skipped "format specifier" part. However, it still does
unnecessary copies internally and even reflects the digits before
putting them into final buffer. It also does strlen() which is done at
runtime.

The following 3 functions

	_print_integer_u32
	_print_integer_u64
	_print_integer_ul

cut all the overhead by printing backwards one character at a time:

	x = 123456789

	|	<====|
	|...123456789|

This is just as fast as current printing by 2 characters at a time,
because pids, fds, uids are small integers so emitting 2 characters
doesn't make much difference. It also generates very small code
(146 bytes total here, not counting the callers).
Current put_dec() and friends are surprisingly large.

All the functions have the following signature:

	char *_print_integer_XXX(char *p, T x);

They are written quite in a very specific way to prevent gcc from
inlining everything and making a mess.

They aren't exported and advertised because idiomatic way of using them
is not something you see every day:
* fixed sized buffer on stack capable of holding the worst case,
* pointer past the end of the buffer (yay 6.5.6 p8!)
* no buffer length checks (wheee),
* no NUL terminator (ha-ha-ha),
* emitting output BACKWARDS (one character at a time!),
* finally one copy to the final buffer (one copy, one!).

	char buf[10 + 1 + 20 + 1], *p = buf + sizeof(buf);

	*--p = '\n';
	p = _print_integer_u64(p, y);
	*--p = ' ';
	p = _print_integer_u32(p, x);

	seq_write(seq, p, buf + sizeof(buf) - p);

As the comment says, do not tell anyone about these functions.

The plan is to use them inside /proc and only inside /proc.

Signed-off-by: Alexey Dobriyan <adobriyan@gmail.com>
---
 fs/proc/internal.h | 11 +++++++++++
 fs/proc/util.c     | 47 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)

diff --git a/fs/proc/internal.h b/fs/proc/internal.h
index 5185d7f6a51e..be4965ef8e48 100644
--- a/fs/proc/internal.h
+++ b/fs/proc/internal.h
@@ -127,6 +127,17 @@ void task_dump_owner(struct task_struct *task, umode_t mode,
 		     kuid_t *ruid, kgid_t *rgid);
 
 unsigned name_to_int(const struct qstr *qstr);
+
+char *_print_integer_u32(char *, u32);
+char *_print_integer_u64(char *, u64);
+static inline char *_print_integer_ul(char *p, unsigned long x)
+{
+	if (sizeof(unsigned long) == 4)
+		return _print_integer_u32(p, x);
+	else
+		return _print_integer_u64(p, x);
+}
+
 /*
  * Offset of the first process in the /proc root directory..
  */
diff --git a/fs/proc/util.c b/fs/proc/util.c
index b161cfa0f9fa..2d9ceab04289 100644
--- a/fs/proc/util.c
+++ b/fs/proc/util.c
@@ -1,4 +1,5 @@
 #include <linux/dcache.h>
+#include <linux/math64.h>
 
 unsigned name_to_int(const struct qstr *qstr)
 {
@@ -21,3 +22,49 @@ unsigned name_to_int(const struct qstr *qstr)
 out:
 	return ~0U;
 }
+
+/*
+ * Print an integer in decimal.
+ * "p" initially points PAST THE END OF THE BUFFER!
+ *
+ * DO NOT USE THESE FUNCTIONS!
+ *
+ * Do not copy these functions.
+ * Do not document these functions.
+ * Do not move these functions to lib/ or elsewhere.
+ * Do not export these functions to modules.
+ * Do not tell anyone about these functions.
+ */
+noinline
+char *_print_integer_u32(char *p, u32 x)
+{
+	do {
+		*--p = '0' + (x % 10);
+		x /= 10;
+	} while (x != 0);
+	return p;
+}
+
+static char *__print_integer_u32(char *p, u32 x)
+{
+	/* 0 <= x < 10^8 */
+	char *p0 = p - 8;
+
+	p = _print_integer_u32(p, x);
+	while (p != p0)
+		*--p = '0';
+	return p;
+}
+
+char *_print_integer_u64(char *p, u64 x)
+{
+	while (x >= 100000000) {
+		u64 q;
+		u32 r;
+
+		q = div_u64_rem(x, 100000000, &r);
+		p = __print_integer_u32(p, r);
+		x = q;
+	}
+	return _print_integer_u32(p, x);
+}
-- 
2.16.4


  parent reply index

Thread overview: 24+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-27 23:14 [PATCH 01/13] seq_file: rewrite seq_puts() in terms of seq_write() Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 02/13] proc: apply seq_puts() whenever possible Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 03/13] proc: rename "p" variable in proc_readfd_common() Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 04/13] proc: rename "p" variable in proc_map_files_readdir() Alexey Dobriyan
2018-08-27 23:14 ` Alexey Dobriyan [this message]
2018-08-27 23:14 ` [PATCH 06/13] proc: convert /proc/self to _print_integer() Alexey Dobriyan
2018-08-29  9:50   ` David Laight
2018-08-30 13:13     ` Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 07/13] proc: convert /proc/thread-self " Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 08/13] proc: convert /proc/*/fd " Alexey Dobriyan
2018-08-27 23:14 ` [PATCH 09/13] proc: convert dentry flushing on exit " Alexey Dobriyan
2018-08-27 23:15 ` [PATCH 10/13] proc: convert readdir /proc " Alexey Dobriyan
2018-08-27 23:15 ` [PATCH 11/13] proc: readdir /proc/*/task Alexey Dobriyan
2018-08-28 12:36   ` Ahmed S. Darwish
2018-08-28 13:04     ` Ahmed S. Darwish
2018-08-28 19:35       ` Alexey Dobriyan
2018-08-29 23:43         ` Andrew Morton
2018-08-30 13:20           ` Alexey Dobriyan
2018-08-28 19:31     ` Alexey Dobriyan
2018-08-27 23:15 ` [PATCH 12/13] proc: convert /proc/*/statm to _print_integer() Alexey Dobriyan
2018-08-27 23:15 ` [PATCH 13/13] proc: convert /proc/*/task/*/children " Alexey Dobriyan
2018-08-28 18:24 ` [PATCH 01/13] seq_file: rewrite seq_puts() in terms of seq_write() Joe Perches
2018-08-28 20:48   ` Joe Perches
2018-09-03 14:17 ` Alexey Dobriyan

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20180827231503.26899-5-adobriyan@gmail.com \
    --to=adobriyan@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=linux-kernel@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

LKML Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lkml.kernel.org/lkml/0 lkml/git/0.git
	git clone --mirror https://lkml.kernel.org/lkml/1 lkml/git/1.git
	git clone --mirror https://lkml.kernel.org/lkml/2 lkml/git/2.git
	git clone --mirror https://lkml.kernel.org/lkml/3 lkml/git/3.git
	git clone --mirror https://lkml.kernel.org/lkml/4 lkml/git/4.git
	git clone --mirror https://lkml.kernel.org/lkml/5 lkml/git/5.git
	git clone --mirror https://lkml.kernel.org/lkml/6 lkml/git/6.git
	git clone --mirror https://lkml.kernel.org/lkml/7 lkml/git/7.git
	git clone --mirror https://lkml.kernel.org/lkml/8 lkml/git/8.git
	git clone --mirror https://lkml.kernel.org/lkml/9 lkml/git/9.git
	git clone --mirror https://lkml.kernel.org/lkml/10 lkml/git/10.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 lkml lkml/ https://lkml.kernel.org/lkml \
		linux-kernel@vger.kernel.org
	public-inbox-index lkml

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.linux-kernel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git