_search_find_match_with_simplify() is inefficient

Yes.

One other thought: I wonder if it may be possible to have an early return in this function. Often it's the case that if you just lower case, and remove diacriticals on both $key and $text (two of the first three lines in search_simplify()), that might be enough to make a match. If that works, this should not change the character count of either string, and we could return the upcased/diacriticaled word at the same position as the match. So that would mean the 90% case was much faster.

I suppose I should assign this to myself, since I'm probably the person who understands this function the best... might be a week or so before I'm able to make a patch though (unless I find time today, which seems unlikely). If someone else wants to take a stab first, that would also be fine.

I think for testing performance, the thing to do would be to (a) add a couple more cases to SearchExcerptTest to exercise the slow parts of the current function and (b) add a timer to it so that if you run it interactively, at the end it has a pass("message") that tells you how much time was spent in the excerpt calculations.

I'm actually going to work on a patch for this now, starting with establishing a performance benchmark.

OK, here's step 1: I added a test to SearchExcerptTest that looks for an excerpt with accents and caps in a longer piece of text. When I used str_repeat($lorem2, 50) in this test, the test ran forever (or at least for quite a while and I gave up). With str_repeat($lorem2, 20) (as in the attached patch), it took about 101-103 seconds to run on my current local machine (which isn't exactly fast). Nicely illustrating the problem. Let's see if we can get it down.

Updating summary with ideas from #3.

So here's a patch for idea 2: Use static to reuse _search_index_truncate() results.

I thought first that it had reduced the test time from 100-103 seconds down to 95-99 seconds, but then it turned out I had made the change in a different git repo from where I was running the tests (doh!). So I would say the range of times on the unpatched code is 95-103 seconds on my test machine.

With this patch for the static in the truncate function, I got 92 seconds on two different runs. This may be within the noise, but it seems to be a small improvement, so I think we should keep this change.

For the next try, I added some to the test so that the search_simplify() part that invokes the hook comes into play in a longer text, and I implemented idea #5, which should fix the "look for caps and accents" problem, but not this new test. I also cleaned up the code in the test a bit. Probably out of scope. Sorry. [Someone added a doSearchExcerpt() method to the test class but didn't bother to move all the preg_replace() calls in there. Moving them in makes the test code quite a bit easier to read, plus centralized and easier to maintain.]

Without the code patch added here, the new test takes 164 seconds in one run, 155 in second run.

With the code patch, the new test takes just 68 seconds, so this is a good thing.

I think that's all for today...

Yeah, I realized this morning that this last patch wouldn't work right. Needs to use Unicode strlen/strpos functions. Good thing we have very comprehensive tests. ;) I'll get back to this later today.

OK, here's a fixed patch, using Unicode functions properly. Also, I thought I should start doing interdiffs.

Note: I had to add a new Unicode::strpos() function, which was missing from the Unicode class. Other than that, this is pretty much the same as the last patch but using Unicode functions, and takes the same time to run the Excerpt test, but actually works (at least, I tested it on the failing test from the last one).

Updating summary as to which parts have made it into the patch, and adding some notes about what search_simplify() actually does.

OK, one more update for today. This addresses item 3. (Fix word splitting in _search_find_match_with_simplify()). It turned out that the reg exps we were using in search_excerpt() and _search_find_match_with_simplify() were kind of wrong, so I fixed them up.

Assuming the patch passes tests (I ran SearchExcerptTest and SearchNodeDiacriticsTest, but who knows about the rest)... the time to run on Excerpt test is down to 31 seconds (as of last patch, it was about 68 seconds). So that's good!

Thanks for testing! Glad this fixes your real-world site.

So I talked to @dawehner about the Unicode function and we need to make it compatible (in the case of no MB extension) with what Unicode::strlen() and Unicode::substr() are already doing, which is to cut out characters
0x80-0xBF. I thought first that substr() was doing something different, due to its somewhat misleading code comments. So this patch changes the new Unicode function, fixes up those comments in substr(), and adds a Unicode test.

I added a new test case with lots of whitespace. Confirmed it takes forever to run without the code patches (I gave up and aborted the test after a while, so not sure exactly how long). With code patches, the time is 33 seconds, so that is the new time to beat.

To do still: Suggestions 1 and 4 from the issue summary, if possible. I think (1) will just make a small improvement, and (4) will be the big win for the remaining slow case (when the hook is involved, see summary).

Updating summary about unicode additions and adding beta eval.

Looking at the way _search_find_match_with_simplify() works, I don't think that suggestion #1 from the issue summary will actually work out -- that's the idea of not doing the entity decode, lower-casing, and diacritical removing each time search_simplify() is called. The reason is that we're passing in a substring from the original $text each time, at a known position, and entity decoding will change the string positions.

So. That leaves #4, to improve the search algorithm.

So, here it is! This code improved the time from 33 seconds down to ***2.5 seconds*** on my local test machine. Woot! I think this is it!

Code actually needs review now.....

RE #17 - thanks for the review!

item 2 - Hah! That is left over from my Fortran programming days. ;) Back then, dividing was inefficient and computers were slow so you always wanted to multiply by 0.5 instead of dividing by 2. Not an issue in this century. Updated code in two places.

item 3/4 - added comments to hopefully clarify what this is doing. There was a comment about (4) in an earlier iteration but it got lost when I redid the code for the binary searches. We do have tests that include Unicode characters in $text, by the way, and they are working correctly; definitely needed a comment to clarify this though.

Doh. Edited patch to take out one extra space and (oh horrors!) didn't make an interdiff file for the one space, and leaving RTBC since it was a direct patch edit so is the same patch file except one character. Hope that's OK.

Unassigning to avoid confusion about committing.