Mailing-List: contact reviews-help@impala.incubator.apache.org; run by ezmlm
Precedence: bulk
Message-Id: <201612020125.uB21PMrC010265@ip-10-146-233-104.ec2.internal>
Date: Fri, 2 Dec 2016 01:25:22 +0000
From: "Tim Armstrong (Code Review)" <gerrit@cloudera.org>
To: impala-cr@cloudera.com, reviews@impala.incubator.apache.org
CC: Jim Apple <jbapple-impala@apache.org>, Michael Ho <kwho@cloudera.com>
Reply-To: tarmstrong@cloudera.com
Subject: =?UTF-8?Q?=5BImpala-ASF-CR=5D_IMPALA-3200=3A_Implement_suballocator_for_splitting_buffers=0A?=
In-Reply-To: <gerrit.1476341621000.I8bfe0e429f67ad273f7c7d0816703a9e6c3da788@gerrit.cloudera.org>
References: <gerrit.1476341621000.I8bfe0e429f67ad273f7c7d0816703a9e6c3da788@gerrit.cloudera.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Content-Disposition: inline
User-Agent: Gerrit/2.12.2
archived-at: Fri, 02 Dec 2016 01:26:31 -0000

Tim Armstrong has posted comments on this change.

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


Patch Set 4:

(30 comments)

http://gerrit.cloudera.org:8080/#/c/4715/4//COMMIT_MSG
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.


http://gerrit.cloudera.org:8080/#/c/4715/5/be/src/bufferpool/suballocator-test.cc
File be/src/bufferpool/suballocator-test.cc:

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


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


PS5, Line 77: list
> vector
Done


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


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


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?
Done


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
Done


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
Done


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


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()
Done


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?
Correct.


Line 289: 
> const
Done


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
Done


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.


http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/bufferpool/suballocator.cc
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.


http://gerrit.cloudera.org:8080/#/c/4715/4/be/src/bufferpool/suballocator.h
File be/src/bufferpool/suballocator.h:

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


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.


http://gerrit.cloudera.org:8080/#/c/4715/5/be/src/bufferpool/suballocator.h
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
Done


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