To LUGNET HomepageTo LUGNET News HomepageTo LUGNET Guide Homepage
 Help on Searching
 
Post new message to lugnet.admin.generalOpen lugnet.admin.general in your NNTP NewsreaderTo LUGNET News Traffic PageSign In (Members)
 Administrative / General / 8480
8479  |  8481
Subject: 
Re: posting weirdness
Newsgroups: 
lugnet.admin.general
Date: 
Sun, 17 Dec 2000 16:21:10 GMT
Viewed: 
182 times
  
In lugnet.admin.general, Larry Pieniazek writes:
No prob. I posted what I wanted to post without the spoiler. Something *is*
broken, then?

Was, ya.

Something about it is chewing up tons and tons
of CPU.  How many whitespace lines are you putting in?

About a screen and a half worth. Haven't people done spoilers lately???

I was using a regex involving \n\s* which compiled into a nondeterministic
finite-state automata in Perl 5.004 and 5.005.  Perl 5.6 is smart enough to
compile it into a deterministic finite-state automata (essentially realising
that \n is part of the \s character class and avoiding a deadly decision tree
trap that results in O(2^n) exponential performance in the NFA case).

The jist of it is that one or two or three newlines in a row chewed up a
millionth of a second of CPU, but twenty newlines in a row chewed up many
seconds of CPU.  A screen and a half worth would want to chew up an hour of
CPU, and two screens worth would try to chew up about two months of CPU.

To fix, I changed the regex so to one that has O(n) performance instead of
O(2^n) performance (where n is the number of newlines in a row).  Thus, now,
even several pages of newlines still only chew up something on the order of
a millionth of a second of CPU.

I may have other similar regex nasties lurking around (for example in the
news-mail gateway).  I'm going to sweep-scan for those now.

--Todd



Message is in Reply To:
  Re: posting weirdness
 
(...) No prob. I posted what I wanted to post without the spoiler. Something *is* broken, then? (...) About a screen and a half worth. Haven't people done spoilers lately??? (...) ++Lar (23 years ago, 17-Dec-00, to lugnet.admin.general)

8 Messages in This Thread:


Entire Thread on One Page:
Nested:  All | Brief | Compact | Dots
Linear:  All | Brief | Compact
    

Custom Search

©2005 LUGNET. All rights reserved. - hosted by steinbruch.info GbR