From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11452 invoked by alias); 6 Apr 2012 09:50:04 -0000 Mailing-List: contact zsh-users-help@zsh.org; run by ezmlm Precedence: bulk X-No-Archive: yes List-Id: Zsh Users List List-Post: List-Help: X-Seq: 16991 Received: (qmail 10858 invoked from network); 6 Apr 2012 09:49:53 -0000 X-Spam-Checker-Version: SpamAssassin 3.3.2 (2011-06-06) on f.primenet.com.au X-Spam-Level: X-Spam-Status: No, score=-1.6 required=5.0 tests=BAYES_00,DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED,FREEMAIL_FROM,NML_ADSP_CUSTOM_MED,RCVD_IN_DNSWL_LOW, T_DKIM_INVALID autolearn=no version=3.3.2 Received-SPF: pass (ns1.primenet.com.au: SPF record at _spf.google.com designates 209.85.210.44 as permitted sender) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=x6/nWAapNPAl0gt9SY3j1RZNY4VCU0aX3KYjFtqcPpY=; b=ZjWisoE+l/qMENyttQOxCPcA7ha3NyxYGdPqQhcrOuEd7+i6ooH4IAtYP3uD7rBrg7 awJPZ6paKvuo+mltcCXutWFZpAKJZqulJh1Q7Vkxwd2IfCnx6JPyLqmpNtgT0aCBSPcF PPC1dijTcOpra7Qsk5skxx5AzuLgUbGWNcgO9hmziyRqnvEKDzlrBCOLIx4OJL2BCrqo cQCq/XpPWcgUQylDSG9W1N/1qQOtwTT5cr1HG5ZiKvFqi53B4n0sG/bQJJU6ewGQhBWQ EHlzfFkqymmouUTPTpJcZkYdjBeroniLPXg03u2KjQN+BrqOQsLh/GXn4Xguob6/jEwS lhOA== MIME-Version: 1.0 In-Reply-To: <120405085125.ZM13673@torch.brasslantern.com> References: <120404005237.ZM10249@torch.brasslantern.com> <120405085125.ZM13673@torch.brasslantern.com> Date: Fri, 6 Apr 2012 11:49:47 +0200 Message-ID: Subject: Re: Large LS_COLORS makes auto_cd very slow From: =?UTF-8?Q?V=C3=A1clav_Zeman?= To: Bart Schaefer Cc: zsh-users@zsh.org Content-Type: multipart/mixed; boundary=047d7b2eda45baf16304bcff939a --047d7b2eda45baf16304bcff939a Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 5 April 2012 17:51, Bart Schaefer wrote: > On Apr 5, 11:30am, Vaclav Zeman wrote: > } > } > Anybody want to have a stab at creating a vastly more efficient versi= on > } > of Src/params.c:arrayuniq() ? > } I wonder if the attached patch does what you want here. It is fairly > } untested and incomplete as I have not been able to find out how to > } make sure that search.h gets included. > > Zsh has its own hash table implementation which ought to be used rather > than introducing any new external dependencies, but otherwise this is > the kind of thing I was suggesting. > > Or perhaps someone else has an even more clever idea. =C2=A0Anything bett= er > than O(N^2) would help. I have reimplemented the change using ZSH's own hash table. Please see the attached patch. --=20 VZ --047d7b2eda45baf16304bcff939a Content-Type: text/plain; charset=US-ASCII; name="hash_arrayuniq-2.diff.txt" Content-Disposition: attachment; filename="hash_arrayuniq-2.diff.txt" Content-Transfer-Encoding: base64 X-Attachment-Id: f_h0p1yj761 PT09IG1vZGlmaWVkIGZpbGUgJ1NyYy9wYXJhbXMuYycKLS0tIFNyYy9wYXJhbXMuYwkyMDEyLTAz LTEzIDA5OjQ3OjAxICswMDAwCisrKyBTcmMvcGFyYW1zLmMJMjAxMi0wNC0wNiAwOTo0MjoyMCAr MDAwMApAQCAtMjksNiArMjksNyBAQAogCiAjaW5jbHVkZSAienNoLm1kaCIKICNpbmNsdWRlICJw YXJhbXMucHJvIgorI2luY2x1ZGUgImhhc2h0YWJsZS5wcm8iCiAKICNpbmNsdWRlICJ2ZXJzaW9u LmgiCiAjaWZkZWYgQ1VTVE9NX1BBVENITEVWRUwKQEAgLTM0NTYsNyArMzQ1Nyw3IEBACiAKIC8q Ki8KIHN0YXRpYyB2b2lkCi1hcnJheXVuaXEoY2hhciAqKngsIGludCBmcmVlb2spCitzaW1wbGVf YXJyYXl1bmlxKGNoYXIgKip4LCBpbnQgZnJlZW9rKQogewogICAgIGNoYXIgKip0LCAqKnAgPSB4 OwogCkBAIC0zNDcxLDYgKzM0NzIsNzMgQEAKIH0KIAogLyoqLworc3RhdGljIHZvaWQKK2FycmF5 dW5pcV9mcmVlbm9kZShIYXNoTm9kZSBobikKK3sKKyAgICAodm9pZClobjsKK30KKworLyoqLwor c3RhdGljIHZvaWQKK2FycmF5dW5pcShjaGFyICoqeCwgaW50IGZyZWVvaykKK3sKKyAgICBjaGFy ICoqaXQsICoqd3JpdGVfaXQ7CisgICAgc2l6ZV90IGFycmF5X3NpemU7CisgICAgaW50IHJldDsK KyAgICBIYXNoTm9kZSBmb3VuZF9pdGVtOworICAgIHN0cnVjdCBoYXNobm9kZSBuZXdfbm9kZTsK KyAgICBIYXNoVGFibGUgaHQ7CisKKyAgICBpZiAoKnggPT0gTlVMTCkKKwlyZXR1cm47CisKKyAg ICBmb3IgKGl0ID0geDsgKml0ICE9IE5VTEw7ICsraXQpCisJOworCisgICAgYXJyYXlfc2l6ZSA9 IGl0IC0geDsKKyAgICBpZiAoYXJyYXlfc2l6ZSA8PSAxMHUpIHsKKwkvKiBmYWxsYmFjayB0byBz aW1wbGVyIHJvdXRpbmUgKi8KKwlzaW1wbGVfYXJyYXl1bmlxKHgsIGZyZWVvayk7CisJcmV0dXJu OworICAgIH0KKworICAgIGh0ID0gbmV3aGFzaHRhYmxlKChpbnQpYXJyYXlfc2l6ZSAqIDIsICJh cnJheXVuaXEiLCBOVUxMKTsKKyAgICAvKiA/Pz8gZXJyb3IgY2hlY2tpbmcgKi8KKyAgICBodC0+ aGFzaCAgICAgICAgPSBoYXNoZXI7CisgICAgaHQtPmVtcHR5dGFibGUgID0gZW1wdHloYXNodGFi bGU7CisgICAgaHQtPmZpbGx0YWJsZSAgID0gTlVMTDsKKyAgICBodC0+Y21wbm9kZXMgICAgPSBz dHJjbXA7CisgICAgaHQtPmFkZG5vZGUgICAgID0gYWRkaGFzaG5vZGU7CisgICAgaHQtPmdldG5v ZGUgICAgID0gZ2V0aGFzaG5vZGUyOworICAgIGh0LT5nZXRub2RlMiAgICA9IGdldGhhc2hub2Rl MjsKKyAgICBodC0+cmVtb3Zlbm9kZSAgPSByZW1vdmVoYXNobm9kZTsKKyAgICBodC0+ZGlzYWJs ZW5vZGUgPSBkaXNhYmxlaGFzaG5vZGU7CisgICAgaHQtPmVuYWJsZW5vZGUgID0gZW5hYmxlaGFz aG5vZGU7CisgICAgaHQtPmZyZWVub2RlICAgID0gYXJyYXl1bmlxX2ZyZWVub2RlOworICAgIGh0 LT5wcmludG5vZGUgICA9IE5VTEw7CisgICAgCisgICAgZm9yIChpdCA9IHgsIHdyaXRlX2l0ID0g eDsgKml0OykgeworCWZvdW5kX2l0ZW0gPSBnZXRoYXNobm9kZShodCwgKml0KTsKKwlpZiAoISBm b3VuZF9pdGVtKSB7CisJICAgIGZvdW5kX2l0ZW0gPSBhZGRoYXNobm9kZTIoaHQsICppdCwgJm5l d19ub2RlKTsKKwkgICAgLyphc3NlcnQoISBmb3VuZF9pdGVtKTsqLworCSAgICAqd3JpdGVfaXQg PSAqaXQ7CisJICAgIGlmIChpdCAhPSB3cml0ZV9pdCkKKwkJKml0ID0gTlVMTDsKKwkgICAgKyt3 cml0ZV9pdDsKKwl9CisJZWxzZSB7CisJICAgIGlmIChmcmVlb2spCisJCXpzZnJlZSgqaXQpOwor CSAgICAqaXQgPSBOVUxMOworCX0KKwkrK2l0OworICAgIH0KKyAgICAKKyAgICBkZWxldGVoYXNo dGFibGUoaHQpOworfQorCisvKiovCiB2b2lkCiB1bmlxYXJyYXkoY2hhciAqKngpCiB7Cgo= --047d7b2eda45baf16304bcff939a--