impala-reviews mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Tim Armstrong (Code Review)" <>
Subject [Impala-ASF-CR] IMPALA-3200: Implement suballocator for splitting buffers
Date Fri, 02 Dec 2016 01:25:22 GMT
Tim Armstrong has posted comments on this change.

Change subject: IMPALA-3200: Implement suballocator for splitting buffers

Patch Set 4:

Commit Message:

PS4, Line 13:  buddy allocation
> Though the number of elements in HTs is a power of two, the size of the all
That's true.

IMO we can cross that bridge if we come to it. I don't think we'd want to increase the size
of hash table buckets. I think shrinking them further is an outside possibility.

Right now this is one of multiple tasks required to switch over to the new buffer pool so
I'd really like to get this code clean and functional for the current hash table case then
move onto other things.

Choosing a # of buckets based on the memory being a power of two size might make more sense
than trying to implement a general-purpose memory allocator. The buffer pool is also oriented
around power-of-two buffers so fragmentation would be problem for large non-power-of-two hash
tables regardless of the suballocator's behaviour.
File be/src/bufferpool/

PS5, Line 72: allocations
> "Suballocations", here and below

Line 72:   /// Verify that the memory for all of the allocations is writable and disjoint
> Maybe replace "Verify" with "ASSERT", for clarity?

PS5, Line 77: list
> vector

PS5, Line 77: clear
> call std::vector::clear() after the for loop to prevent UB if a caller uses

Line 85:   ObjectPool obj_pool_;
> Each of these member variables could use an explanation about why it is her

Line 101:   ASSERT_OK(pool.RegisterClient("client", &global_reservation_, profile(), &client));
> The ASSERTs in this file could generally benefit from more info in the "<<"
I added debug strings and parameters in some places. It's kind of hard to anticipate what
will actually be useful but I added some of the obvious things.

Line 111:     allocs.emplace_back();
> I generally think of ASSERT as being for failures in which the test should 
My perspective is that EXPECT is only worth using when it's independent of the remainder of
the test. What I've seen a lot of the time with EXPECT in other tests is that if there's a
bug, then later parts of the tests go off into the weeds and crash.

In this case there's no way to recover without adding extra untested code that would pop the
last allocation off the back.

Line 116: 
> Can we allocate 0 bytes here?
I added a couple of separate tests to test edge cases (-1,0,MAX+1).

Line 127:   EXPECT_EQ(global_reservation_.GetUsedReservation(), allocated_mem);
> call FreeAllocations?

PS5, Line 147: EST
> It might also be good to test edge cases: (1 << i) - 1
I added some more sizes in.

Line 159:     memset(alloc->data(), 0, alloc->len()); // Check memory is writable.
> Add note that ASAN performs this check.
ASAN helps here, but we detect a lot of problems without ASAN, e.g. if the memory is not mapped.

Line 180: 
> either "NUM_ALLOCS" or "total_mem", above

PS5, Line 184: // Start with allocations smaller than the page.
             :   int64_t curr_alloc_size = TEST_BUFFER_LEN / 8;
> Could be more readable as a for loop

Line 188:     shuffle(allocs.begin(), allocs.end(), rng_);
> Can this be range-based, like the loop on 205?

Line 197:     // Test that the memory isn't fragmented more than expected. In the worst case,
> Can you add a comment explaining why should they never require more than an
I added a fairly lengthy explanation. Hopefully it's sufficiently clear - it's kind of hard
to explain intuitively.

Line 206:   for (unique_ptr<Suballocation>& alloc : allocs) {
> call FreeAllocations()

PS5, Line 215: TEST_F(SuballocatorTest, NeverExpandReservation) {
             :   const int64_t TOTAL_MEM = TEST_BUFFER_LEN * 100;
             :   global_reservation_.InitRootTracker(NULL, TOTAL_MEM);
             :   BufferPool pool(TEST_BUFFER_LEN, TOTAL_MEM);
             :   ReservationTracker reservation;
             :   reservation.InitChildTracker(NULL, &global_reservation_, NULL, TOTAL_MEM);
             :   BufferPool::Client client;
             :   ASSERT_OK(pool.RegisterClient("client", &reservation, profile(), &client));
> This section seems like a good candidate for a member function, as it appea
I tried to reduce the amount of boilerplate a bit by factoring out some common functions.
I like having the setup logic explicit at the top of the test, so tried to avoid overabstracting
to the point of obscuring what was actually happening.

Line 263: 
> This tests only correctness, not anything about fragmentation, right?

Line 289: 
> const

PS5, Line 290: 
> The first parameter below is 2 - that's the mean, right, so the average is 
The documentation for lognormal_distribution is misleading/wrong. Empirically the mean is
between 11.5 and 12 with m=2 n=1 (I wrote a short program to compute it).

PS5, Line 334: (
> I didn't see this in the header file. I'd suggest that this expectation sho

Line 336:     ASSERT_EQ(0, reinterpret_cast<uint64_t>(alloc->data()) % 8);
> std::iota
I tried it but it was less readable in practice because the loop bounds aren't obviously the
same as the verification below.
File be/src/bufferpool/

Line 144:     int64_t child_len = free_node->len_ / 2;
> Does not look done. Maybe some changes were left out of PS5 by mistake?
Hm not sure, fixed now.
File be/src/bufferpool/suballocator.h:

Line 37: };
> Maybe typedef liberally? impala::ExpansionStrategy strikes me as potentiall

PS4, Line 127: must
> Looks missing?
Ah, forgot to comment that I added the explanation to Allocate().

Line 171:   Suballocation* prev_free_;
> std::unique_ptr to me means that all other references are statically scoped
unique_ptr really only enforces unique ownership, not any kind of static scoping. unique_ptr
+ raw pointer for non-owning references is the right pattern when the unique_ptr reference
always outlives the non-owning reference. 

Static scope is sufficient but not necessary for that to be true. It's also a happy case where
you can avoid use-after-free automatically.

shared_ptr I think only makes sense when you have n > 1 references and it is impossible
(or at least difficult) to determine which will be the longest-lived reference.

We do this elsewhere in the code with scoped_ptr/unique_ptr - e.g. passing around and storing
raw pointers to the RuntimeState that's owned by PlanFragmentExecutor.
File be/src/bufferpool/suballocator.h:

PS5, Line 94: 
            :   std::unique_ptr<Suballocation> Co
> not anymore
I'm not sure I understand this - internally the allocations are all powers-of-two.

Line 106:   /// Whether to expand reservations when needed to fulfil allocations.
> Deserves a comment

PS5, Line 202: 
> Since only unused Suballocations need these, they can be "intrusive" - you 
Seems like a valid optimisation but not sure it's worth adding so long as we're only dealing
with larger allocations. Probably if memory overhead was a big concern I'd redesign more drastically
to avoid storing all of this stuff per allocation.

To view, visit
To unsubscribe, visit

Gerrit-MessageType: comment
Gerrit-Change-Id: I8bfe0e429f67ad273f7c7d0816703a9e6c3da788
Gerrit-PatchSet: 4
Gerrit-Project: Impala-ASF
Gerrit-Branch: master
Gerrit-Owner: Tim Armstrong <>
Gerrit-Reviewer: Jim Apple <>
Gerrit-Reviewer: Michael Ho
Gerrit-Reviewer: Michael Ho <>
Gerrit-Reviewer: Tim Armstrong <>
Gerrit-HasComments: Yes

View raw message