Commit Diff
Diff:
ed9312f04bcebc7aee4f7e7d96d6ec467cb9bb66
3a15e1807a369c0a7827363eca22c9f1a8598d9c
Commit:
3a15e1807a369c0a7827363eca22c9f1a8598d9c
Tree:
2c67cd45cf72ba51c293f05711dc86f78961fac3
Author:
Mark Jamsek <mark@jamsek.dev>
Date:
Mon Aug 1 04:16:18 2022 UTC
Message:
ARRAY_LIST allocation optimisation

Rather than realloc in fixed-sized blocks, use the 1.5 * allocated scheme
when growing the array. This produces fewer allocations and up to 3x speedup
on large diffs.

ok stsp@
commit - ed9312f04bcebc7aee4f7e7d96d6ec467cb9bb66
commit + 3a15e1807a369c0a7827363eca22c9f1a8598d9c
blob - 112da0c2e234000d38b2dea5c3b1112fa045b7a0
blob + 8b503d2f97ddd5ce74010697dc9c40b1e8a4b7af
--- include/arraylist.h
+++ include/arraylist.h
@@ -63,14 +63,18 @@
(ARRAY_LIST).p = recallocarray((ARRAY_LIST).head, \
(ARRAY_LIST).len, \
(ARRAY_LIST).allocated + \
- ((ARRAY_LIST).alloc_blocksize ? : 8), \
+ ((ARRAY_LIST).allocated ? \
+ (ARRAY_LIST).allocated / 2 : \
+ (ARRAY_LIST).alloc_blocksize ? : 8), \
sizeof(*(ARRAY_LIST).head)); \
if ((ARRAY_LIST).p == NULL) { \
NEW_ITEM_P = NULL; \
break; \
} \
(ARRAY_LIST).allocated += \
- (ARRAY_LIST).alloc_blocksize ? : 8; \
+ (ARRAY_LIST).allocated ? \
+ (ARRAY_LIST).allocated / 2 : \
+ (ARRAY_LIST).alloc_blocksize ? : 8, \
(ARRAY_LIST).head = (ARRAY_LIST).p; \
(ARRAY_LIST).p = NULL; \
}; \
Omar Polo