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/suballocator-test.cc:

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

Line 72:   /// Verify that the memory for all of the allocations is writable 
and disjoint by
> 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 
> 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, the
> 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, 
             :   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 

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/suballocator.cc:

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 

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 

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 

Line 106:   /// Whether to expand reservations when needed to fulfil 
> 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 

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 <tarmstr...@cloudera.com>
Gerrit-Reviewer: Jim Apple <jbapple-imp...@apache.org>
Gerrit-Reviewer: Michael Ho
Gerrit-Reviewer: Michael Ho <k...@cloudera.com>
Gerrit-Reviewer: Tim Armstrong <tarmstr...@cloudera.com>
Gerrit-HasComments: Yes

Reply via email to