summaryrefslogtreecommitdiffstats
path: root/src/vppinfra/vec.h
diff options
context:
space:
mode:
authorDamjan Marion <damarion@cisco.com>2022-04-11 18:41:49 +0200
committerFlorin Coras <florin.coras@gmail.com>2022-04-12 22:40:52 +0000
commite4fa1d2f6b8721318c0f104f2615588b5d4e0441 (patch)
tree70d33a24bae0b9aa993fe6e03960e2b135accb70 /src/vppinfra/vec.h
parent65e770d895b13a6e5c73d13f436872ea626e47e3 (diff)
vppinfra: vector perf improvements
Type: improvement Change-Id: I37c187af80c21b8fb1ab15af112527a837e0df9e Signed-off-by: Damjan Marion <damarion@cisco.com>
Diffstat (limited to 'src/vppinfra/vec.h')
-rw-r--r--src/vppinfra/vec.h204
1 files changed, 155 insertions, 49 deletions
diff --git a/src/vppinfra/vec.h b/src/vppinfra/vec.h
index bfb7b1b7fc6..f45f45e3388 100644
--- a/src/vppinfra/vec.h
+++ b/src/vppinfra/vec.h
@@ -101,8 +101,20 @@
@param align alignment (may be zero)
@return v_prime pointer to resized vector, may or may not equal v
*/
-void *_vec_realloc (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
- uword align, void *heap);
+
+typedef struct
+{
+ void *heap;
+ u32 elt_sz;
+ u16 hdr_sz;
+ u16 align;
+} vec_attr_t;
+
+void *_vec_alloc_internal (uword n_elts, const vec_attr_t *const attr);
+void *_vec_realloc_internal (void *v, uword n_elts,
+ const vec_attr_t *const attr);
+void *_vec_resize_internal (void *v, uword n_elts,
+ const vec_attr_t *const attr);
/* calculate minimum alignment out of data natural alignment and provided
* value, should not be < VEC_MIN_ALIGN */
@@ -139,36 +151,24 @@ vec_get_heap (void *v)
return _vec_heap (v);
}
-static_always_inline void *
-_vec_realloc_inline (void *v, uword n_elts, uword elt_sz, uword hdr_sz,
- uword align, void *heap)
+static_always_inline uword
+vec_get_align (void *v)
{
- if (PREDICT_TRUE (v != 0))
- {
- /* Vector header must start heap object. */
- ASSERT (clib_mem_heap_is_heap_object (vec_get_heap (v), vec_header (v)));
-
- /* Typically we'll not need to resize. */
- if ((n_elts * elt_sz) <= vec_max_bytes (v))
- {
- _vec_set_len (v, n_elts, elt_sz);
- return v;
- }
- }
-
- /* Slow path: call helper function. */
- return _vec_realloc (v, n_elts, elt_sz, hdr_sz, align, heap);
+ return 1ULL << _vec_find (v)->log2_align;
}
static_always_inline void
_vec_prealloc (void **vp, uword n_elts, uword hdr_sz, uword align, void *heap,
uword elt_sz)
{
+ const vec_attr_t va = {
+ .elt_sz = elt_sz, .hdr_sz = hdr_sz, .align = align, .heap = heap
+ };
void *v;
ASSERT (vp[0] == 0);
- v = _vec_realloc (0, n_elts, elt_sz, hdr_sz, align, heap);
+ v = _vec_alloc_internal (n_elts, &va);
_vec_set_len (v, 0, elt_sz);
_vec_update_pointer (vp, v);
}
@@ -247,9 +247,26 @@ _vec_resize_will_expand (void *v, uword n_elts, uword elt_sz)
static_always_inline void
_vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
{
- void *v = vp[0];
- v = _vec_realloc_inline (v, vec_len (v) + n_add, elt_sz, hdr_sz, align, 0);
- _vec_update_pointer (vp, v);
+ void *v = *vp;
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = _vec_alloc_internal (n_add, &va);
+ return;
+ }
+
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, _vec_len (v) + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, _vec_len (v) + n_add, elt_sz);
}
#define vec_resize_ha(V, N, H, A) \
@@ -324,7 +341,10 @@ _vec_resize (void **vp, uword n_add, uword hdr_sz, uword align, uword elt_sz)
@return V new vector
*/
#define vec_new_generic(T, N, H, A, P) \
- _vec_realloc (0, N, sizeof (T), H, _vec_align ((T *) 0, A), P)
+ _vec_alloc_internal (N, &((vec_attr_t){ .align = _vec_align ((T *) 0, A), \
+ .hdr_sz = (H), \
+ .heap = (P), \
+ .elt_sz = sizeof (T) }))
/** \brief Create new vector of given type and length
(unspecified alignment, no header).
@@ -390,11 +410,12 @@ static_always_inline void *
_vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
{
uword len = vec_len (v);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
void *n = 0;
if (len)
{
- n = _vec_realloc (0, len, elt_sz, hdr_size, align, 0);
+ n = _vec_alloc_internal (len, &va);
clib_memcpy_fast (n, v, len * elt_sz);
}
return n;
@@ -438,7 +459,8 @@ _vec_dup (void *v, uword hdr_size, uword align, uword elt_sz)
static_always_inline void
_vec_clone (void **v1p, void *v2, uword align, uword elt_sz)
{
- v1p[0] = _vec_realloc (0, vec_len (v2), elt_sz, 0, align, 0);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align };
+ v1p[0] = _vec_alloc_internal (vec_len (v2), &va);
}
#define vec_clone(NEW_V, OLD_V) \
_vec_clone ((void **) &(NEW_V), OLD_V, _vec_align (NEW_V, 0), \
@@ -464,14 +486,35 @@ static_always_inline void
_vec_validate (void **vp, uword index, uword header_size, uword align,
void *heap, uword elt_sz)
{
- void *v = vp[0];
- uword vl = vec_len (v);
- if (index >= vl)
+ void *v = *vp;
+ uword vl, n_elts = index + 1;
+
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = header_size };
+ *vp = _vec_alloc_internal (n_elts, &va);
+ return;
+ }
+
+ vl = _vec_len (v);
+
+ if (PREDICT_FALSE (index < vl))
+ return;
+
+ if (PREDICT_FALSE (index >= _vec_find (v)->grow_elts + vl))
{
- v = _vec_realloc_inline (v, index + 1, elt_sz, header_size, align, heap);
- _vec_zero_elts (v, vl, index - vl + 1, elt_sz);
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = header_size };
+ v = _vec_resize_internal (v, n_elts, &va);
_vec_update_pointer (vp, v);
}
+ else
+ _vec_set_len (v, n_elts, elt_sz);
+
+ _vec_zero_elts (v, vl, n_elts - vl, elt_sz);
}
#define vec_validate_hap(V, I, H, A, P) \
@@ -572,10 +615,28 @@ static_always_inline void *
_vec_add1 (void **vp, uword hdr_sz, uword align, uword elt_sz)
{
void *v = vp[0];
- uword len = vec_len (v);
- v = _vec_realloc_inline (v, len + 1, elt_sz, hdr_sz, align, 0);
+ uword len;
- _vec_update_pointer (vp, v);
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ return *vp = _vec_alloc_internal (1, &va);
+ }
+
+ len = _vec_len (v);
+
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + 1, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + 1, elt_sz);
return v + len * elt_sz;
}
@@ -616,11 +677,31 @@ static_always_inline void
_vec_add2 (void **vp, void **pp, uword n_add, uword hdr_sz, uword align,
uword elt_sz)
{
- void *v = vp[0];
- uword len = vec_len (vp[0]);
- v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
- _vec_update_pointer (vp, v);
- pp[0] = v + len * elt_sz;
+ void *v = *vp;
+ uword len;
+
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = *pp = _vec_alloc_internal (n_add, &va);
+ return;
+ }
+
+ len = _vec_len (v);
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + n_add, elt_sz);
+
+ *pp = v + len * elt_sz;
}
#define vec_add2_ha(V, P, N, H, A) \
@@ -663,17 +744,38 @@ static_always_inline void
_vec_add (void **vp, void *e, word n_add, uword hdr_sz, uword align,
uword elt_sz)
{
- void *v = vp[0];
- uword len = vec_len (v);
+ void *v = *vp;
+ uword len;
ASSERT (n_add >= 0);
if (n_add < 1)
return;
- v = _vec_realloc_inline (v, len + n_add, elt_sz, hdr_sz, align, 0);
+ if (PREDICT_FALSE (v == 0))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ *vp = v = _vec_alloc_internal (n_add, &va);
+ clib_memcpy_fast (v, e, n_add * elt_sz);
+ return;
+ }
+
+ len = _vec_len (v);
+
+ if (PREDICT_FALSE (_vec_find (v)->grow_elts < n_add))
+ {
+ const vec_attr_t va = { .elt_sz = elt_sz,
+ .align = align,
+ .hdr_sz = hdr_sz };
+ v = _vec_resize_internal (v, len + n_add, &va);
+ _vec_update_pointer (vp, v);
+ }
+ else
+ _vec_set_len (v, len + n_add, elt_sz);
+
clib_memcpy_fast (v + len * elt_sz, e, n_add * elt_sz);
- _vec_update_pointer (vp, v);
}
#define vec_add_ha(V, E, N, H, A) \
@@ -747,11 +849,12 @@ _vec_insert (void **vp, uword n_insert, uword ins_pt, u8 init, uword hdr_sz,
{
void *v = vp[0];
uword len = vec_len (v);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
ASSERT (ins_pt <= len);
- v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
- clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
+ v = _vec_resize_internal (v, len + n_insert, &va);
+ clib_memmove (v + va.elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
(len - ins_pt) * elt_sz);
_vec_zero_elts (v, ins_pt, n_insert, elt_sz);
_vec_update_pointer (vp, v);
@@ -839,10 +942,11 @@ _vec_insert_elts (void **vp, void *e, uword n_insert, uword ins_pt,
{
void *v = vp[0];
uword len = vec_len (v);
+ const vec_attr_t va = { .elt_sz = elt_sz, .align = align, .hdr_sz = hdr_sz };
ASSERT (ins_pt <= len);
- v = _vec_realloc_inline (v, len + n_insert, elt_sz, hdr_sz, align, 0);
+ v = _vec_resize_internal (v, len + n_insert, &va);
clib_memmove (v + elt_sz * (ins_pt + n_insert), v + ins_pt * elt_sz,
(len - ins_pt) * elt_sz);
_vec_zero_elts (v, ins_pt, n_insert, elt_sz);
@@ -938,7 +1042,8 @@ _vec_append (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
if (PREDICT_TRUE (len2 > 0))
{
- v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
+ const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
+ v1 = _vec_resize_internal (v1, len1 + len2, &va);
clib_memcpy_fast (v1 + len1 * v1_elt_sz, v2, len2 * v2_elt_sz);
_vec_update_pointer (v1p, v1);
}
@@ -971,7 +1076,8 @@ _vec_prepend (void **v1p, void *v2, uword v1_elt_sz, uword v2_elt_sz,
if (PREDICT_TRUE (len2 > 0))
{
- v1 = _vec_realloc_inline (v1, len1 + len2, v2_elt_sz, 0, align, 0);
+ const vec_attr_t va = { .elt_sz = v2_elt_sz, .align = align };
+ v1 = _vec_resize_internal (v1, len1 + len2, &va);
clib_memmove (v1 + len2 * v2_elt_sz, v1p[0], len1 * v1_elt_sz);
clib_memcpy_fast (v1, v2, len2 * v2_elt_sz);
_vec_update_pointer (v1p, v1);