From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
	id S1756331AbbCRRKi (ORCPT <rfc822;w@1wt.eu>);
	Wed, 18 Mar 2015 13:10:38 -0400
Received: from mail-la0-f46.google.com ([209.85.215.46]:33364 "EHLO
	mail-la0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org
	with ESMTP id S1756257AbbCRRKb (ORCPT
	<rfc822;linux-kernel@vger.kernel.org>);
	Wed, 18 Mar 2015 13:10:31 -0400
From: Rasmus Villemoes <linux@rasmusvillemoes.dk>
To: Denys Vlasenko <vda.linux@googlemail.com>
Cc: Andrew Morton <akpm@linux-foundation.org>,
        "Peter Zijlstra \(Intel\)" <peterz@infradead.org>,
        Tejun Heo <tj@kernel.org>,
        Linux Kernel Mailing List <linux-kernel@vger.kernel.org>
Subject: Re: [RFC] lib/vsprintf.c: Even faster decimal conversion
Organization: D03
References: <1424476281-26873-1-git-send-email-linux@rasmusvillemoes.dk>
	<CAK1hOcNsVyHHFX4e+=-_2MrWFnjDedWcO0sS+2gatCeLrV20sw@mail.gmail.com>
X-Hashcash: 1:20:150318:tj@kernel.org::qVESbXWefat05kEI:00000ijI
X-Hashcash: 1:20:150318:peterz@infradead.org::iT1nGMfgzHysA0gY:000000000000000000000000000000000000000001kMH
X-Hashcash: 1:20:150318:vda.linux@googlemail.com::OX7V1O41W9nkdIs6:00000000000000000000000000000000000001+Zk
X-Hashcash: 1:20:150318:linux-kernel@vger.kernel.org::bX5cCzAs8ZIpTGhl:0000000000000000000000000000000002U1Y
X-Hashcash: 1:20:150318:akpm@linux-foundation.org::MswztIp5cBGdsOHA:0000000000000000000000000000000000004/aP
Date: Wed, 18 Mar 2015 18:10:23 +0100
In-Reply-To: <CAK1hOcNsVyHHFX4e+=-_2MrWFnjDedWcO0sS+2gatCeLrV20sw@mail.gmail.com>
	(Denys Vlasenko's message of "Wed, 18 Mar 2015 01:50:35 +0100")
Message-ID: <87r3sm2pvk.fsf@rasmusvillemoes.dk>
User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (gnu/linux)
MIME-Version: 1.0
Content-Type: text/plain
Sender: linux-kernel-owner@vger.kernel.org
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

On Wed, Mar 18 2015, Denys Vlasenko <vda.linux@googlemail.com> wrote:


> Your code does four 16-bit stores.
> The version below does two 32-bit ones instead,
> and it is also marginally smaller.
>
> char *put_dec_full8(char *buf, unsigned r)
> {
>         unsigned q;
>         u32 v;
>
>         /* 0 <= r < 10^8 */
>         q = (r * (u64)0x28f5c29) >> 32;
>         v = (u32)decpair[r - 100*q] << 16;
>
>         /* 0 <= q < 10^6 */
>         r = (q * (u64)0x28f5c29) >> 32;
>         v = v | decpair[q - 100*r];
>         ((u32*)buf)[0] = v;
>
>         /* 0 <= r < 10^4 */
>         q = (r * 0x147b) >> 19;
>         v = (u32)decpair[r - 100*q] << 16;
>
>         /* 0 <= q < 100 */
>         v = v | decpair[q];
>         ((u32*)buf)[1] = v;
>
>         return buf + 8;
> }
>
> It may be faster not only because of having fewer stores,
> but because on x86, this code (moving 16-bit halves):
>
>         movw    decpair(%ebx,%ebx), %dx
>         movw    %dx, 4(%eax)
>         movw    decpair(%ecx,%ecx), %dx
>         movw    %dx, 6(%eax)
>
> suffers from register merge stall when 16-bit value
> is read into lower part of %edx. 32-bit code
> has no such stalls:
>
>         movzwl  decpair(%ebx,%ebx), %edx
>         sall    $16, %edx
>         movzwl  decpair(%ecx,%ecx), %ecx
>         orl     %ecx, %edx
>         movl    %edx, 4(%eax)
>

[On little-endian, I'm pretty sure the <<16 should be applied to the
second and fourth decpair value.]

Thanks for the suggestion. However, I don't see any change in the size
of the generated code (gcc 4.7), and, at least on my Xeon machine,
converting both ULONG_MAX and uniformly random u64s becomes slightly
slower (54 vs 56 cycles and 61 vs 65 cycles).

Rasmus