Deal with Javascript integer limitations in heap snapshot processing to handle 64-bit target VMs.

Deal with Javascript integer limitations in heap snapshot processing to handle 64-bit target VMs.

R=turnidge@google.com

Committed: https://github.com/dart-lang/sdk/commit/1ef2b68e65d4150a971f29929d4ce5dbf90d7d9c

[rmacnak, 2015-06-30 21:33:02]

rmacnak@google.com changed reviewers:
+ turnidge@google.com

[sra1, 2015-07-01 17:09:33]

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

[sra1, 2015-07-01 17:09:33]

DBC

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
runtime/observatory/lib/object_graph.dart:102: return (high << 56) | (mid << 28)
| low;
why do this when they are zero?

You can get correct values up to 2^53 if you multiply and add instead of shift
and or.

return low + 0x10000000 * mid;

<< 56 doesn't work on dart2js since bit ops are 32 bit.
I think it is optimized to 0, but I'm not sure.

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
runtime/observatory/lib/object_graph.dart:258: combine28(stream.high);
A trick which probably runs faster in dart2js is

(1) premultiply

int high = stream.high;
int mid = stream.mid;
int low = stream.low;
int multiplier = _graph._kObjectAlignment;

low = multiplier * low;
mid = multiplier * mid + (low >> 28);
high = multiplier * high + (mid >> 28);
low = 0xFFFFFFF & low;
mid = 0xFFFFFFF & mid;

(2) Chunked hex conversion

if (high == 0 && mid == 0) return low.toRadixString(16);
String lowDigits = (low + 0x10000000).toRadixString(16).substring(1);
if (high == 0) return mid.toString(16) + lowDigits;
String midDigits = (mid + 0x10000000).toRadixString(16).substring(1);
return high.toRadixString(16) + midDigits + lowDigits;


The above will work better by avoiding non-smi intermediates in the premultiply
if you arrange that low/mid/high are 24/24/16 or 20/20/24 rather than 28/28/8.
It might even be necessary for the shift that computes the carry since that is
32 bit arithmetic on JS.

pkg/fixnum/lib/src/int64.dart is full of this kind of hackery.

[rmacnak, 2015-07-07 23:19:05]

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
runtime/observatory/lib/object_graph.dart:102: return (high << 56) | (mid << 28)
| low;
On 2015/07/01 17:09:33, sra1 wrote:
> why do this when they are zero?
> 
> You can get correct values up to 2^53 if you multiply and add instead of shift
> and or.
> 
> return low + 0x10000000 * mid;
> 
> << 56 doesn't work on dart2js since bit ops are 32 bit.
> I think it is optimized to 0, but I'm not sure.
> 

The intent was to still allow large values on Dartium. But we need to fit in
uint32 for typed arrays even on Dartium in a few places, so replaced with
clampedUint32. Using multiplication to get that last bit.

https://codereview.chromium.org/1219103002/diff/1/runtime/observatory/lib/obj...
runtime/observatory/lib/object_graph.dart:258: combine28(stream.high);
On 2015/07/01 17:09:33, sra1 wrote:
> A trick which probably runs faster in dart2js is
> 
> (1) premultiply
> 
> int high = stream.high;
> int mid = stream.mid;
> int low = stream.low;
> int multiplier = _graph._kObjectAlignment;
> 
> low = multiplier * low;
> mid = multiplier * mid + (low >> 28);
> high = multiplier * high + (mid >> 28);
> low = 0xFFFFFFF & low;
> mid = 0xFFFFFFF & mid;
> 
> (2) Chunked hex conversion
> 
> if (high == 0 && mid == 0) return low.toRadixString(16);
> String lowDigits = (low + 0x10000000).toRadixString(16).substring(1);
> if (high == 0) return mid.toString(16) + lowDigits;
> String midDigits = (mid + 0x10000000).toRadixString(16).substring(1);
> return high.toRadixString(16) + midDigits + lowDigits;
> 
> 
> The above will work better by avoiding non-smi intermediates in the
premultiply
> if you arrange that low/mid/high are 24/24/16 or 20/20/24 rather than 28/28/8.
> It might even be necessary for the shift that computes the carry since that is
> 32 bit arithmetic on JS.
> 
> pkg/fixnum/lib/src/int64.dart is full of this kind of hackery.

The hot path is the use of readUnsigned parsing the snapshot, which dictates the
28/28/8 representation. This getter will only run for a hundred or so objects
compared to hundreds of thousands for parsing, so it's worth a slow down here.
But thanks for the tip.

[turnidge, 2015-07-08 22:52:03]

https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
File runtime/observatory/lib/object_graph.dart (right):

https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
runtime/observatory/lib/object_graph.dart:14: class AddressMapper {
High level question - is it possible to write some unit tests for any of these
methods?  There is a ton of bit-twiddling going on here.  Honestly, then chance
that I will find an off-by-one is small but the chance that you will is high. 
And if anybody else wants to changes this in the future, they will need the
tests to be sure they didn't break it.

[rmacnak, 2015-07-09 20:35:45]

On 2015/07/08 22:52:03, turnidge wrote:
>
https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
> File runtime/observatory/lib/object_graph.dart (right):
> 
>
https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
> runtime/observatory/lib/object_graph.dart:14: class AddressMapper {
> High level question - is it possible to write some unit tests for any of these
> methods?  There is a ton of bit-twiddling going on here.  Honestly, then
chance
> that I will find an off-by-one is small but the chance that you will is high. 
> And if anybody else wants to changes this in the future, they will need the
> tests to be sure they didn't break it.

Added some, but not thrilled about having to make AddressMapper and ReadStream
public.

[Cutch, 2015-07-10 23:10:00]

On 2015/07/08 22:52:03, turnidge wrote:
>
https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
> File runtime/observatory/lib/object_graph.dart (right):
> 
>
https://codereview.chromium.org/1219103002/diff/20001/runtime/observatory/lib...
> runtime/observatory/lib/object_graph.dart:14: class AddressMapper {
> High level question - is it possible to write some unit tests for any of these
> methods?  There is a ton of bit-twiddling going on here.  Honestly, then
chance
> that I will find an off-by-one is small but the chance that you will is high. 
> And if anybody else wants to changes this in the future, they will need the
> tests to be sure they didn't break it.

+1 on tests for this bit fiddling code.

[turnidge, 2015-07-14 00:00:35]

lgtm

Thanks for adding the tests.

[rmacnak, 2015-07-14 00:28:00]

Committed patchset #3 (id:40001) manually as
1ef2b68e65d4150a971f29929d4ce5dbf90d7d9c (presubmit successful).