Use an array of pages for the large arrays....

Use an array of pages for the large arrays.

The large arrays of ints used by the suffix array code sometimes can't be
allocated due to fragmented address space.  Using an array of 'pages' lets
the allocation be satisfied by many smaller allocations.

BUG=none
TEST=none


Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=48547

[jar (doing other things), 2010-05-27 07:34:17]

I noticed one bug, and a few style nits that should be changed.  You should also
probably add the unit test as suggested, and the DCHECK (either of which would
have caught the bug).

In light of the bug, I took the liberty of suggesting some optional changes that
I think would have made it harder to induce the bug.  ...so you can disregard
those changes if you prefer.

http://codereview.chromium.org/2228003/diff/3001/4002
File courgette/third_party/bsdiff_create.cc (right):

http://codereview.chromium.org/2228003/diff/3001/4002#newcode50
courgette/third_party/bsdiff_create.cc:50: T** pages_;
nit: style: members are listed at the end of a private section, which comes
after the public section.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode53
courgette/third_party/bsdiff_create.cc:53: enum {
nit: style: constants are listed near the start of the public or private section
in which they land.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize - 1);
At a minimum, consider adding:
DCHECK_LE(page, page_count_);

You might even make it a CHECK().

http://codereview.chromium.org/2228003/diff/3001/4002#newcode74
courgette/third_party/bsdiff_create.cc:74: size_t page_count = (size + kPageSize
- 1) >> kLogPageSize;
Suggest you use a name that is more distinct from page_count_ such as
requested_pages.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode83
courgette/third_party/bsdiff_create.cc:83: page_count_ = page_count_;
I suspect you meant to do:
page_count_ = page_count;

i.e., slot_value = local_value

This should have been caught in a unit test, as the destructor would usually
leak tremendously.  A DCHECK in the operator[] would also have revealed an
out-of-range access.

Consider adding a unit test that allocated and deallocated a large block of
memory, several times.  For example, allocated 200MB and dealocate it 20 times. 
It should actually run pretty quickly.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode85
courgette/third_party/bsdiff_create.cc:85: for (size_t i = 0; i < page_count;
++i) {
personal style suggestion (not required): Consider using a loop like:
for (page_count_ = 0; page_count_ < page_count; ++page_count_)

With a litle care in your inner loop below, you wont' need to do the above "Make
it safe to call clear() on error path".

http://codereview.chromium.org/2228003/diff/3001/4002#newcode106
courgette/third_party/bsdiff_create.cc:106: }
nit: style: Add macro to prevent unsafe copying.

[sra1, 2010-05-28 06:28:38]

Thanks for the review.  I fixed most issues and added another unit test.

http://codereview.chromium.org/2228003/diff/3001/4002
File courgette/third_party/bsdiff_create.cc (right):

http://codereview.chromium.org/2228003/diff/3001/4002#newcode50
courgette/third_party/bsdiff_create.cc:50: T** pages_;
On 2010/05/27 07:34:18, jar wrote:
> nit: style: members are listed at the end of a private section, which comes
> after the public section.

Done.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize - 1);
On 2010/05/27 07:34:18, jar wrote:
> At a minimum, consider adding:
> DCHECK_LE(page, page_count_);
> 
> You might even make it a CHECK().

I tried a DCHECK but it caused a 2x perf hit on optimized code.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode74
courgette/third_party/bsdiff_create.cc:74: size_t page_count = (size + kPageSize
- 1) >> kLogPageSize;
On 2010/05/27 07:34:18, jar wrote:
> Suggest you use a name that is more distinct from page_count_ such as
> requested_pages.

Done.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode85
courgette/third_party/bsdiff_create.cc:85: for (size_t i = 0; i < page_count;
++i) {
On 2010/05/27 07:34:18, jar wrote:
> personal style suggestion (not required): Consider using a loop like:
> for (page_count_ = 0; page_count_ < page_count; ++page_count_)
> 
> With a litle care in your inner loop below, you wont' need to do the above
"Make
> it safe to call clear() on error path".

Done.

http://codereview.chromium.org/2228003/diff/3001/4002#newcode106
courgette/third_party/bsdiff_create.cc:106: }
On 2010/05/27 07:34:18, jar wrote:
> nit: style: Add macro to prevent unsafe copying.

Done.

[jar (doing other things), 2010-05-28 06:45:06]

I'd still argue for the DCHECK.  See notes below.

Thanks for making the other changes. LGTM.

http://codereview.chromium.org/2228003/diff/3001/4002
File courgette/third_party/bsdiff_create.cc (right):

http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize - 1);
hmmm... a DCHECK generates zero code in a production (optmizied) build, so I
suspect your assertion of a perf reduction is mistaken.

On 2010/05/28 06:28:38, sra1 wrote:
> On 2010/05/27 07:34:18, jar wrote:
> > At a minimum, consider adding:
> > DCHECK_LE(page, page_count_);
> > 
> > You might even make it a CHECK().
> 
> I tried a DCHECK but it caused a 2x perf hit on optimized code.
>

[sra1, 2010-05-29 00:50:28]

Thanks for the review.  Sumbitted.

http://codereview.chromium.org/2228003/diff/3001/4002
File courgette/third_party/bsdiff_create.cc (right):

http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize - 1);
On 2010/05/28 06:45:06, jar wrote:
> hmmm... a DCHECK generates zero code in a production (optmizied) build, so I
> suspect your assertion of a perf reduction is mistaken.
> 
> On 2010/05/28 06:28:38, sra1 wrote:
> > On 2010/05/27 07:34:18, jar wrote:
> > > At a minimum, consider adding:
> > > DCHECK_LE(page, page_count_);
> > > 
> > > You might even make it a CHECK().
> > 
> > I tried a DCHECK but it caused a 2x perf hit on optimized code.
> > 
> 
> 

I was surprised, but I measured 2x.

DCHECK(foo); expands to

while (false && (foo)) logging::LogMessage(__FILE__,__LINE).stream();

This expansion permits e.g. DCHECK(foo) << "ouch";


While eventually the compiler will eliminate the zero-trip while-loop, the
presence of the code in the function causes the compiler (VS2005, at least) to
decide not to inline the function.  (LogMessage is a class, so there is a
temporary object 'allocation', the explicit constructor call and an implicit
paired destructor call. An apparent loop containing three function calls makes
the inlining candidate look too big.)  Different command-line flags or a
different compiler might do better.

[jar (doing other things), 2010-05-29 01:43:40]

http://codereview.chromium.org/2228003/diff/3001/4002
File courgette/third_party/bsdiff_create.cc (right):

http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize - 1);
Apparently there are 3 distinct builds.
a) Debug (DCHECK is active)
b) Release (DHECK is dynamically controlled by command line)
c) Official (DCHECK is removed completely)

Also note that the Official builds take about 3 hours of linker time to
optimize.

Where did you run your benchmark?




On 2010/05/29 00:50:28, sra1 wrote:
> On 2010/05/28 06:45:06, jar wrote:
> > hmmm... a DCHECK generates zero code in a production (optmizied) build, so I
> > suspect your assertion of a perf reduction is mistaken.
> > 
> > On 2010/05/28 06:28:38, sra1 wrote:
> > > On 2010/05/27 07:34:18, jar wrote:
> > > > At a minimum, consider adding:
> > > > DCHECK_LE(page, page_count_);
> > > > 
> > > > You might even make it a CHECK().
> > > 
> > > I tried a DCHECK but it caused a 2x perf hit on optimized code.
> > > 
> > 
> > 
> 
> I was surprised, but I measured 2x.
> 
> DCHECK(foo); expands to
> 
> while (false && (foo)) logging::LogMessage(__FILE__,__LINE).stream();
> 
> This expansion permits e.g. DCHECK(foo) << "ouch";
> 
> 
> While eventually the compiler will eliminate the zero-trip while-loop, the
> presence of the code in the function causes the compiler (VS2005, at least) to
> decide not to inline the function.  (LogMessage is a class, so there is a
> temporary object 'allocation', the explicit constructor call and an implicit
> paired destructor call. An apparent loop containing three function calls makes
> the inlining candidate look too big.)  Different command-line flags or a
> different compiler might do better.
>

[sra1, 2010-05-30 00:38:24]

On 2010/05/29 01:43:40, jar wrote:
> http://codereview.chromium.org/2228003/diff/3001/4002
> File courgette/third_party/bsdiff_create.cc (right):
> 
> http://codereview.chromium.org/2228003/diff/3001/4002#newcode66
> courgette/third_party/bsdiff_create.cc:66: size_t offset = i & (kPageSize -
1);
> Apparently there are 3 distinct builds.
> a) Debug (DCHECK is active)
> b) Release (DHECK is dynamically controlled by command line)
> c) Official (DCHECK is removed completely)

Thanks for the clarification.  I was running the Release build, unware* that
this is not representative of the released product.
If I follow the instructions to do an 'Official' build, the DCHECK is completely
removed, which I verified by disassembling the .exe

*It is hard to tell that there is something better than 'Release' without tribal
knowledge.  The configuration is called 'Release' and the other options visible
in Visual studio are Debug and Purify, so I thought that Release was the most
optimized.  It would be helpful if Official build was another configuration that
co-existed with the others, but as it stands for Visual Studio development, you
have to exit VS, set environment variables, rebuild the .sln file and then do a
clean build of the 'Release' configuration.

> 
> Also note that the Official builds take about 3 hours of linker time to
> optimize.
> 
> Where did you run your benchmark?
> 
> 
> 
> 
> On 2010/05/29 00:50:28, sra1 wrote:
> > On 2010/05/28 06:45:06, jar wrote:
> > > hmmm... a DCHECK generates zero code in a production (optmizied) build, so
I
> > > suspect your assertion of a perf reduction is mistaken.
> > > 
> > > On 2010/05/28 06:28:38, sra1 wrote:
> > > > On 2010/05/27 07:34:18, jar wrote:
> > > > > At a minimum, consider adding:
> > > > > DCHECK_LE(page, page_count_);
> > > > > 
> > > > > You might even make it a CHECK().
> > > > 
> > > > I tried a DCHECK but it caused a 2x perf hit on optimized code.
> > > > 
> > > 
> > > 
> > 
> > I was surprised, but I measured 2x.
> > 
> > DCHECK(foo); expands to
> > 
> > while (false && (foo)) logging::LogMessage(__FILE__,__LINE).stream();
> > 
> > This expansion permits e.g. DCHECK(foo) << "ouch";
> > 
> > 
> > While eventually the compiler will eliminate the zero-trip while-loop, the
> > presence of the code in the function causes the compiler (VS2005, at least)
to
> > decide not to inline the function.  (LogMessage is a class, so there is a
> > temporary object 'allocation', the explicit constructor call and an implicit
> > paired destructor call. An apparent loop containing three function calls
makes
> > the inlining candidate look too big.)  Different command-line flags or a
> > different compiler might do better.
> >