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

Issue 220293002: OrderedHashTable implementation with Set and Map interfaces (Closed)

Created:
6 years, 8 months ago by adamk
Modified:
6 years, 8 months ago
CC:
v8-dev, arv (Not doing code reviews)
Visibility:
Public.

Description

OrderedHashTable implementation with Set and Map interfaces OrderedHashTable is an insertion-ordered HashTable based on Jason Orendorff's writeup of a data structure attributed to Tyler Close: https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables It is intended as the new backing store for JSSet/JSMap, as ES6 requires insertion-order-based iteration. Note, however, that in the interest of keeping the initial check-in small this patch does not yet include any iteration support. This change also doesn't yet touch any existing behavior, but in a branch I've verified that these structures pass the existing JSSet/JSMap mjsunit tests. BUG=v8:1793 LOG=N R=mstarzinger@chromium.org Committed: https://code.google.com/p/v8/source/detail?r=20522

Patch Set 1 #

Total comments: 19

Patch Set 2 : Handlified #

Patch Set 3 : Avoid test duplication with templates #

Patch Set 4 : Added a PretenureFlag to Allocate #

Patch Set 5 : Actually use pretenure flag #

Total comments: 4

Patch Set 6 : Patch for landing #

Total comments: 1
Unified diffs Side-by-side diffs Delta from patch set Stats (+575 lines, -24 lines) Patch
M src/factory.h View 1 chunk +3 lines, -0 lines 0 comments Download
M src/factory.cc View 1 1 chunk +10 lines, -0 lines 0 comments Download
M src/objects.h View 1 2 3 4 5 2 chunks +160 lines, -0 lines 1 comment Download
M src/objects.cc View 1 2 3 4 5 1 chunk +191 lines, -0 lines 0 comments Download
M test/cctest/cctest.gyp View 1 chunk +1 line, -0 lines 0 comments Download
M test/cctest/test-dictionary.cc View 1 2 8 chunks +52 lines, -24 lines 0 comments Download
A test/cctest/test-ordered-hash-table.cc View 1 2 1 chunk +158 lines, -0 lines 0 comments Download

Messages

Total messages: 12 (0 generated)
adamk
This could definitely use some more polish before landing (for example, the initial capacity of ...
6 years, 8 months ago (2014-04-01 00:13:17 UTC) #1
arv (Not doing code reviews)
https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15898 src/objects.cc:15898: MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap* heap, int capacity) { We should probably ...
6 years, 8 months ago (2014-04-01 15:22:44 UTC) #2
Michael Starzinger
Looking good, I like this. The bulk of the comments is about handles vs. raw ...
6 years, 8 months ago (2014-04-02 12:09:36 UTC) #3
Michael Starzinger
One clarification. https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924 src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() { On 2014/04/02 12:09:37, Michael ...
6 years, 8 months ago (2014-04-02 12:12:17 UTC) #4
rossberg
https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924 src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() { On 2014/04/02 12:09:37, Michael Starzinger wrote: ...
6 years, 8 months ago (2014-04-02 13:09:12 UTC) #5
adamk
https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924 src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() { On 2014/04/02 13:09:12, rossberg wrote: > ...
6 years, 8 months ago (2014-04-02 22:01:10 UTC) #6
adamk
Updated tests to avoid duplication
6 years, 8 months ago (2014-04-03 22:38:48 UTC) #7
adamk
https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15898 src/objects.cc:15898: MaybeObject* OrderedHashTable<entrysize>::Allocate(Heap* heap, int capacity) { On 2014/04/01 15:22:45, ...
6 years, 8 months ago (2014-04-03 22:53:38 UTC) #8
Michael Starzinger
LGTM, just two nits left. https://codereview.chromium.org/220293002/diff/1/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/1/src/objects.cc#newcode15924 src/objects.cc:15924: MaybeObject* OrderedHashTable<entrysize>::EnsureGrowable() { On ...
6 years, 8 months ago (2014-04-04 09:38:12 UTC) #9
adamk
https://codereview.chromium.org/220293002/diff/80001/src/objects.cc File src/objects.cc (right): https://codereview.chromium.org/220293002/diff/80001/src/objects.cc#newcode15900 src/objects.cc:15900: // capacity must be a factor of two On ...
6 years, 8 months ago (2014-04-04 20:18:35 UTC) #10
adamk
Committed patchset #6 manually as r20522 (presubmit successful).
6 years, 8 months ago (2014-04-04 20:42:04 UTC) #11
arv (Not doing code reviews)
6 years, 8 months ago (2014-04-07 00:01:20 UTC) #12
Message was sent while issue was closed.
LGTM

https://codereview.chromium.org/220293002/diff/100001/src/objects.h
File src/objects.h (right):

https://codereview.chromium.org/220293002/diff/100001/src/objects.h#newcode4259
src/objects.h:4259: // Only Object* keys are supported, with Object::SameValue()
used as the
ES6 Map/Set uses SameValueZero (which treats -0 and +0 as equal). We currently
have a hack to handle this on the js side. Since this is only used for
JSMap/JSSet we might want to change this on the C++ side.

Powered by Google App Engine
This is Rietveld 408576698