Patch 9.0.0165

[Bram Moolenaar]

Patch 9.0.0165
Problem: Looking up a text property type by ID is slow.
Solution: Keep an array of property types sorted on ID.
Files: src/textprop.c, src/structs.h


*** ../vim-9.0.0164/src/textprop.c 2022-08-06 17:10:16.137025282 +0100
--- src/textprop.c 2022-08-07 18:18:45.104863461 +0100
***************
*** 11,22 ****
* 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
--- 11,16 ----
***************
*** 42,47 ****
--- 36,42 ----

// 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,57 ****
* Returns NULL if the item can't be found.
*/
static hashitem_T *
! find_prop_hi(char_u *name, buf_T *buf)
{
hashtab_T *ht;
hashitem_T *hi;
--- 46,52 ----
* Returns NULL if the item can't be found.
*/
static hashitem_T *
! find_prop_type_hi(char_u *name, buf_T *buf)
{
hashtab_T *ht;
hashitem_T *hi;
***************
*** 72,83 ****
}

/*
! * Like find_prop_hi() but return the property type.
*/
static proptype_T *
! find_prop(char_u *name, buf_T *buf)
{
! hashitem_T *hi = find_prop_hi(name, buf);

if (hi == NULL)
return NULL;
--- 67,78 ----
}

/*
! * Like find_prop_type_hi() but return the property type.
*/
static proptype_T *
! find_prop_type(char_u *name, buf_T *buf)
{
! hashitem_T *hi = find_prop_type_hi(name, buf);

if (hi == NULL)
return NULL;
***************
*** 91,97 ****
int
find_prop_type_id(char_u *name, buf_T *buf)
{
! proptype_T *pt = find_prop(name, buf);

if (pt == NULL)
return 0;
--- 86,92 ----
int
find_prop_type_id(char_u *name, buf_T *buf)
{
! proptype_T *pt = find_prop_type(name, buf);

if (pt == NULL)
return 0;
***************
*** 106,115 ****
static proptype_T *
lookup_prop_type(char_u *name, buf_T *buf)
{
! proptype_T *type = find_prop(name, buf);

if (type == NULL)
! type = find_prop(name, NULL);
if (type == NULL)
semsg(_(e_type_not_exist), name);
return type;
--- 101,110 ----
static proptype_T *
lookup_prop_type(char_u *name, buf_T *buf)
{
! proptype_T *type = find_prop_type(name, buf);

if (type == NULL)
! type = find_prop_type(name, NULL);
if (type == NULL)
semsg(_(e_type_not_exist), name);
return type;
***************
*** 730,758 ****
curbuf->b_ml.ml_flags |= ML_LINE_DIRTY;
}

static proptype_T *
! find_type_by_id(hashtab_T *ht, int id)
{
! long todo;
! hashitem_T *hi;

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)
{
! if (!HASHITEM_EMPTY(hi))
! {
! proptype_T *prop = HI2PT(hi);

! if (prop->pt_id == id)
! return prop;
! --todo;
! }
}
return NULL;
}
--- 725,786 ----
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, proptype_T ***array, int id)
{
! int low = 0;
! int high;

if (ht == NULL)
return NULL;

! // Make the loopup faster by creating an array with pointers to
! // hashtable entries, sorted on pt_id.
! if (*array == NULL)
! {
! long todo;
! hashitem_T *hi;
! int i = 0;
!
! *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,781 ****
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);
if (pt == NULL)
{
! pt = find_type_by_id(global_proptypes, prop->tp_type);
buflocal = FALSE;
}
if (pt != NULL)
--- 800,810 ----
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, &buf->b_proparray, prop->tp_type);
if (pt == NULL)
{
! pt = find_type_by_id(global_proptypes, &global_proparray,
! prop->tp_type);
buflocal = FALSE;
}
if (pt != NULL)
***************
*** 796,804 ****
{
proptype_T *type;

! type = find_type_by_id(buf->b_proptypes, id);
if (type == NULL)
! type = find_type_by_id(global_proptypes, id);
return type;
}

--- 825,833 ----
{
proptype_T *type;

! type = find_type_by_id(buf->b_proptypes, &buf->b_proparray, id);
if (type == NULL)
! type = find_type_by_id(global_proptypes, &global_proparray, id);
return type;
}

***************
*** 1523,1529 ****
return;
dict = argvars[1].vval.v_dict;

! prop = find_prop(name, buf);
if (add)
{
hashtab_T **htp;
--- 1552,1558 ----
return;
dict = argvars[1].vval.v_dict;

! prop = find_prop_type(name, buf);
if (add)
{
hashtab_T **htp;
***************
*** 1539,1545 ****
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 (*htp == NULL)
{
*htp = ALLOC_ONE(hashtab_T);
--- 1568,1583 ----
STRCPY(prop->pt_name, name);
prop->pt_id = ++proptype_id;
prop->pt_flags = PT_FLAG_COMBINE;
! 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,1684 ****
return;
}

! hi = find_prop_hi(name, buf);
if (hi != NULL)
{
hashtab_T *ht;
proptype_T *prop = HI2PT(hi);

if (buf == NULL)
ht = global_proptypes;
else
ht = buf->b_proptypes;
hash_remove(ht, hi);
vim_free(prop);
}
--- 1707,1728 ----
return;
}

! 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,1720 ****
return;
}

! prop = find_prop(name, buf);
if (prop != NULL)
{
dict_T *d = rettv->vval.v_dict;
--- 1758,1764 ----
return;
}

! prop = find_prop_type(name, buf);
if (prop != NULL)
{
dict_T *d = rettv->vval.v_dict;
***************
*** 1818,1823 ****
--- 1862,1868 ----
{
clear_ht_prop_types(global_proptypes);
global_proptypes = NULL;
+ VIM_CLEAR(global_proparray);
}
#endif

***************
*** 1829,1834 ****
--- 1874,1880 ----
{
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().
*** ../vim-9.0.0164/src/structs.h 2022-08-05 17:04:43.402914763 +0100
--- src/structs.h 2022-08-07 17:37:46.584158761 +0100
***************
*** 3084,3089 ****
--- 3084,3090 ----
#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

*** ../vim-9.0.0164/src/version.c 2022-08-07 18:09:05.769933098 +0100
--- src/version.c 2022-08-07 18:17:54.789320344 +0100
***************
*** 737,738 ****
--- 737,740 ----
{ /* Add new patch number below this line */
+ /**/
+ 165,
/**/

--
hundred-and-one symptoms of being an internet addict:
270. You are subscribed to a mailing list for every piece of software
you use.

/// Bram Moolenaar -- Br...@Moolenaar.net -- http://www.Moolenaar.net \\\
/// \\\
\\\ sponsor Vim, vote for features -- http://www.Vim.org/sponsor/ ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///