[Bf-blender-cvs] [1524f414dbd] master: BLI: optimize GSQueue implementation to allocate in chunks, like BLI_Stack
Brecht Van Lommel
noreply at git.blender.org
Tue Oct 1 16:15:14 CEST 2019
Commit: 1524f414dbd5ac536019223c0ef54b3c8676e465
Author: Brecht Van Lommel
Date: Tue Oct 1 11:13:28 2019 +0200
Branches: master
https://developer.blender.org/rB1524f414dbd5ac536019223c0ef54b3c8676e465
BLI: optimize GSQueue implementation to allocate in chunks, like BLI_Stack
===================================================================
M source/blender/blenlib/BLI_gsqueue.h
M source/blender/blenlib/intern/gsqueue.c
===================================================================
diff --git a/source/blender/blenlib/BLI_gsqueue.h b/source/blender/blenlib/BLI_gsqueue.h
index 72cd5c7f4ec..4bd53dfddbe 100644
--- a/source/blender/blenlib/BLI_gsqueue.h
+++ b/source/blender/blenlib/BLI_gsqueue.h
@@ -27,12 +27,10 @@
typedef struct _GSQueue GSQueue;
GSQueue *BLI_gsqueue_new(size_t elem_size);
-bool BLI_gsqueue_is_empty(GSQueue *gq);
-int BLI_gsqueue_len(GSQueue *gq);
-void BLI_gsqueue_peek(GSQueue *gq, void *r_item);
+bool BLI_gsqueue_is_empty(const GSQueue *gq);
+size_t BLI_gsqueue_len(const GSQueue *gq);
void BLI_gsqueue_pop(GSQueue *gq, void *r_item);
void BLI_gsqueue_push(GSQueue *gq, const void *item);
-void BLI_gsqueue_push_back(GSQueue *gq, const void *item);
void BLI_gsqueue_free(GSQueue *gq);
#endif /* __BLI_GSQUEUE_H__ */
diff --git a/source/blender/blenlib/intern/gsqueue.c b/source/blender/blenlib/intern/gsqueue.c
index 6d0fdfacb10..fed8a7366b6 100644
--- a/source/blender/blenlib/intern/gsqueue.c
+++ b/source/blender/blenlib/intern/gsqueue.c
@@ -12,9 +12,6 @@
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
- *
- * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
- * All rights reserved.
*/
/** \file
@@ -22,9 +19,6 @@
*
* \brief A generic structure queue
* (a queue for fixed length generally small) structures.
- *
- * \note Only use this if you need (first-in-first-out),
- * otherwise #BLI_Stack is more efficient (first-in-last-out).
*/
#include <string.h>
@@ -35,148 +29,167 @@
#include "BLI_gsqueue.h"
#include "BLI_strict_flags.h"
-typedef struct _GSQueueElem GSQueueElem;
-struct _GSQueueElem {
- GSQueueElem *next;
+/* target chunk size: 64kb */
+#define CHUNK_SIZE_DEFAULT (1 << 16)
+/* ensure we get at least this many elems per chunk */
+#define CHUNK_ELEM_MIN 32
+
+/* Gets the first or last element in the queue */
+#define CHUNK_FIRST_ELEM(_queue) \
+ ((void)0, \
+ (((char *)(_queue)->chunk_first->data) + ((_queue)->elem_size * (_queue)->chunk_first_index)))
+#define CHUNK_LAST_ELEM(_queue) \
+ ((void)0, \
+ (((char *)(_queue)->chunk_last->data) + ((_queue)->elem_size * (_queue)->chunk_last_index)))
+
+struct QueueChunk {
+ struct QueueChunk *next;
char data[0];
};
struct _GSQueue {
- GSQueueElem *head;
- GSQueueElem *tail;
- size_t elem_size;
+ struct QueueChunk *chunk_first; /* first active chunk to pop from */
+ struct QueueChunk *chunk_last; /* flast active chunk to push onto */
+ struct QueueChunk *chunk_free; /* free chunks to reuse */
+ size_t chunk_first_index; /* index into 'chunk_first' */
+ size_t chunk_last_index; /* index into 'chunk_last' */
+ size_t chunk_elem_max; /* number of elements per chunk */
+ size_t elem_size; /* memory size of elements */
+ size_t totelem; /* total number of elements */
};
/**
- * Create a new GSQueue.
- *
- * \param elem_size: The size of the structures in the queue.
- * \retval The new queue
+ * \return number of elements per chunk, optimized for slop-space.
*/
-GSQueue *BLI_gsqueue_new(size_t elem_size)
+static size_t queue_chunk_elem_max_calc(const size_t elem_size, size_t chunk_size)
{
- GSQueue *gq = MEM_mallocN(sizeof(*gq), "gqueue_new");
- gq->head = gq->tail = NULL;
- gq->elem_size = elem_size;
+ /* get at least this number of elems per chunk */
+ const size_t elem_size_min = elem_size * CHUNK_ELEM_MIN;
+
+ BLI_assert((elem_size != 0) && (chunk_size != 0));
+
+ while (UNLIKELY(chunk_size <= elem_size_min)) {
+ chunk_size <<= 1;
+ }
+
+ /* account for slop-space */
+ chunk_size -= (sizeof(struct QueueChunk) + MEM_SIZE_OVERHEAD);
- return gq;
+ return chunk_size / elem_size;
}
-/**
- * Query if the queue is empty
- */
-bool BLI_gsqueue_is_empty(GSQueue *gq)
+GSQueue *BLI_gsqueue_new(const size_t elem_size)
{
- return (gq->head == NULL);
+ GSQueue *queue = MEM_callocN(sizeof(*queue), "BLI_gsqueue_new");
+
+ queue->chunk_elem_max = queue_chunk_elem_max_calc(elem_size, CHUNK_SIZE_DEFAULT);
+ queue->elem_size = elem_size;
+ /* force init */
+ queue->chunk_last_index = queue->chunk_elem_max - 1;
+
+ return queue;
}
-/**
- * Query number elements in the queue
- */
-int BLI_gsqueue_len(GSQueue *gq)
+static void queue_free_chunk(struct QueueChunk *data)
{
- GSQueueElem *elem;
- int size = 0;
-
- for (elem = gq->head; elem; elem = elem->next) {
- size++;
+ while (data) {
+ struct QueueChunk *data_next = data->next;
+ MEM_freeN(data);
+ data = data_next;
}
-
- return size;
}
/**
- * Access the item at the head of the queue
- * without removing it.
- *
- * \param r_item: A pointer to an appropriately
- * sized structure (the size passed to #BLI_gsqueue_new)
+ * Free the queue's data and the queue itself
*/
-void BLI_gsqueue_peek(GSQueue *gq, void *r_item)
+void BLI_gsqueue_free(GSQueue *queue)
{
- memcpy(r_item, &gq->head->data, gq->elem_size);
+ queue_free_chunk(queue->chunk_first);
+ queue_free_chunk(queue->chunk_free);
+ MEM_freeN(queue);
}
/**
- * Access the item at the head of the queue
- * and remove it.
+ * Copies the source value onto the end of the queue
+ *
+ * \note This copies #GSQueue.elem_size bytes from \a src,
+ * (the pointer itself is not stored).
*
- * \param r_item: A pointer to an appropriately
- * sized structure (the size passed to #BLI_gsqueue_new).
- * Can be NULL if desired.
+ * \param src: source data to be copied to the queue.
*/
-void BLI_gsqueue_pop(GSQueue *gq, void *r_item)
+void BLI_gsqueue_push(GSQueue *queue, const void *src)
{
- GSQueueElem *elem = gq->head;
- if (elem == gq->tail) {
- gq->head = gq->tail = NULL;
- }
- else {
- gq->head = gq->head->next;
- }
+ queue->chunk_last_index++;
+ queue->totelem++;
+
+ if (UNLIKELY(queue->chunk_last_index == queue->chunk_elem_max)) {
+ struct QueueChunk *chunk;
+ if (queue->chunk_free) {
+ chunk = queue->chunk_free;
+ queue->chunk_free = chunk->next;
+ }
+ else {
+ chunk = MEM_mallocN(sizeof(*chunk) + (queue->elem_size * queue->chunk_elem_max), __func__);
+ }
+
+ chunk->next = NULL;
+
+ if (queue->chunk_last == NULL) {
+ queue->chunk_first = chunk;
+ }
+ else {
+ queue->chunk_last->next = chunk;
+ }
- if (r_item) {
- memcpy(r_item, elem->data, gq->elem_size);
+ queue->chunk_last = chunk;
+ queue->chunk_last_index = 0;
}
- MEM_freeN(elem);
+
+ BLI_assert(queue->chunk_last_index < queue->chunk_elem_max);
+
+ /* Return last of queue */
+ void *dst = CHUNK_LAST_ELEM(queue);
+ memcpy(dst, src, queue->elem_size);
}
/**
- * Push an element onto the tail of the queue.
+ * Retrieves and removes the first element from the queue.
+ * The value is copies to \a dst, which must be at least \a elem_size bytes.
*
- * \param item: A pointer to an appropriately
- * sized structure (the size passed to BLI_gsqueue_new).
+ * Does not reduce amount of allocated memory.
*/
-void BLI_gsqueue_push(GSQueue *gq, const void *item)
+void BLI_gsqueue_pop(GSQueue *queue, void *dst)
{
- GSQueueElem *elem;
+ BLI_assert(BLI_gsqueue_is_empty(queue) == false);
+
+ memcpy(dst, CHUNK_FIRST_ELEM(queue), queue->elem_size);
+ queue->chunk_first_index++;
+ queue->totelem--;
+
+ if (UNLIKELY(queue->chunk_first_index == queue->chunk_elem_max || queue->totelem == 0)) {
+ struct QueueChunk *chunk_free = queue->chunk_first;
- /* compare: prevent events added double in row */
- if (!BLI_gsqueue_is_empty(gq)) {
- if (0 == memcmp(item, gq->head->data, gq->elem_size)) {
- return;
+ queue->chunk_first = queue->chunk_first->next;
+ queue->chunk_first_index = 0;
+ if (queue->chunk_first == NULL) {
+ queue->chunk_last = NULL;
+ queue->chunk_last_index = queue->chunk_elem_max - 1;
}
- }
- elem = MEM_mallocN(sizeof(*elem) + gq->elem_size, "gqueue_push");
- memcpy(elem->data, item, gq->elem_size);
- elem->next = NULL;
- if (BLI_gsqueue_is_empty(gq)) {
- gq->tail = gq->head = elem;
- }
- else {
- gq->tail = gq->tail->next = elem;
+ chunk_free->next = queue->chunk_free;
+ queue->chunk_free = chunk_free;
}
}
-/**
- * Push an element back onto the head of the queue (so
- * it would be returned from the next call to BLI_gsqueue_pop).
- *
- * \param item: A pointer to an appropriately
- * sized structure (the size passed to BLI_gsqueue_new).
- */
-void BLI_gsqueue_push_back(GSQueue *gq, const void *item)
+size_t BLI_gsqueue_len(const GSQueue *queue)
{
- GSQueueElem *elem = MEM_mallocN(sizeof(*elem) + gq->elem_size, "gqueue_push");
- memcpy(elem->data, item, gq->elem_size);
- elem->next = gq->head;
-
- if (BLI_gsqueue_is_empty(gq)) {
- gq->head = gq->tail = elem;
- }
- else {
- gq->head = elem;
- }
+ return queue->totelem;
}
/**
- * Free the queue
+ * Returns true if the queue is empty, false otherwise
*/
-void BLI_gsqueue_free(GSQueue *gq)
+bool BLI_gsqueue_is_empty(const GSQueue *queue)
{
- while (gq->head) {
- BLI_gsqueue_pop(gq, NULL);
- }
- MEM_freeN(gq);
+ return (queue->chunk_first == NULL);
}
More information about the Bf-blender-cvs
mailing list