pg.ddx.io  pgsql-hackers@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Fabien COELHO <coelho@cri.ensmp.fr>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Andres Freund <andres@anarazel.de>
Cc: Vik Fearing <vik.fearing@2ndquadrant.com>
Cc: Stephen Frost <sfrost@snowman.net>
Cc: Dean Rasheed <dean.a.rasheed@gmail.com>
Cc: Chapman Flack <chap@anastigmatix.net>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Greatest Common Divisor
Date: Sat, 4 Jan 2020 09:59:46 +0100 (CET)
Message-ID: <alpine.DEB.2.21.2001040941250.31333@pseudo> (raw)
In-Reply-To: <15070.1578097070@sss.pgh.pa.us>
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>


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.





view thread (70+ messages)  latest in thread

Message-ID: <alpine.DEB.2.21.2001040941250.31333@pseudo>
Permalink:  ../alpine.DEB.2.21.2001040941250.31333@pseudo/
Also on:    postgresql.org/message-id/alpine.DEB.2.21.2001040941250.31333@pseudo

 · 

reply
Reply instructions:

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

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-hackers@postgresql.org
  Cc: coelho@cri.ensmp.fr, tgl@sss.pgh.pa.us, andres@anarazel.de, vik.fearing@2ndquadrant.com, sfrost@snowman.net, dean.a.rasheed@gmail.com, chap@anastigmatix.net, pgsql-hackers@lists.postgresql.org
  Subject: Re: Greatest Common Divisor
  In-Reply-To: <alpine.DEB.2.21.2001040941250.31333@pseudo>

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

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox