Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Re: regex on gigabyte string

by dave_the_m (Parson)
on Jan 26, 2013 at 17:46 UTC ( #1015521=note: print w/ replies, xml ) Need Help??


in reply to regex on gigabyte string

The regex engine is largely 32-bit; in particular, the indices of captures within a string are stored as 32-bit signed values, so they can't do captures more than 2Gb into a string.

Dave.


Comment on Re: regex on gigabyte string
Re^2: regex on gigabyte string (31 bits)
by tye (Cardinal) on Jan 26, 2013 at 19:11 UTC

    Worse than that, I've seen tools explicitly dump something like (...)*? in a regex as something very close to (...){0,32766}?, because repetition only supported 15 bits, not 32, at least in some cases (but maybe that isn't true of modern versions of Perl). But it also seemed like those tools didn't always do such. So I'm not sure how often that limitation applies.

    But it is easy to find the breaking point for this particular regex:

    $ perl -del DB<1> x 0+( () = join('','<c>','x'x(1<<30),'</c>') =~ m{<c.*?/c>}g ) 0 1 DB<2> x 0+( () = join('','<c>','x'x(1<<31),'</c>') =~ m{<c.*?/c>}g ) 0 0 DB<3> x 0+( () = join('','<c>','x'x((1<<31)-8),'</c>') =~ m{<c.*?/c> +}g ) 0 1 DB<4> x 0+( () = join('','<c>','x'x((1<<31)-7),'</c>') =~ m{<c.*?/c> +}g ) 0 0

    So (my version of) Perl can't deal with a capture string of more than 2**31-1 characters. And:

    $ perl -del DB<2> x 0+( () = join('',('<c>','x'x((1<<30)-10),'</c>')x2) =~ m{<c. +*?/c>}g ) 0 2 DB<1> x 0+( () = join('',('<c>','x'x((1<<30)-10),'</c>')x3) =~ m{<c. +*?/c>}g ) 0 0

    Surprisingly, it fails to even find the first match if there is a match beyond the 2**31-1 character position? Even trying to iterate to that point doesn't really help (perhaps .*? backtracks?):

    $ perl -del DB<1> $x = join('',('<c>','x'x((1<<30)-10),'</c>')x2); while( $x =~ +m{<c.*?/c>}g ) { print pos($x), $/ } 1073741821 2147483642 DB<1> $x = join('',('<c>','x'x((1<<30)-10),'</c>')x3); while( $x =~ +m{<c.*?/c>}g ) { print pos($x), $/ } DB<2>

    So one needs to deal with the string in reasonably-sized chunks. Which makes me wonder which XML-parsing modules manage to get that right. Their test suites should include a tag with a 4GB attribute value (with an escaped character at the end). :)

    - tye        

Re^2: regex on gigabyte string
by focusonz (Initiate) on Jan 26, 2013 at 19:15 UTC

    There you go! That is the shortcoming.

    keywords: PERL 64bit(x54)and 32bit(x86) MAXIMUM STRING SIZE REGEX ENGINE 2GB per dave_the_m and focusonz test

    keywords: PERL MAXIMUM STRING SIZE 4GB 32bit(x86) ALSO IS WINDOWS X86 LIMIT

    keywords: PERL MAXIMUM STRING SIZE 16GB 64bit(x64) ALSO IS Windows 7 Home Premium X64 LIMIT

    See http://msdn.microsoft.com/en-us/library/windows/desktop/aa366778%28v=vs.85%29.aspx#physical_memory_limits_windows_7

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1015521]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (7)
As of 2014-09-30 23:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (385 votes), past polls