From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 List-Post: List-Help: List-Unsubscribe: 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 , 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 Subject: Re: Huge delay for completions when not sorting Date: Mon, 2 Jul 2018 05:52:03 +0000 (UTC) Message-ID: References: <651A4CB3-1D36-4668-9DC0-EFACDE13E26D@dana.is> Reply-To: martin@mvath.de X-Complaints-To: usenet@blaine.gmane.org User-Agent: slrn/1.0.3 (Linux) Bart Schaefer wrote: > On Sun, Jul 1, 2018 at 1:38 PM, dana 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.