patch 9.0.0165: looking up a text property type by ID is slowv9.0.0165

Problem:    Looking up a text property type by ID is slow.
Solution:   Keep an array of property types sorted on ID.

3 files changed, 84 insertions, 35 deletions

diff --git a/src/structs.h b/src/structs.h
index 5b05c6487c..fcc9c79c3a 100644
--- a/src/structs.h
+++ b/src/structs.h
@@ -3084,6 +3084,7 @@ struct file_buffer
 #ifdef FEAT_PROP_POPUP
     int		b_has_textprop;	// TRUE when text props were added
     hashtab_T	*b_proptypes;	// text property types local to buffer
+    proptype_T	**b_proparray;	// entries of b_proptypes sorted on tp_id
     garray_T	b_textprop_text; // stores text for props, index by (-id - 1)
 #endif
 
diff --git a/src/textprop.c b/src/textprop.c
index 8670c87c33..679535375c 100644
--- a/src/textprop.c
+++ b/src/textprop.c
@@ -11,12 +11,6 @@
  * Text properties implementation.  See ":help text-properties".
  *
  * TODO:
- * - Adjust text property column and length when text is inserted/deleted.
- *   -> search for changed_bytes() from misc1.c
- *   -> search for mark_col_adjust()
- * - Perhaps we only need TP_FLAG_CONT_NEXT and can drop TP_FLAG_CONT_PREV?
- * - Add an array for global_proptypes, to quickly lookup a prop type by ID
- * - Add an array for b_proptypes, to quickly lookup a prop type by ID
  * - Checking the text length to detect text properties is slow.  Use a flag in
  *   the index, like DB_MARKED?
  * - Also test line2byte() with many lines, so that ml_updatechunk() is taken
@@ -42,6 +36,7 @@
 
 // The global text property types.
 static hashtab_T *global_proptypes = NULL;
+static proptype_T **global_proparray = NULL;
 
 // The last used text property type ID.
 static int proptype_id = 0;
@@ -51,7 +46,7 @@ static int proptype_id = 0;
  * Returns NULL if the item can't be found.
  */
     static hashitem_T *
-find_prop_hi(char_u *name, buf_T *buf)
+find_prop_type_hi(char_u *name, buf_T *buf)
 {
     hashtab_T	*ht;
     hashitem_T	*hi;
@@ -72,12 +67,12 @@ find_prop_hi(char_u *name, buf_T *buf)
 }
 
 /*
- * Like find_prop_hi() but return the property type.
+ * Like find_prop_type_hi() but return the property type.
  */
     static proptype_T *
-find_prop(char_u *name, buf_T *buf)
+find_prop_type(char_u *name, buf_T *buf)
 {
-    hashitem_T	*hi = find_prop_hi(name, buf);
+    hashitem_T	*hi = find_prop_type_hi(name, buf);
 
     if (hi == NULL)
 	return NULL;
@@ -91,7 +86,7 @@ find_prop(char_u *name, buf_T *buf)
     int
 find_prop_type_id(char_u *name, buf_T *buf)
 {
-    proptype_T *pt = find_prop(name, buf);
+    proptype_T *pt = find_prop_type(name, buf);
 
     if (pt == NULL)
 	return 0;
@@ -106,10 +101,10 @@ find_prop_type_id(char_u *name, buf_T *buf)
     static proptype_T *
 lookup_prop_type(char_u *name, buf_T *buf)
 {
-    proptype_T *type = find_prop(name, buf);
+    proptype_T *type = find_prop_type(name, buf);
 
     if (type == NULL)
-	type = find_prop(name, NULL);
+	type = find_prop_type(name, NULL);
     if (type == NULL)
 	semsg(_(e_type_not_exist), name);
     return type;
@@ -730,29 +725,62 @@ add_text_props(linenr_T lnum, textprop_T *text_props, int text_prop_count)
     curbuf->b_ml.ml_flags |= ML_LINE_DIRTY;
 }
 
+/*
+ * Function passed to qsort() for sorting proptype_T on pt_id.
+ */
+    static int
+compare_pt(const void *s1, const void *s2)
+{
+    proptype_T	*tp1 = *(proptype_T **)s1;
+    proptype_T	*tp2 = *(proptype_T **)s2;
+
+    return tp1->pt_id == tp2->pt_id ? 0 : tp1->pt_id < tp2->pt_id ? -1 : 1;
+}
+
     static proptype_T *
-find_type_by_id(hashtab_T *ht, int id)
+find_type_by_id(hashtab_T *ht, proptype_T ***array, int id)
 {
-    long	todo;
-    hashitem_T	*hi;
+    int low = 0;
+    int high;
 
     if (ht == NULL)
 	return NULL;
 
-    // TODO: Make this faster by keeping a list of types sorted on ID and use
-    // a binary search.
-
-    todo = (long)ht->ht_used;
-    for (hi = ht->ht_array; todo > 0; ++hi)
+    // Make the loopup faster by creating an array with pointers to
+    // hashtable entries, sorted on pt_id.
+    if (*array == NULL)
     {
-	if (!HASHITEM_EMPTY(hi))
-	{
-	    proptype_T *prop = HI2PT(hi);
+	long	    todo;
+	hashitem_T  *hi;
+	int	    i = 0;
 
-	    if (prop->pt_id == id)
-		return prop;
-	    --todo;
+	*array = ALLOC_MULT(proptype_T *, ht->ht_used);
+	if (*array == NULL)
+	    return NULL;
+	todo = (long)ht->ht_used;
+	for (hi = ht->ht_array; todo > 0; ++hi)
+	{
+	    if (!HASHITEM_EMPTY(hi))
+	    {
+		(*array)[i++] = HI2PT(hi);
+		--todo;
+	    }
 	}
+	qsort((void *)*array, ht->ht_used, sizeof(proptype_T *), compare_pt);
+    }
+
+    // binary search in the sorted array
+    high = ht->ht_used;
+    while (high > low)
+    {
+	int m = (high + low) / 2;
+
+	if ((*array)[m]->pt_id == id)
+	    return (*array)[m];
+	if ((*array)[m]->pt_id > id)
+	    high = m;
+	else
+	    low = m + 1;
     }
     return NULL;
 }
@@ -772,10 +800,11 @@ prop_fill_dict(dict_T *dict, textprop_T *prop, buf_T *buf)
     dict_add_number(dict, "start", !(prop->tp_flags & TP_FLAG_CONT_PREV));
     dict_add_number(dict, "end", !(prop->tp_flags & TP_FLAG_CONT_NEXT));
 
-    pt = find_type_by_id(buf->b_proptypes, prop->tp_type);
+    pt = find_type_by_id(buf->b_proptypes, &buf->b_proparray, prop->tp_type);
     if (pt == NULL)
     {
-	pt = find_type_by_id(global_proptypes, prop->tp_type);
+	pt = find_type_by_id(global_proptypes, &global_proparray,
+								prop->tp_type);
 	buflocal = FALSE;
     }
     if (pt != NULL)
@@ -796,9 +825,9 @@ text_prop_type_by_id(buf_T *buf, int id)
 {
     proptype_T *type;
 
-    type = find_type_by_id(buf->b_proptypes, id);
+    type = find_type_by_id(buf->b_proptypes, &buf->b_proparray, id);
     if (type == NULL)
-	type = find_type_by_id(global_proptypes, id);
+	type = find_type_by_id(global_proptypes, &global_proparray, id);
     return type;
 }
 
@@ -1523,7 +1552,7 @@ prop_type_set(typval_T *argvars, int add)
 	return;
     dict = argvars[1].vval.v_dict;
 
-    prop = find_prop(name, buf);
+    prop = find_prop_type(name, buf);
     if (add)
     {
 	hashtab_T **htp;
@@ -1539,7 +1568,16 @@ prop_type_set(typval_T *argvars, int add)
 	STRCPY(prop->pt_name, name);
 	prop->pt_id = ++proptype_id;
 	prop->pt_flags = PT_FLAG_COMBINE;
-	htp = buf == NULL ? &global_proptypes : &buf->b_proptypes;
+	if (buf == NULL)
+	{
+	    htp = &global_proptypes;
+	    VIM_CLEAR(global_proparray);
+	}
+	else
+	{
+	    htp = &buf->b_proptypes;
+	    VIM_CLEAR(buf->b_proparray);
+	}
 	if (*htp == NULL)
 	{
 	    *htp = ALLOC_ONE(hashtab_T);
@@ -1669,16 +1707,22 @@ f_prop_type_delete(typval_T *argvars, typval_T *rettv UNUSED)
 	    return;
     }
 
-    hi = find_prop_hi(name, buf);
+    hi = find_prop_type_hi(name, buf);
     if (hi != NULL)
     {
 	hashtab_T	*ht;
 	proptype_T	*prop = HI2PT(hi);
 
 	if (buf == NULL)
+	{
 	    ht = global_proptypes;
+	    VIM_CLEAR(global_proparray);
+	}
 	else
+	{
 	    ht = buf->b_proptypes;
+	    VIM_CLEAR(buf->b_proparray);
+	}
 	hash_remove(ht, hi);
 	vim_free(prop);
     }
@@ -1714,7 +1758,7 @@ f_prop_type_get(typval_T *argvars, typval_T *rettv)
 		return;
 	}
 
-	prop = find_prop(name, buf);
+	prop = find_prop_type(name, buf);
 	if (prop != NULL)
 	{
 	    dict_T *d = rettv->vval.v_dict;
@@ -1818,6 +1862,7 @@ clear_global_prop_types(void)
 {
     clear_ht_prop_types(global_proptypes);
     global_proptypes = NULL;
+    VIM_CLEAR(global_proparray);
 }
 #endif
 
@@ -1829,6 +1874,7 @@ clear_buf_prop_types(buf_T *buf)
 {
     clear_ht_prop_types(buf->b_proptypes);
     buf->b_proptypes = NULL;
+    VIM_CLEAR(buf->b_proparray);
 }
 
 // Struct used to return two values from adjust_prop().
diff --git a/src/version.c b/src/version.c
index be59f1be2e..bccf787ef8 100644
--- a/src/version.c
+++ b/src/version.c
@@ -736,6 +736,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    165,
+/**/
     164,
 /**/
     163,