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 16:13:11 +0200 Message-ID: <87ioc5kd54.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 1430921998 9562 80.91.229.3 (6 May 2015 14:19:58 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 6 May 2015 14:19:58 +0000 (UTC) Cc: Stefan Monnier , emacs-devel To: Artur Malabarba Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Wed May 06 16:19:56 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 1Yq0Az-0005Dl-6S for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 16:19:53 +0200 Original-Received: from localhost ([::1]:45439 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq0Ay-0003R8-Hz for ged-emacs-devel@m.gmane.org; Wed, 06 May 2015 10:19:52 -0400 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:52810) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq0AX-0003HR-Hh for emacs-devel@gnu.org; Wed, 06 May 2015 10:19:29 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yq0AS-0007ys-Ew for emacs-devel@gnu.org; Wed, 06 May 2015 10:19:25 -0400 Original-Received: from mail-wg0-x22b.google.com ([2a00:1450:400c:c00::22b]:35108) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yq0AS-0007yn-8g for emacs-devel@gnu.org; Wed, 06 May 2015 10:19:20 -0400 Original-Received: by wgyo15 with SMTP id o15so13371650wgy.2 for ; Wed, 06 May 2015 07:19:19 -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=nBDfnZ3TsSrnUaplGV/qISwBD1rfioKAv9zQwDkt5I8=; b=Ht+UPcE4OxethaBXy4PmBBaTIwjjkcg8MvyI8gJp5lZnDk17PUBQ6iJAn7haZ4qh7p T/W/XncFXFyDRQmf0usULBWEddP2diQPwbvf/IbT+yWxvqPXJD3SdZ1MCShh8zL+fjk4 dI0uYdEwgRXFUgTbukElW/BKpgL8G7kDejSWoJb5w5NysGNWC1YWmOxix+5W0iDUM2Ez D1su0Z1b5M5RVx/yv+OUPRKGmBhxhM0pGuA2WR6km140BAYhsAofUSjVqg6bTNhaFAB2 OwQx/dKT5Mk9SsceBg4EHXN1zR//gZ06NkvX0+ti2zL3pU4Iizqfz4VLzk59nLgjMO5N NQ9A== X-Received: by 10.194.121.135 with SMTP id lk7mr19188795wjb.26.1430921959630; Wed, 06 May 2015 07:19:19 -0700 (PDT) Original-Received: from firefly (dyn069045.nbw.tue.nl. [131.155.69.45]) by mx.google.com with ESMTPSA id s4sm2403260wix.14.2015.05.06.07.19.18 (version=TLSv1.2 cipher=RC4-SHA bits=128/128); Wed, 06 May 2015 07:19:18 -0700 (PDT) In-Reply-To: (Artur Malabarba's message of "Wed, 6 May 2015 15:04:19 +0100") 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::22b 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:186284 Archived-At: Artur Malabarba writes: >> I attach the patch. I did a bunch of `benchmark-run' and it seems that >> 100 elements is the breaking point. > > Small question. How much slower is this patch compared to the current > version on a list of 99 elements? (Due to having to calculate the > length) For 99 unique candidates, the call to `length' takes 5% time compared to the call to `delete-dups': (/ 3.774e-06 6.3028e-05) 0.05987814939392017 It becomes worse for a small amount of unique candidates, going to 30% for 10 candidates, but a lot of that is the standard cost of calling a function. I don't know if it's worth optimizing further. Oleh