tag: try not to reallocate tag.items in every add() call

If many tag_items are added at once while the tag cache is being
loaded, manage these items in a static fixed list, instead of
reallocating the list with every newly created item.  This reduces
heap fragmentation.

Massif results again:

 mk before:  total 12,837,632; useful 10,626,383; extra 2,211,249
 mk now:     total 12,736,720; useful 10,626,383; extra 2,110,337

The "useful" value is the same since this patch only changes the way
we allocate the same amount of memory, but heap fragmentation was
reduced by 5%.

3 files changed, 91 insertions, 7 deletions

diff --git a/src/song.c b/src/song.c
index f7e71d76f..8651a0100 100644
--- a/src/song.c
+++ b/src/song.c
@@ -240,9 +240,12 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 
 	while (myFgets(buffer, bufferSize, fp) && 0 != strcmp(SONG_END, buffer)) {
 		if (0 == strncmp(SONG_KEY, buffer, strlen(SONG_KEY))) {
-			if (song)
+			if (song) {
 				insertSongIntoList(list, &nextSongNode,
 						   song->url, song);
+				if (song->tag != NULL)
+					tag_end_add(song->tag);
+			}
 
 			song = newNullSong();
 			song->url = xstrdup(buffer + strlen(SONG_KEY));
@@ -257,15 +260,21 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 			   song->url = xstrdup(&(buffer[strlen(SONG_FILE)]));
 			 */
 		} else if (matchesAnMpdTagItemKey(buffer, &itemType)) {
-			if (!song->tag)
+			if (!song->tag) {
 				song->tag = tag_new();
+				tag_begin_add(song->tag);
+			}
+
 			tag_add_item(song->tag, itemType,
 				     &(buffer
 				       [strlen(mpdTagItemKeys[itemType]) +
 					2]));
 		} else if (0 == strncmp(SONG_TIME, buffer, strlen(SONG_TIME))) {
-			if (!song->tag)
+			if (!song->tag) {
 				song->tag = tag_new();
+				tag_begin_add(song->tag);
+			}
+
 			song->tag->time = atoi(&(buffer[strlen(SONG_TIME)]));
 		} else if (0 == strncmp(SONG_MTIME, buffer, strlen(SONG_MTIME))) {
 			song->mtime = atoi(&(buffer[strlen(SONG_MTIME)]));
@@ -274,8 +283,11 @@ void readSongInfoIntoList(FILE * fp, SongList * list, Directory * parentDir)
 			FATAL("songinfo: unknown line in db: %s\n", buffer);
 	}
 
-	if (song)
+	if (song) {
 		insertSongIntoList(list, &nextSongNode, song->url, song);
+		if (song->tag != NULL)
+			tag_end_add(song->tag);
+	}
 
 	while (nextSongNode) {
 		nodeTemp = nextSongNode->nextNode;
diff --git a/src/tag.c b/src/tag.c
index a27417554..f9dc767f2 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -361,6 +361,53 @@ static inline const char *fix_utf8(const char *str, size_t *length_r) {
 	return temp;
 }
 
+/**
+ * Maximum number of items managed in the bulk list; if it is
+ * exceeded, we switch back to "normal" reallocation.
+ */
+#define BULK_MAX 64
+
+static struct {
+#ifndef NDEBUG
+	int busy;
+#endif
+	struct tag_item *items[BULK_MAX];
+} bulk;
+
+void tag_begin_add(struct tag *tag)
+{
+	assert(!bulk.busy);
+	assert(tag != NULL);
+	assert(tag->items == NULL);
+	assert(tag->numOfItems == 0);
+
+#ifndef NDEBUG
+	bulk.busy = 1;
+#endif
+	tag->items = bulk.items;
+}
+
+void tag_end_add(struct tag *tag)
+{
+	if (tag->items == bulk.items) {
+		assert(tag->numOfItems <= BULK_MAX);
+
+		if (tag->numOfItems > 0) {
+			/* copy the tag items from the bulk list over
+			   to a new list (which fits exactly) */
+			tag->items = xmalloc(tag->numOfItems *
+					     sizeof(tag->items[0]));
+			memcpy(tag->items, bulk.items,
+			       tag->numOfItems * sizeof(tag->items[0]));
+		} else
+			tag->items = NULL;
+	}
+
+#ifndef NDEBUG
+	bulk.busy = 0;
+#endif
+}
+
 static void appendToTagItems(struct tag *tag, enum tag_type type,
 			     const char *value, size_t len)
 {
@@ -380,8 +427,19 @@ static void appendToTagItems(struct tag *tag, enum tag_type type,
 	}
 
 	tag->numOfItems++;
-	tag->items = xrealloc(tag->items,
-			      tag->numOfItems * sizeof(*tag->items));
+
+	if (tag->items != bulk.items)
+		/* bulk mode disabled */
+		tag->items = xrealloc(tag->items,
+				      tag->numOfItems * sizeof(*tag->items));
+	else if (tag->numOfItems >= BULK_MAX) {
+		/* bulk list already full - switch back to non-bulk */
+		assert(bulk.busy);
+
+		tag->items = xmalloc(tag->numOfItems * sizeof(tag->items[0]));
+		memcpy(tag->items, bulk.items,
+		       (tag->numOfItems - 1) * sizeof(tag->items[0]));
+	}
 
 	tag->items[i] = tag_pool_get_item(type, p, len);
 
diff --git a/src/tag.h b/src/tag.h
index 21dbfa487..11a123089 100644
--- a/src/tag.h
+++ b/src/tag.h
@@ -61,8 +61,22 @@ void tag_clear_items_by_type(struct tag *tag, enum tag_type itemType);
 
 void tag_free(struct tag *tag);
 
+/**
+ * Gives an optional hint to the tag library that we will now add
+ * several tag items; this is used by the library to optimize memory
+ * allocation.  Only one tag may be in this state, and this tag must
+ * not have any items yet.  You must call tag_end_add() when you are
+ * done.
+ */
+void tag_begin_add(struct tag *tag);
+
+/**
+ * Finishes the operation started with tag_begin_add().
+ */
+void tag_end_add(struct tag *tag);
+
 void tag_add_item_n(struct tag *tag, enum tag_type itemType,
-			    const char *value, size_t len);
+		    const char *value, size_t len);
 
 static inline void tag_add_item(struct tag *tag, enum tag_type itemType,
 				const char *value)