New bigint implementation in the vm.

New bigint implementation in the vm.

R=srdjan@google.com

Committed: https://code.google.com/p/dart/source/detail?r=40061

[regis, 2014-09-05 23:07:42]

regis@google.com changed reviewers:
+ srdjan@google.com

[regis, 2014-09-05 23:07:43]

This is slower than the replaced version, because no intrinsics are implemented
yet.

[Florian Schneider, 2014-09-08 09:10:19]

fschneider@google.com changed reviewers:
+ fschneider@google.com

[Florian Schneider, 2014-09-08 09:10:20]

dbc:

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:43: static const int DIGIT_BITS = 32;
Ideally, this should be platform-specific and dependent on the machine-word
size.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:56: static const int FP_BITS = 52;
These constants should not be needed anymore since they are used to make the
math work in JavaScript.

[srdjan, 2014-09-08 19:19:49]

https://codereview.chromium.org/509153003/diff/40001/runtime/bin/dartutils.cc
File runtime/bin/dartutils.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/bin/dartutils.cc...
runtime/bin/dartutils.cc:877: 
two lines

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:80: */
Remove dead code.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc
File runtime/lib/integers.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc#...
runtime/lib/integers.cc:60: return result.AsValidInteger();
maybe: result.IsNull() ? result.raw() : result.AsValidInteger(); ?

You could add a comment to all relevant methods that they return  null if a
bigint operation is required.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc#...
runtime/lib/integers.cc:489: DEFINE_NATIVE_ENTRY(Bigint_allocate, 1) {
Why one argument? type?

https://codereview.chromium.org/509153003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:387: ASSERT(!value.IsBigint() ||
!Bigint::Cast(value).FitsIntoInt64());
We need these asserts in some form.

[regis, 2014-09-09 19:18:14]

Thanks.

I've cleaned up a few more TODOs and added intrinsics for bigint field
accessors.

I have also added overriding methods in class _Bigint to shortcut the native
calls that would return null, because the receiver is bigint.

Please, have another look.

I think we can submit this version and then start to optimize it by providing
more intrinsics.

Thanks,
Regis

https://codereview.chromium.org/509153003/diff/40001/runtime/bin/dartutils.cc
File runtime/bin/dartutils.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/bin/dartutils.cc...
runtime/bin/dartutils.cc:877: 
On 2014/09/08 19:19:49, srdjan wrote:
> two lines

Done.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:43: static const int DIGIT_BITS = 32;
On 2014/09/08 09:10:19, Florian Schneider wrote:
> Ideally, this should be platform-specific and dependent on the machine-word
> size.

Ideally, yes. But this would require a tremendous amount of quasi-duplicated
code, both C++ and Dart. The plan is to only support 32-bit digits on all
platforms. Later, however, we could change the code to guarantee an even number
of digits, which would allow manipulating 2 digits at a time in intrinsics on
64-bit platforms.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:56: static const int FP_BITS = 52;
On 2014/09/08 09:10:19, Florian Schneider wrote:
> These constants should not be needed anymore since they are used to make the
> math work in JavaScript.

These constants are needed to approximate a division step using the FPU. Nothing
to do with Javascript.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:80: */
On 2014/09/08 19:19:49, srdjan wrote:
> Remove dead code.

Done.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc
File runtime/lib/integers.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc#...
runtime/lib/integers.cc:60: return result.AsValidInteger();
On 2014/09/08 19:19:49, srdjan wrote:
> maybe: result.IsNull() ? result.raw() : result.AsValidInteger(); ?
> 
> You could add a comment to all relevant methods that they return  null if a
> bigint operation is required.

Done.

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/integers.cc#...
runtime/lib/integers.cc:489: DEFINE_NATIVE_ENTRY(Bigint_allocate, 1) {
On 2014/09/08 19:19:49, srdjan wrote:
> Why one argument? type?

This is the null type arguments, since class Bigint is not parameterized. Added
comment.

https://codereview.chromium.org/509153003/diff/40001/runtime/vm/intermediate_...
File runtime/vm/intermediate_language.cc (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/vm/intermediate_...
runtime/vm/intermediate_language.cc:387: ASSERT(!value.IsBigint() ||
!Bigint::Cast(value).FitsIntoInt64());
On 2014/09/08 19:19:49, srdjan wrote:
> We need these asserts in some form.

I made the Bigint instances representing small numbers non-constant and
reinstated these asserts here.

[srdjan, 2014-09-09 19:31:44]

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:233: void _copyTo(r) {
Please add type to arguments (here and below).

[srdjan, 2014-09-09 20:22:01]

LGTM

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/bigint_operat...
File runtime/vm/bigint_operations_test.cc (left):

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/bigint_operat...
runtime/vm/bigint_operations_test.cc:2237: "01234567890ABCDEE");
Can we move these tests to Dart code?

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/object.cc#new...
runtime/vm/object.cc:15630: ASSERT(IsBigint());
Is the assert needed? I assume Bigint::Cast has one? (here and below).

[regis, 2014-09-09 21:19:38]

Thanks!

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/40001/runtime/lib/bigint.dart#...
runtime/lib/bigint.dart:233: void _copyTo(r) {
On 2014/09/09 19:31:44, srdjan wrote:
> Please add type to arguments (here and below).

Done.

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/bigint_operat...
File runtime/vm/bigint_operations_test.cc (left):

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/bigint_operat...
runtime/vm/bigint_operations_test.cc:2237: "01234567890ABCDEE");
On 2014/09/09 20:22:01, srdjan wrote:
> Can we move these tests to Dart code?

We could. It's a lot of work. Ivan said it was not necessary. I'll do it in a
following cl if we think we should not lose these tests. Let's discuss tomorrow.

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/object.cc
File runtime/vm/object.cc (right):

https://codereview.chromium.org/509153003/diff/60001/runtime/vm/object.cc#new...
runtime/vm/object.cc:15630: ASSERT(IsBigint());
On 2014/09/09 20:22:01, srdjan wrote:
> Is the assert needed? I assume Bigint::Cast has one? (here and below).

Correct. Assert removed here and below.

[regis, 2014-09-09 21:48:06]

Committed patchset #6 (id:100001) manually as r40061 (presubmit successful).

[Vyacheslav Egorov (Google), 2014-09-10 11:44:11]

vegorov@google.com changed reviewers:
+ vegorov@google.com

[Vyacheslav Egorov (Google), 2014-09-10 11:44:12]

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:79: Uint32List get _digits native "Bigint_getDigits";
Any reason why is this not a real field?

This is completely nontransparent for the optimizer. 

Even if you recognize and inline this as LoadField with an offset it will still
be worse because optimizer can't used Field based aliasing for fields that we
refer by offsets.

[regis, 2014-09-10 17:34:17]

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:79: Uint32List get _digits native "Bigint_getDigits";
On 2014/09/10 11:44:12, Vyacheslav Egorov (Google) wrote:
> Any reason why is this not a real field?
> 
> This is completely nontransparent for the optimizer. 
> 
> Even if you recognize and inline this as LoadField with an offset it will
still
> be worse because optimizer can't used Field based aliasing for fields that we
> refer by offsets.
> 

Class _Bigint being part of the integer class hierarchy, we need handles for it.
It is also used early in bootstrapping the system (e.g. bigint literals in
source), so we need to be able to allocate and initialize a bigint instance from
C++ without calling into Dart.

So either we declare the fields in Dart and make access from C++ somewhat
complicated, or we declare them in C++ (RawBigint) and provide native accessors.

Ivan and Srdjan recommended the second approach and suggested to handle the 3
required fields like the length field of Array.

I am opened to either way, as long as it is efficient.

I do not expect field accesses to be the bottleneck anyway. The fields neg and
used are typically accessed once in each method and I plan to introduce local
variables to cache the digits field.

[Vyacheslav Egorov (Google), 2014-09-10 17:40:44]

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart
File runtime/lib/bigint.dart (right):

https://codereview.chromium.org/509153003/diff/100001/runtime/lib/bigint.dart...
runtime/lib/bigint.dart:79: Uint32List get _digits native "Bigint_getDigits";
On 2014/09/10 17:34:17, regis wrote:
> On 2014/09/10 11:44:12, Vyacheslav Egorov (Google) wrote:
> > Any reason why is this not a real field?
> > 
> > This is completely nontransparent for the optimizer. 
> > 
> > Even if you recognize and inline this as LoadField with an offset it will
> still
> > be worse because optimizer can't used Field based aliasing for fields that
we
> > refer by offsets.
> > 
> 
> Class _Bigint being part of the integer class hierarchy, we need handles for
it.
> It is also used early in bootstrapping the system (e.g. bigint literals in
> source), so we need to be able to allocate and initialize a bigint instance
from
> C++ without calling into Dart.
> 
> So either we declare the fields in Dart and make access from C++ somewhat
> complicated, or we declare them in C++ (RawBigint) and provide native
accessors.
> 
> Ivan and Srdjan recommended the second approach and suggested to handle the 3
> required fields like the length field of Array.
> 
> I am opened to either way, as long as it is efficient.
> 
> I do not expect field accesses to be the bottleneck anyway. The fields neg and
> used are typically accessed once in each method and I plan to introduce local
> variables to cache the digits field.
> 

But we can force fields declared in the dart code into offsets "expected
offsets" known to C++ code, e.g. we deal with offsetInBytes in TypedData in this
manner.

I think is totally preferable to having a getter like this that does nothing but
marshall a field from C++ side and then having intrinsic for it.