From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.bugs Subject: bug#20887: 'make bootstrap' now verrrry slow due to recent isearch changes Date: Fri, 26 Jun 2015 10:52:36 +0300 Message-ID: <83y4j6dhyz.fsf@gnu.org> References: <558A0950.2000501@cs.ucla.edu> <2nbng5pou7.fsf@fencepost.gnu.org> <558AB250.5040908@cs.ucla.edu> <83vbeddu4d.fsf@gnu.org> <83si9hdthc.fsf@gnu.org> <83mvzoex5g.fsf@gnu.org> <838ub7eso2.fsf@gnu.org> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1435305216 23774 80.91.229.3 (26 Jun 2015 07:53:36 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 26 Jun 2015 07:53:36 +0000 (UTC) Cc: 20887@debbugs.gnu.org To: bruce.connor.am@gmail.com Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Fri Jun 26 09:53:24 2015 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1Z8ORw-0002B7-Ch for geb-bug-gnu-emacs@m.gmane.org; Fri, 26 Jun 2015 09:53:24 +0200 Original-Received: from localhost ([::1]:58714 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Z8ORv-0000t4-Q8 for geb-bug-gnu-emacs@m.gmane.org; Fri, 26 Jun 2015 03:53:23 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:36625) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Z8ORh-0000e4-Pl for bug-gnu-emacs@gnu.org; Fri, 26 Jun 2015 03:53:10 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Z8ORc-0002VD-Lv for bug-gnu-emacs@gnu.org; Fri, 26 Jun 2015 03:53:09 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:56300) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Z8ORc-0002V5-Ak for bug-gnu-emacs@gnu.org; Fri, 26 Jun 2015 03:53:04 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.80) (envelope-from ) id 1Z8ORb-0008Cj-Jy for bug-gnu-emacs@gnu.org; Fri, 26 Jun 2015 03:53:03 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Eli Zaretskii Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Fri, 26 Jun 2015 07:53:03 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 20887 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: Original-Received: via spool by 20887-submit@debbugs.gnu.org id=B20887.143530517131517 (code B ref 20887); Fri, 26 Jun 2015 07:53:03 +0000 Original-Received: (at 20887) by debbugs.gnu.org; 26 Jun 2015 07:52:51 +0000 Original-Received: from localhost ([127.0.0.1]:57746 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Z8ORO-0008CH-Q7 for submit@debbugs.gnu.org; Fri, 26 Jun 2015 03:52:51 -0400 Original-Received: from mtaout26.012.net.il ([80.179.55.182]:47840) by debbugs.gnu.org with esmtp (Exim 4.80) (envelope-from ) id 1Z8ORM-0008C2-A1 for 20887@debbugs.gnu.org; Fri, 26 Jun 2015 03:52:49 -0400 Original-Received: from conversion-daemon.mtaout26.012.net.il by mtaout26.012.net.il (HyperSendmail v2007.08) id <0NQJ00J00KK3CT00@mtaout26.012.net.il> for 20887@debbugs.gnu.org; Fri, 26 Jun 2015 10:55:20 +0300 (IDT) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by mtaout26.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0NQJ00JHNKO8C400@mtaout26.012.net.il>; Fri, 26 Jun 2015 10:55:20 +0300 (IDT) In-reply-to: X-012-Sender: halo1@inter.net.il X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.15 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 3.x X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:104365 Archived-At: > Date: Thu, 25 Jun 2015 18:32:51 +0100 > From: Artur Malabarba > 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.")