From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Oleh Krehel Newsgroups: gmane.emacs.devel Subject: Re: What to do for faster `remove-duplicates'? Date: Wed, 06 May 2015 15:51:55 +0200 Message-ID: <87y4l1ke4k.fsf@gmail.com> References: <87383atb2p.fsf@gmail.com> <873839ltoa.fsf@gmail.com> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain X-Trace: ger.gmane.org 1430920705 19126 80.91.229.3 (6 May 2015 13:58:25 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 6 May 2015 13:58:25 +0000 (UTC) Cc: emacs-devel@gnu.org To: Stefan Monnier Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 06 15:58:17 2015 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 1Ypzq4-0007fy-Rn for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 15:58:16 +0200 Original-Received: from localhost ([::1]:45248 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ypzq4-0006bD-CS for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 09:58:16 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:45584) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ypzpv-0006Pc-De for emacs-devel@gnu.org; Wed, 06 May 2015 09:58:13 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Ypzpq-0008Pr-CZ for emacs-devel@gnu.org; Wed, 06 May 2015 09:58:07 -0400 Original-Received: from mail-wg0-x22e.google.com ([2a00:1450:400c:c00::22e]:35262) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Ypzpq-0008Pc-6B for emacs-devel@gnu.org; Wed, 06 May 2015 09:58:02 -0400 Original-Received: by wgyo15 with SMTP id o15so12632166wgy.2 for ; Wed, 06 May 2015 06:58:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:cc:subject:references:date:in-reply-to:message-id :user-agent:mime-version:content-type; bh=XKFb+fjc25Z1/F6SHerxJ7LrBkxlOjNLEYaxJe/FeLc=; b=TN99/5G9YZWW7/17HFH8zlkdinNk4gcwFFV1MtTxLQkyB2r5f12OS5I1xpSbqpOmpd aBiBUdUxZEfdiY4s5S53m2tjz6CRkOZBS0mYuapj6qmZqq3JftCMwIm9w/E94m5M80Bi 8FkBYmbKT3LvSntB5jHIrzxxr7JP0jZ70cVLyMWx9edrO6fF2c2y1Z1/Yd5sA5TdHs7z UeaiLstN8OG9P9QnZ8o9Lr6zrl8nolKrVB7nIkIsaGciBdO8x7FJPswmegtyk93EzLxG kH9qCS5Mp/ftLdlMIO3/i+gbeox+W88n0ZJoMwvDy3f5POl8cEJilUFsi0hgT5IOmEnh qPIQ== X-Received: by 10.181.13.16 with SMTP id eu16mr5449749wid.10.1430920681456; Wed, 06 May 2015 06:58:01 -0700 (PDT) Original-Received: from firefly (dyn069045.nbw.tue.nl. [131.155.69.45]) by mx.google.com with ESMTPSA id l3sm2309255wik.16.2015.05.06.06.58.00 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Wed, 06 May 2015 06:58:01 -0700 (PDT) In-Reply-To: (Stefan Monnier's message of "Wed, 06 May 2015 09:50:42 -0400") User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/25.0.50 (gnu/linux) X-detected-operating-system: by eggs.gnu.org: Error: Malformed IPv6 address (bad octet value). X-Received-From: 2a00:1450:400c:c00::22e 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:186282 Archived-At: Stefan Monnier writes: >> I attach the patch. I did a bunch of `benchmark-run' and it seems that >> 100 elements is the breaking point. > > Looks good, please install. It's hard to believe that you need a whole 100 > elements before it pays off ;-) For a different completely unique collection, it breaks at 30. This is because list-style deletion works faster when there are a lot of duplicates. Oleh