diff options
author | Brecht Van Lommel <brechtvanlommel@gmail.com> | 2019-10-01 12:13:28 +0300 |
---|---|---|
committer | Brecht Van Lommel <brechtvanlommel@gmail.com> | 2019-10-01 17:10:38 +0300 |
commit | 1524f414dbd5ac536019223c0ef54b3c8676e465 (patch) | |
tree | 56e6d88a8d4bce3545daa3807faf3121c4f73e84 /source/blender | |
parent | 574265f52fa2967c41b11916ba327e85ac68d03f (diff) |
BLI: optimize GSQueue implementation to allocate in chunks, like BLI_Stack
Diffstat (limited to 'source/blender')
-rw-r--r-- | source/blender/blenlib/BLI_gsqueue.h | 6 | ||||
-rw-r--r-- | source/blender/blenlib/intern/gsqueue.c | 217 |
2 files changed, 117 insertions, 106 deletions
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); } |