Re: "Stack overflow in regexp"
On 11 Jul 1999, Jan Vroonhof wrote:
Justin Vallon <vallon(a)mindspring.com> writes:
> I think the (regexp internal fail_stack) stack size can be increased on
> all platforms from 2000 to 20000 at the cost of 16000*4 ~= 64k.
I just had a glance at it too, but isn't the maximum (on a 32 bit machine).
2 * re_max_failures * MAX_FAILURE_ITEMS * 4
Where MAX_FAILURE_ITEMS = 5 * 3 + 5 = 19
thus the cost is about 38 times higher. And on a 64-bit machine it is
about 80 times higher. Which more or less explains why DEC OSF's 2MB
stack gives problems.
Yes. For 32-bit machine, 2000 => 2*2000*19*4 = 304e3. 20000 => 3040e3.
Double for 64-bit ints/pointers. So cost = ~2.736e6 bytes, or ~5.472e6
bytes for 64-bit machine.
If stack allocation is used, the maximum of 2* is typically never reached
(most likely 1024), but the worst case would be 20000*19*4 => 1.52Mb.
Although, that's probably wrong because you can't un-alloca, and the
re-alloca just leaks the old memory, so it could potentially waste quite a
bit of stack space.
I'm still not clear on what the DEC OSF comment is all about, though:
#if defined (MATCH_MAY_ALLOCATE)
/* 4400 was enough to cause a crash on Alpha OSF/1,
whose default stack limit is 2mb. */
int re_max_failures = 20000;
#else
int re_max_failures = 2000;
#endif
Does this apply to the !defined(MATCH_MAY_ALLOCATE) code?
Does anybody know why regexp lets its stack grow exponentially?
Redoubling an array on an overflow yields O(n) behavior for append/push,
at the expense of space.
-Justin
vallon(a)mindspring.com