code review 1174041: re2: memory diet

re2: memory diet

Cut unnecessary fields from Regexp and order to align better.
Combine smallsub and sub into one field.
Changes sizeof(Regexp) - a single node - from 104 to 40 bytes.

Use sorted array as permanent representation
of character class, avoiding the bloat of STL set<>.

Combined with CL 1129043, cuts storage used
by a typical RE2 object by about 60%.

[rsc, 2010-05-10 00:33:18]

Hello r (cc: re2-dev@googlegroups.com),

I'd like you to review this change.

[r, 2010-05-10 16:26:30]

http://codereview.appspot.com/1174041/diff/2001/3004
File re2/regexp.cc (right):

http://codereview.appspot.com/1174041/diff/2001/3004#newcode656
re2/regexp.cc:656: else {
inconsistent braces.

http://codereview.appspot.com/1174041/diff/2001/3004#newcode677
re2/regexp.cc:677: else  // rr[m].lo <= r && r <= rr[m].hi
and again

http://codereview.appspot.com/1174041/diff/2001/3005
File re2/regexp.h (right):

http://codereview.appspot.com/1174041/diff/2001/3005#newcode471
re2/regexp.h:471: if (n < 0 || (uint16)n != n)
C cast

http://codereview.appspot.com/1174041/diff/2001/3005#newcode509
re2/regexp.h:509: // are responsible for not exceeding this limit.
you're adding fragility and distributing the defences, which is a bit scary. is
there a cheap (in memory and cpu) way of at least advertising the
responsibility.

http://codereview.appspot.com/1174041/diff/2001/3005#newcode542
re2/regexp.h:542: void *the_union_[2];  // as big as any other element, for
memset
odd choice. why not char the_union[sizeof(CharClass)] ?

http://codereview.appspot.com/1174041/diff/2001/3007
File re2/testing/charclass_test.cc (right):

http://codereview.appspot.com/1174041/diff/2001/3007#newcode100
re2/testing/charclass_test.cc:100: } else
i put braces around the else when there are braces around the if.
when the disparity is this large, i also reverse the condition to put the little
guy first. makes it easier to see.

[rsc, 2010-05-10 22:37:12]

All done.

On Mon, May 10, 2010 at 09:26,  <r@golang.org> wrote:
>
> http://codereview.appspot.com/1174041/diff/2001/3004
> File re2/regexp.cc (right):
>
> http://codereview.appspot.com/1174041/diff/2001/3004#newcode656
> re2/regexp.cc:656: else {
> inconsistent braces.
>
> http://codereview.appspot.com/1174041/diff/2001/3004#newcode677
> re2/regexp.cc:677: else  // rr[m].lo <= r && r <= rr[m].hi
> and again
>
> http://codereview.appspot.com/1174041/diff/2001/3005
> File re2/regexp.h (right):
>
> http://codereview.appspot.com/1174041/diff/2001/3005#newcode471
> re2/regexp.h:471: if (n < 0 || (uint16)n != n)
> C cast
>
> http://codereview.appspot.com/1174041/diff/2001/3005#newcode509
> re2/regexp.h:509: // are responsible for not exceeding this limit.
> you're adding fragility and distributing the defences, which is a bit
> scary. is there a cheap (in memory and cpu) way of at least advertising
> the responsibility.

Inside the class there's not much I can do to stop code from
editing the fields directly, but nothing did anyway: they all called the
private method AllocSub which now has a LOG(FATAL) if called
with too big an n.  The requirement only affects the internal interface.
The public entry points - Concat, Alternate, and the parser - all
gracefully handle larger operations by building a two-level tree
instead of a single node.

I've changed the comment to

  // Concat and Alternate handle larger numbers of subexpressions
  // by building concatenation or alternation trees.
  // Other routines should call Concat or Alternate instead of
  // filling in sub() by hand.

> http://codereview.appspot.com/1174041/diff/2001/3005#newcode542
> re2/regexp.h:542: void *the_union_[2];  // as big as any other element,
> for memset
> odd choice. why not char the_union[sizeof(CharClass)] ?

The union has a few two-int structs and a few two-pointer structs.
This is trying to be the same size as the two-pointer structs.
There's no easy out here because the union is anonymous.

Russ

[r2, 2010-05-10 22:56:39]

LGTM

On May 10, 2010, at 3:37 PM, Russ Cox wrote:

> All done.
>
> On Mon, May 10, 2010 at 09:26,  <r@golang.org> wrote:
>>
>> http://codereview.appspot.com/1174041/diff/2001/3004
>> File re2/regexp.cc (right):
>>
>> http://codereview.appspot.com/1174041/diff/2001/3004#newcode656
>> re2/regexp.cc:656: else {
>> inconsistent braces.
>>
>> http://codereview.appspot.com/1174041/diff/2001/3004#newcode677
>> re2/regexp.cc:677: else  // rr[m].lo <= r && r <= rr[m].hi
>> and again
>>
>> http://codereview.appspot.com/1174041/diff/2001/3005
>> File re2/regexp.h (right):
>>
>> http://codereview.appspot.com/1174041/diff/2001/3005#newcode471
>> re2/regexp.h:471: if (n < 0 || (uint16)n != n)
>> C cast
>>
>> http://codereview.appspot.com/1174041/diff/2001/3005#newcode509
>> re2/regexp.h:509: // are responsible for not exceeding this limit.
>> you're adding fragility and distributing the defences, which is a bit
>> scary. is there a cheap (in memory and cpu) way of at least  
>> advertising
>> the responsibility.
>
> Inside the class there's not much I can do to stop code from
> editing the fields directly, but nothing did anyway: they all called  
> the
> private method AllocSub which now has a LOG(FATAL) if called
> with too big an n.  The requirement only affects the internal  
> interface.
> The public entry points - Concat, Alternate, and the parser - all
> gracefully handle larger operations by building a two-level tree
> instead of a single node.
>
> I've changed the comment to
>
>  // Concat and Alternate handle larger numbers of subexpressions
>  // by building concatenation or alternation trees.
>  // Other routines should call Concat or Alternate instead of
>  // filling in sub() by hand.
>
>> http://codereview.appspot.com/1174041/diff/2001/3005#newcode542
>> re2/regexp.h:542: void *the_union_[2];  // as big as any other  
>> element,
>> for memset
>> odd choice. why not char the_union[sizeof(CharClass)] ?
>
> The union has a few two-int structs and a few two-pointer structs.
> This is trying to be the same size as the two-pointer structs.
> There's no easy out here because the union is anonymous.
>
> Russ

[rsc, 2010-05-10 23:03:42]

*** Submitted as http://code.google.com/p/re2/source/detail?r=8671a31359c3 ***

re2: memory diet

Cut unnecessary fields from Regexp and order to align better.
Combine smallsub and sub into one field.
Changes sizeof(Regexp) - a single node - from 104 to 40 bytes.

Use sorted array as permanent representation
of character class, avoiding the bloat of STL set<>.

Combined with CL 1129043, cuts storage used
by a typical RE2 object by about 60%.

R=r
CC=re2-dev
http://codereview.appspot.com/1174041