GitLab

Currently as part of AhoCorasickNode, we store pointers to other nodes
as part of the edge map and failure and output links. On a 64 bit
machine, the size of a pointer would be 8 bytes, so replacing it with a
4 byte array index yields decreased memory usage.

However doing this also has a drawback. Since we store array indices in
an uint32_t, the maximum size of the trie would be limitied by the
maximum possible value that an uint32_t can store as opposed to
vector<AhoCorasickNode>::max_size().

Also, the current implementation of GetTreeSize ignores any possible
overflow in computing the tree size, which can lead to a DCHECK failures
as well as incorrect results (It's not clear if it can lead to invalid
memory access). Change it to explicitly crash if the computed tree size
overflows and can't be stored in an uint32_t.

On my local machine, this reduces the amount of memory for the
SubstringSetMatcher perf test from ~33 Mb to ~25 Mb.

BUG=974391

Change-Id: Ib2541b514b8993e414891b1f678e590f6292dc98
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/2050099
Commit-Queue: Karan Bhatia <karandeepb@chromium.org>
Reviewed-by: Dominic Battré <battre@chromium.org>
Cr-Commit-Position: refs/heads/master@{#740848}