patch 9.0.0165: looking up a text property type by ID is slow
Problem: Looking up a text property type by ID is slow.
Solution: Keep an array of property types sorted on ID.
diff --git a/src/textprop.c b/src/textprop.c
index 8670c87..6795353 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 @@
* 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 @@
}
/*
- * 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 @@
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 @@
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 @@
curbuf->b_ml.ml_flags |= ML_LINE_DIRTY;
}
- static proptype_T *
-find_type_by_id(hashtab_T *ht, int id)
+/*
+ * Function passed to qsort() for sorting proptype_T on pt_id.
+ */
+ static int
+compare_pt(const void *s1, const void *s2)
{
- long todo;
- hashitem_T *hi;
+ 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, proptype_T ***array, int id)
+{
+ 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 @@
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 @@
{
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 @@
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 @@
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 @@
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 @@
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_ht_prop_types(global_proptypes);
global_proptypes = NULL;
+ VIM_CLEAR(global_proparray);
}
#endif
@@ -1829,6 +1874,7 @@
{
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().