* util/vector: hoist quicksort scratch buffers out of the recursion
vector_quick_sort allocated its two element-sized scratch buffers (t and
pivot) with malloc/free on every recursive call. For a vector of n elements
the sort makes O(n) recursive calls, i.e. O(n) malloc/free pairs purely for
scratch space, and each call could also fail half-way through the sort.
Split the function into a small entry point that allocates the two buffers
once and a recursive worker that receives them as scratch. The buffers are
reused across the whole recursion (each partition step finishes using them
before recursing, and the recursion is sequential, so sharing one pair is
safe). Small elements -- the common case, including every RzPVector-backed
sort -- use stack buffers and allocate nothing at all; only elements larger
than 256 bytes fall back to a single heap allocation for the whole sort.
The element movement and rand()-based pivot selection are unchanged, so the
result is identical for any input (verified byte-for-byte against the previous
implementation for ascending and descending orders over many random arrays).
* util/vector: evaluate the comparator once per element in the quicksort
The partition loop tested the element against the pivot with two separate
calls to the comparator:
if ((cmp(VEC_INDEX(a, i), pivot, user) < 0 && !reverse) ||
(cmp(VEC_INDEX(a, i), pivot, user) > 0 && reverse)) {
Because cmp is an opaque function pointer the compiler cannot common up the
two calls, so depending on the result and the reverse flag the comparator was
invoked up to twice per element. Compute the result once into a local and test
that:
int c = cmp(VEC_INDEX(a, i), pivot, user);
if ((c < 0 && !reverse) || (c > 0 && reverse)) {
This halves comparator calls in the worst case and is a clear win whenever the
comparator is non-trivial (the common case for struct elements). Measured on a
shared host: ~12-14% faster for int sorting and ~30% faster with a moderately
expensive comparator. The ordering is unchanged (verified byte-for-byte).
* util/vector: simplify rz_pvector_remove_data index computation
The index of the located slot was computed as
size_t index = (el - (void **)vec->v.a) * sizeof(void **) / vec->v.elem_size;
For an RzPVector the element size is always sizeof(void *), so the
`* sizeof(void **) / vec->v.elem_size` factor is identically 1 and the pointer
difference `el - (void **)vec->v.a` already yields the index directly. Drop the
redundant scaling, which removes a multiply and a divide and makes the intent
clear. Behaviour is unchanged.
* test/unit: add RzVector sort and rz_pvector_remove_data regression tests
The existing sort tests only sort 4-5 small elements and there was no test for
rz_pvector_remove_data. Add coverage for the code paths exercised by the sort
changes and the remove_data cleanup:
- test_vector_sort_large sort 2000 heavily-duplicated ut32 values
ascending and descending, verifying the result
is ordered and a permutation of the input (vs a
reference qsort). Drives the recursion deeply
and the shared scratch buffers.
- test_vector_sort_large_elem sort 400 elements of 304 bytes each, taking the
heap-allocated scratch fallback, and check the
full payload (not just the key) stays consistent
through all the element moves.
- test_pvector_remove_data remove interior, first and last elements by
value while preserving order, and confirm
removing an absent value is a no-op.
All pass on both the previous and the optimized implementation (the sort and
remove_data changes are behaviour-preserving).
* test/bench: benchmark rz_vector_sort and rz_pvector_sort
bench_vector.c benchmarked only remove_at and swap. Add sort benchmarks so the
suite covers the functions touched by the sort optimizations and can be run
against the old and new librz for before/after numbers:
- rz_vector_sort over 4k ut64 with a cheap comparator
- rz_vector_sort over 4k ut64 with a deliberately expensive comparator
(shows the effect of evaluating the comparator once per element)
- rz_pvector_sort over 4k pointers (reference; pvector sort is unchanged)
Each iteration refills the buffer from an unsorted master copy via a single
memcpy before sorting; that overhead is identical across builds so the measured
delta reflects the sort.
---------
Co-authored-by: Anton Kochkov <anton.kochkov@gmail.com>
* Fix revert if adding a node failed.
* Reduce allocations by keeping only a single RzGraphEdge object per edge around.
* Add benchmark for graph deletion and addition of nodes/edges
* Use rz_pvector_remove_at_unsorted to save some runtime.
* Use realloc and memmove for matrix graphs on capacity increase.
* Add helper to determine memory usage.
* Add benchmark
* Revert matrix capacity extension to simple and jsut as fast loop.
* Missing type annotations
* Add option to replace (geometric) invalid values with another value.
* Add geometric Mean and Std Dev to benchmarks.
* Add Doxygen documentation
* Add a README to the bench dir as intro.
* Add Welfords square of sums algorithm for variance and std deviation calculations.
* Add standard deviation to benchmarks
* Simplify Welford
* Add geometric mean and standard deviation to Welford Sums
* Add order ignoring remove_at version with better performance.
* Optimize rz_vector_swap by using stack memory for small elements.
* Add benchmark for rz_vector_swap
* Build the benchmarks as part of 'linux-meson-gcc-tests' step
* Fix bench_il build error
* Add macro to avoid compiler optimization on benchmarked code
* Fix incorrect format specifier
* Cast to uint64_t
* Add ht benchmarks
* Initial implementation
* Finalize native per-group lookup support
* Lookup SSE2 implementation
* Improve hashing
* Add support for custom elem_size
* Avoid double h2 hashing when reserving slot
* Make custom elem_size support conditional
* Fix issues with bitwise and default lookup implementations
* Implement deletion trick optimization
* Track growth_size instead of deleted_slots
* Refactor SDB to access ht via API instead of internals
* Modify SDB tests which rely on hashtable order
* Fix SDB build warnings
* Fix bug with finding next power of two
* foreach_kv to return a bool result
* Change SDB diff order expected by serialize_analysis unit test
* Fix bug in the bitwise lookup implementation
* Remove second call to rz_core_init() which causes memory leaks
* Update some regression tests to accept reordered output
* Adapt ht clear to new implementation
* Use fini_kv_pair and fix 1 potential leak on malloc failure
* Fix cmd/types test after merge
* Avoid second call to calsize_key and avoid iter leaks on malloc failure
* Improve hash distribution
* Extend benchmark suite
* Fix bug with string hashing
* Branchless write to mirrored ctrl bytes
* Simplify string hash and remove potential UB
* Move RZ_PREFETCH macro to rz_types.h
* Add SSE2 discovery in Meson
* Forward SDB string hash function to ht string hash
* Try to revert test_cpu_profiles() to avoid relying on a baked SDB file
* Revert SDB/CDB hash function change
* Fix SDB reference to HT hash function instead of CDB hash
* Change calloc to malloc
* Avoid storing/checking key_len and key_value if they are ut64
* Improve string hash function
* Rename default hash functions
* Improve bench code
* linter.yml: set clang-path to point to llvm-18
* Add an in-place addition of bitvectors.
* Decouple _elem_len from assumption it has just enough bytes to hold len in bits.
* Add in-place copy of bits.
* Use default copy bits bitvector function.
* Mark stack allocated bit vector.
* Add inplace variant of complement_1
* Implement inplace bitvecotr not.
* Add inplace variant of rz_bv_and
* Implement inplace variant of rz_bv_or
* Implement inplace variant of rz_bv_xor
* Constify rz_bv_lsb/msb
* Implement inplace variant of rz_bv_neg
* Fix inplace add. Add inplace SUB
* Remove prefix
* Remove invalid const
* Implement in-place casting of bit vectors.
* Add a hash test
* Fix unnecessary &
* Prevent OOB reads & writes by copying only the minimum of bytes.
* Add inplace MUL
* Add ble version for bitvector set/get with bytes.
* Add documentation for inplace bitvector functions.
* Add bench of add/sub() and sub/add_inplace().
* Remove rz_bv_copy_nbits_inplace because it was the same as rz_bv_copy_nbits.
* Add benchmark for rz_bv_copy_nbits
* Improve performance for large to large and small to small bitvector copy
* Fix bug with nbit=64 and simplify code
* Add test for same bitvector copy
* Move bit copy logic to separate function in rz_bits.h + improve comments
* Support same vector copy for unaligned case
* Expect non-null RzTable in bench utils and add comments
* Test against reference implementation instead of hardcoded values
