[runtime] Implement SmallOrderedHashTable

Implements the Allocate, Add, and HasKey operations. Also, adds GC
support for this new instance type.

Bug: v8:6443
Change-Id: I1cc7ba2faead2a11f7b0381a57858629e123aee6
Reviewed-on: https://chromium-review.googlesource.com/500447
Commit-Queue: Sathya Gunasekaran <gsathya@chromium.org>
Reviewed-by: Michael Starzinger <mstarzinger@chromium.org>
Reviewed-by: Ulan Degenbaev <ulan@chromium.org>
Reviewed-by: Hannes Payer <hpayer@chromium.org>
Reviewed-by: Camillo Bruni <cbruni@chromium.org>
Cr-Commit-Position: refs/heads/master@{#45551}
diff --git a/include/v8.h b/include/v8.h
index 698c595..6326e35 100644
--- a/include/v8.h
+++ b/include/v8.h
@@ -8800,8 +8800,8 @@
   static const int kNodeIsIndependentShift = 3;
   static const int kNodeIsActiveShift = 4;
 
-  static const int kJSApiObjectType = 0xbb;
-  static const int kJSObjectType = 0xbc;
+  static const int kJSApiObjectType = 0xbc;
+  static const int kJSObjectType = 0xbd;
   static const int kFirstNonstringType = 0x80;
   static const int kOddballType = 0x82;
   static const int kForeignType = 0x86;
diff --git a/src/ast/ast-types.cc b/src/ast/ast-types.cc
index 1cdd5ca..5ba7662 100644
--- a/src/ast/ast-types.cc
+++ b/src/ast/ast-types.cc
@@ -310,6 +310,7 @@
     case CELL_TYPE:
     case WEAK_CELL_TYPE:
     case PROTOTYPE_INFO_TYPE:
+    case SMALL_ORDERED_HASH_SET_TYPE:
     case TUPLE2_TYPE:
     case TUPLE3_TYPE:
     case CONTEXT_EXTENSION_TYPE:
diff --git a/src/compiler/types.cc b/src/compiler/types.cc
index 8cbad08..34fe1d8 100644
--- a/src/compiler/types.cc
+++ b/src/compiler/types.cc
@@ -320,6 +320,7 @@
     case DEBUG_INFO_TYPE:
     case STACK_FRAME_INFO_TYPE:
     case WEAK_CELL_TYPE:
+    case SMALL_ORDERED_HASH_SET_TYPE:
     case PROTOTYPE_INFO_TYPE:
     case TUPLE2_TYPE:
     case TUPLE3_TYPE:
diff --git a/src/deoptimizer.cc b/src/deoptimizer.cc
index f69ac22..6ad0b76 100644
--- a/src/deoptimizer.cc
+++ b/src/deoptimizer.cc
@@ -4212,6 +4212,7 @@
     case STACK_FRAME_INFO_TYPE:
     case CELL_TYPE:
     case WEAK_CELL_TYPE:
+    case SMALL_ORDERED_HASH_SET_TYPE:
     case PROTOTYPE_INFO_TYPE:
     case TUPLE2_TYPE:
     case TUPLE3_TYPE:
diff --git a/src/factory.cc b/src/factory.cc
index 2c93313..dc2eb2b 100644
--- a/src/factory.cc
+++ b/src/factory.cc
@@ -240,6 +240,15 @@
   return Handle<FrameArray>::cast(result);
 }
 
+Handle<SmallOrderedHashSet> Factory::NewSmallOrderedHashSet(
+    int size, PretenureFlag pretenure) {
+  DCHECK_LE(0, size);
+  CALL_HEAP_FUNCTION(
+      isolate(),
+      isolate()->heap()->AllocateSmallOrderedHashSet(size, pretenure),
+      SmallOrderedHashSet);
+}
+
 Handle<OrderedHashSet> Factory::NewOrderedHashSet() {
   return OrderedHashSet::Allocate(isolate(), OrderedHashSet::kMinCapacity);
 }
diff --git a/src/factory.h b/src/factory.h
index 779e397..be3aee8 100644
--- a/src/factory.h
+++ b/src/factory.h
@@ -82,6 +82,10 @@
   Handle<OrderedHashSet> NewOrderedHashSet();
   Handle<OrderedHashMap> NewOrderedHashMap();
 
+  Handle<SmallOrderedHashSet> NewSmallOrderedHashSet(
+      int size = SmallOrderedHashSet::kMinCapacity,
+      PretenureFlag pretenure = NOT_TENURED);
+
   // Create a new PrototypeInfo struct.
   Handle<PrototypeInfo> NewPrototypeInfo();
 
diff --git a/src/heap/heap.cc b/src/heap/heap.cc
index b9f633a..23f6104 100644
--- a/src/heap/heap.cc
+++ b/src/heap/heap.cc
@@ -2391,6 +2391,7 @@
     ALLOCATE_VARSIZE_MAP(BYTE_ARRAY_TYPE, byte_array)
     ALLOCATE_VARSIZE_MAP(BYTECODE_ARRAY_TYPE, bytecode_array)
     ALLOCATE_VARSIZE_MAP(FREE_SPACE_TYPE, free_space)
+    ALLOCATE_VARSIZE_MAP(SMALL_ORDERED_HASH_SET_TYPE, small_ordered_hash_set)
 
 #define ALLOCATE_FIXED_TYPED_ARRAY_MAP(Type, type, TYPE, ctype, size) \
   ALLOCATE_VARSIZE_MAP(FIXED_##TYPE##_ARRAY_TYPE, fixed_##type##_array)
@@ -3037,6 +3038,25 @@
   return result;
 }
 
+AllocationResult Heap::AllocateSmallOrderedHashSet(int capacity,
+                                                   PretenureFlag pretenure) {
+  DCHECK_EQ(0, capacity % SmallOrderedHashSet::kLoadFactor);
+  CHECK_GE(SmallOrderedHashSet::kMaxCapacity, capacity);
+
+  int size = SmallOrderedHashSet::Size(capacity);
+  AllocationSpace space = SelectSpace(pretenure);
+  HeapObject* result = nullptr;
+  {
+    AllocationResult allocation = AllocateRaw(size, space);
+    if (!allocation.To(&result)) return allocation;
+  }
+
+  result->set_map_after_allocation(small_ordered_hash_set_map(),
+                                   SKIP_WRITE_BARRIER);
+  Handle<SmallOrderedHashSet> table(SmallOrderedHashSet::cast(result));
+  table->Initialize(isolate(), capacity);
+  return result;
+}
 
 AllocationResult Heap::AllocateByteArray(int length, PretenureFlag pretenure) {
   if (length < 0 || length > ByteArray::kMaxLength) {
diff --git a/src/heap/heap.h b/src/heap/heap.h
index 07422c2..0150c0f 100644
--- a/src/heap/heap.h
+++ b/src/heap/heap.h
@@ -91,6 +91,7 @@
   V(Map, ordered_hash_table_map, OrderedHashTableMap)                          \
   V(Map, unseeded_number_dictionary_map, UnseededNumberDictionaryMap)          \
   V(Map, sloppy_arguments_elements_map, SloppyArgumentsElementsMap)            \
+  V(Map, small_ordered_hash_set_map, SmallOrderedHashSetMap)                   \
   V(Map, message_object_map, JSMessageObjectMap)                               \
   V(Map, external_map, ExternalMap)                                            \
   V(Map, bytecode_array_map, BytecodeArrayMap)                                 \
@@ -315,6 +316,7 @@
   V(OnePointerFillerMap)                \
   V(OptimizedOut)                       \
   V(OrderedHashTableMap)                \
+  V(SmallOrderedHashSetMap)             \
   V(ScopeInfoMap)                       \
   V(ScriptContextMap)                   \
   V(SharedFunctionInfoMap)              \
@@ -2011,6 +2013,9 @@
   MUST_USE_RESULT AllocationResult
   AllocateFixedArray(int length, PretenureFlag pretenure = NOT_TENURED);
 
+  MUST_USE_RESULT AllocationResult AllocateSmallOrderedHashSet(
+      int length, PretenureFlag pretenure = NOT_TENURED);
+
   // Allocate an uninitialized object.  The memory is non-executable if the
   // hardware and OS allow.  This is the single choke-point for allocations
   // performed by the runtime and should not be bypassed (to extend this to
diff --git a/src/heap/objects-visiting-inl.h b/src/heap/objects-visiting-inl.h
index 6071c5f..8f06cd9 100644
--- a/src/heap/objects-visiting-inl.h
+++ b/src/heap/objects-visiting-inl.h
@@ -93,6 +93,11 @@
       &FlexibleBodyVisitor<StaticVisitor, JSWeakCollection::BodyDescriptor,
                            int>::Visit);
 
+  table_.Register(
+      kVisitSmallOrderedHashSet,
+      &FlexibleBodyVisitor<StaticVisitor, SmallOrderedHashSet::BodyDescriptor,
+                           int>::Visit);
+
   table_.Register(kVisitJSRegExp, &JSObjectVisitor::Visit);
 
   table_.Register(kVisitDataObject, &DataObjectVisitor::Visit);
@@ -191,6 +196,11 @@
                   &FixedBodyVisitor<StaticVisitor, PropertyCell::BodyDescriptor,
                                     void>::Visit);
 
+  table_.Register(
+      kVisitSmallOrderedHashSet,
+      &FlexibleBodyVisitor<StaticVisitor, SmallOrderedHashSet::BodyDescriptor,
+                           void>::Visit);
+
   table_.Register(kVisitWeakCell, &VisitWeakCell);
 
   table_.Register(kVisitTransitionArray, &VisitTransitionArray);
diff --git a/src/heap/objects-visiting.cc b/src/heap/objects-visiting.cc
index 08b3ef2..663ab8d 100644
--- a/src/heap/objects-visiting.cc
+++ b/src/heap/objects-visiting.cc
@@ -102,6 +102,9 @@
     case JS_ARRAY_BUFFER_TYPE:
       return kVisitJSArrayBuffer;
 
+    case SMALL_ORDERED_HASH_SET_TYPE:
+      return kVisitSmallOrderedHashSet;
+
     case JS_OBJECT_TYPE:
     case JS_ERROR_TYPE:
     case JS_ARGUMENTS_TYPE:
diff --git a/src/heap/objects-visiting.h b/src/heap/objects-visiting.h
index 6cd27c4..91e751a 100644
--- a/src/heap/objects-visiting.h
+++ b/src/heap/objects-visiting.h
@@ -25,39 +25,40 @@
 namespace internal {
 
 #define VISITOR_ID_LIST(V) \
-  V(SeqOneByteString)      \
-  V(SeqTwoByteString)      \
-  V(ShortcutCandidate)     \
+  V(AllocationSite)        \
   V(ByteArray)             \
   V(BytecodeArray)         \
-  V(FreeSpace)             \
+  V(Cell)                  \
+  V(Code)                  \
+  V(ConsString)            \
+  V(DataObject)            \
   V(FixedArray)            \
   V(FixedDoubleArray)      \
-  V(FixedTypedArrayBase)   \
   V(FixedFloat64Array)     \
-  V(NativeContext)         \
-  V(AllocationSite)        \
-  V(DataObject)            \
-  V(JSObjectFast)          \
-  V(JSObject)              \
+  V(FixedTypedArrayBase)   \
+  V(FreeSpace)             \
   V(JSApiObject)           \
-  V(Struct)                \
-  V(ConsString)            \
-  V(SlicedString)          \
-  V(ThinString)            \
-  V(Symbol)                \
-  V(Oddball)               \
-  V(Code)                  \
-  V(Map)                   \
-  V(Cell)                  \
-  V(PropertyCell)          \
-  V(WeakCell)              \
-  V(TransitionArray)       \
-  V(SharedFunctionInfo)    \
-  V(JSFunction)            \
-  V(JSWeakCollection)      \
   V(JSArrayBuffer)         \
-  V(JSRegExp)
+  V(JSFunction)            \
+  V(JSObject)              \
+  V(JSObjectFast)          \
+  V(JSRegExp)              \
+  V(JSWeakCollection)      \
+  V(Map)                   \
+  V(NativeContext)         \
+  V(Oddball)               \
+  V(PropertyCell)          \
+  V(SeqOneByteString)      \
+  V(SeqTwoByteString)      \
+  V(SharedFunctionInfo)    \
+  V(ShortcutCandidate)     \
+  V(SlicedString)          \
+  V(SmallOrderedHashSet)   \
+  V(Struct)                \
+  V(Symbol)                \
+  V(ThinString)            \
+  V(TransitionArray)       \
+  V(WeakCell)
 
 // For data objects, JS objects and structs along with generic visitor which
 // can visit object of any size we provide visitors specialized by
@@ -359,9 +360,10 @@
   V(SeqTwoByteString)            \
   V(SharedFunctionInfo)          \
   V(SlicedString)                \
+  V(SmallOrderedHashSet)         \
   V(Symbol)                      \
-  V(TransitionArray)             \
   V(ThinString)                  \
+  V(TransitionArray)             \
   V(WeakCell)
 
 // The base class for visitors that need to dispatch on object type.
diff --git a/src/objects-body-descriptors-inl.h b/src/objects-body-descriptors-inl.h
index 081986f..4225d14 100644
--- a/src/objects-body-descriptors-inl.h
+++ b/src/objects-body-descriptors-inl.h
@@ -7,6 +7,7 @@
 
 #include "src/assembler-inl.h"
 #include "src/objects-body-descriptors.h"
+#include "src/objects/hash-table.h"
 #include "src/transitions.h"
 
 namespace v8 {
@@ -245,6 +246,40 @@
   }
 };
 
+class SmallOrderedHashSet::BodyDescriptor final : public BodyDescriptorBase {
+ public:
+  static bool IsValidSlot(HeapObject* obj, int offset) {
+    SmallOrderedHashSet* table = reinterpret_cast<SmallOrderedHashSet*>(obj);
+    if (offset < table->GetDataTableStartOffset()) return false;
+    return IsValidSlotImpl(obj, offset);
+  }
+
+  template <typename ObjectVisitor>
+  static inline void IterateBody(HeapObject* obj, int object_size,
+                                 ObjectVisitor* v) {
+    SmallOrderedHashSet* table = reinterpret_cast<SmallOrderedHashSet*>(obj);
+    int start = table->GetDataTableStartOffset();
+    for (int i = 0; i < table->Capacity(); i++) {
+      IteratePointer(obj, start + (i * kPointerSize), v);
+    }
+  }
+
+  template <typename StaticVisitor>
+  static inline void IterateBody(HeapObject* obj, int object_size) {
+    Heap* heap = obj->GetHeap();
+    SmallOrderedHashSet* table = reinterpret_cast<SmallOrderedHashSet*>(obj);
+    int start = table->GetDataTableStartOffset();
+    for (int i = 0; i < table->Capacity(); i++) {
+      IteratePointer<StaticVisitor>(heap, obj, start + (i * kPointerSize));
+    }
+  }
+
+  static inline int SizeOf(Map* map, HeapObject* obj) {
+    SmallOrderedHashSet* table = reinterpret_cast<SmallOrderedHashSet*>(obj);
+    return table->Size();
+  }
+};
+
 class ByteArray::BodyDescriptor final : public BodyDescriptorBase {
  public:
   static bool IsValidSlot(HeapObject* obj, int offset) { return false; }
@@ -656,7 +691,9 @@
       return Op::template apply<Symbol::BodyDescriptor>(p1, p2, p3);
     case BYTECODE_ARRAY_TYPE:
       return Op::template apply<BytecodeArray::BodyDescriptor>(p1, p2, p3);
-
+    case SMALL_ORDERED_HASH_SET_TYPE:
+      return Op::template apply<SmallOrderedHashSet::BodyDescriptor>(p1, p2,
+                                                                     p3);
     case HEAP_NUMBER_TYPE:
     case MUTABLE_HEAP_NUMBER_TYPE:
     case FILLER_TYPE:
diff --git a/src/objects-debug.cc b/src/objects-debug.cc
index ae10ccd..8510e69 100644
--- a/src/objects-debug.cc
+++ b/src/objects-debug.cc
@@ -249,6 +249,9 @@
     case JS_DATA_VIEW_TYPE:
       JSDataView::cast(this)->JSDataViewVerify();
       break;
+    case SMALL_ORDERED_HASH_SET_TYPE:
+      SmallOrderedHashSet::cast(this)->SmallOrderedHashSetVerify();
+      break;
 
 #define MAKE_STRUCT_CASE(NAME, Name, name) \
   case NAME##_TYPE:                        \
@@ -1013,6 +1016,35 @@
         reject_reactions()->IsFixedArray());
 }
 
+void SmallOrderedHashSet::SmallOrderedHashSetVerify() {
+  CHECK(IsSmallOrderedHashSet());
+  Isolate* isolate = GetIsolate();
+
+  for (int entry = 0; entry < NumberOfBuckets(); entry++) {
+    int bucket = GetFirstEntry(entry);
+    if (bucket == kNotFound) continue;
+    Object* val = GetDataEntry(bucket);
+    CHECK(!val->IsTheHole(isolate));
+  }
+
+  for (int entry = 0; entry < NumberOfElements(); entry++) {
+    int chain = GetNextEntry(entry);
+    if (chain == kNotFound) continue;
+    Object* val = GetDataEntry(chain);
+    CHECK(!val->IsTheHole(isolate));
+  }
+
+  for (int entry = 0; entry < NumberOfElements(); entry++) {
+    Object* val = GetDataEntry(entry);
+    VerifyPointer(val);
+  }
+
+  for (int entry = NumberOfElements(); entry < Capacity(); entry++) {
+    Object* val = GetDataEntry(entry);
+    CHECK(val->IsTheHole(isolate));
+  }
+}
+
 void JSRegExp::JSRegExpVerify() {
   JSObjectVerify();
   Isolate* isolate = GetIsolate();
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 825cf72..221ed4c 100644
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -31,6 +31,7 @@
 #include "src/lookup-cache-inl.h"
 #include "src/lookup.h"
 #include "src/objects.h"
+#include "src/objects/hash-table.h"
 #include "src/objects/literal-objects.h"
 #include "src/objects/module-info.h"
 #include "src/objects/regexp-match-info.h"
@@ -115,6 +116,7 @@
 TYPE_CHECKER(TypeFeedbackInfo, TUPLE3_TYPE)
 TYPE_CHECKER(WeakCell, WEAK_CELL_TYPE)
 TYPE_CHECKER(WeakFixedArray, FIXED_ARRAY_TYPE)
+TYPE_CHECKER(SmallOrderedHashSet, SMALL_ORDERED_HASH_SET_TYPE)
 
 #define TYPED_ARRAY_TYPE_CHECKER(Type, type, TYPE, ctype, size) \
   TYPE_CHECKER(Fixed##Type##Array, FIXED_##TYPE##_ARRAY_TYPE)
@@ -640,6 +642,7 @@
 CAST_ACCESSOR(TypeFeedbackInfo)
 CAST_ACCESSOR(UnseededNumberDictionary)
 CAST_ACCESSOR(WeakCell)
+CAST_ACCESSOR(SmallOrderedHashSet)
 CAST_ACCESSOR(WeakFixedArray)
 CAST_ACCESSOR(WeakHashTable)
 
@@ -4209,6 +4212,9 @@
     return reinterpret_cast<FixedTypedArrayBase*>(
         this)->TypedArraySize(instance_type);
   }
+  if (instance_type == SMALL_ORDERED_HASH_SET_TYPE) {
+    return reinterpret_cast<SmallOrderedHashSet*>(this)->Size();
+  }
   DCHECK(instance_type == CODE_TYPE);
   return reinterpret_cast<Code*>(this)->CodeSize();
 }
@@ -6417,6 +6423,12 @@
   WRITE_INTPTR_FIELD(this, kForeignAddressOffset, OffsetFrom(value));
 }
 
+template <class Derived>
+void SmallOrderedHashTable<Derived>::SetDataEntry(int entry, Object* value) {
+  int offset = GetDataEntryOffset(entry);
+  NOBARRIER_WRITE_FIELD(this, offset, value);
+  WRITE_BARRIER(GetHeap(), this, offset, value);
+}
 
 ACCESSORS(JSGeneratorObject, function, JSFunction, kFunctionOffset)
 ACCESSORS(JSGeneratorObject, context, Context, kContextOffset)
diff --git a/src/objects.cc b/src/objects.cc
index b51aebc..741e73a 100644
--- a/src/objects.cc
+++ b/src/objects.cc
@@ -59,6 +59,7 @@
 #include "src/objects/compilation-cache-inl.h"
 #include "src/objects/debug-objects-inl.h"
 #include "src/objects/frame-array-inl.h"
+#include "src/objects/hash-table.h"
 #include "src/objects/map.h"
 #include "src/property-descriptor.h"
 #include "src/prototype.h"
@@ -3159,6 +3160,8 @@
   os << value();
 }
 
+#define FIELD_ADDR(p, offset) \
+  (reinterpret_cast<byte*>(p) + offset - kHeapObjectTag)
 
 #define FIELD_ADDR_CONST(p, offset) \
   (reinterpret_cast<const byte*>(p) + offset - kHeapObjectTag)
@@ -18883,6 +18886,173 @@
 template bool OrderedHashTable<OrderedHashMap, 2>::HasKey(
     Handle<OrderedHashMap> table, Handle<Object> key);
 
+template <>
+Handle<SmallOrderedHashSet>
+SmallOrderedHashTable<SmallOrderedHashSet>::Allocate(Isolate* isolate,
+                                                     int capacity,
+                                                     PretenureFlag pretenure) {
+  return isolate->factory()->NewSmallOrderedHashSet(capacity, pretenure);
+}
+
+template <class Derived>
+void SmallOrderedHashTable<Derived>::Initialize(Isolate* isolate,
+                                                int capacity) {
+  int num_buckets = capacity / kLoadFactor;
+  int num_chains = capacity;
+
+  SetNumberOfBuckets(num_buckets);
+  SetNumberOfElements(0);
+  SetNumberOfDeletedElements(0);
+
+  byte* hashtable_start =
+      FIELD_ADDR(this, kHeaderSize + (kBucketsStartOffset * kOneByteSize));
+  memset(hashtable_start, kNotFound, num_buckets + num_chains);
+
+  if (isolate->heap()->InNewSpace(this)) {
+    MemsetPointer(RawField(this, GetDataTableStartOffset()),
+                  isolate->heap()->the_hole_value(), capacity);
+  } else {
+    for (int i = 0; i < capacity; i++) {
+      SetDataEntry(i, isolate->heap()->the_hole_value());
+    }
+  }
+
+#ifdef DEBUG
+  for (int i = 0; i < num_buckets; ++i) {
+    DCHECK_EQ(kNotFound, GetFirstEntry(i));
+  }
+
+  for (int i = 0; i < num_chains; ++i) {
+    DCHECK_EQ(kNotFound, GetNextEntry(i));
+  }
+#endif  // DEBUG
+}
+
+template <class Derived>
+Handle<Derived> SmallOrderedHashTable<Derived>::Add(Handle<Derived> table,
+                                                    Handle<Object> key) {
+  Isolate* isolate = table->GetIsolate();
+  if (table->HasKey(isolate, key)) return table;
+
+  if (table->UsedCapacity() >= table->Capacity()) {
+    table = Derived::Grow(table);
+  }
+
+  int hash = Object::GetOrCreateHash(table->GetIsolate(), key)->value();
+  int nof = table->NumberOfElements();
+
+  // Read the existing bucket values.
+  int bucket = table->HashToBucket(hash);
+  int previous_entry = table->HashToFirstEntry(hash);
+
+  // Insert a new entry at the end,
+  int new_entry = nof + table->NumberOfDeletedElements();
+
+  // TODO(gsathya): Add support for entrysize > 1.
+  table->SetDataEntry(new_entry, *key);
+  table->SetFirstEntry(bucket, new_entry);
+  table->SetNextEntry(new_entry, previous_entry);
+
+  // and update book keeping.
+  table->SetNumberOfElements(nof + 1);
+
+  return table;
+}
+
+template <class Derived>
+bool SmallOrderedHashTable<Derived>::HasKey(Isolate* isolate,
+                                            Handle<Object> key) {
+  DisallowHeapAllocation no_gc;
+  Object* raw_key = *key;
+  Object* hash = key->GetHash();
+
+  if (hash->IsUndefined(isolate)) return false;
+  int entry = HashToFirstEntry(Smi::cast(hash)->value());
+
+  // Walk the chain in the bucket to find the key.
+  while (entry != kNotFound) {
+    Object* candidate_key = KeyAt(entry);
+    if (candidate_key->SameValueZero(raw_key)) return true;
+    entry = GetNextEntry(entry);
+  }
+  return false;
+}
+
+template <class Derived>
+Handle<Derived> SmallOrderedHashTable<Derived>::Rehash(Handle<Derived> table,
+                                                       int new_capacity) {
+  DCHECK_GE(kMaxCapacity, new_capacity);
+  Isolate* isolate = table->GetIsolate();
+
+  Handle<Derived> new_table = SmallOrderedHashTable<Derived>::Allocate(
+      isolate, new_capacity,
+      isolate->heap()->InNewSpace(*table) ? NOT_TENURED : TENURED);
+  int nof = table->NumberOfElements();
+  int nod = table->NumberOfDeletedElements();
+  int new_entry = 0;
+
+  {
+    DisallowHeapAllocation no_gc;
+    for (int old_entry = 0; old_entry < (nof + nod); ++old_entry) {
+      Object* key = table->KeyAt(old_entry);
+      if (key->IsTheHole(isolate)) continue;
+
+      int hash = Smi::cast(key->GetHash())->value();
+      int bucket = new_table->HashToBucket(hash);
+      int chain = new_table->GetFirstEntry(bucket);
+
+      new_table->SetFirstEntry(bucket, new_entry);
+      new_table->SetNextEntry(new_entry, chain);
+
+      for (int i = 0; i < Derived::kEntrySize; ++i) {
+        Object* value = table->GetDataEntry(old_entry + i);
+        new_table->SetDataEntry(new_entry + i, value);
+      }
+
+      ++new_entry;
+    }
+
+    new_table->SetNumberOfElements(nof);
+  }
+  return new_table;
+}
+
+template <class Derived>
+Handle<Derived> SmallOrderedHashTable<Derived>::Grow(Handle<Derived> table) {
+  int capacity = table->Capacity();
+  int new_capacity = capacity;
+
+  // Don't need to grow if we can simply clear out deleted entries instead.
+  // TODO(gsathya): Compact in place, instead of allocating a new table.
+  if (table->NumberOfDeletedElements() < (capacity >> 1)) {
+    new_capacity = capacity << 1;
+
+    // The max capacity of our table is 254. We special case for 256 to
+    // account for our growth strategy, otherwise we would only fill up
+    // to 128 entries in our table.
+    if (new_capacity == kGrowthHack) {
+      new_capacity = kMaxCapacity;
+    }
+
+    // TODO(gsathya): Transition to OrderedHashTable for size > kMaxCapacity.
+  }
+
+  return Rehash(table, new_capacity);
+}
+
+template bool SmallOrderedHashTable<SmallOrderedHashSet>::HasKey(
+    Isolate* isolate, Handle<Object> key);
+template Handle<SmallOrderedHashSet>
+SmallOrderedHashTable<SmallOrderedHashSet>::Add(
+    Handle<SmallOrderedHashSet> table, Handle<Object> key);
+template Handle<SmallOrderedHashSet>
+SmallOrderedHashTable<SmallOrderedHashSet>::Rehash(
+    Handle<SmallOrderedHashSet> table, int new_capacity);
+template Handle<SmallOrderedHashSet> SmallOrderedHashTable<
+    SmallOrderedHashSet>::Grow(Handle<SmallOrderedHashSet> table);
+template void SmallOrderedHashTable<SmallOrderedHashSet>::Initialize(
+    Isolate* isolate, int capacity);
+
 template<class Derived, class TableType>
 void OrderedHashTableIterator<Derived, TableType>::Transition() {
   DisallowHeapAllocation no_allocation;
diff --git a/src/objects.h b/src/objects.h
index 1554e1f..db3c6ff 100644
--- a/src/objects.h
+++ b/src/objects.h
@@ -151,6 +151,7 @@
 //       - Module
 //       - ModuleInfoEntry
 //     - WeakCell
+//     - SmallOrderedHashSet
 //
 // Formats of Object*:
 //  Smi:        [31 bit signed int] 0
@@ -370,6 +371,7 @@
   V(CELL_TYPE)                                                                 \
   V(WEAK_CELL_TYPE)                                                            \
   V(PROPERTY_CELL_TYPE)                                                        \
+  V(SMALL_ORDERED_HASH_SET_TYPE)                                               \
   /* TODO(yangguo): these padding types are for ABI stability. Remove after*/  \
   /* version 6.0 branch, or replace them when there is demand for new types.*/ \
   V(PADDING_TYPE_1)                                                            \
@@ -712,6 +714,7 @@
   CELL_TYPE,
   WEAK_CELL_TYPE,
   PROPERTY_CELL_TYPE,
+  SMALL_ORDERED_HASH_SET_TYPE,
 
   // TODO(yangguo): these padding types are for ABI stability. Remove after
   // version 6.0 branch, or replace them when there is demand for new types.
@@ -1089,6 +1092,7 @@
   V(SharedFunctionInfo)                \
   V(SlicedString)                      \
   V(SloppyArgumentsElements)           \
+  V(SmallOrderedHashSet)               \
   V(SourcePositionTableWithFrameCache) \
   V(String)                            \
   V(StringSet)                         \
diff --git a/src/objects/hash-table.h b/src/objects/hash-table.h
index f3c68a8..1a5d73e 100644
--- a/src/objects/hash-table.h
+++ b/src/objects/hash-table.h
@@ -584,6 +584,201 @@
   }
 };
 
+// This is similar to the OrderedHashTable, except for the memory
+// layout where we use byte instead of Smi. The max capacity of this
+// is only 254, we transition to an OrderedHashTable beyond that
+// limit.
+//
+// Each bucket and chain value is a byte long. The padding exists so
+// that the DataTable entries start aligned. A bucket or chain value
+// of 255 is used to denote an unknown entry.
+//
+// Memory layout: [ Header ] [ HashTable ] [ Chains ] [ Padding ] [ DataTable ]
+//
+// On a 64 bit machine with capacity = 4 and 2 entries,
+//
+// [ Header ]  :
+//    [0  .. 7]  : Number of elements
+//    [8  .. 15] : Number of deleted elements
+//    [16 .. 23] : Number of buckets
+//
+// [ HashTable ] :
+//    [24 .. 31] : First chain-link for bucket 1
+//    [32 .. 40] : First chain-link for bucket 2
+//
+// [ Chains ] :
+//    [40 .. 47] : Next chain link for entry 1
+//    [48 .. 55] : Next chain link for entry 2
+//    [56 .. 63] : Next chain link for entry 3
+//    [64 .. 71] : Next chain link for entry 4
+//
+// [ Padding ] :
+//    [72 .. 127] : Padding
+//
+// [ DataTable ] :
+//    [128 .. 128 + kEntrySize - 1] : Entry 1
+//    [128 + kEntrySize .. 128 + kEntrySize + kEntrySize - 1] : Entry 2
+//
+template <class Derived>
+class SmallOrderedHashTable : public HeapObject {
+ public:
+  void Initialize(Isolate* isolate, int capacity);
+
+  static Handle<Derived> Allocate(Isolate* isolate, int capacity,
+                                  PretenureFlag pretenure = NOT_TENURED);
+
+  // Adds |value| to |table|, if the capacity isn't enough, a new
+  // table is created. The original |table| is returned if there is
+  // capacity to store |value| otherwise the new table is returned.
+  static Handle<Derived> Add(Handle<Derived> table, Handle<Object> value);
+
+  // Returns a true if the OrderedHashTable contains the key
+  bool HasKey(Isolate* isolate, Handle<Object> key);
+
+  // Iterates only fields in the DataTable.
+  class BodyDescriptor;
+
+  // Returns an SmallOrderedHashTable (possibly |table|) with enough
+  // space to add at least one new element.
+  static Handle<Derived> Grow(Handle<Derived> table);
+
+  static Handle<Derived> Rehash(Handle<Derived> table, int new_capacity);
+
+  void SetDataEntry(int entry, Object* value);
+
+  // TODO(gsathya): There should be a better way to do this.
+  static int GetDataTableStartOffset(int capacity) {
+    int nof_buckets = capacity / kLoadFactor;
+    int nof_chain_entries = capacity;
+
+    int padding_index = kBucketsStartOffset + nof_buckets + nof_chain_entries;
+    int padding_offset = padding_index * kBitsPerByte;
+
+    return ((padding_offset + kPointerSize - 1) / kPointerSize) * kPointerSize;
+  }
+
+  int GetDataTableStartOffset() { return GetDataTableStartOffset(Capacity()); }
+
+  static int Size(int capacity) {
+    int data_table_start = GetDataTableStartOffset(capacity);
+    int data_table_size = capacity * Derived::kEntrySize * kBitsPerPointer;
+    return data_table_start + data_table_size;
+  }
+
+  int Size() { return Size(Capacity()); }
+
+  void SetFirstEntry(int bucket, byte value) {
+    set(kBucketsStartOffset + bucket, value);
+  }
+
+  int GetFirstEntry(int bucket) { return get(kBucketsStartOffset + bucket); }
+
+  void SetNextEntry(int entry, int next_entry) {
+    set(GetChainTableOffset() + entry, next_entry);
+  }
+
+  int GetNextEntry(int entry) { return get(GetChainTableOffset() + entry); }
+
+  Object* GetDataEntry(int entry) {
+    int offset = GetDataEntryOffset(entry);
+    return READ_FIELD(this, offset);
+  }
+
+  // TODO(gsathya): This will be specialized once we support entrysize > 1.
+  Object* KeyAt(int entry) {
+    int offset = GetDataEntryOffset(entry);
+    return READ_FIELD(this, offset);
+  }
+
+  int HashToBucket(int hash) { return hash & (NumberOfBuckets() - 1); }
+
+  int HashToFirstEntry(int hash) {
+    int bucket = HashToBucket(hash);
+    int entry = GetFirstEntry(bucket);
+    return entry;
+  }
+
+  int GetChainTableOffset() { return kBucketsStartOffset + NumberOfBuckets(); }
+
+  void SetNumberOfBuckets(int num) { set(kNumberOfBucketsOffset, num); }
+
+  void SetNumberOfElements(int num) { set(kNumberOfElementsOffset, num); }
+
+  void SetNumberOfDeletedElements(int num) {
+    set(kNumberOfDeletedElementsOffset, num);
+  }
+
+  int NumberOfElements() { return get(kNumberOfElementsOffset); }
+
+  int NumberOfDeletedElements() { return get(kNumberOfDeletedElementsOffset); }
+
+  int NumberOfBuckets() { return get(kNumberOfBucketsOffset); }
+
+  static const byte kNotFound = 0xFF;
+  static const int kMinCapacity = 4;
+
+  // We use the value 255 to indicate kNotFound for chain and bucket
+  // values, which means that this value can't be used a valid
+  // index.
+  static const int kMaxCapacity = 254;
+  STATIC_ASSERT(kMaxCapacity < kNotFound);
+
+  static const int kNumberOfElementsOffset = 0;
+  static const int kNumberOfDeletedElementsOffset = 1;
+  static const int kNumberOfBucketsOffset = 2;
+  static const int kBucketsStartOffset = 3;
+
+  // The load factor is used to derive the number of buckets from
+  // capacity during Allocation. We also depend on this to calaculate
+  // the capacity from number of buckets after allocation. If we
+  // decide to change kLoadFactor to something other than 2, capacity
+  // should be stored as another field of this object.
+  static const int kLoadFactor = 2;
+  static const int kBitsPerPointer = kPointerSize * kBitsPerByte;
+
+  // Our growth strategy involves doubling the capacity until we reach
+  // kMaxCapacity, but since the kMaxCapacity is always less than 256,
+  // we will never fully utilize this table. We special case for 256,
+  // by changing the new capacity to be kMaxCapacity in
+  // SmallOrderedHashTable::Grow.
+  static const int kGrowthHack = 256;
+
+ protected:
+  // This is used for accessing the non |DataTable| part of the
+  // structure.
+  byte get(int index) {
+    return READ_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize));
+  }
+
+  void set(int index, byte value) {
+    WRITE_BYTE_FIELD(this, kHeaderSize + (index * kOneByteSize), value);
+  }
+
+  int GetDataEntryOffset(int entry) {
+    int datatable_start = GetDataTableStartOffset();
+    int offset_in_datatable = entry * Derived::kEntrySize * kPointerSize;
+    return datatable_start + offset_in_datatable;
+  }
+
+  // Returns the number elements that can fit into the allocated buffer.
+  int Capacity() { return NumberOfBuckets() * kLoadFactor; }
+
+  int UsedCapacity() { return NumberOfElements() + NumberOfDeletedElements(); }
+};
+
+class SmallOrderedHashSet : public SmallOrderedHashTable<SmallOrderedHashSet> {
+ public:
+  DECLARE_CAST(SmallOrderedHashSet)
+
+  DECLARE_PRINTER(SmallOrderedHashSet)
+  DECLARE_VERIFIER(SmallOrderedHashSet)
+
+  static const int kEntrySize = 1;
+
+  // Iterates only fields in the DataTable.
+  class BodyDescriptor;
+};
+
 // OrderedHashTableIterator is an iterator that iterates over the keys and
 // values of an OrderedHashTable.
 //
diff --git a/test/cctest/BUILD.gn b/test/cctest/BUILD.gn
index d5365df..aff255a 100644
--- a/test/cctest/BUILD.gn
+++ b/test/cctest/BUILD.gn
@@ -158,6 +158,7 @@
     "test-mementos.cc",
     "test-modules.cc",
     "test-object.cc",
+    "test-orderedhashtable.cc",
     "test-parsing.cc",
     "test-platform.cc",
     "test-profile-generator.cc",
diff --git a/test/cctest/cctest.gyp b/test/cctest/cctest.gyp
index cf30741..4c9cb2d 100644
--- a/test/cctest/cctest.gyp
+++ b/test/cctest/cctest.gyp
@@ -176,6 +176,7 @@
       'test-mementos.cc',
       'test-modules.cc',
       'test-object.cc',
+      'test-orderedhashtable.cc',
       'test-parsing.cc',
       'test-platform.cc',
       'test-profile-generator.cc',
diff --git a/test/cctest/test-orderedhashtable.cc b/test/cctest/test-orderedhashtable.cc
new file mode 100644
index 0000000..6dece0e
--- /dev/null
+++ b/test/cctest/test-orderedhashtable.cc
@@ -0,0 +1,284 @@
+// Copyright 2017 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+#include <utility>
+#include "src/v8.h"
+
+#include "src/objects-inl.h"
+#include "test/cctest/cctest.h"
+
+using namespace v8::internal;
+
+static Isolate* GetIsolateFrom(LocalContext* context) {
+  return reinterpret_cast<Isolate*>((*context)->GetIsolate());
+}
+
+void Verify(Handle<SmallOrderedHashSet> set) {
+#if VERIFY_HEAP
+  set->ObjectVerify();
+#endif
+}
+
+TEST(Insertion) {
+  LocalContext context;
+  Isolate* isolate = GetIsolateFrom(&context);
+  Factory* factory = isolate->factory();
+  HandleScope scope(isolate);
+
+  Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfElements());
+
+  // Add a new key.
+  Handle<Smi> key1(Smi::FromInt(1), isolate);
+  CHECK(!set->HasKey(isolate, key1));
+  set = SmallOrderedHashSet::Add(set, key1);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(1, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+
+  // Add existing key.
+  set = SmallOrderedHashSet::Add(set, key1);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(1, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+
+  Handle<String> key2 = factory->NewStringFromAsciiChecked("foo");
+  CHECK(!set->HasKey(isolate, key2));
+  set = SmallOrderedHashSet::Add(set, key2);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(2, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+
+  set = SmallOrderedHashSet::Add(set, key2);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(2, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+
+  Handle<Symbol> key3 = factory->NewSymbol();
+  CHECK(!set->HasKey(isolate, key3));
+  set = SmallOrderedHashSet::Add(set, key3);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(3, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+  CHECK(set->HasKey(isolate, key3));
+
+  set = SmallOrderedHashSet::Add(set, key3);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(3, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+  CHECK(set->HasKey(isolate, key3));
+
+  Handle<Object> key4 = factory->NewHeapNumber(42.0);
+  CHECK(!set->HasKey(isolate, key4));
+  set = SmallOrderedHashSet::Add(set, key4);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(4, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+  CHECK(set->HasKey(isolate, key3));
+  CHECK(set->HasKey(isolate, key4));
+
+  set = SmallOrderedHashSet::Add(set, key4);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(4, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+  CHECK(set->HasKey(isolate, key3));
+  CHECK(set->HasKey(isolate, key4));
+}
+
+TEST(DuplicateHashCode) {
+  LocalContext context;
+  Isolate* isolate = GetIsolateFrom(&context);
+  Factory* factory = isolate->factory();
+  HandleScope scope(isolate);
+
+  Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
+  Handle<JSObject> key1 = factory->NewJSObjectWithNullProto();
+  set = SmallOrderedHashSet::Add(set, key1);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(1, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+
+  Handle<Name> hash_code_symbol = isolate->factory()->hash_code_symbol();
+  Handle<Smi> hash =
+      Handle<Smi>::cast(JSObject::GetDataProperty(key1, hash_code_symbol));
+
+  Handle<JSObject> key2 = factory->NewJSObjectWithNullProto();
+  LookupIterator it(key2, hash_code_symbol, key2, LookupIterator::OWN);
+  CHECK(key2->AddDataProperty(
+                &it, hash, NONE, v8::internal::AccessCheckInfo::THROW_ON_ERROR,
+                v8::internal::AccessCheckInfo::CERTAINLY_NOT_STORE_FROM_KEYED)
+            .IsJust());
+
+  set = SmallOrderedHashSet::Add(set, key2);
+  Verify(set);
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(2, set->NumberOfElements());
+  CHECK(set->HasKey(isolate, key1));
+  CHECK(set->HasKey(isolate, key2));
+}
+
+TEST(Grow) {
+  LocalContext context;
+  Isolate* isolate = GetIsolateFrom(&context);
+  Factory* factory = isolate->factory();
+  HandleScope scope(isolate);
+
+  Handle<SmallOrderedHashSet> set = factory->NewSmallOrderedHashSet();
+  std::vector<Handle<Object>> keys;
+  for (size_t i = 0; i < 4; i++) {
+    Handle<Smi> key(Smi::FromInt(static_cast<int>(i)), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 0; i < 4; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 4; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(4, set->NumberOfElements());
+  CHECK_EQ(2, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 4; i < 8; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 4; i < 8; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 8; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(8, set->NumberOfElements());
+  CHECK_EQ(4, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 8; i < 16; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 8; i < 16; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 16; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(16, set->NumberOfElements());
+  CHECK_EQ(8, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 16; i < 32; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 16; i < 32; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 32; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(32, set->NumberOfElements());
+  CHECK_EQ(16, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 32; i < 64; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 32; i < 64; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 64; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(64, set->NumberOfElements());
+  CHECK_EQ(32, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 64; i < 128; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 64; i < 128; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 128; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(128, set->NumberOfElements());
+  CHECK_EQ(64, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+
+  for (int i = 128; i < 254; i++) {
+    Handle<Smi> key(Smi::FromInt(i), isolate);
+    keys.push_back(key);
+  }
+
+  for (size_t i = 128; i < 254; i++) {
+    set = SmallOrderedHashSet::Add(set, keys[i]);
+    Verify(set);
+  }
+
+  for (size_t i = 0; i < 254; i++) {
+    CHECK(set->HasKey(isolate, keys[i]));
+    Verify(set);
+  }
+
+  CHECK_EQ(254, set->NumberOfElements());
+  CHECK_EQ(127, set->NumberOfBuckets());
+  CHECK_EQ(0, set->NumberOfDeletedElements());
+  Verify(set);
+}
diff --git a/tools/v8heapconst.py b/tools/v8heapconst.py
index 2031367..58c84ee 100644
--- a/tools/v8heapconst.py
+++ b/tools/v8heapconst.py
@@ -77,77 +77,78 @@
   173: "CELL_TYPE",
   174: "WEAK_CELL_TYPE",
   175: "PROPERTY_CELL_TYPE",
-  176: "PADDING_TYPE_1",
-  177: "PADDING_TYPE_2",
-  178: "PADDING_TYPE_3",
-  179: "PADDING_TYPE_4",
-  180: "JS_PROXY_TYPE",
-  181: "JS_GLOBAL_OBJECT_TYPE",
-  182: "JS_GLOBAL_PROXY_TYPE",
-  183: "JS_SPECIAL_API_OBJECT_TYPE",
-  184: "JS_VALUE_TYPE",
-  185: "JS_MESSAGE_OBJECT_TYPE",
-  186: "JS_DATE_TYPE",
-  187: "JS_API_OBJECT_TYPE",
-  188: "JS_OBJECT_TYPE",
-  189: "JS_ARGUMENTS_TYPE",
-  190: "JS_CONTEXT_EXTENSION_OBJECT_TYPE",
-  191: "JS_GENERATOR_OBJECT_TYPE",
-  192: "JS_ASYNC_GENERATOR_OBJECT_TYPE",
-  193: "JS_MODULE_NAMESPACE_TYPE",
-  194: "JS_ARRAY_TYPE",
-  195: "JS_ARRAY_BUFFER_TYPE",
-  196: "JS_TYPED_ARRAY_TYPE",
-  197: "JS_DATA_VIEW_TYPE",
-  198: "JS_SET_TYPE",
-  199: "JS_MAP_TYPE",
-  200: "JS_SET_ITERATOR_TYPE",
-  201: "JS_MAP_ITERATOR_TYPE",
-  202: "JS_WEAK_MAP_TYPE",
-  203: "JS_WEAK_SET_TYPE",
-  204: "JS_PROMISE_CAPABILITY_TYPE",
-  205: "JS_PROMISE_TYPE",
-  206: "JS_REGEXP_TYPE",
-  207: "JS_ERROR_TYPE",
-  208: "JS_ASYNC_FROM_SYNC_ITERATOR_TYPE",
-  209: "JS_STRING_ITERATOR_TYPE",
-  210: "JS_TYPED_ARRAY_KEY_ITERATOR_TYPE",
-  211: "JS_FAST_ARRAY_KEY_ITERATOR_TYPE",
-  212: "JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE",
-  213: "JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  214: "JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  215: "JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  216: "JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  217: "JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  218: "JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  219: "JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  220: "JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  221: "JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  222: "JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  223: "JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  224: "JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  225: "JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  226: "JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  227: "JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  228: "JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE",
-  229: "JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE",
-  230: "JS_INT8_ARRAY_VALUE_ITERATOR_TYPE",
-  231: "JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE",
-  232: "JS_INT16_ARRAY_VALUE_ITERATOR_TYPE",
-  233: "JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE",
-  234: "JS_INT32_ARRAY_VALUE_ITERATOR_TYPE",
-  235: "JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE",
-  236: "JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE",
-  237: "JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE",
-  238: "JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE",
-  239: "JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE",
-  240: "JS_FAST_ARRAY_VALUE_ITERATOR_TYPE",
-  241: "JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE",
-  242: "JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE",
-  243: "JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE",
-  244: "JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE",
-  245: "JS_BOUND_FUNCTION_TYPE",
-  246: "JS_FUNCTION_TYPE",
+  176: "SMALL_ORDERED_HASH_SET_TYPE",
+  177: "PADDING_TYPE_1",
+  178: "PADDING_TYPE_2",
+  179: "PADDING_TYPE_3",
+  180: "PADDING_TYPE_4",
+  181: "JS_PROXY_TYPE",
+  182: "JS_GLOBAL_OBJECT_TYPE",
+  183: "JS_GLOBAL_PROXY_TYPE",
+  184: "JS_SPECIAL_API_OBJECT_TYPE",
+  185: "JS_VALUE_TYPE",
+  186: "JS_MESSAGE_OBJECT_TYPE",
+  187: "JS_DATE_TYPE",
+  188: "JS_API_OBJECT_TYPE",
+  189: "JS_OBJECT_TYPE",
+  190: "JS_ARGUMENTS_TYPE",
+  191: "JS_CONTEXT_EXTENSION_OBJECT_TYPE",
+  192: "JS_GENERATOR_OBJECT_TYPE",
+  193: "JS_ASYNC_GENERATOR_OBJECT_TYPE",
+  194: "JS_MODULE_NAMESPACE_TYPE",
+  195: "JS_ARRAY_TYPE",
+  196: "JS_ARRAY_BUFFER_TYPE",
+  197: "JS_TYPED_ARRAY_TYPE",
+  198: "JS_DATA_VIEW_TYPE",
+  199: "JS_SET_TYPE",
+  200: "JS_MAP_TYPE",
+  201: "JS_SET_ITERATOR_TYPE",
+  202: "JS_MAP_ITERATOR_TYPE",
+  203: "JS_WEAK_MAP_TYPE",
+  204: "JS_WEAK_SET_TYPE",
+  205: "JS_PROMISE_CAPABILITY_TYPE",
+  206: "JS_PROMISE_TYPE",
+  207: "JS_REGEXP_TYPE",
+  208: "JS_ERROR_TYPE",
+  209: "JS_ASYNC_FROM_SYNC_ITERATOR_TYPE",
+  210: "JS_STRING_ITERATOR_TYPE",
+  211: "JS_TYPED_ARRAY_KEY_ITERATOR_TYPE",
+  212: "JS_FAST_ARRAY_KEY_ITERATOR_TYPE",
+  213: "JS_GENERIC_ARRAY_KEY_ITERATOR_TYPE",
+  214: "JS_UINT8_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  215: "JS_INT8_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  216: "JS_UINT16_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  217: "JS_INT16_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  218: "JS_UINT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  219: "JS_INT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  220: "JS_FLOAT32_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  221: "JS_FLOAT64_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  222: "JS_UINT8_CLAMPED_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  223: "JS_FAST_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  224: "JS_FAST_HOLEY_SMI_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  225: "JS_FAST_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  226: "JS_FAST_HOLEY_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  227: "JS_FAST_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  228: "JS_FAST_HOLEY_DOUBLE_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  229: "JS_GENERIC_ARRAY_KEY_VALUE_ITERATOR_TYPE",
+  230: "JS_UINT8_ARRAY_VALUE_ITERATOR_TYPE",
+  231: "JS_INT8_ARRAY_VALUE_ITERATOR_TYPE",
+  232: "JS_UINT16_ARRAY_VALUE_ITERATOR_TYPE",
+  233: "JS_INT16_ARRAY_VALUE_ITERATOR_TYPE",
+  234: "JS_UINT32_ARRAY_VALUE_ITERATOR_TYPE",
+  235: "JS_INT32_ARRAY_VALUE_ITERATOR_TYPE",
+  236: "JS_FLOAT32_ARRAY_VALUE_ITERATOR_TYPE",
+  237: "JS_FLOAT64_ARRAY_VALUE_ITERATOR_TYPE",
+  238: "JS_UINT8_CLAMPED_ARRAY_VALUE_ITERATOR_TYPE",
+  239: "JS_FAST_SMI_ARRAY_VALUE_ITERATOR_TYPE",
+  240: "JS_FAST_HOLEY_SMI_ARRAY_VALUE_ITERATOR_TYPE",
+  241: "JS_FAST_ARRAY_VALUE_ITERATOR_TYPE",
+  242: "JS_FAST_HOLEY_ARRAY_VALUE_ITERATOR_TYPE",
+  243: "JS_FAST_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE",
+  244: "JS_FAST_HOLEY_DOUBLE_ARRAY_VALUE_ITERATOR_TYPE",
+  245: "JS_GENERIC_ARRAY_VALUE_ITERATOR_TYPE",
+  246: "JS_BOUND_FUNCTION_TYPE",
+  247: "JS_FUNCTION_TYPE",
 }
 
 # List of known V8 maps.
@@ -194,69 +195,70 @@
   0x02f69: (133, "MutableHeapNumberMap"),
   0x02fc1: (170, "OrderedHashTableMap"),
   0x03019: (170, "SloppyArgumentsElementsMap"),
-  0x03071: (185, "JSMessageObjectMap"),
-  0x030c9: (136, "BytecodeArrayMap"),
-  0x03121: (170, "ModuleInfoMap"),
-  0x03179: (173, "NoClosuresCellMap"),
-  0x031d1: (173, "OneClosureCellMap"),
-  0x03229: (173, "ManyClosuresCellMap"),
-  0x03281: (64, "StringMap"),
-  0x032d9: (73, "ConsOneByteStringMap"),
-  0x03331: (65, "ConsStringMap"),
-  0x03389: (77, "ThinOneByteStringMap"),
-  0x033e1: (69, "ThinStringMap"),
-  0x03439: (67, "SlicedStringMap"),
-  0x03491: (75, "SlicedOneByteStringMap"),
-  0x034e9: (66, "ExternalStringMap"),
-  0x03541: (82, "ExternalStringWithOneByteDataMap"),
-  0x03599: (74, "ExternalOneByteStringMap"),
-  0x035f1: (98, "ShortExternalStringMap"),
-  0x03649: (114, "ShortExternalStringWithOneByteDataMap"),
-  0x036a1: (0, "InternalizedStringMap"),
-  0x036f9: (2, "ExternalInternalizedStringMap"),
-  0x03751: (18, "ExternalInternalizedStringWithOneByteDataMap"),
-  0x037a9: (10, "ExternalOneByteInternalizedStringMap"),
-  0x03801: (34, "ShortExternalInternalizedStringMap"),
-  0x03859: (50, "ShortExternalInternalizedStringWithOneByteDataMap"),
-  0x038b1: (42, "ShortExternalOneByteInternalizedStringMap"),
-  0x03909: (106, "ShortExternalOneByteStringMap"),
-  0x03961: (139, "FixedUint8ArrayMap"),
-  0x039b9: (138, "FixedInt8ArrayMap"),
-  0x03a11: (141, "FixedUint16ArrayMap"),
-  0x03a69: (140, "FixedInt16ArrayMap"),
-  0x03ac1: (143, "FixedUint32ArrayMap"),
-  0x03b19: (142, "FixedInt32ArrayMap"),
-  0x03b71: (144, "FixedFloat32ArrayMap"),
-  0x03bc9: (145, "FixedFloat64ArrayMap"),
-  0x03c21: (146, "FixedUint8ClampedArrayMap"),
-  0x03c79: (157, "ScriptMap"),
-  0x03cd1: (170, "FeedbackVectorMap"),
-  0x03d29: (170, "DebugEvaluateContextMap"),
-  0x03d81: (170, "ScriptContextTableMap"),
-  0x03dd9: (170, "UnseededNumberDictionaryMap"),
-  0x03e31: (188, "ExternalMap"),
-  0x03e89: (106, "NativeSourceStringMap"),
-  0x03ee1: (152, "InterceptorInfoMap"),
-  0x03f39: (204, "JSPromiseCapabilityMap"),
-  0x03f91: (149, "AccessorInfoMap"),
-  0x03fe9: (150, "AccessorPairMap"),
-  0x04041: (151, "AccessCheckInfoMap"),
-  0x04099: (153, "FunctionTemplateInfoMap"),
-  0x040f1: (154, "ObjectTemplateInfoMap"),
-  0x04149: (155, "AllocationSiteMap"),
-  0x041a1: (156, "AllocationMementoMap"),
-  0x041f9: (158, "AliasedArgumentsEntryMap"),
-  0x04251: (159, "PromiseResolveThenableJobInfoMap"),
-  0x042a9: (160, "PromiseReactionJobInfoMap"),
-  0x04301: (161, "DebugInfoMap"),
-  0x04359: (162, "StackFrameInfoMap"),
-  0x043b1: (163, "PrototypeInfoMap"),
-  0x04409: (164, "Tuple2Map"),
-  0x04461: (165, "Tuple3Map"),
-  0x044b9: (166, "ContextExtensionMap"),
-  0x04511: (167, "ModuleMap"),
-  0x04569: (168, "ModuleInfoEntryMap"),
-  0x045c1: (169, "AsyncGeneratorRequestMap"),
+  0x03071: (176, "SmallOrderedHashSetMap"),
+  0x030c9: (186, "JSMessageObjectMap"),
+  0x03121: (136, "BytecodeArrayMap"),
+  0x03179: (170, "ModuleInfoMap"),
+  0x031d1: (173, "NoClosuresCellMap"),
+  0x03229: (173, "OneClosureCellMap"),
+  0x03281: (173, "ManyClosuresCellMap"),
+  0x032d9: (64, "StringMap"),
+  0x03331: (73, "ConsOneByteStringMap"),
+  0x03389: (65, "ConsStringMap"),
+  0x033e1: (77, "ThinOneByteStringMap"),
+  0x03439: (69, "ThinStringMap"),
+  0x03491: (67, "SlicedStringMap"),
+  0x034e9: (75, "SlicedOneByteStringMap"),
+  0x03541: (66, "ExternalStringMap"),
+  0x03599: (82, "ExternalStringWithOneByteDataMap"),
+  0x035f1: (74, "ExternalOneByteStringMap"),
+  0x03649: (98, "ShortExternalStringMap"),
+  0x036a1: (114, "ShortExternalStringWithOneByteDataMap"),
+  0x036f9: (0, "InternalizedStringMap"),
+  0x03751: (2, "ExternalInternalizedStringMap"),
+  0x037a9: (18, "ExternalInternalizedStringWithOneByteDataMap"),
+  0x03801: (10, "ExternalOneByteInternalizedStringMap"),
+  0x03859: (34, "ShortExternalInternalizedStringMap"),
+  0x038b1: (50, "ShortExternalInternalizedStringWithOneByteDataMap"),
+  0x03909: (42, "ShortExternalOneByteInternalizedStringMap"),
+  0x03961: (106, "ShortExternalOneByteStringMap"),
+  0x039b9: (139, "FixedUint8ArrayMap"),
+  0x03a11: (138, "FixedInt8ArrayMap"),
+  0x03a69: (141, "FixedUint16ArrayMap"),
+  0x03ac1: (140, "FixedInt16ArrayMap"),
+  0x03b19: (143, "FixedUint32ArrayMap"),
+  0x03b71: (142, "FixedInt32ArrayMap"),
+  0x03bc9: (144, "FixedFloat32ArrayMap"),
+  0x03c21: (145, "FixedFloat64ArrayMap"),
+  0x03c79: (146, "FixedUint8ClampedArrayMap"),
+  0x03cd1: (157, "ScriptMap"),
+  0x03d29: (170, "FeedbackVectorMap"),
+  0x03d81: (170, "DebugEvaluateContextMap"),
+  0x03dd9: (170, "ScriptContextTableMap"),
+  0x03e31: (170, "UnseededNumberDictionaryMap"),
+  0x03e89: (189, "ExternalMap"),
+  0x03ee1: (106, "NativeSourceStringMap"),
+  0x03f39: (152, "InterceptorInfoMap"),
+  0x03f91: (205, "JSPromiseCapabilityMap"),
+  0x03fe9: (149, "AccessorInfoMap"),
+  0x04041: (150, "AccessorPairMap"),
+  0x04099: (151, "AccessCheckInfoMap"),
+  0x040f1: (153, "FunctionTemplateInfoMap"),
+  0x04149: (154, "ObjectTemplateInfoMap"),
+  0x041a1: (155, "AllocationSiteMap"),
+  0x041f9: (156, "AllocationMementoMap"),
+  0x04251: (158, "AliasedArgumentsEntryMap"),
+  0x042a9: (159, "PromiseResolveThenableJobInfoMap"),
+  0x04301: (160, "PromiseReactionJobInfoMap"),
+  0x04359: (161, "DebugInfoMap"),
+  0x043b1: (162, "StackFrameInfoMap"),
+  0x04409: (163, "PrototypeInfoMap"),
+  0x04461: (164, "Tuple2Map"),
+  0x044b9: (165, "Tuple3Map"),
+  0x04511: (166, "ContextExtensionMap"),
+  0x04569: (167, "ModuleMap"),
+  0x045c1: (168, "ModuleInfoEntryMap"),
+  0x04619: (169, "AsyncGeneratorRequestMap"),
 }
 
 # List of known V8 objects.