Jim Apple has posted comments on this change. Change subject: IMPALA-3200: Implement suballocator for splitting buffers ......................................................................
Patch Set 4: (34 comments) http://gerrit.cloudera.org:8080/#/c/4715/4//COMMIT_MSG Commit Message: PS4, Line 13: buddy allocation Buddy allocators tend to have high internal fragmentation.Did you consider a strategy like Two-level Segregated Fit? http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/bufferpool/suballocator-test.cc File be/src/bufferpool/suballocator-test.cc: Line 28: why the gap? Line 44: virtual void SetUp() { override, here and below PS4, Line 63: != NULL elide PS4, Line 68: Random 'Randomness' or 'PRNG'; the seed itself is not random Line 75: void VerifyMemoryValid(const vector<unique_ptr<Suballocation>>& allocs); static Line 78: void FreeAllocations( static PS4, Line 80: unique_ptr<Suballocation> auto PS4, Line 88: default_random_engine It might be good to pick one for repeatability reasons http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/bufferpool/suballocator.cc File be/src/bufferpool/suballocator.cc: Line 40: free_lists_[i] = NULL; This is the default. If you elide this loop, this should happen anyway. Line 59: const int target_list_idx = Bits::Log2CeilingNonZero64(bytes); How do you know bytes is non-zero? Line 60: for (int i = target_list_idx; i < ALLOCATION_SIZES; ++i) { This can be O(1) with ctz and a bitmap for the freelist emptiness Line 88: int64_t buffer_len = max(min_buffer_len_, BitUtil::RoundUpToPowerOfTwo(bytes)); const Line 127: if (!status.ok()) { if (!Suballocation::Create(&nodes[i]).ok()) {... Line 144: int64_t child_len = free_node->len_ / 2; const PS4, Line 233: != NULL elide http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/bufferpool/suballocator.h File be/src/bufferpool/suballocator.h: Line 31: enum class ExpandReservations { ExpansionStrategy, maybe? Line 37: }; This can live inside Suballocator, right? PS4, Line 39: buddy There are a few different variants of buddy systems. It might be good to spell out which one you're using, though maybe only in the .cc file. PS4, Line 43: relatively large allocations Yet free_lists_ goes all the way down to one byte? Why not enforce this at the interface level? Line 50: ExpandReservations expand_reservations); Can you annotate these params in a comment Line 54: /// Allocate bytes from BufferPool. The allocation is NULL if unsuccessful because nullptr, here and elsewhere Line 71: /// Allocate a buffer of size 'bytes' from the buffer pool and initialize 'result' bytes must be less than MAX_ALLOCATION_BYTES PS4, Line 79: Can fail if malloc() fails if new returns nullptr PS4, Line 109: by 'but' PS4, Line 127: must or else leaked memory or some kind of segfault or nasal demons? PS4, Line 132: Destructor Elide Line 138: private: also disallow_copy_and_assign? Line 152: /// The buffer backing the suballocation, if the suballocation is backed by an entire capitalization, here and elsewhere: Suballocation and Allocation Line 153: /// buffer. Otherwise uninitialized. 'buffer_' is open iff buddy is NULL. buddy_ Line 156: /// If this is a left child, the parent of this and its buddy. The parent's allocation It would be helpful to explain the tree structure first. Line 159: std::unique_ptr<Suballocation> parent_; Can the parent be a buddy, thus being pointed to by its buddy and one of its children? Line 171: Suballocation* prev_free_; so next_free_ is not really unique? I'm troubled by this design pattern. Did you consider weak_ptrs? http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/common/names.h File be/src/common/names.h: Line 124: using std::move; This might be overkill. I'd like 'move' to be available as a variable name sometimes. -- To view, visit http://gerrit.cloudera.org:8080/4715 To unsubscribe, visit http://gerrit.cloudera.org:8080/settings Gerrit-MessageType: comment Gerrit-Change-Id: I8bfe0e429f67ad273f7c7d0816703a9e6c3da788 Gerrit-PatchSet: 4 Gerrit-Project: Impala-ASF Gerrit-Branch: master Gerrit-Owner: Tim Armstrong <[email protected]> Gerrit-Reviewer: Jim Apple <[email protected]> Gerrit-Reviewer: Michael Ho Gerrit-HasComments: Yes
