I played with different (maybe wrong) implementations of
flyspell-word-search-backward and measured time against t.txt
(produced by the one-liner). All implementations are attached.

perl -e 'print(((join " ", ("met and") x 10) . "\n") x 30000)' > t.txt

my-test-agustin                            - Implementation from Agustin Martin with regexp-quote
my-test-concat-up                          - and concat moved upper
my-test-concat-up-goto                     - and goto-char moved into setq
my-test-concat-up-goto-notcap              - and ?: added to the first group
my-test-concat-up-goto-notcap-bob          - and \b replaced by \`
my-test-concat-up-goto-notcap-bob-bobp     - and goto-char replaced with conditional forward-char (on bobp)
my-test-concat-up-goto-notcap-nobob-bobp   - and the first group is removed, this case is handled separately,
my-test-concat-up-goto-notcap-nobob-nobobp - and bobp check is replaced by progn due to separate handling
my-test-goto-notcap-nobob-nobobp           - and concat moved down (back),
my-test-concat-up-goto-notcap-nobob-bobp-fixed - fixed for correct handling of beginning of buffer.

# |String| Time           |Result| Function name
1  nd  (0 0 192227 640000)  nil   my-test-agustin
2  nd  (0 0 192569 63000)   nil   my-test-concat-up
3  nd  (0 0 193895 468000)  nil   my-test-concat-up-goto
4  nd  (0 0 194372 743000)  nil   my-test-concat-up-goto-notcap
5  nd  (0 0 151535 868000)  nil   my-test-concat-up-goto-notcap-bob
6  nd  (0 0 131831 49000)   nil   my-test-concat-up-goto-notcap-bob-bobp
7  nd  (0 0 92012 191000)   nil   my-test-concat-up-goto-notcap-nobob-bobp
8  nd  (0 0 93928 281000)   nil   my-test-concat-up-goto-notcap-nobob-nobobp
9  nd  (0 0 93796 52000)    nil   my-test-goto-notcap-nobob-nobobp
10 nd  (0 0 94061 645000)   nil   my-test-concat-up-goto-notcap-nobob-bobp-fixed

It is from Messages of (my-try "nd") in t.txt.

The last 4 functions are quite close and often mixes differently due
to fluctuations. Really they could not be measured against this file
because re-search-forward always should return nil, I think.

Functions 7, 8, 9 are not correct: they find a word if we search a
word at the beginning of buffer staying at the middle of it. Function
10 has logic to handle this case.

Other corner cases should be thought and tried too. The times could be
different for other files and other words.

On Mon, Feb 24, 2014 at 03:02:51AM +0400, Aleksey Cherepanov wrote:
> I've performed some tests against my .org file (not in emacs -Q):

> On Sun, Feb 23, 2014 at 11:56:59PM +0400, Aleksey Cherepanov wrote:
> > Maybe it would be faster to not capture word but capture one char or
> > void but I doubt the difference would be noticable.
> 
> 307899: (0 3 174172 939000) :: \(?:[^[:alpha:]]\|\`\)\([[:alpha:]]+\)
> 307899: (0 3 250515 907000) :: \([^[:alpha:]]\|\`\)\(?:[[:alpha:]]+\)
> 307899: (0 3 218270 136000) :: \([^[:alpha:]]\|\`\)[[:alpha:]]+
> Unexpectedly capturing of word works a bit faster. Maybe it is not a
> word but the second group and it would work differently for search
> forward. Or alpha+ instead of fixed word caused it. Anyway the
> difference is very small.

We could avoid capturing at all. And it works faster as shown by 4
last functions.

Thanks!

-- 
Regards,
Aleksey Cherepanov