Add a new constructor for empty XArrays, VG_(newSizedXA). This is
identical to VG_(newXA) but allows passing in a size hint. In the
case where the likely final size of the XArray is known at creation
time, this allows avoiding the repeated (implicit) resizing and
copying of the array as elements are added, which can save a vast
amount of dynamic memory allocation turnover.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@11568 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/coregrind/m_xarray.c b/coregrind/m_xarray.c
index cdcf978..4dc8ebd 100644
--- a/coregrind/m_xarray.c
+++ b/coregrind/m_xarray.c
@@ -44,6 +44,7 @@
Int (*cmpFn) ( void*, void* ); /* cmp fn (may be NULL) */
Word elemSzB; /* element size in bytes */
void* arr; /* pointer to elements */
+ Word initsizeE; /* HINT only: initial size, 0 if no hint */
Word usedsizeE; /* # used elements in arr */
Word totsizeE; /* max size of arr, in elements */
Bool sorted; /* is it sorted? */
@@ -72,6 +73,7 @@
xa->free = free_fn;
xa->cmpFn = NULL;
xa->elemSzB = elemSzB;
+ xa->initsizeE = 0;
xa->usedsizeE = 0;
xa->totsizeE = 0;
xa->sorted = False;
@@ -79,6 +81,19 @@
return xa;
}
+XArray* VG_(newSizedXA) ( void*(*alloc_fn)(HChar*,SizeT),
+ HChar* cc,
+ void(*free_fn)(void*),
+ Word elemSzB,
+ Word nInitialElems )
+{
+ XArray* xa;
+ tl_assert(nInitialElems >= 0);
+ xa = VG_(newXA)( alloc_fn, cc, free_fn, elemSzB );
+ xa->initsizeE = nInitialElems;
+ return xa;
+}
+
XArray* VG_(cloneXA)( HChar* cc, XArray* xao )
{
struct _XArray* xa = (struct _XArray*)xao;
@@ -145,7 +160,7 @@
static inline void ensureSpaceXA ( struct _XArray* xa )
{
- if (xa->usedsizeE == xa->totsizeE) {
+ if (UNLIKELY(xa->usedsizeE == xa->totsizeE)) {
void* tmp;
Word newsz;
if (xa->totsizeE == 0)
@@ -158,7 +173,11 @@
Hence increase the initial array size for tiny elements in
an attempt to avoid reallocations of size 2, 4, 8 if the
array does start to fill up. */
- if (xa->elemSzB == 1) newsz = 8;
+ /* Also, if there's a hinted initial size, use that instead of
+ the logic in the preceding comment. */
+ tl_assert(xa->initsizeE >= 0);
+ if (xa->initsizeE > 0) newsz = xa->initsizeE;
+ else if (xa->elemSzB == 1) newsz = 8;
else if (xa->elemSzB == 2) newsz = 4;
else newsz = 2;
} else {
diff --git a/include/pub_tool_xarray.h b/include/pub_tool_xarray.h
index cd1b02e..ff8dfb3 100644
--- a/include/pub_tool_xarray.h
+++ b/include/pub_tool_xarray.h
@@ -54,6 +54,17 @@
void(*free_fn)(void*),
Word elemSzB );
+/* Same as VG_(newXA), except allows specification of an initial
+ number of elements for the array, so as to avoid a potentially
+ large wasted cost of repeatedly resizing the array when the caller
+ knows something about what the expected final size is going to
+ be. */
+extern XArray* VG_(newSizedXA) ( void*(*alloc_fn)(HChar*,SizeT),
+ HChar* cc,
+ void(*free_fn)(void*),
+ Word elemSzB,
+ Word nInitialElems );
+
/* Free all memory associated with an XArray. */
extern void VG_(deleteXA) ( XArray* );