Inline instance object hash code into object header on 64 bit.

Inline instance object hash code into object header on 64 bit.

64 bit objects have 32 bits of free space in the header word.
This is used for the hash code in string objects. We take it
for the default hash code on all objects that don't override
the hashCode getter.

This is both faster and a memory reduction.  Eg it shaves about
70% off the running time of this microbenchmark:

List list = [];

class Thing {
  get hashCode => 42;
}

class Thing2 {
  get hashCode => 42;
}

class Thing3 { }
class Thing4 { }

main() {
  int sum = 103;
  for (int i = 0; i < 10000000; i++) {
    list = [];
    list.add("foo");
    list.add(123);
    list.add(1.23);
    list.add(new Object());
    list.add(new Thing());
    list.add(new Thing2());
    list.add(new Thing3());
    list.add(new Thing4());
    for (int j = 0; j < 2; j++) {
      sum ^= biz(list);
    }
  }
  print(sum);
}

int biz(List list) {
  int sum = 103;
  for (var x in list) {
    sum ^= x.hashCode;
  }
  return sum;
}

R=rmacnak@google.com, vegorov@google.com
BUG=

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

[Vyacheslav Egorov (Google), 2017-05-30 15:25:00]

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

https://codereview.chromium.org/2912863006/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:914: #if defined(HASH_IN_OBJECT_HEADER)
How do we make sure that this list is exhaustive? 

For example what happens if I call:

(1).runtimeType.hash

?

[erikcorry, 2017-05-30 15:47:39]

Description was changed from

==========
Inline instance object hash code into object header on 64 bit.

64 bit objects have 32 bits of free space in the header word.
This is used for the hash code in string objects. We take it
for the default hash code on all objects that don't override
the hashCode getter.

This is both faster and a memory reduction.  Eg it shaves about
25% off the running time of this microbenchmark:

List list = [];

class Thing {
  get hashCode => 42;
}

class Thing2 {
  get hashCode => 42;
}

class Thing3 { }
class Thing4 { }

main() {
  int sum = 103;
  for (int i = 0; i < 10000000; i++) {
    list = [];
    list.add("foo");
    list.add(123);
    list.add(1.23);
    list.add(new Object());
    list.add(new Thing());
    list.add(new Thing2());
    list.add(new Thing3());
    list.add(new Thing4());
    for (int j = 0; j < 2; j++) {
      sum ^= biz(list);
    }
  }
  print(sum);
}

int biz(List list) {
  int sum = 103;
  for (var x in list) {
    sum ^= x.hashCode;
  }
  return sum;
}

R=vegorov@google.com
BUG=
==========

to

==========
Inline instance object hash code into object header on 64 bit.

64 bit objects have 32 bits of free space in the header word.
This is used for the hash code in string objects. We take it
for the default hash code on all objects that don't override
the hashCode getter.

This is both faster and a memory reduction.  Eg it shaves about
70% off the running time of this microbenchmark:

List list = [];

class Thing {
  get hashCode => 42;
}

class Thing2 {
  get hashCode => 42;
}

class Thing3 { }
class Thing4 { }

main() {
  int sum = 103;
  for (int i = 0; i < 10000000; i++) {
    list = [];
    list.add("foo");
    list.add(123);
    list.add(1.23);
    list.add(new Object());
    list.add(new Thing());
    list.add(new Thing2());
    list.add(new Thing3());
    list.add(new Thing4());
    for (int j = 0; j < 2; j++) {
      sum ^= biz(list);
    }
  }
  print(sum);
}

int biz(List list) {
  int sum = 103;
  for (var x in list) {
    sum ^= x.hashCode;
  }
  return sum;
}

R=vegorov@google.com
BUG=
==========

[erikcorry, 2017-06-02 15:34:04]

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

https://codereview.chromium.org/2912863006/diff/1/runtime/vm/object.cc#newcod...
runtime/vm/object.cc:914: #if defined(HASH_IN_OBJECT_HEADER)
On 2017/05/30 15:25:00, Vyacheslav Egorov (Google) wrote:
> How do we make sure that this list is exhaustive? 
> 
> For example what happens if I call:
> 
> (1).runtimeType.hash
> 
> ?

Good point that does not work.

Instead, the new version uses the visitor to give hash codes to all objects in
the VM isolate.  PTAL.

[Vyacheslav Egorov (Google), 2017-06-07 06:21:15]

lgtm

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/heap.h
File runtime/vm/heap.h (right):

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/heap.h#newco...
runtime/vm/heap.h:36: #if defined(HASH_IN_OBJECT_HEADER)
maybe  instead

enum WeakSelector {
#if ... 
  kHashes,
#endif

}

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

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:996: class PremarkingVisitor : public ObjectVisitor {
Maybe this name needs to be changed?

[rmacnak, 2017-06-13 00:17:52]

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

[rmacnak, 2017-06-13 00:17:53]

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_arm64.cc:1847: __ str(R1, FieldAddress(R0,
String::hash_offset()), kUnsignedWord);
These intrinsics and their C++ counterparts need to use atomics since the
mutator can assign a hash at the same time the sweeper is trying to clear the
mark bit.  

I suspect the combination of a 4-byte access here and an overlapping 8-byte
access from the sweeper creates undefined behavior for the sweeper's atomic
access on ARM.

Alternatively, the declaration in RawObject could be split into two fields as
you did in become.h so the sweeper isn't touching the hash.

In any case, FreeListElement, ForwardingCorpse and RawObject should all
consistently use a one-field or two-field header.

[Vyacheslav Egorov (Google), 2017-06-13 06:12:25]

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_arm64.cc:1847: __ str(R1, FieldAddress(R0,
String::hash_offset()), kUnsignedWord);
On 2017/06/13 00:17:52, rmacnak wrote:
> These intrinsics and their C++ counterparts need to use atomics since the
> mutator can assign a hash at the same time the sweeper is trying to clear the
> mark bit.  
> 
> I suspect the combination of a 4-byte access here and an overlapping 8-byte
> access from the sweeper creates undefined behavior for the sweeper's atomic
> access on ARM.
> 
> Alternatively, the declaration in RawObject could be split into two fields as
> you did in become.h so the sweeper isn't touching the hash.
> 
> In any case, FreeListElement, ForwardingCorpse and RawObject should all
> consistently use a one-field or two-field header.

Nice catch! Alternatively to atomics we could probably use 4 byte accesses in
the sweeper instead - because it does not need to access hash part of the header
anyway.

[erikcorry, 2017-06-16 09:26:39]

This CL is ready for another look

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/heap.h
File runtime/vm/heap.h (right):

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/heap.h#newco...
runtime/vm/heap.h:36: #if defined(HASH_IN_OBJECT_HEADER)
On 2017/06/07 06:21:15, Vyacheslav Egorov (Google) wrote:
> maybe  instead
> 
> enum WeakSelector {
> #if ... 
>   kHashes,
> #endif
> 
> }

Done.

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
File runtime/vm/intrinsifier_arm64.cc (right):

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/intrinsifier...
runtime/vm/intrinsifier_arm64.cc:1847: __ str(R1, FieldAddress(R0,
String::hash_offset()), kUnsignedWord);
On 2017/06/13 06:12:25, Vyacheslav Egorov (Google) wrote:
> On 2017/06/13 00:17:52, rmacnak wrote:
> > These intrinsics and their C++ counterparts need to use atomics since the
> > mutator can assign a hash at the same time the sweeper is trying to clear
the
> > mark bit.  
> > 
> > I suspect the combination of a 4-byte access here and an overlapping 8-byte
> > access from the sweeper creates undefined behavior for the sweeper's atomic
> > access on ARM.
> > 
> > Alternatively, the declaration in RawObject could be split into two fields
as
> > you did in become.h so the sweeper isn't touching the hash.
> > 
> > In any case, FreeListElement, ForwardingCorpse and RawObject should all
> > consistently use a one-field or two-field header.
> 
> Nice catch! Alternatively to atomics we could probably use 4 byte accesses in
> the sweeper instead - because it does not need to access hash part of the
header
> anyway.

I fixed all the places we update the tags bits to use 32 bit operations.  I
didn't change the ones that happen during allocation, since the allocator does
not race with the sweeper threads (you can't allocate on a page where sweeping
has not completed).

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

https://codereview.chromium.org/2912863006/diff/40001/runtime/vm/object.cc#ne...
runtime/vm/object.cc:996: class PremarkingVisitor : public ObjectVisitor {
On 2017/06/07 06:21:15, Vyacheslav Egorov (Google) wrote:
> Maybe this name needs to be changed?

VMIsolateFixingVisitor

[rmacnak, 2017-06-19 18:12:22]

lgtm w/ assembler tests

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.h:745: void ldxr(Register rt, Register rn,
OperandSize size = kDoubleWord) {
Please copy the ldxr/stxr tests in assembler_arm64_test.cc to try both access
sizes.

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_x...
File runtime/vm/assembler_x64_test.cc (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_x...
runtime/vm/assembler_x64_test.cc:1745: 
Duplicate tests for 32-bit access.

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/become.h
File runtime/vm/become.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/become.h#ne...
runtime/vm/become.h:57: int32_t hash_;
This is uint32_t in FreeList and RawObject.

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

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:998: class VMIsolateFixingVisitor : public ObjectVisitor {
Consider FinalizeVMIsolateVisitor

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:1036: int counter_;
intptr_t

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/raw_object....
runtime/vm/raw_object.h:1289: // uword so that the variable length data is 64
bit aligned on 64 bit
Not sure alignment helps here. The data is sleb encoded, so it is accessed
bytewise anyway.

[erikcorry, 2017-06-19 18:42:33]

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/raw_object.h
File runtime/vm/raw_object.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/raw_object....
runtime/vm/raw_object.h:1289: // uword so that the variable length data is 64
bit aligned on 64 bit
On 2017/06/19 18:12:22, rmacnak wrote:
> Not sure alignment helps here. The data is sleb encoded, so it is accessed
> bytewise anyway.

The 2nd argument to OPEN_ARRAY_START is intptr_t so there's an assert in
OPEN_ARRAY_START that says we should be intptr_t-aligned.  I'm not sure why.

[erikcorry, 2017-06-21 12:12:12]

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_a...
File runtime/vm/assembler_arm64.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_a...
runtime/vm/assembler_arm64.h:745: void ldxr(Register rt, Register rn,
OperandSize size = kDoubleWord) {
On 2017/06/19 18:12:21, rmacnak wrote:
> Please copy the ldxr/stxr tests in assembler_arm64_test.cc to try both access
> sizes.

Done.

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_x...
File runtime/vm/assembler_x64_test.cc (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/assembler_x...
runtime/vm/assembler_x64_test.cc:1745: 
On 2017/06/19 18:12:21, rmacnak wrote:
> Duplicate tests for 32-bit access.

Done.

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/become.h
File runtime/vm/become.h (right):

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/become.h#ne...
runtime/vm/become.h:57: int32_t hash_;
On 2017/06/19 18:12:21, rmacnak wrote:
> This is uint32_t in FreeList and RawObject.

Done.

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

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:998: class VMIsolateFixingVisitor : public ObjectVisitor {
On 2017/06/19 18:12:21, rmacnak wrote:
> Consider FinalizeVMIsolateVisitor

Done.

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:1036: int counter_;
On 2017/06/19 18:12:21, rmacnak wrote:
> intptr_t

We are storing it into a 32 bit field, and it may not be 0.  If I make this an
intptr_t then it could be 0x100000000 which is not zero, but then it would be
zero when stored.  So leaving as is.

[erikcorry, 2017-06-22 07:25:58]

Description was changed from

==========
Inline instance object hash code into object header on 64 bit.

64 bit objects have 32 bits of free space in the header word.
This is used for the hash code in string objects. We take it
for the default hash code on all objects that don't override
the hashCode getter.

This is both faster and a memory reduction.  Eg it shaves about
70% off the running time of this microbenchmark:

List list = [];

class Thing {
  get hashCode => 42;
}

class Thing2 {
  get hashCode => 42;
}

class Thing3 { }
class Thing4 { }

main() {
  int sum = 103;
  for (int i = 0; i < 10000000; i++) {
    list = [];
    list.add("foo");
    list.add(123);
    list.add(1.23);
    list.add(new Object());
    list.add(new Thing());
    list.add(new Thing2());
    list.add(new Thing3());
    list.add(new Thing4());
    for (int j = 0; j < 2; j++) {
      sum ^= biz(list);
    }
  }
  print(sum);
}

int biz(List list) {
  int sum = 103;
  for (var x in list) {
    sum ^= x.hashCode;
  }
  return sum;
}

R=vegorov@google.com
BUG=
==========

to

==========
Inline instance object hash code into object header on 64 bit.

64 bit objects have 32 bits of free space in the header word.
This is used for the hash code in string objects. We take it
for the default hash code on all objects that don't override
the hashCode getter.

This is both faster and a memory reduction.  Eg it shaves about
70% off the running time of this microbenchmark:

List list = [];

class Thing {
  get hashCode => 42;
}

class Thing2 {
  get hashCode => 42;
}

class Thing3 { }
class Thing4 { }

main() {
  int sum = 103;
  for (int i = 0; i < 10000000; i++) {
    list = [];
    list.add("foo");
    list.add(123);
    list.add(1.23);
    list.add(new Object());
    list.add(new Thing());
    list.add(new Thing2());
    list.add(new Thing3());
    list.add(new Thing4());
    for (int j = 0; j < 2; j++) {
      sum ^= biz(list);
    }
  }
  print(sum);
}

int biz(List list) {
  int sum = 103;
  for (var x in list) {
    sum ^= x.hashCode;
  }
  return sum;
}

R=rmacnak@google.com, vegorov@google.com
BUG=

Committed:
https://github.com/dart-lang/sdk/commit/ac6310d5f30af5a338207a9948565096ac47c4a5
==========

[erikcorry, 2017-06-22 07:25:59]

Committed patchset #7 (id:120001) manually as
ac6310d5f30af5a338207a9948565096ac47c4a5 (presubmit successful).

[Vyacheslav Egorov (Google), 2017-06-22 07:30:46]

DBC

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

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:1036: int counter_;
On 2017/06/21 12:12:12, erikcorry wrote:
> On 2017/06/19 18:12:21, rmacnak wrote:
> > intptr_t
> 
> We are storing it into a 32 bit field, and it may not be 0.  If I make this an
> intptr_t then it could be 0x100000000 which is not zero, but then it would be
> zero when stored.  So leaving as is.

We mask it before storing so it can't be 0x100000000.

Also if you make assumptions about the size of the variable you need to use a
type with explicit size uint32_t because int can be anything (4, 8 byte etc)

[erikcorry, 2017-06-22 08:00:53]

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

https://codereview.chromium.org/2912863006/diff/100001/runtime/vm/object.cc#n...
runtime/vm/object.cc:1036: int counter_;
On 2017/06/22 07:30:46, Vyacheslav Egorov (Google) wrote:
> On 2017/06/21 12:12:12, erikcorry wrote:
> > On 2017/06/19 18:12:21, rmacnak wrote:
> > > intptr_t
> > 
> > We are storing it into a 32 bit field, and it may not be 0.  If I make this
an
> > intptr_t then it could be 0x100000000 which is not zero, but then it would
be
> > zero when stored.  So leaving as is.
> 
> We mask it before storing so it can't be 0x100000000.
> 
> Also if you make assumptions about the size of the variable you need to use a
> type with explicit size uint32_t because int can be anything (4, 8 byte etc)

Oh yeah, good point about the masking.

In this case we really don't care what size the counter is, but I get that the
VM has a historical bias against the 'int' type (which is 4 bytes on all but the
most obscure platforms that we don't support anyway).

Fixed in https://codereview.chromium.org/2948153003