From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: grischka Newsgroups: gmane.emacs.devel Subject: Re: Case mapping of sharp s Date: Fri, 20 Nov 2009 00:25:34 +0100 Message-ID: <4B05D3EE.2000101@gmx.de> References: <4B05A11F.5000700@gmx.de> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Trace: ger.gmane.org 1258673172 32465 80.91.229.12 (19 Nov 2009 23:26:12 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Thu, 19 Nov 2009 23:26:12 +0000 (UTC) Cc: emacs-devel@gnu.org, handa@m17n.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Nov 20 00:26:05 2009 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1NBGO4-00049E-VT for ged-emacs-devel@m.gmane.org; Fri, 20 Nov 2009 00:26:05 +0100 Original-Received: from localhost ([127.0.0.1]:47963 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NBGO4-0000Ro-7A for ged-emacs-devel@m.gmane.org; Thu, 19 Nov 2009 18:26:04 -0500 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1NBGNz-0000RM-0E for emacs-devel@gnu.org; Thu, 19 Nov 2009 18:25:59 -0500 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1NBGNt-0000PN-M4 for emacs-devel@gnu.org; Thu, 19 Nov 2009 18:25:57 -0500 Original-Received: from [199.232.76.173] (port=41586 helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1NBGNt-0000PJ-Dp for emacs-devel@gnu.org; Thu, 19 Nov 2009 18:25:53 -0500 Original-Received: from mail.gmx.net ([213.165.64.20]:58214) by monty-python.gnu.org with smtp (Exim 4.60) (envelope-from ) id 1NBGNs-0002PG-Re for emacs-devel@gnu.org; Thu, 19 Nov 2009 18:25:53 -0500 Original-Received: (qmail invoked by alias); 19 Nov 2009 23:25:49 -0000 Original-Received: from p57A09EDB.dip0.t-ipconnect.de (EHLO [192.168.1.3]) [87.160.158.219] by mail.gmx.net (mp015) with SMTP; 20 Nov 2009 00:25:49 +0100 X-Authenticated: #18588216 X-Provags-ID: V01U2FsdGVkX19ZgAsswNVZ/EOBoG5kJL2ol0bwlDUmevSAfKcLYa rAxNMwM5QkcmGu User-Agent: Thunderbird 2.0.0.23 (Windows/20090812) In-Reply-To: X-Y-GMX-Trusted: 0 X-FuHaFi: 0.62 X-detected-operating-system: by monty-python.gnu.org: Genre and OS details not recognized. X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:117311 Archived-At: Stefan Monnier wrote: >> Actually I think there is something simply wrong with the simple >> search, as it's much slower even for single chars (where bm doesn't >> have any advantage) and additionally in some weird random fashion >> it's again slower for backwards search, such as 14, 37, 66 ... 94 >> secs, where the bm takes 0.5 secs and simple forward constantly >> ~3.7 secs, all for isearch'ing one character in a 100Mb file. > > I can guess why it's much slower going backward: the simple search > operates on chars rather than bytes. The internal encoding we use > (currently based on utf-8) is designed to be easy to parse going forward > but not so easy going backward (IIRC our encoding is actually even a bit > more painful in this case than pure utf-8). BM on the other hand works > on bytes, so there's no such slowdown. Okay, it's utf-8 (aka multibyte I suppose) however I was using the same buffer in both cases (just a different search string). So whatever makes it more difficult to scan backwards the same situation exists for bm too. Also how can it happen that a C function varies between 4 and 90 seconds for the same action. > As for the general slowdown, it may also be due to having to parse the > char (encoded in utf-8) and then look it up in the corresponding char table > (a tree of arrays). From what I saw the simple_search() calls out to lisp for every single buffer-byte whereas boyer_moore() just translates it with a prefabricated C table. However if simple_search just would prepare the first char of the pattern in both lower and uppercase version readily for comparison it could be as fast as bm I guess (for a pattern length of less than 4 that is) --- grischka > > But maybe we're doing something silly somewhere. > > > Stefan >