From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Noam Postavsky Newsgroups: gmane.emacs.devel Subject: =?UTF-8?Q?Re=3A_=5BEmacs=2Ddiffs=5D_master_c66aaa6=3A_Recomplexify_=E2=80=98de?= =?UTF-8?Q?lete=2Dtrailing=2Dwhitespace=E2=80=99_by_treating_=5Cn_as_whitespace_aga?= =?UTF-8?Q?in?= Date: Wed, 15 Mar 2017 20:18:24 -0400 Message-ID: References: <20170315023157.29463.36647@vcs0.savannah.gnu.org> <20170315023159.30AA520CAB@vcs0.savannah.gnu.org> NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary=001a1134e0bae4fe86054acdff95 X-Trace: blaine.gmane.org 1489623518 1485 195.159.176.226 (16 Mar 2017 00:18:38 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Thu, 16 Mar 2017 00:18:38 +0000 (UTC) Cc: Emacs developers To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Mar 16 01:18:32 2017 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1coJ7c-0007no-9O for ged-emacs-devel@m.gmane.org; Thu, 16 Mar 2017 01:18:28 +0100 Original-Received: from localhost ([::1]:40091 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1coJ7i-00067g-CM for ged-emacs-devel@m.gmane.org; Wed, 15 Mar 2017 20:18:34 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:41159) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1coJ7b-00067b-LH for emacs-devel@gnu.org; Wed, 15 Mar 2017 20:18:28 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1coJ7a-0003w1-HN for emacs-devel@gnu.org; Wed, 15 Mar 2017 20:18:27 -0400 Original-Received: from mail-ot0-x22f.google.com ([2607:f8b0:4003:c0f::22f]:36590) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1coJ7a-0003vr-BZ for emacs-devel@gnu.org; Wed, 15 Mar 2017 20:18:26 -0400 Original-Received: by mail-ot0-x22f.google.com with SMTP id i1so38074945ota.3 for ; Wed, 15 Mar 2017 17:18:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=DzU6YmoZACs7LfwC8WArPYEUJVOEC3fkDIZHEv4CRas=; b=Bbk7TF+dFoh/GemR9U4rW+nFeyQjF2+KXe5rPfiVFYrnR+91gztqeoCsP03dovU0Gj n9iHIAzyKrWOO6/vZ1ABo1gkM/bFwicHcq+qHDb9yNj98P2bNsy35iAg9+VJtjmgYH2+ mJ03k8L8OYzQMrTZ/QMKeDN+pqqmppNHzDGAsyzvr8jBzXLIkbkTkG2Xdhq2U1xbuyy7 ahSvV88dbImXUO6H1Uh08PVZMXq76tJZLCPdHsiXes8W92SVFA/QiwFNZvPuLmgKxlR/ tmw2o+DP7ud699xDB/my9YE2nAQjx5SPPW7s6Pw9+Cw2Gi4de9ek6gKQwpNuKYdXUk4/ Eepg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=DzU6YmoZACs7LfwC8WArPYEUJVOEC3fkDIZHEv4CRas=; b=p5QFmO5c1oGXzRIQYBiHRn5pLj2P9SITIWiKYThglNwBPrHsgoBCcba8XX15ZPdiCB 6httNUebxRjI6MYb3CfLI0QvdvSGQmK15Bdh5IbUvFWMpBq8CeWlWTS91h4j8jpjhqvX ezyANcVHFpPO1RrvVtyqkz96qIJM4nZ6Az1iBwtKRLK7n2qC0Y2I4U7nnMPUiMcN2FcO f4S5uxWvxG2vG1xqyGV0kVz29XNkVpAzehGgFfIkzzGPSEV8RIFg+IcyCeI3sYumCvb+ rZDNqk+LsmDYyTx6XFRSvI/VXz5MG16jmn8pgG1awQ2E3SvTMTDkX5OCrHL27fpMhbo9 Mezg== X-Gm-Message-State: AFeK/H2OGkoDYOeDmNpOaIfgZKIXE9+Kn3eJkqM+lCERs8F4CoNFqQL7jD+Zq8F0W7jRA3B60hEPZzDi/OSC1A== X-Received: by 10.202.244.10 with SMTP id s10mr3548531oih.187.1489623505426; Wed, 15 Mar 2017 17:18:25 -0700 (PDT) Original-Received: by 10.157.80.172 with HTTP; Wed, 15 Mar 2017 17:18:24 -0700 (PDT) In-Reply-To: X-Google-Sender-Auth: ehUZOlPObCKatIzUd7lqwIi3XuY X-detected-operating-system: by eggs.gnu.org: Genre and OS details not recognized. X-Received-From: 2607:f8b0:4003:c0f::22f X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: "Emacs-devel" Xref: news.gmane.org gmane.emacs.devel:213066 Archived-At: --001a1134e0bae4fe86054acdff95 Content-Type: text/plain; charset=UTF-8 On Wed, Mar 15, 2017 at 4:26 PM, Stefan Monnier wrote: > because "[\s\t]+$" shouldn't backtrack. Using "\\s-+$" with > a syntax-table that puts \n in the whitespace syntax is indeed asking > for trouble, but I'm surprised "[\s\t]+$" is only twice as fast as this > pathological case (and hence presumably much slower than "\\s-+$" when > \n is not whitespace). Why should one backtrack and not the other? The *2 ratio seems to hold for both pathologically slow and normal case. Matching against a sequence of non-trailing whitespace seens to have quadradic complexity (see attached, timings are from an elisp buffer), does that give you any hints? --001a1134e0bae4fe86054acdff95 Content-Type: text/x-emacs-lisp; charset=US-ASCII; name="trailing-ws-regexp-benchmark.el" Content-Disposition: attachment; filename="trailing-ws-regexp-benchmark.el" Content-Transfer-Encoding: base64 X-Attachment-Id: f_j0bncax50 OzsgUGF0aG9sb2dpY2FsIGNhc2UsIGJvdGggc2VlbSB0byBiZSBxdWFkcmF0aWMgaW4gdGhlIGxl bmd0aCBvZiBhIHdoaXRlc3BhY2Ugc2VxdWVuY2UuCihiZW5jaG1hcmsgMSBgKHN0cmluZy1tYXRj aCAiW1xzXHRdKyQiICwoY29uY2F0IChtYWtlLXN0cmluZyAxMDAwID9ccykgIlgiKSkpIkVsYXBz ZWQgdGltZTogMC4wOTAwMDBzIgooYmVuY2htYXJrIDEgYChzdHJpbmctbWF0Y2ggIltcc1x0XSsk IiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgMjAwMCA/XHMpICJYIikpKSJFbGFwc2VkIHRpbWU6IDAu MjU4MDAwcyIKKGJlbmNobWFyayAxIGAoc3RyaW5nLW1hdGNoICJbXHNcdF0rJCIgLChjb25jYXQg KG1ha2Utc3RyaW5nIDQwMDAgP1xzKSAiWCIpKSkiRWxhcHNlZCB0aW1lOiAwLjYzMDAwMHMiCihi ZW5jaG1hcmsgMSBgKHN0cmluZy1tYXRjaCAiW1xzXHRdKyQiICwoY29uY2F0IChtYWtlLXN0cmlu ZyA4MDAwID9ccykgIlgiKSkpIkVsYXBzZWQgdGltZTogMi4yNjAwMDBzIgooYmVuY2htYXJrIDEg YChzdHJpbmctbWF0Y2ggIltcc1x0XSskIiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgMTYwMDAgP1xz KSAiWCIpKSkiRWxhcHNlZCB0aW1lOiA5LjMwNjAwMHMiCgooYmVuY2htYXJrIDEgYChzdHJpbmct bWF0Y2ggIlxccy0rJCIgLChjb25jYXQgKG1ha2Utc3RyaW5nIDEwMDAgP1xzKSAiWCIpKSkiRWxh cHNlZCB0aW1lOiAwLjM5NTAwMHMiCihiZW5jaG1hcmsgMSBgKHN0cmluZy1tYXRjaCAiXFxzLSsk IiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgMjAwMCA/XHMpICJYIikpKSJFbGFwc2VkIHRpbWU6IDAu MzQ3MDAwcyIKKGJlbmNobWFyayAxIGAoc3RyaW5nLW1hdGNoICJcXHMtKyQiICwoY29uY2F0ICht YWtlLXN0cmluZyA0MDAwID9ccykgIlgiKSkpIkVsYXBzZWQgdGltZTogMS4yODIwMDBzIgooYmVu Y2htYXJrIDEgYChzdHJpbmctbWF0Y2ggIlxccy0rJCIgLChjb25jYXQgKG1ha2Utc3RyaW5nIDgw MDAgP1xzKSAiWCIpKSkiRWxhcHNlZCB0aW1lOiA1LjA1MTAwMHMiCihiZW5jaG1hcmsgMSBgKHN0 cmluZy1tYXRjaCAiXFxzLSskIiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgMTYwMDAgP1xzKSAiWCIp KSkiRWxhcHNlZCB0aW1lOiAyMC4xNDQwMDBzIgoKOzsgTm9ybWFsIGNhc2UsIGxpbmVhci4KKGJl bmNobWFyayAxIGAoc3RyaW5nLW1hdGNoICJbXHNcdF0rJCIgLChjb25jYXQgKG1ha2Utc3RyaW5n IDgwMDAgP18pICJYIikpKSJFbGFwc2VkIHRpbWU6IDAuMDAxMDAwcyIKKGJlbmNobWFyayAxIGAo c3RyaW5nLW1hdGNoICJbXHNcdF0rJCIgLChjb25jYXQgKG1ha2Utc3RyaW5nIDE2MDAwID9fKSAi WCIpKSkiRWxhcHNlZCB0aW1lOiAwLjAwMjAwMHMiCihiZW5jaG1hcmsgMSBgKHN0cmluZy1tYXRj aCAiW1xzXHRdKyQiICwoY29uY2F0IChtYWtlLXN0cmluZyAzMjAwMCA/XykgIlgiKSkpIkVsYXBz ZWQgdGltZTogMC4wMDMwMDBzIgooYmVuY2htYXJrIDEgYChzdHJpbmctbWF0Y2ggIltcc1x0XSsk IiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgNjQwMDAgP18pICJYIikpKSJFbGFwc2VkIHRpbWU6IDAu MDA3MDAwcyIKCihiZW5jaG1hcmsgMSBgKHN0cmluZy1tYXRjaCAiXFxzLSskIiAsKGNvbmNhdCAo bWFrZS1zdHJpbmcgODAwMCA/XykgIlgiKSkpIkVsYXBzZWQgdGltZTogMC4wMDQwMDBzIgooYmVu Y2htYXJrIDEgYChzdHJpbmctbWF0Y2ggIlxccy0rJCIgLChjb25jYXQgKG1ha2Utc3RyaW5nIDE2 MDAwID9fKSAiWCIpKSkiRWxhcHNlZCB0aW1lOiAwLjAwODAwMHMiCihiZW5jaG1hcmsgMSBgKHN0 cmluZy1tYXRjaCAiXFxzLSskIiAsKGNvbmNhdCAobWFrZS1zdHJpbmcgMzIwMDAgP18pICJYIikp KSJFbGFwc2VkIHRpbWU6IDAuMDE2MDAwcyIKKGJlbmNobWFyayAxIGAoc3RyaW5nLW1hdGNoICJc XHMtKyQiICwoY29uY2F0IChtYWtlLXN0cmluZyA2NDAwMCA/XykgIlgiKSkpIkVsYXBzZWQgdGlt ZTogMC4wMzEwMDBzIgo= --001a1134e0bae4fe86054acdff95--