linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Andy Shevchenko <andriy.shevchenko@linux.intel.com>
To: Alexey Dobriyan <adobriyan@gmail.com>
Cc: akpm@linux-foundation.org, linux-kernel@vger.kernel.org,
	linux-fsdevel@vger.kernel.org, pmladek@suse.com,
	rostedt@goodmis.org, sergey.senozhatsky@gmail.com,
	linux@rasmusvillemoes.dk
Subject: Re: [PATCH 03/15] print_integer: new and improved way of printing integers
Date: Tue, 21 Apr 2020 00:27:23 +0300	[thread overview]
Message-ID: <20200420212723.GE185537@smile.fi.intel.com> (raw)
In-Reply-To: <20200420211911.GC185537@smile.fi.intel.com>

On Tue, Apr 21, 2020 at 12:19:11AM +0300, Andy Shevchenko wrote:
> On Mon, Apr 20, 2020 at 11:57:31PM +0300, Alexey Dobriyan wrote:
> > Time honored way to print integers via vsnprintf() or equivalent has
> > unavoidable slowdown of parsing format string. This can't be fixed in C,
> > without introducing external preprocessor.
> > 
> > seq_put_decimal_ull() partially saves the day, but there are a lot of
> > branches inside and overcopying still.
> > 
> > _print_integer_*() family of functions is meant to make printing
> > integers as fast as possible by deleting format string parsing and doing
> > as little work as possible.
> > 
> > It is based on the following observations:
> > 
> > 1) memcpy is done in forward direction
> > 	it can be done backwards but nobody does that,
> > 
> > 2) digits can be extracted in a very simple loop which costs only
> > 	1 multiplication and shift (division by constant is not division)
> > 
> > All the above asks for the following signature, semantics and pattern of
> > printing out beloved /proc files:
> > 
> > 	/* seq_printf(seq, "%u %llu\n", A, b); */
> > 
> > 	char buf[10 + 1 + 20 + 1];
> > 	char *p = buf + sizeof(buf);
> > 
> > 	*--p = '\n';
> > 	p = _print_integer_u64(p, B);
> > 	*--p = ' ';
> > 	p = _print_integer_u32(p, A);
> > 
> > 	seq_write(seq, p, buf + sizeof(buf) - p);
> > 
> > 1) stack buffer capable of holding the biggest string is allocated.
> > 
> > 2) "p" is pointer to start of the string. Initially it points past
> > 	the end of the buffer WHICH IS NOT NUL-TERMINATED!
> > 
> > 3) _print_integer_*() actually prints an integer from right to left
> > 	and returns new start of the string.
> > 
> > 			     <--------|
> > 				123
> > 				^
> > 				|
> > 				+-- p
> > 
> > 4) 1 character is printed with
> > 
> > 	*--p = 'x';
> > 
> > 	It generates very efficient code as multiple writes can be
> > 	merged.
> > 
> > 5) fixed string is printed with
> > 
> > 	p = memcpy(p - 3, "foo", 3);
> > 
> > 	Complers know what memcpy() does and write-combine it.
> > 	4/8-byte writes become 1 instruction and are very efficient.
> > 
> > 6) Once everything is printed, the result is written to seq_file buffer.
> > 	It does only one overflow check and 1 copy.
> > 
> > This generates very efficient code (and small!).
> > 
> > In regular seq_printf() calls, first argument and format string are
> > constantly reloaded. Format string will most likely with [rip+...] which
> > is quite verbose.
> > 
> > seq_put_decimal_ull() will do branches (and even more branches
> > with "width" argument)
> > 
> 
> > 	TODO
> > 	benchmark with mainline because nouveau is broken for me -(
> > 	vsnprintf() changes make the code slower
> 
> Exactly main point of this exercise. I don't believe that algos in vsprintf.c
> are too dumb to use division per digit (yes, division by constant which is not
> power of two is a heavy operation).
> 

And second point here, why not to use existing algos from vsprintf.c?

-- 
With Best Regards,
Andy Shevchenko



  reply	other threads:[~2020-04-20 21:27 UTC|newest]

Thread overview: 26+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-04-20 20:57 [PATCH 01/15] sched: make nr_running() return "unsigned int" Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 02/15] sched: make nr_iowait_cpu() " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 03/15] print_integer: new and improved way of printing integers Alexey Dobriyan
2020-04-20 21:19   ` Andy Shevchenko
2020-04-20 21:27     ` Andy Shevchenko [this message]
2020-04-21  1:54       ` Steven Rostedt
2020-04-21 16:49         ` Alexey Dobriyan
2020-04-21 21:08           ` Steven Rostedt
2020-04-23  3:42           ` Sergey Senozhatsky
2020-04-21 16:31     ` Alexey Dobriyan
2020-04-21 16:59   ` Matthew Wilcox
2020-04-20 20:57 ` [PATCH 04/15] print_integer, proc: rewrite /proc/self via print_integer() Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 05/15] print_integer, proc: rewrite /proc/thread-self " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 06/15] print_integer, proc: rewrite /proc/loadavg " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 07/15] print_integer, proc: rewrite /proc/stat " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 08/15] print_integer, proc: rewrite /proc/uptime " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 09/15] proc: s/p/tsk/ Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 10/15] print_integer, proc: rewrite /proc/*/fd via print_integer() Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 11/15] print_integer, proc: rewrite /proc/*/stat " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 12/15] print_integer, proc: rewrite /proc/*/statm " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 13/15] print_integer, printf: rewrite num_to_str() " Alexey Dobriyan
2020-04-20 20:57 ` [PATCH 14/15] print_integer, printf: rewrite the rest of lib/vsprintf.c " Alexey Dobriyan
2020-04-21  2:01   ` Steven Rostedt
2020-04-20 20:57 ` [PATCH 15/15] print_integer, proc: rewrite /proc/meminfo " Alexey Dobriyan
2020-04-20 21:05 ` [PATCH 01/15] sched: make nr_running() return "unsigned int" Matthew Wilcox
2020-04-21 17:06   ` 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=20200420212723.GE185537@smile.fi.intel.com \
    --to=andriy.shevchenko@linux.intel.com \
    --cc=adobriyan@gmail.com \
    --cc=akpm@linux-foundation.org \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux@rasmusvillemoes.dk \
    --cc=pmladek@suse.com \
    --cc=rostedt@goodmis.org \
    --cc=sergey.senozhatsky@gmail.com \
    --subject='Re: [PATCH 03/15] print_integer: new and improved way of printing integers' \
    /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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).