New zone-backed list datastructure to replace ZoneList

test/unittests/zone/zone-chunk-list-unittest.cc

+// Copyright 2016 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 "src/zone/zone-chunk-list.h"

[Jakob Kummerow, 2016/10/26 14:45:10]

nit: one empty line after this

+#include "src/list-inl.h"
+#include "src/list.h"

[Jakob Kummerow, 2016/10/26 14:45:10]

nit: if you #include foo-inl.h, you don't need foo.h

+#include "src/zone/accounting-allocator.h"
+#include "src/zone/zone-containers.h"
+#include "src/zone/zone.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace v8 {
+namespace internal {
+
+const size_t kItemCount = size_t(1) << 14;

[Jakob Kummerow, 2016/10/26 14:45:10]

suggestion: 1 << 10 is enough; once you reach maximum chunk size, nothing
interesting will happen that hasn't happened before.

+
+size_t ZoneArraySizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  zone.NewArray<uintptr_t>(kItemCount);
+
+  PrintF("\nZone array used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t InitializedZoneListSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_list = new (&zone) ZoneList<uintptr_t>(kItemCount, &zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_list->Add(reinterpret_cast<uintptr_t>(i), &zone);
+  }
+
+  PrintF("\nInitialized Zone list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t ChunkListSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_chunk_list = new (&zone) ZoneChunkList<uintptr_t>(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list->push_back(reinterpret_cast<uintptr_t>(i));
+  }
+
+  PrintF("\nChunk zone list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t ChunkListMisusedSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_chunk_list = new (&zone) ZoneChunkList<uintptr_t>(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list->push_front(reinterpret_cast<uintptr_t>(i));
+  }
+
+  PrintF("\nMisused chunk zone list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t DequeSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_linked_list =
+      new (zone.New(sizeof(ZoneDeque<uintptr_t>))) ZoneDeque<uintptr_t>(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_linked_list->push_back(reinterpret_cast<uintptr_t>(i));
+  }
+
+  PrintF("\nDeque list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t EmptyZoneListSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_list = new (&zone) ZoneList<uintptr_t>(0, &zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_list->Add(reinterpret_cast<uintptr_t>(i), &zone);
+  }
+
+  PrintF("\nEmpty Zone list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+size_t LinkedListSizeTest() {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  auto zone_linked_list = new (zone.New(sizeof(ZoneLinkedList<uintptr_t>)))
+      ZoneLinkedList<uintptr_t>(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_linked_list->push_back(reinterpret_cast<uintptr_t>(i));
+  }
+
+  PrintF("\nLinked list used: %zu B\n", zone.allocation_size());
+  return zone.allocation_size();
+}
+
+TEST(Zone, ListSizeComparisons) {

[Jakob Kummerow, 2016/10/26 14:45:10]

While this test is useful to validate the design, I don't think it provides
value in the long term, and should be deleted before committing this CL.

+  size_t zone_array_size = ZoneArraySizeTest();
+  size_t initialized_zone_list_size = InitializedZoneListSizeTest();
+  size_t chunk_list_size = ChunkListSizeTest();
+  size_t dequeue_size = DequeSizeTest();
+  size_t empty_zone_list_size = EmptyZoneListSizeTest();
+  size_t linked_list_size = LinkedListSizeTest();
+  size_t misused_chunk_list_size = ChunkListMisusedSizeTest();
+
+  EXPECT_LE(zone_array_size, initialized_zone_list_size);
+  EXPECT_LE(initialized_zone_list_size, chunk_list_size);
+  EXPECT_LE(chunk_list_size, dequeue_size);
+  EXPECT_LE(dequeue_size, linked_list_size);
+  EXPECT_LE(linked_list_size, empty_zone_list_size);
+  EXPECT_LE(linked_list_size, misused_chunk_list_size);
+}
+
+TEST(Zone, ChunkListForwardIterationTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    count++;

[Jakob Kummerow, 2016/10/26 14:45:10]

suggestion: add "EXPECT_EQ(count, static_cast<size_t>(item));" as the first
thing in this loop, drop ChunkListDataTest below, and save some test time :-)

+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(Zone, ChunkListReverseIterationTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (auto it = zone_chunk_list.rbegin(); it != zone_chunk_list.rend(); ++it) {
+    count++;
+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(Zone, ChunkListDataTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i) % 100);
+  }
+
+  uintptr_t number = 0;
+  for (uintptr_t item : zone_chunk_list) {
+    EXPECT_EQ(item, number);
+    number = (number + 1) % 100;
+  }
+}
+
+TEST(Zone, ChunkListPushFrontTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_front(static_cast<uintptr_t>(i));
+  }
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    count++;
+  }
+
+  EXPECT_EQ(count, kItemCount);
+}
+
+TEST(Zone, ChunkListRewindTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  zone_chunk_list.Rewind(42);
+
+  size_t count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    count++;
+  }
+
+  EXPECT_EQ(count, 42);
+  EXPECT_EQ(count, zone_chunk_list.size());
+
+  zone_chunk_list.Rewind(0);
+
+  count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    count++;
+  }
+
+  EXPECT_EQ(count, 0);
+  EXPECT_EQ(count, zone_chunk_list.size());
+
+  zone_chunk_list.Rewind(100);
+
+  count = 0;
+
+  for (uintptr_t item : zone_chunk_list) {
+    count++;
+  }
+
+  EXPECT_EQ(count, 0);
+  EXPECT_EQ(count, zone_chunk_list.size());
+}
+
+TEST(Zone, ChunkListFindTest) {
+  AccountingAllocator allocator;
+  Zone zone(&allocator, ZONE_NAME);
+
+  ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
+
+  for (size_t i = 0; i < kItemCount; ++i) {
+    zone_chunk_list.push_back(static_cast<uintptr_t>(i));
+  }
+
+  const size_t index = kItemCount / 2 + 42;
+
+  EXPECT_EQ(*zone_chunk_list.Find(index), static_cast<uintptr_t>(index));
+
+  *zone_chunk_list.Find(index) = 42;
+
+  EXPECT_EQ(*zone_chunk_list.Find(index), 42);
+}
+
+}  // namespace internal
+}  // namespace v8