Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(657)

Issue 915323002: Compact LinkedHashMap/Set implementation. (Closed)

Created:
5 years, 10 months ago by koda
Modified:
5 years, 10 months ago
CC:
reviews_dartlang.org, vm-dev_dartlang.org
Visibility:
Public.

Description

Compact LinkedHashMap/Set implementation. Add GC-friendly replacement for default Map/Set: * open-addressing hash table, avoiding the overhead of chained entries * index separate from the keys/values, allowing more of it to fit in the cache * new keys are always appended, to allow insertion-order iteration * spare bits in index entries are used to store hashes * index is typed data, so can be ignored by GC Enable it with --use_compact_hash (disabled by default). Reduces Dart2JS compilation time for huge codebase (N=200) by ~30%, due to reduced time in GC. Slightly slower for small maps and maps with deletions: json benchmarks regress by ~5%. R=vegorov@google.com Committed: https://code.google.com/p/dart/source/detail?r=43840

Patch Set 1 #

Patch Set 2 : #

Total comments: 33

Patch Set 3 : #

Patch Set 4 : #

Total comments: 2

Patch Set 5 : #

Unified diffs Side-by-side diffs Delta from patch set Stats (+501 lines, -1 line) Patch
M runtime/lib/collection_patch.dart View 1 2 3 4 3 chunks +9 lines, -1 line 0 comments Download
M runtime/lib/collection_sources.gypi View 1 2 3 4 1 chunk +1 line, -0 lines 0 comments Download
A runtime/lib/compact_hash.dart View 1 2 3 4 1 chunk +471 lines, -0 lines 0 comments Download
M runtime/lib/linked_hash_map.cc View 1 2 3 4 2 chunks +8 lines, -0 lines 0 comments Download
M runtime/vm/bootstrap_natives.h View 1 2 3 4 1 chunk +1 line, -0 lines 0 comments Download
M tests/corelib/hash_map2_test.dart View 1 2 3 4 1 chunk +4 lines, -0 lines 0 comments Download
M tests/corelib/hash_map_test.dart View 1 2 3 4 1 chunk +4 lines, -0 lines 0 comments Download
M tests/corelib/hash_set_test.dart View 1 2 3 4 1 chunk +3 lines, -0 lines 0 comments Download

Messages

Total messages: 10 (2 generated)
koda
5 years, 10 months ago (2015-02-12 06:29:47 UTC) #2
Vyacheslav Egorov (Google)
https://codereview.chromium.org/915323002/diff/20001/runtime/lib/collection_patch.dart File runtime/lib/collection_patch.dart (right): https://codereview.chromium.org/915323002/diff/20001/runtime/lib/collection_patch.dart#newcode1070 runtime/lib/collection_patch.dart:1070: if (_useCompactCached) { Any reason why you can't just ...
5 years, 10 months ago (2015-02-12 15:42:42 UTC) #3
koda
PTAL https://codereview.chromium.org/915323002/diff/20001/runtime/lib/collection_patch.dart File runtime/lib/collection_patch.dart (right): https://codereview.chromium.org/915323002/diff/20001/runtime/lib/collection_patch.dart#newcode1070 runtime/lib/collection_patch.dart:1070: if (_useCompactCached) { On 2015/02/12 15:42:40, Vyacheslav Egorov ...
5 years, 10 months ago (2015-02-17 17:26:29 UTC) #4
Vyacheslav Egorov (Google)
lgtm! https://codereview.chromium.org/915323002/diff/20001/runtime/lib/compact_hash.dart File runtime/lib/compact_hash.dart (right): https://codereview.chromium.org/915323002/diff/20001/runtime/lib/compact_hash.dart#newcode137 runtime/lib/compact_hash.dart:137: if (pair == _CompactHashTableMixin._DELETED_PAIR) { On 2015/02/17 17:26:29, ...
5 years, 10 months ago (2015-02-17 23:39:01 UTC) #5
Vyacheslav Egorov (Google)
Yeah, I wonder if final int d = (hashPattern ^ pair) << 1; if (d ...
5 years, 10 months ago (2015-02-17 23:49:40 UTC) #6
koda
On 2015/02/17 23:49:40, Vyacheslav Egorov (Google) wrote: > Yeah, I wonder if > > final ...
5 years, 10 months ago (2015-02-17 23:56:26 UTC) #7
koda
... or, on second thought, shifting 'd' is only an issue with ~billions of entries ...
5 years, 10 months ago (2015-02-18 00:03:33 UTC) #8
koda
5 years, 10 months ago (2015-02-18 13:58:45 UTC) #10
Message was sent while issue was closed.
Committed patchset #5 (id:80001) manually as r43840 (presubmit successful).

Powered by Google App Engine
This is Rietveld 408576698