From e4fa1d2f6b8721318c0f104f2615588b5d4e0441 Mon Sep 17 00:00:00 2001 From: Damjan Marion Date: Mon, 11 Apr 2022 18:41:49 +0200 Subject: vppinfra: vector perf improvements Type: improvement Change-Id: I37c187af80c21b8fb1ab15af112527a837e0df9e Signed-off-by: Damjan Marion --- src/vppinfra/vec.h | 204 ++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 155 insertions(+), 49 deletions(-) (limited to 'src/vppinfra/vec.h') 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); -- cgit 1.2.3-korg