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

From: Eli Zaretskii <[email-masked]>
Date: Fri, 26 Jun 2015 10:52:36 +0300

> Date: Thu, 25 Jun 2015 18:32:51 +0100
> From: Artur Malabarba <[email-masked]>
> Cc: [email-masked]
> 
> 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.")