Re: Large LS_COLORS makes auto_cd very slow

["Václav Zeman" <vhaisman@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 2087 bytes --]

On 4 April 2012 09:52, Bart Schaefer <schaefer@brasslantern.com> wrote:
> On Apr 3,  9:08pm, Jesper Nygårds wrote:
> }
> } /us<tab>
> }
> } whereas completion after an explicit cd is nearly instantaneous:
> }
> } cd /us<tab>
> }
> } It seems rather odd to me that coloring would render this so slow. I
> } suppose the delay is caused by zsh trying to color some list of
> } possible completions, but why would it be so very slow?
>
> /us<tab> as the first word in the buffer is in command position, so is
> completing any/all of commands, executables, builtins, functions,
> aliases, suffix-aliases, reserved-words, jobs and parameters.
>
> For each of these categories, _setup line 12 rebuilds the value of
> the _comp_colors array to add new patterns such that any pattern that
> started with '=' gets copied with a prefix matching the tag currently
> being tested; e.g. '(commands)=...' or '(jobs)=...'
>
> This is done even for tags that won't have any matches because the
> colors array has to be ready for the internals to use when a match is
> found, there's no way to "call back" to build it on demand.
>
> The expensive bit is that _comp_colors is declared as a unique array,
> so every time it gets rebuilt the resulting 1700+ entries are all
> compared against one another to make sure there is no duplication.
> Repeat that nine times and it takes a while.
>
> With "cd" in front, it's restricted to directories only, so the array
> is only rebuilt once.
>
> Addenda for -workers:
>
> Anybody want to have a stab at creating a vastly more efficient version
> of Src/params.c:arrayuniq() ?  I came up with a faster way to remove the
> duplicate elements, but the problem here is to efficiently determine
> that there are no duplicates to remove.  Perhaps throw the elements into
> a hash table and then make one pass looking up each element.
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.

-- 
VZ

[-- Attachment #2: hash_arrayuniq.diff --]
[-- Type: application/octet-stream, Size: 1880 bytes --]

=== modified file 'Src/params.c'
--- Src/params.c	2012-03-13 09:47:01 +0000
+++ Src/params.c	2012-04-05 09:25:52 +0000
@@ -3456,7 +3456,7 @@
 
 /**/
 static void
-arrayuniq(char **x, int freeok)
+simple_arrayuniq(char **x, int freeok)
 {
     char **t, **p = x;
 
@@ -3471,6 +3471,62 @@
 }
 
 /**/
+static void
+arrayuniq(char **x, int freeok)
+{
+    char **it, **write_it;
+    size_t array_size;
+    int ret;
+    ENTRY item;
+    ENTRY * found_item;
+
+    if (*x == NULL)
+	return;
+
+    for (it = x; *it != NULL; ++it)
+	;
+
+    array_size = it - x;
+    if (array_size <= 10u) {
+	/* fallback to simpler routine */
+	simple_arrayuniq (x, freeok);
+	return;
+    }
+
+    ret = hcreate (array_size);
+    assert (ret);
+    if (! ret) {
+	/* fallback to routine without memory allocation needs */
+	simple_arrayuniq (x, freeok);
+	return;
+    }
+
+    item.data = NULL;
+    
+    for (it = x, write_it = x; *it;) {
+	item.key = *it;
+	found_item = hsearch (item, FIND);
+	if (! found_item) {
+	    found_item = hsearch (item, ENTER);
+	    assert (found_item);
+	    *write_it = *it;
+	    if (it != write_it)
+		*it = NULL;
+	    ++write_it;
+	}
+	else {
+	    if (freeok)
+		zsfree (*it);
+	    *it = NULL;
+	}
+	++it;
+    }
+    
+    
+    hdestroy ();
+}
+
+/**/
 void
 uniqarray(char **x)
 {

=== modified file 'configure.ac'
--- configure.ac	2012-03-05 10:06:28 +0000
+++ configure.ac	2012-04-05 09:21:42 +0000
@@ -610,7 +610,7 @@
 		 termios.h sys/param.h sys/filio.h string.h memory.h \
 		 limits.h fcntl.h libc.h sys/utsname.h sys/resource.h \
 		 locale.h errno.h stdio.h stdarg.h varargs.h stdlib.h \
-		 unistd.h sys/capability.h \
+		 unistd.h sys/capability.h search.h \
 		 utmp.h utmpx.h sys/types.h pwd.h grp.h poll.h sys/mman.h \
 		 netinet/in_systm.h pcre.h langinfo.h wchar.h stddef.h \
 		 sys/stropts.h iconv.h ncurses.h ncursesw/ncurses.h \