bug#20887: 'make bootstrap' now verrrry slow due to recent isearch changes

[Eli Zaretskii]

> Date: Thu, 25 Jun 2015 18:32:51 +0100
> From: Artur Malabarba <bruce.connor.am@gmail.com>
> Cc: 20887@debbugs.gnu.org
> 
> I'm aware I could run a loop inside the lambda going from (car key) to
> (cdr key), and then do the `(funcall func ...)' on each item in the
> range, but I fail to see how that would be faster than running a
> second map-char-table. In fact, the number of steps involved is much
> larger if you loop:
>  - the current version has a map of 100 steps and another of 5721,
>  - your proposal would have a map of 100 steps, each containing a loop
> of about 120 steps, which totals to over 12000 steps (I counted).
> 
> Again, maybe I'm missing something, or maybe looping would be much
> faster than that second `map-char-table', but it seems to me like it
> would just be doing more work.

It's not faster, but it's not slower, either.  Looping is not what
takes time here, and if you think map-char-table can somehow magically
avoid any looping, you should look at its implementation.

What takes time here is map-char-table itself and the body of the
loop, where the data is processed.

For the record, I show the variant I had in mind below.  I timed it on
my system, and found it delivering the same speed as your version, up
to the system clock accuracy.

(defconst character-fold-table
  (eval-when-compile
    (let* ((equiv (make-char-table 'character-fold-table))
           (table (unicode-property-table-internal 'decomposition))
           (func (char-table-extra-slot table 1)))
      ;; Compile a list of all complex characters that each simple
      ;; character should match.
      (map-char-table
       (lambda (i dec)
         (when (consp i))
           (let ((ifirst (car i))
                 (ilast (cdr i)))
             ;; Ensure the table is populated for this range.
             (funcall func ifirst dec table)
             ;; Loop over all non-trivial decompositions in the range.
             (while (<= ifirst ilast)
               (setq dec (funcall func ifirst (aref table ifirst) table))
               (or (not (consp dec))
                   (and (eq ifirst (car dec))
                        (null (cdr dec)))
                   (progn
                     ;; Discard a possible formatting tag.
                     (when (symbolp (car dec))
                       (setq dec (cdr dec)))
                     (let ((d dec) k found multiletter)
                       (while (and d (not found))
                         (setq k (pop d))
                         ;; Is k a number or letter, per unicode standard?
                         (setq found
                               (memq (get-char-code-property k 
'general-category)
                                     '(Lu Ll Lt Lm Lo Nd Nl No))))
                       (if found
                           ;; Check if the decomposition has more than
                           ;; one letter, because then we don't want
                           ;; the first letter to match the
                           ;; decomposition.
                           (dolist (k d)
                             (when (memq
                                    (get-char-code-property k 'general-category)
                                    '(Lu Ll Lt Lm Lo Nd Nl No))
                               (setq multiletter t)))
                         ;; If there's no number or letter on the
                         ;; decomposition, take the first character in it.
                         (setq found (car-safe dec)))
                       ;; Add i to the list of characters that k can
                       ;; represent. Also possibly add its
                       ;; decomposition, so we can match multi-char
                       ;; representations like (format "a%c" 769)
                       (when (and found (not (eq ifirst k)))
                         (let ((chars (cons (char-to-string ifirst)
                                            (aref equiv k))))
                           (aset equiv k
                                 (if multiletter chars
                                   (cons (apply #'string dec) chars))))))))
               (setq ifirst (1+ ifirst)))))
             table)

      ;; Convert the lists of characters we compiled into regexps.
      (map-char-table
       (lambda (i v) (let ((re (regexp-opt (cons (char-to-string i) v))))
                  (if (consp i)
                      (set-char-table-range equiv i re)
                    (aset equiv i re))))
       equiv)
      equiv))
  "Used for folding characters of the same group during search.")