commit eb4adfd9ef8f9c4e46c77c5178fd19ad1b914544
from: Mark Jamsek <mark@jamsek.dev>
date: Mon Aug 01 04:20:59 2022 UTC

sync files from diff.git 3a15e1807a369c0a7827363eca22c9f1a8598d9c

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 - 94b80cfa87e0bfc8933b9e7614974209e87de290
commit + eb4adfd9ef8f9c4e46c77c5178fd19ad1b914544
blob - 112da0c2e234000d38b2dea5c3b1112fa045b7a0
blob + 8b503d2f97ddd5ce74010697dc9c40b1e8a4b7af
--- lib/arraylist.h
+++ lib/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; \
 		}; \