commit 9ebd31ec452c4cce92a00cf8031c063393bf9fd7
from: Mark Jamsek <mark@jamsek.dev>
via: Thomas Adam <thomas@xteddy.org>
date: Sat Aug 06 20:57:41 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 - 07dd3ed35a32846bee5a7e36c2423eb8b404b9e3
commit + 9ebd31ec452c4cce92a00cf8031c063393bf9fd7
blob - e40991a834713fea7cac5b9d536165249b00acc4
blob + 45fff0814875e571893213a65e3e72727d12a116
--- lib/arraylist.h
+++ lib/arraylist.h
@@ -66,14 +66,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; \
 		}; \