code review 1129043: re2: memory diet part 2

re2: memory diet part 2

Change program representation from Inst* graph
with forwarding pointers to contiguous array of Inst
with forwarding indices.  Cuts sizeof(Inst) from 24 to 8 bytes,
fewer allocated objects, presumably better cache locality.

The SparseArray<Inst*> would now be SparseArray<int>
except that the instruction number was always the array index,
so the value is redundant.  Use SparseSets instead, saving 60%
of the storage footprint due to SparseArrays.

Convert all back ends to use new program representation.

Free unused storage at end of IsOnePass (good for ~30%).

Build with -DNDEBUG by default, to disable DCHECKs.
Add obj/dbg/* target to Makefile to build in debug mode.

[rsc, 2010-05-10 00:32:45]

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

I'd like you to review this change.

[r, 2010-05-10 16:33:10]

LGTM

http://codereview.appspot.com/1129043/diff/2001/3008
File re2/prog.h (right):

http://codereview.appspot.com/1129043/diff/2001/3008#newcode87
re2/prog.h:87: // Constructors per opcode
are these really constructors?

http://codereview.appspot.com/1129043/diff/2001/3008#newcode154
re2/prog.h:154: uint8 foldcase_; //   convert A-Z to a-z before checking range.
ascii only?

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

On Mon, May 10, 2010 at 09:33,  <r@golang.org> wrote:
> LGTM

> http://codereview.appspot.com/1129043/diff/2001/3008#newcode87
> re2/prog.h:87: // Constructors per opcode
> are these really constructors?

Changed to Initializers.

> http://codereview.appspot.com/1129043/diff/2001/3008#newcode154
> re2/prog.h:154: uint8 foldcase_; //   convert A-Z to a-z before checking
> range.
> ascii only?

Yes.  ASCII case-insensitive is common enough to special case
during compilation (already in before this CL).  Unicode is still
handled correctly; there's just a special case to recognize when
the char class is no more than ASCII case folding in disguise.

[rsc, 2010-05-10 23:35:54]

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

re2: memory diet part 2

Change program representation from Inst* graph
with forwarding pointers to contiguous array of Inst
with forwarding indices.  Cuts sizeof(Inst) from 24 to 8 bytes,
fewer allocated objects, presumably better cache locality.

The SparseArray<Inst*> would now be SparseArray<int>
except that the instruction number was always the array index,
so the value is redundant.  Use SparseSets instead, saving 60%
of the storage footprint due to SparseArrays.

Convert all back ends to use new program representation.

Free unused storage at end of IsOnePass (good for ~30%).

Build with -DNDEBUG by default, to disable DCHECKs.
Add obj/dbg/* target to Makefile to build in debug mode.

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