https://redmine.ruby-lang.org/https://redmine.ruby-lang.org/favicon.ico?17113305112013-12-06T16:14:11ZRuby Issue Tracking SystemRuby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=434512013-12-06T16:14:11Zduerst (Martin Dürst)duerst@it.aoyama.ac.jp
<ul></ul><p>This runs in no time on ruby 2.0.0p247 (2013-06-27) [i386-mingw32] (same patch level!). Can you give more details about your environment?</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=434632013-12-06T23:40:07Zmpelzsherman (Michael Pelz-Sherman)mpelzsherman@gmail.com
<ul></ul><p>duerst (Martin Dürst) wrote:</p>
<blockquote>
<p>This runs in no time on ruby 2.0.0p247 (2013-06-27) [i386-mingw32] (same patch level!). Can you give more details about your environment?</p>
</blockquote>
<p>Model Name: MacBook Pro<br>
Model Identifier: MacBookPro9,1<br>
Processor Name: Intel Core i7<br>
Processor Speed: 2.3 GHz<br>
Number of Processors: 1<br>
Total Number of Cores: 4<br>
L2 Cache (per Core): 256 KB<br>
L3 Cache: 6 MB<br>
Memory: 16 GB<br>
Boot ROM Version: MBP91.00D3.B08<br>
SMC Version (system): 2.1f173<br>
Serial Number (system): C02JP19HF1G3</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=434642013-12-06T23:41:24Zmpelzsherman (Michael Pelz-Sherman)mpelzsherman@gmail.com
<ul></ul><p>Running ruby-2.0.0-p247 [ x86_64 ], installed using RVM.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=434792013-12-07T11:07:29ZAnonymous
<ul></ul><p>Reproduced on trunk:</p>
<p>irb(main):027:0> RUBY_DESCRIPTION<br>
=> "ruby 2.1.0dev (2013-12-07 trunk 44044) [x86_64-darwin13.0]"<br>
irb(main):028:0> Benchmark.measure { Time.parse("12:00 PM " + "f"*30) }.to_s<br>
=> " 4.760000 0.000000 4.760000 ( 4.759983)\n"<br>
irb(main):029:0> Benchmark.measure { Time.parse("12:00 PM " + "f"*31) }.to_s<br>
=> " 7.770000 0.000000 7.770000 ( 7.787989)\n"<br>
irb(main):030:0> Benchmark.measure { Time.parse("12:00 PM " + "f"*32) }.to_s<br>
=> " 12.390000 0.000000 12.390000 ( 12.405786)\n"</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=434872013-12-07T16:48:55Zhsbt (Hiroshi SHIBATA)hsbt@ruby-lang.org
<ul><li><strong>Target version</strong> set to <i>2.1.0</i></li></ul> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435172013-12-08T19:56:18Zphasis68 (Heesob Park)phasis@gmail.com
<ul></ul><p>It can be reproduced on ruby 2.0.0-p247 i386-mingw32.</p>
<p>I modified a test code to extension library free version.</p>
<p>C:\work>ruby -v<br>
ruby 2.0.0p247 (2013-06-27) [i386-mingw32]</p>
<p>C:\work>type test.rb<br>
require 'benchmark'<br>
str = "12:00 PM fffffffffffffffffffffffffffff"<br>
pat=/((?:\d+\s*:\s*\d+(?:\s*:\s*\d+(?:[,.]\d*)?)?|\d+\s<em>h(?:\s</em>\d+m?(?:\s*\d+s?)<br>
?)?)(?:\s*<a>ap</a>)?|\d+\s*<a>ap</a>)(?:\s*((?:gmt|utc?)?[-+]\d<br>
+(?:[,.:]\d+(?::\d+)?)?|[[:alpha:].\s]+(?:standard|daylight)\stime\b|[[:alpha:]]<br>
+(?:\sdst)?\b))?/i<br>
p Benchmark.measure { pat.match(str) }</p>
<p>C:\work>ruby test.rb<br>
#<Benchmark::Tms:0x24a3440 @label="", @real=3.303211, @cstime=0.0, @cutime=0.0,<br>
@stime=0.0, @utime=3.2969999999999997, @total=3.2969999999999997></p>
<p>Interestingly, this issue is not reproduced on irb session or without filename.</p>
<p>C:\work>ruby < test.rb<br>
#<Benchmark::Tms:0x24cf4e0 @label="", @real=0.0, @cstime=0.0, @cutime=0.0, @stim<br>
e=0.0, @utime=0.0, @total=0.0></p>
<p>C:\work>irb<br>
DL is deprecated, please use Fiddle<br>
irb(main):001:0> require 'benchmark'<br>
=> true<br>
irb(main):002:0> str = "12:00 PM fffffffffffffffffffffffffffff"<br>
=> "12:00 PM fffffffffffffffffffffffffffff"<br>
<:].\s]+(?:standard|daylight)\stime\b|[[:alpha:]]+(?:\sdst)?\b))?/i<br>
=> /((?:\d+\s*:\s*\d+(?:\s*:\s*\d+(?:[,.]\d*)?)?|\d+\s<em>h(?:\s</em>\d+m?(?:\s*\d+s?)?<br>
)?)(?:\s*<a>ap</a>)?|\d+\s*<a>ap</a>)(?:\s*((?:gmt|utc?)?[-+]\d+<br>
(?:[,.:]\d+(?::\d+)?)?|[[:alpha:].\s]+(?:standard|daylight)\stime\b|[[:alpha:]]+<br>
(?:\sdst)?\b))?/i<br>
irb(main):004:0> p Benchmark.measure { pat.match(str) }<br>
#<Benchmark::Tms:0x27059a0 @label="", @real=0.0, @cstime=0.0, @cutime=0.0, @stim<br>
e=0.0, @utime=0.0, @total=0.0><br>
=> #<Benchmark::Tms:0x27059a0 @label="", @real=0.0, @cstime=0.0, @cutime=0.0, @s<br>
time=0.0, @utime=0.0, @total=0.0></p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435202013-12-08T21:38:38Zakr (Akira Tanaka)akr@fsij.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Assigned</i></li><li><strong>Assignee</strong> set to <i>tadf (tadayoshi funaba)</i></li></ul><p>I assigned this issue to tadf because the pattern<br>
is written in ext/date/date_parse.c.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435312013-12-09T10:34:59Zphasis68 (Heesob Park)phasis@gmail.com
<ul></ul><p>I think this is an issue of Oniguruma(regular expressions library).</p>
<p>Here is a shortest code of producing this issue.<br>
p /(?:[[:alpha:]]+\s)?/i.match("f"*40)</p>
<p>The [:alpha:] bracket and case ignore flag combination shows bad performance.</p>
<p>The simple workaround is using [a-z] instead of [:alpha:].</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435322013-12-09T10:59:21Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul></ul><p>[[:alpha:]] doesn't equal to [a-z], the former matches unicode alphabet categories.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435332013-12-09T11:14:38Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Assigned</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>This issue was solved with changeset r44086.<br>
Michael, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<p>date_parse.c: get rid of backtrack explosion</p>
<ul>
<li>ext/date/date_parse.c (parse_time): unset case-insensitive flag<br>
for [:alpha:], which already implies both cases, to get rid of<br>
backtrack explosion. <a href="/issues/9221">[ruby-core:58876]</a> [Bug <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: Time.parse performance becomes exponentially worse as string length grows (Closed)" href="https://redmine.ruby-lang.org/issues/9221">#9221</a>]</li>
</ul> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435372013-12-09T11:43:33Zphasis68 (Heesob Park)phasis@gmail.com
<ul></ul><p>I know [[:alpha:]] is not equal to [a-z].<br>
But, it seems that the current time parsing is only for ascii string.</p>
<p>BTW, date_strptime.c has the same regular expression on line 567-572.<br>
It should be modified also.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435522013-12-10T00:20:24Znagachika (Tomoyuki Chikanaga)nagachika00@gmail.com
<ul><li><strong>Status</strong> changed from <i>Closed</i> to <i>Open</i></li><li><strong>Backport</strong> changed from <i>1.9.3: UNKNOWN, 2.0.0: UNKNOWN</i> to <i>1.9.3: REQUIRED, 2.0.0: REQUIRED</i></li></ul><p>Thank you for your notice. I'll re-open this ticket.<br>
And I confirmed ruby_1_9_3 and ruby_2_0_0 have these regular expressions.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435652013-12-10T11:42:04Zheadius (Charles Nutter)headius@headius.com
<ul></ul><p>Also affects JRuby: <a href="https://github.com/jruby/jruby/issues/1319" class="external">https://github.com/jruby/jruby/issues/1319</a></p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=435772013-12-10T23:58:46Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li></ul><p>This issue was solved with changeset r44126.<br>
Michael, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<p>date_strptime.c: get rid of backtrack explosion</p>
<ul>
<li>ext/date/date_strptime.c (date__strptime_internal): unset<br>
case-insensitive flag for [:alpha:], which already implies both<br>
cases, to get rid of backtrack explosion. <a href="/issues/9221">[ruby-core:58984]</a><br>
[Bug <a class="issue tracker-1 status-5 priority-4 priority-default closed" title="Bug: Time.parse performance becomes exponentially worse as string length grows (Closed)" href="https://redmine.ruby-lang.org/issues/9221">#9221</a>]</li>
</ul> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=437862013-12-21T03:50:08Znagachika (Tomoyuki Chikanaga)nagachika00@gmail.com
<ul><li><strong>Backport</strong> changed from <i>1.9.3: REQUIRED, 2.0.0: REQUIRED</i> to <i>1.9.3: REQUIRED, 2.0.0: DONE</i></li></ul><p>r44086 and r44126 are backported to ruby_2_0_0 branch at r44126.</p> Ruby master - Bug #9221: Time.parse performance becomes exponentially worse as string length growshttps://redmine.ruby-lang.org/issues/9221?journal_id=446862014-01-29T05:45:47Zusa (Usaku NAKAMURA)usa@garbagecollect.jp
<ul><li><strong>Backport</strong> changed from <i>1.9.3: REQUIRED, 2.0.0: DONE</i> to <i>1.9.3: DONE, 2.0.0: DONE</i></li></ul><p>backported into ruby_1_9_3 at r44746.</p>