Date: Sat, 4 Jan 2020 09:59:46 +0100 (CET)
From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Tom Lane <tgl@sss.pgh.pa.us>
cc: Andres Freund <andres@anarazel.de>,
    Vik Fearing <vik.fearing@2ndquadrant.com>,
    Stephen Frost <sfrost@snowman.net>,
    Dean Rasheed <dean.a.rasheed@gmail.com>,
    Chapman Flack <chap@anastigmatix.net>,
    PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
In-Reply-To: <15070.1578097070@sss.pgh.pa.us>
Message-ID: <alpine.DEB.2.21.2001040941250.31333@pseudo>
References: <alpine.DEB.2.21.1912290815520.889@pseudo>
 <5E08D947.9000902@anastigmatix.net>
 <alpine.DEB.2.21.1912291755510.14206@pseudo>
 <CAEZATCX9YgkWupVFcJ5ixkEJMyf2X5ZecN8K5r12oOB8mDHzWQ@mail.gmail.com>
 <20200102145712.GN3195@tamriel.snowman.net>
 <16242.1577977961@sss.pgh.pa.us>
 <6855727c-3836-21cc-18f9-e79227b99079@2ndquadrant.com>
 <alpine.DEB.2.21.2001032010470.12030@pseudo>
 <5bf72c6b-1290-2ba0-770b-8a13e899fd98@2ndquadrant.com>
 <13445.1578095358@sss.pgh.pa.us>
 <20200104001001.wzkk5nrea323hwyx@alap3.anarazel.de>
 <15070.1578097070@sss.pgh.pa.us>
User-Agent: Alpine 2.21 (DEB 202 2017-01-01)
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII; format=flowed
Precedence: bulk


Hello Tom,

>> Which architecture has single cycle division? I think it's way above
>> that, based on profiles I've seen. And Agner seems to back me up:
>> https://www.agner.org/optimize/instruction_tables.pdf
>> That lists a 32/64 idiv with a latency of ~26/~42-95 cycles, even on a
>> moder uarch like skylake-x.
>
> Huh.  I figured Intel would have thrown sufficient transistors at that
> problem by now.

It is not just a problem of number of transistors, division is 
intrisically iterative (with various kind of iterations used in division 
algorithms), involving some level of guessing and other arithmetics, so 
the latency can only be bad, and the possibility of implementing that in 1 
cycle at 3 GHz looks pretty remote.

-- 
Fabien.