From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Leo Liu Newsgroups: gmane.emacs.devel Subject: Re: why is reverse a string in-place so much slower than a vector? Date: Fri, 25 Apr 2014 17:35:58 +0800 Message-ID: References: <87zjj9n53w.fsf@igel.home> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1398418597 26621 80.91.229.3 (25 Apr 2014 09:36:37 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 25 Apr 2014 09:36:37 +0000 (UTC) Cc: emacs-devel@gnu.org To: Andreas Schwab Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Fri Apr 25 11:36:30 2014 Return-path: Envelope-to: ged-emacs-devel@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 1WdcYX-0006k7-HY for ged-emacs-devel@m.gmane.org; Fri, 25 Apr 2014 11:36:29 +0200 Original-Received: from localhost ([::1]:56813 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WdcYX-0004P6-31 for ged-emacs-devel@m.gmane.org; Fri, 25 Apr 2014 05:36:29 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:51868) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WdcYL-0004Ow-Mi for emacs-devel@gnu.org; Fri, 25 Apr 2014 05:36:26 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1WdcY9-0005bd-A0 for emacs-devel@gnu.org; Fri, 25 Apr 2014 05:36:17 -0400 Original-Received: from mail-pb0-x230.google.com ([2607:f8b0:400e:c01::230]:57644) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1WdcY9-0005bQ-38 for emacs-devel@gnu.org; Fri, 25 Apr 2014 05:36:05 -0400 Original-Received: by mail-pb0-f48.google.com with SMTP id md12so3005907pbc.21 for ; Fri, 25 Apr 2014 02:36:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:face:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=elvuJC2ahuU4DL3R2bzq/YDIZMqsjtx5rwhQfSETQkc=; b=PNgYzQSqZ7H+WrOBiP2fC1KOECCkF4XPIfqH0Smxtfxyatlcb4TqJJyWIKcxEUcjux 2Ep2a3iRjB6GxdhBsnj34X7Lvg5XUOiG3R/dB08sHQgVADh65GM5aOZ+lIJGdJRd7aa2 koFg1i/PFDxKdvYa4F0TNzRlomwAEBjRcTKKdqLuO2teUbA9CUWA+hNAFwsrA/zC0FL1 sFygMTzKttO8uIOQVu59NznvQB/dqOVP8abgvOTQbQRorloa3t6Abm5WIRXPwakhmB78 vb/Co5YlO1xu75k0GSk1eo6RYcpnyU/kopR3LJiYCp3ZGc9cRvS29r+B4NHHl2IFoeBq A4fw== X-Received: by 10.68.240.34 with SMTP id vx2mr9929949pbc.1.1398418563734; Fri, 25 Apr 2014 02:36:03 -0700 (PDT) Original-Received: from fortuna ([123.115.255.237]) by mx.google.com with ESMTPSA id ba5sm14596644pbc.61.2014.04.25.02.36.01 for (version=TLSv1.1 cipher=RC4-SHA bits=128/128); Fri, 25 Apr 2014 02:36:03 -0700 (PDT) Face: iVBORw0KGgoAAAANSUhEUgAAACgAAAAoBAMAAAB+0KVeAAAAGFBMVEUKDAg1NjRWV1V9fnyg op/DxcLk5uP8/voi63ReAAAACXBIWXMAAAWJAAAFiQFtaJ36AAAAB3RJTUUH1goZAgAz00bgXgAA AeVJREFUKM9lk0Fz2jAQhQXJD3CCO70CmcC1YMtcWyTZ14Bl69xats4N9r6/3zWQBlodNKNPu/s0 b1cCQFuZGpfVVh3vAvBJolIXRkapSuoRUtIdFyo1Y5xSdlAj7OtvD1XnXxmWRi+eWgcxyCed1lVV B1CrKyujMoi+eLA5kU1SsjoHlW+nQjTtFxk4MXgrOxvIqzoTZR8XgPaLl419zgsMaSGFPiUOZCIh thsx5Xy9NsK8Kwf/JoQgMxcVJ301HKkcSWaT0O7FY056J4U9xcYfnmVXG4801lW6lqwu2nKFZoHC HuzvaTVndZ+LaRQgZdthXw1cpynEkLEwyFHXk/aIxNQ6QeooJuzPMB+wn+D7JJNsiCcVA13/A3h/ xE9J+WidpAwoYNmRFwyvSRhNVtsdaAewzZZP5uw82QL9+tyNfocyP0McAzICUr5Mk9RdIjWasUNx aIIt6NK4ZtXIMdfMQt3nuMAyWbLI4DqZ4xPq/ag8jPond4XU/cLuOgw6XCFX/YCUfcDAMMH58fD4 G9kDchwfqVefkBwup2uZM+Q4WhJt5jN3AxXCsaS2yXEDuWgS8VOzW0gFjhEPmLyFMKBFaLb1HRwc DiaKwx0EeTMRYnYPQRW3PP4HApvlMv0PttX5v/D6Aws3IOSEwzmLAAAAAElFTkSuQmCC In-Reply-To: <87zjj9n53w.fsf@igel.home> (Andreas Schwab's message of "Fri, 25 Apr 2014 11:14:11 +0200") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (CentOS 6.5) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2607:f8b0:400e:c01::230 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 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-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:171625 Archived-At: On 2014-04-25 11:14 +0200, Andreas Schwab wrote: > String random access has linear complexity: there is a single element > cache for the last known char->byte mapping for the last accessed > string, and the runtime depends on the distance from this point. Your > rev function represents the worst case behaviour. Thanks for this piece of critical information. I guess this is all due to `string_char_to_byte'? Leo