linux-kernel - Re: [PATCHv2 2/3] lib: vsprintf: optimised put

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Tue, 10 Aug 2010 06:15:52 +0200
From:	Denys Vlasenko <vda.linux@...glemail.com>
To:	Michal Nazarewicz <mina86@...a86.com>
Cc:	linux-kernel@...r.kernel.org, m.nazarewicz@...sung.com,
	"Douglas W. Jones" <jones@...uiowa.edu>,
	Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCHv2 2/3] lib: vsprintf: optimised put_dec() for 32-bit machines

On Sunday 08 August 2010 21:29, Michal Nazarewicz wrote:
> Compared to previous version: the code is used only if:
> 1. if long long is 64-bit (ie. ULLONG_MAX == 2**64-1), and
> 2. user did not select optimisation for size with Kconfig.

I measured the size and it does not seem to make sense
to exclude it on -Os. On x86:

put_dec_full change: 0x93 -> 0x47 bytes
put_dec      change: 0x12c -> 0x137 bytes

IOW, there is net code size reduction (compared to current kernel,
it may be a slight growth compared to patch 1).

So, please use the optimized code even for CONFIG_CC_OPTIMIZE_FOR_SIZE.


> Here are the results (normalised to the fastest/smallest):
>                     :        ARM       Atom
> -- Speed ----------------------------------
> orig_put_dec        :   9.333822   2.083110  Original
> mod1_put_dec        :   9.282045   1.904564
> mod2_put_dec        :   9.260409   1.910302
> mod3_put_dec        :   9.320053   1.905689  Proposed by previous patch
> mod4_put_dec        :   9.297146   1.933971
> mod5_put_dec        :  13.034318   2.434942
> mod6_put_dec        :   1.000000   1.000000  Proposed by this patch
> mod7_put_dec        :   1.009574   1.014147
> mod8_put_dec        :   7.226004   1.953460
> -- Size -----------------------------------
> orig_put_dec        :   1.000000   1.000000  Original
> mod1_put_dec        :   1.000000   1.000000
> mod2_put_dec        :   1.361111   1.403226
> mod3_put_dec        :   1.000000   1.000000  Proposed by previous patch
> mod4_put_dec        :   1.361111   1.403226
> mod5_put_dec        :   1.000000   1.000000
> mod6_put_dec        :   2.555556   3.508065  Proposed by this patch
> mod7_put_dec        :   2.833333   3.911290
> mod8_put_dec        :   2.027778   2.258065

I believe these are old results? Size growth is just too big.


> As it can be obsevred, proposed version of the put_dec function is
> twice as fast as the original version on Atom and almost 10 times
> faster on ARM.  I imagine that it may be similar on other "embedded"
> processors.
> 
> This may be skewed by the fact that the benchmark is using GCC's
> 64-bit division operator instead of kernel's do_div but it would
> appear that by avoiding 64-bit division something can be gained.

Re speed: on Phenom II in 32-bit mode, I see ~x3.3 speedup
on conversions involving large integers (might be skewed
by gcc's full-blown 64-bit division in "old" code - kernel's
div is smarter).


> PS. From Mr. Jones site: "Nonetheless, before relying on the material
> here, it would be prudent to check the arithmetic!" hence I checked
> all the calculations myself and everything seemed fine.  I've also run
> test applitacion several times so it tested a few 64-bit numbers..."

I tested [0, 100 million] and [2^64-100 million, 2^64-1] ranges.
No errors.


> +#if BITS_PER_LONG != 32 || defined CONFIG_CC_OPTIMIZE_FOR_SIZE || \
> +	ULLONG_MAX != 18446744073709551615ULL

I think it's better to say "if BITS_PER_LONG > 32 and ULLONG_MAX > 2^64-1",
since it expresses your intent better. Also, add comments explaining
what case you optimize for:

#if BITS_PER_LONG > 32 || ULLONG_MAX > 18446744073709551615ULL

/* Generic code */
...

#else /* BITS_PER_LONG <= 32 && ULLONG_MAX <= 2^64-1 */

/* Optimized code for arches with 64-bit long longs */
...


> +static noinline_for_stack
> +char *put_dec(char *buf, unsigned long long n)
> +{
> +	uint32_t d3, d2, d1, q;
> +
> +	if (!n) {
> +		*buf++ = '0';
> +		return buf;
> +	}

You may as well use the above shortcut for n <= 9, not only for 0.

> +	buf = put_dec_full4(buf, q % 10000);
> +	q   = q / 10000;
> +
> +	d1  = q + 7671 * d3 + 9496 * d2 + 6 * d1;
> +	buf = put_dec_full4(buf, d1 % 10000);
> +	q   = d1 / 10000;

I experimented with moving division up, before put_dec_full4:
q   = d1 / 10000;
buf = put_dec_full4(buf, d1 % 10000);
but gcc appears to be smart emough to do this transformation
itself. But you may still do it for older (dumber) gcc's.

-- 
vda
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/