Re: tsearch in core patch, for inclusion

"Florian G. Pflug" <fgp(at)phlo(dot)org> writes:
> Markus Schiltknecht wrote:
>> I didn't find hard facts about runtime complexity of LALR,
>> though (pointers are very welcome).

> a) and b) should be O(1). Processing one token pushes at most one state
> onto the stack, so overall no more than N stats can be popped off again,
> making the whole algorithm O(N) with N being the number of tokens of the
> input stream.

Yeah. I was concerned about the costs involved in trying to pack the
state tables, but it appears that that cost is all paid when the grammar
is compiled --- looking into gram.c, it appears the inner loop contains
just simple array lookups. Still, bloating of the state tables is
something we ought to pay attention to, because there's a distributed
cost once they no longer fit in a processor's L1 cache. On my machine
"size gram.o" is over 360K already ...

regards, tom lane