From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: David Kastrup Newsgroups: gmane.emacs.devel Subject: Re: Adding rassq-delete-all to lisp/subr.el. Date: Tue, 19 Apr 2005 18:39:06 +0200 Message-ID: <854qe267rp.fsf@lola.goethe.zz> References: <87k6my7v56.fsf@xs4all.nl> <851x967qc5.fsf@lola.goethe.zz> <877jiy68hv.fsf@xs4all.nl> NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: sea.gmane.org 1114034795 6254 80.91.229.2 (20 Apr 2005 22:06:35 GMT) X-Complaints-To: usenet@sea.gmane.org NNTP-Posting-Date: Wed, 20 Apr 2005 22:06:35 +0000 (UTC) Cc: emacs-devel@gnu.org Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Thu Apr 21 00:06:33 2005 Return-path: Original-Received: from lists.gnu.org ([199.232.76.165]) by ciao.gmane.org with esmtp (Exim 4.43) id 1DONJn-0005si-FR for ged-emacs-devel@m.gmane.org; Thu, 21 Apr 2005 00:05:12 +0200 Original-Received: from localhost ([127.0.0.1] helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DONOK-0007Ko-Be for ged-emacs-devel@m.gmane.org; Wed, 20 Apr 2005 18:09:52 -0400 Original-Received: from mailman by lists.gnu.org with tmda-scanned (Exim 4.43) id 1DOM4c-0001wc-6b for emacs-devel@gnu.org; Wed, 20 Apr 2005 16:45:26 -0400 Original-Received: from exim by lists.gnu.org with spam-scanned (Exim 4.43) id 1DOM4a-0001vw-I6 for emacs-devel@gnu.org; Wed, 20 Apr 2005 16:45:25 -0400 Original-Received: from [199.232.76.173] (helo=monty-python.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1DOM4a-0006eE-9S for emacs-devel@gnu.org; Wed, 20 Apr 2005 16:45:24 -0400 Original-Received: from [151.189.21.43] (helo=mail-in-03.arcor-online.net) by monty-python.gnu.org with esmtp (TLS-1.0:DHE_RSA_3DES_EDE_CBC_SHA:24) (Exim 4.34) id 1DOLsp-0007ZT-GP for emacs-devel@gnu.org; Wed, 20 Apr 2005 16:33:15 -0400 Original-Received: from lola.goethe.zz (i53879BBD.versanet.de [83.135.155.189]) by mail-in-03.arcor-online.net (Postfix) with ESMTP id 9C581164E62; Wed, 20 Apr 2005 20:14:00 +0200 (CEST) Original-Received: by lola.goethe.zz (Postfix, from userid 1002) id 1F5561C1E223; Tue, 19 Apr 2005 18:39:06 +0200 (CEST) Original-To: Lute Kamstra In-Reply-To: <877jiy68hv.fsf@xs4all.nl> (Lute Kamstra's message of "Tue, 19 Apr 2005 18:23:24 +0200") User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux) 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:36196 X-Report-Spam: http://spam.gmane.org/gmane.emacs.devel:36196 Lute Kamstra writes: > David Kastrup writes: > >> And I am not too fond of quadratic complexity algorithms. > > Me neither, but I was lazy and adapted assq-delete-all. > >> If one takes >> (defun checkit () >> (setq x nil) >> (dotimes (i 100001) (push (cons (- i) i) x)) >> (float-time >> (time-since (prog1 (current-time) >> (dotimes (i 101) >> (setq x (rassq-delete-all (* 100 i) x))))))) >> >> The discrepancy seems pretty small after byte compilation, which seems >> strange. > > delq in defined in C and it's only called 101 times. Ah, right. If we removed all elements piecemeal, this would be different. >> What makes a _significant_ difference is using (car (cdr...)) instead >> of (cadr...): for some unfathomable reason, cadr introduces a >> temporary binding to "x", and that is really expensive in the inner >> loop. > > Strange, (cadr ...) is just a defsubst for (car (cdr ...)). So > compiled it should make no difference. The defsubst binds and unbinds x. I consider that a byte compiler deficiency. -- David Kastrup, Kriemhildstr. 15, 44793 Bochum