From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-workers-return-43131-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 22878 invoked by alias); 2 Jul 2018 05:54:31 -0000
Mailing-List: contact zsh-workers-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Workers List <zsh-workers.zsh.org>
List-Post: <mailto:zsh-workers@zsh.org>
List-Help: <mailto:zsh-workers-help@zsh.org>
List-Unsubscribe: <mailto:zsh-workers-unsubscribe@zsh.org>
X-Seq: 43131
Received: (qmail 2554 invoked by uid 1010); 2 Jul 2018 05:54:31 -0000
X-Qmail-Scanner-Diagnostics: from 195.159.176.226 by f.primenet.com.au (envelope-from <gcszd-zsh-workers@m.gmane.org>, uid 7791) with qmail-scanner-2.11 
 (clamdscan: 0.99.2/21882. spamassassin: 3.4.1.  
 Clear:RC:0(195.159.176.226):SA:0(-0.9/5.0):. 
 Processed in 1.966643 secs); 02 Jul 2018 05:54:31 -0000
X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on f.primenet.com.au
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,
	HEADER_FROM_DIFFERENT_DOMAINS,RDNS_NONE autolearn=no autolearn_force=no
	version=3.4.1
X-Envelope-From: gcszd-zsh-workers@m.gmane.org
X-Qmail-Scanner-Mime-Attachments: |
X-Qmail-Scanner-Zip-Files: |
X-Injected-Via-Gmane: http://gmane.org/
To: zsh-workers@zsh.org
From: Martin Vaeth <martin@mvath.de>
Subject: Re: Huge delay for completions when not sorting
Date: Mon, 2 Jul 2018 05:52:03 +0000 (UTC)
Message-ID: <slrnpjjfg6.pci.martin@clover.invalid>
References: <slrnpji5if.45o.martin@clover.invalid>
 <651A4CB3-1D36-4668-9DC0-EFACDE13E26D@dana.is>
 <CAH+w=7ayv2D4LEBmo0Ms7y58tHJH+PHfsazRq-drT_SSOqZQ5A@mail.gmail.com>
Reply-To: martin@mvath.de
X-Complaints-To: usenet@blaine.gmane.org
User-Agent: slrn/1.0.3 (Linux)

Bart Schaefer <schaefer@brasslantern.com> wrote:
> On Sun, Jul 1, 2018 at 1:38 PM, dana <dana@dana.is> wrote:
>
>> For each completion possibility, it performs a series of
>> checks against every subsequent possibility (compcore.c @ 3239)

Quadratic running time; so the result is not surprising.

BTW, the timing came from a real-world application:
Completion of package names for eix (a package database lookup in gentoo):
~20000 packages of the form "category/package" and then
~20000 with only "category/" (i.e. most of the latter are duplicates,
but these duplicates happen to be at the very end).

Unsorted output makes sense in this example since each of the 2 forms
are already added in a sorted manner.

> hash table

When building a temporary hash table it would be enough to store pointers
to the strings there to avoid data duplication.