[tex-k] Easy-to-fix efficiency bug in kpathsea?

[Doug McKenna]

Looks good to me!

And I agree that the average case is probably not affected much.  It's just that str_list_float() was implemented to accomplish something that was might have been "noticeable in practice", so the argument can go both ways.

Whatever, there's no downside to the fix.

- Doug McKenna


----- Original Message -----
From: "Karl Berry" <karl at freefriends.org>
To: doug at mathemaesthetics.com
Cc: tex-k at tug.org
Sent: Friday, January 5, 2018 11:55:26 AM
Subject: Re: [tex-k] Easy-to-fix efficiency bug in kpathsea?

Hi Doug - thanks. I made the change below. Let me know if you see
problems with it.

I agree with your analysis (not that I could prove it either), though I
believe the difference is unnoticeable in practice, since (a) all such
cpu stuff is dwarfed by I/O time nowadays, and (b) most searches are
first-result-only, and (c) lists are short. Names in the runtime are
supposed to be unique, and mostly are. 

As for regression tests: if only we had some :( ...  --thanks, karl.

--- pathsearch.c	(revision 46220)
+++ pathsearch.c	(working copy)
@@ -117,6 +117,7 @@
                     boolean search_all)
 {
   str_llist_elt_type *elt;
+  str_llist_elt_type *next_elt;
   str_list_type ret;
   unsigned name_len = strlen (name);
   unsigned allocated = INIT_ALLOC;
@@ -124,11 +125,13 @@
 
   ret = str_list_init ();
 
-  for (elt = *dirs; elt; elt = STR_LLIST_NEXT (*elt))
+  for (elt = *dirs; elt; elt = next_elt)
     {
       const_string dir = STR_LLIST (*elt);
       unsigned dir_len = strlen (dir);
 
+      next_elt = STR_LLIST_NEXT (*elt); /* in case elt floats */
+
       while (dir_len + name_len + 1 > allocated)
         {
           allocated += allocated;
@@ -165,22 +168,26 @@
 }
 
 /* Note: NAMES[i] is not modified.  */
+
 static str_list_type
 dir_list_search_list (kpathsea kpse, str_llist_type *dirs, string* names,
                       boolean search_all)
 {
   str_llist_elt_type *elt;
+  str_llist_elt_type *next_elt;
   str_list_type ret;
   unsigned allocated = INIT_ALLOC;
   string potential = XTALLOC(allocated, char);
 
   ret = str_list_init ();
 
-  for (elt = *dirs; elt; elt = STR_LLIST_NEXT(*elt)) {
+  for (elt = *dirs; elt; elt = next_elt) {
       const_string dir = STR_LLIST (*elt);
       unsigned dir_len = strlen (dir);
       int i;
 
+      next_elt = STR_LLIST_NEXT (*elt); /* in case elt floats */
+
       for (i = 0; names[i]; i++) {
           const_string name = names[i];
           unsigned name_len;