From: Robert Klemme <shortcutter@...>
Date: 2010-01-25T23:03:43+09:00
Subject: [ruby-core:27802] Re: [Bug #2644] memory over-allocation with regexp

2010/1/25 Greg Hazel <redmine@ruby-lang.org>:
> Bug #2644: memory over-allocation with regexp
> http://redmine.ruby-lang.org/issues/show/2644
>
> Author: Greg Hazel
> Status: Open, Priority: Normal
> ruby -v: ruby 1.8.7 (2009-06-12 patchlevel 174) [x86_64-linux]
>
> Using a simple regular expression ruby allocates far too much memory, and can stack overflow.
>
> Code:
> p 1
> s = "2" + (" " * 84149170)
> p 2
> s.match(/(\d) (.*)/)
> p 3
>
> Output:
> 1
> 2
> hmm.rb:4:in `match': Stack overflow in regexp matcher: /(\d) (.*)/ (RegexpError)
> � � � �from hmm.rb:4
>
> Stack overflow is not the worst of it. It's actually trying to allocate very large amounts of memory. Here is the output of REE, which prints when malloc tries to grab a lot:
>
> 1
> 2
> tcmalloc: large alloc 1090519040 bytes == 0x49867000 @
> tcmalloc: large alloc 2181038080 bytes == 0x8aa67000 @
> tcmalloc: large alloc 18446744072140881920 bytes == (nil) @
> tcmalloc: large alloc 4362076160 bytes == (nil) @
> hmm.rb:4:in `match': Stack overflow in regexp matcher: /(\d) (.*)/ (RegexpError)
> � � � �from hmm.rb:4
>
> External observation of processes show that this is memory over-allocation occurs across normal builds of 1.8.6, 1.8.7 and even 1.9.1
>
> (Before you say "this is just a problem with regexp in general!", I tested the same thing on python and perl. Both work satisfactorily with even larger strings.)

Question is how much the fix costs and how realistic this is.  Even in
case there is not a fix, here's an easy workaround for the regular
expression you presented: avoid backtracking through greediness (works
on 1.9 and JRuby only):

15:00:28 Temp$ allruby match-break.rb
CYGWIN_NT-5.1 padrklemme1 1.7.1(0.218/5/3) 2009-12-07 11:48 i686 Cygwin
========================================
ruby 1.8.7 (2008-08-11 patchlevel 72) [i386-cygwin]
match-break.rb:4: nested *?+ in regexp: /(\d) (.*+)/
========================================
ruby 1.9.1p376 (2009-12-07 revision 26041) [i386-cygwin]
1
2
3
========================================
jruby 1.4.0 (ruby 1.8.7 patchlevel 174) (2009-11-02 69fbfa3) (Java
HotSpot(TM) Client VM 1.6.0_17) [x86-java]
1
2
3
15:01:13 Temp$ cat match-break.rb
p 1
s = "2" + (" " * 84149170)
p 2
s.match(/(\d) (.*+)/)
p 3
15:01:18 Temp$

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/