82054 - FindInReadable is O(m*n)

Status: NEW

(Core :: XPCOM, defect, P3)

Description

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

As the comment in nsReadableUtils.h says, FindInReadable is potentially O(N*M)
since it just tests for a match at each point along the segment.  I started
digging around in nsReadableUtils.cpp today to try to implement
CaseInsensitiveRFindInReadable, got distracted (and discouraged since the best
way to do what I want is to implement reverse iterators, which isn't something
that could be done in a few hours), and ended up hacking on this for a bit (and
a bit longer than I intended).  I'm sure there's a better approach, but I did
come up with something.  I'm not sure whether this is something we'd want.  If
it is, it needs a lot more testing...

Anyway, I'll stick the patch on this bug.  Any thoughts?

Comment 1

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: algorithm I came up with (I should really look for a better one...)

Comment 2

[Chris Waterson]

I would guess that most of the time, we search for small substrings (four
characters or less) in small strings (64 characters or less). In this case, I
would guess that setting up a DFA to do the search may well dwarf the cost of
doing the search itself, and would be beaten by brute force.

Does this patch have any noticable negative effect on the gross tests we run?
(jrgm's page loader or iBench, for example?) I'd suspect that this would be the
only way we'd be able to notice the small but pervasive tax we'd be paying to
set up the DFA.

scc and I discussed this when he was out last, and he was considering allowing
search to support a ``pluggable algorithm''...

Comment 3

[timeless]

for our new string classes, don't we know m and n before we start searching? in 
which case we should be able to easily pick some threshold -- of course we'd 
have to decide what we want it to be...

Comment 4

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

The construction of the DFA shouldn't dwarf the cost of searching since it's not
a full-fledged DFA, but a pseudo-DFA that's much simpler to construct.

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: patch with reverse iterators and RFind* too (untested, but compiles on Windows)

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Oops, that patch had a typo that caused none of the templates to be instantiated.

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: version of above that *really* compiles on Windows

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: above, plus fix to nsCharTraits.h, plus tests

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

I only needed to fix one of the bugs in nsCharTraits.h (relating to not handling
reverse iterators correctly), and I did that in a somewhat ugly way.

The above patch also includes a test program that makes 120 test assertions. 
The first 6 fail, all of the following 114 pass.  The first 6 relate to what
should happen when we search for an empty string.  What *should* happen?

Comment 10

[Brendan Eich [:brendan]]

Nits: else after return non-sequitur, and gratuitous (-n) parentheses:

+        if (SameFragment(first, last)) {
+          PRInt32 n = last.get() - first.get();
+          return PRUint32((n>0) ? n : (-n));
+        } else {
+          return first.size_forward();
+        }

More tomorrow (need sleep), but one thought on empty matching: Perl and JS "bump
along" the index at which to resume when matching a global regular expression
that can match the empty string, so that the regexp (or the regexp plus its
target string, in Perl5) form an iterator.  For a flat string search, JS matches
'' at the beginning of the target string ("hello".indexOf('') returns 0;
"hello".indexOf(3) returns 3).  Hope this helps,

/be

Comment 11

[Scott Collins]

I'm applying your patch so I can build it and examine it in situ.  Off the bat,
though, I might have fixed |readable_distance| with a judiciously placed |abs()|
or the like; and I'm leary of the normalization happening in your |RBegin..|s,
as that's what's stopping |copy_string| and friends from working for you.  It
needs some thinking about.

Comment 12

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Why is the normalization breaking |copy_string|?  The problem seems to me that
|copy_string| expects |read| and |readable_distance| to return a pointer and a
length forward from that pointer.

One bit of the current code that would be impossible to duplicate with reverse
iterators is the part that assures that copy_string always works on overlapping
buffers (consider trying to use it to reverse a string).  Other than that it
doesn't seem too hard to make it work with reverse iterators.

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: compiles warning-free on VC6 and gcc 3.0, still struggling with gcc 2.7.2.3

Comment 14

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Attachment: also compiles on gcc 2.7.2.3 (split some stuff into nsStringIterator2.h)