commit 3a15e1807a369c0a7827363eca22c9f1a8598d9c
from: Mark Jamsek <mark@jamsek.dev>
date: Mon Aug 01 04:16:18 2022 UTC

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; \
 		}; \