Re: Do we need an unsigned multiplyHigh?

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
I am looking forward to intrinsic support for 128 bit math using ?Long2?
and XMM (or even YMM, ZMM) instructions.
This is the best way forward, I hope.

Personally I would like to see a long long type, or even uint128, uint256,
uint512 style notation.

Another option might be something like long<128> or an annotation like
@uint128 long or even @decimal128 double but who knows.

Regards, Peter.


On 25 September 2017 at 18:48, Andrew Haley <[hidden email]> wrote:

> On 25/09/17 18:21, Adam Petcher wrote:
> > I agree that an unsigned multiplyHigh would be useful for crypto
> > purposes, and we should consider adding it. Of course, I would much
> > rather have multiply operations that return both 64-bit parts of the
> > result, but that is going to be hard to do well without value types. So
> > it would be nice to have something like this in the meantime.
>
> I take your point, but it won't be excruciatingly difficult for the C2
> compiler to turn the multiply operations into a single one, if the CPU
> can do that.  From what I've seen recently, though, on non-x86 it's
> common for the two halves of the result to be calculated by separate
> instructions.
>
> > If we are going to add this operation, it should probably be added
> > along with an intrinsic. I think the Java code can simply factor out
> > the else branch from the existing multiplyHigh code. This way,
> > unsignedMultiplyHigh will be at least as fast as multiplyHigh,
> > whether the intrinsic implementation is available or not.
>
> Sure.  I can do that.
>
> > If possible, the implementation of this operation should not branch on
> > either operand. This would make it more widely useful for constant-time
> > crypto implementations. Though this property would need to go into the
> > spec in order for constant-time crypto code to use this method, and I
> > don't know how reasonable it is to put something like this in the spec.
>
> OK.  I can do it so that there are no branches in the Java.  The Java
> code for signed multiplyHigh has some data-dependent branches in an
> attempt to speed it up, though.  I don't know how effective they are,
> and I could have a look at taking them out.
>
> > Side note: at the moment, I am using signed arithmetic in prototypes for
> > Poly1305, X25519, and EdDSA, partially due to lack of support for
> > unsigned operations like this one. I don't think having
> > unsignedMultiplyHigh would, on its own, convince me to use an unsigned
> > representation, but the forces are different for each
> > algorithm/implementation.
>
> Sure.  I don't think it really matters from a performance point of
> view which you use, given intrinsics for both.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
We have arrays already but we don't have primitive types of more than
64-bit. If we had uint128 for example we wouldn't need this method.

On 26 Sep. 2017 11:31, "Andrew Haley" <[hidden email]> wrote:

> On 26/09/17 08:25, Peter Lawrey wrote:
> > I am looking forward to intrinsic support for 128 bit math using ?Long2?
> > and XMM (or even YMM, ZMM) instructions.
> > This is the best way forward, I hope.
> >
> > Personally I would like to see a long long type, or even uint128,
> uint256,
> > uint512 style notation.
> >
> > Another option might be something like long<128> or an annotation like
> > @uint128 long or even @decimal128 double but who knows.
>
> Do you actually need any of that?  I think vector types make more sense.
> Java already has a great many scalar types.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
None, except you end up jumping through hoops to implement 128 bit
arithmetic efficiently or cleanly. At some point language support for such
a basic operation is the simplest and clearest solution.

On 26 Sep. 2017 17:25, "Andrew Haley" <[hidden email]> wrote:

> On 26/09/17 11:20, Peter Lawrey wrote:
> > We have arrays already but we don't have primitive types of more than
> > 64-bit. If we had uint128 for example we wouldn't need this method.
>
> Perhaps not, but why is needing this method a problem?
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
If you need multiplyHigh for 128-bit then you need uint256. At some point
you have to decide whether you need that many bits as a supported
operation.  When Java was created a 64-bit long as the widest type made
sense, however CPUs such as x64 now support 128, 256 and 512 bit natively
and having the JVM dong its best to work this out is not as clean as
defining it explicitly.


On 26 September 2017 at 15:57, Andrew Haley <[hidden email]> wrote:

> On 26/09/17 15:53, Peter Lawrey wrote:
> > None, except you end up jumping through hoops to implement 128 bit
> > arithmetic efficiently or cleanly. At some point language support for
> such
> > a basic operation is the simplest and clearest solution.
>
> There's nothing inefficient about this approach.  I don't quite see
> how 128-bit types help with cleanliness, because then you'd need a
> multiplyHigh for 128-bit types, surely?  You need that for the type
> system to be complete.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
Indeed cleanliness is in the eye of the beholder. ;)
I feel for mathematical code like this it should be possible to write
something as fast and clear as C++, whether that is desirable or not is
another matter.

Perhaps project Valhalla will be a way to return multiple values by having
a composite value type, or panama with it's support for XMM instructions
(or both)




On 27 September 2017 at 16:44, Andrew Haley <[hidden email]> wrote:

> On 27/09/17 11:28, Peter Lawrey wrote:
> > If you need multiplyHigh for 128-bit then you need uint256. At some point
> > you have to decide whether you need that many bits as a supported
> > operation.  When Java was created a 64-bit long as the widest type made
> > sense, however CPUs such as x64 now support 128, 256 and 512 bit natively
> > and having the JVM dong its best to work this out is not as clean as
> > defining it explicitly.
>
> I guess cleanliness is in the eye of the beholder.  IMO multiplyHigh is
> as clean as we need, and I'd rather see more complexity there than in
> the type system.  It'd be nice to be able to return more than one scalar
> value from a method, for sure.
>
> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671
>
Reply | Threaded
Open this post in threaded view
|

Re: Do we need an unsigned multiplyHigh?

Peter Lawrey-3
For context,
While I am more than happy to the builtin encryption libraries which don't
need to be written in Java, we do use wider integers to speed up our parser
and text renders. e.g. it is faster to parse/cache a date/time as if it was
a 128-bit value, than 16 bytes, one byte at a time. This is a use case
which I wouldn't expect a library have an intrinsic for.

Peter.


On 27 September 2017 at 21:45, John Rose <[hidden email]> wrote:

> On Sep 27, 2017, at 8:25 AM, Peter Lawrey <[hidden email]> wrote:
>
>
> Perhaps project Valhalla will be a way to return multiple values by having
> a composite value type, or panama with it's support for XMM instructions
> (or both)
>
>
> That seems likely; we are aiming in both of those directions,
> to support direct programming with AVX-type registers (not
> just x86 specific, by the way) and general support for by-value
> return of structured objects (starting with "minimal value types").
>
> For now, though, every method is limited to at most 64 bits
> of return value "payload", which means that 128-bit operations
> need to be split into two method calls, or else buffer their
> result into a temp object (e.g., array).  The JIT knows how
> to combine two intrinsic calls into a single machine operation,
> in some very limited circumstances, notably the classic
> "div/rem" instructions.  This technique would probably work
> for 64-to-128 multiplies.  (Also AES-128, by the way.)
>
> — John
>