diff options
author | Tavian Barnes <tavianator@gmail.com> | 2009-06-29 22:12:48 +0000 |
---|---|---|
committer | Tavian Barnes <tavianator@gmail.com> | 2009-06-29 22:12:48 +0000 |
commit | d13f5f01ad28d2c44c413b98d2742d7b72bbb542 (patch) | |
tree | e33a081d25852aaf3e8157fbbe4f14c3172b0345 | |
parent | bc178c264d12f73dc43357814056f571eb886102 (diff) | |
download | dimension-d13f5f01ad28d2c44c413b98d2742d7b72bbb542.tar.xz |
Remove thread-synchronization from arrays, which was way too slow, and
only really needed for dmnsn_progress anyway.
-rw-r--r-- | doc/libdimension.texi | 22 | ||||
-rw-r--r-- | libdimension/array.c | 143 | ||||
-rw-r--r-- | libdimension/dimension/array.h | 16 | ||||
-rw-r--r-- | libdimension/dimension/progress.h | 3 | ||||
-rw-r--r-- | libdimension/progress.c | 84 | ||||
-rw-r--r-- | libdimension/raytrace.c | 2 | ||||
-rw-r--r-- | libdimensionxx/dimensionxx/array.hpp | 61 |
7 files changed, 108 insertions, 223 deletions
diff --git a/doc/libdimension.texi b/doc/libdimension.texi index 2329feb..371a5dd 100644 --- a/doc/libdimension.texi +++ b/doc/libdimension.texi @@ -121,35 +121,19 @@ void dmnsn_array_pop(dmnsn_array *array, void *obj); void dmnsn_array_get(const dmnsn_array *array, size_t i, void *obj); @findex dmnsn_array_set() void dmnsn_array_set(dmnsn_array *array, size_t i, const void *obj); +@findex dmnsn_array_at() +void *dmnsn_array_at(dmnsn_array *array, size_t i); @findex dmnsn_array_size() size_t dmnsn_array_size(const dmnsn_array *array); @findex dmnsn_array_resize() void dmnsn_array_resize(dmnsn_array *array, size_t length); - -/* Non-atomic operations for manual locking */ -@findex dmnsn_array_at() -void *dmnsn_array_at(dmnsn_array *array, size_t i); -@findex dmnsn_array_size_unlocked() -size_t dmnsn_array_size_unlocked(const dmnsn_array *array); -@findex dmnsn_array_resize_unlocked() -void dmnsn_array_resize_unlocked(dmnsn_array *array, size_t length); - -/* Manual locking */ -@findex dmnsn_array_rdlock() -void dmnsn_array_rdlock(const dmnsn_array *array); -@findex dmnsn_array_wrlock() -void dmnsn_array_wrlock(dmnsn_array *array); -@findex dmnsn_array_unlock() -void dmnsn_array_unlock(const dmnsn_array *array); @end example @cindex array The Dimension Library often has cause to work with adjustable-size arrays. It provides an interface for dynamically-allocated arrays of arbitrary objects. Arrays are allocated with the @code{dmnsn_new_array()} function, and freed with the @code{dmnsn_delete_array()} function, a pattern common in libdimension. @code{dmnsn_new_array()} takes the size of the new array's elements as its parameter. Unlike other allocation functions throughout libdimension, @code{dmnsn_new_array()} cannot fail if it returns (other allocators may return NULL). In fact, all array operations are guaranteed to either succeed or report a fatal error, which may happen if memory allocation fails. -Arrays in libdimension are thread-safe; every individual operation is atomic. libdimension provides push, pop, get, and set operations for arrays, taking a pointer to an object to read or write as their last parameter, the array index when applicable as the second-last parameter, and the @code{dmnsn_array *} as the first parameter. The array's length may be queried with @code{dmnsn_array_size()}, or set with @code{dmnsn_array_resize()}. - -When sets of array operations must be atomic, one may use the manual locking array interface. Implemented as a read-write lock, applications should call @code{dmnsn_array_rdlock()} to set a read-lock, @code{dmnsn_array_wrlock()} to set a write-lock, and @code{dmnsn_array_unlock()} to unlock the array. While the array is locked, one may call @code{dmnsn_array_at()} to get a pointer to the @code{i}'th element of the array, or the @code{*_unlocked} suffixed versions of the @code{..._size()} and @code{..._resize()} functions to get or set the size, respectively. +Arrays support the push, pop, get, and set operations for arrays, taking a pointer to an object to read or write as their last parameter, the array index when applicable as the second-last parameter, and the @code{dmnsn_array *} as the first parameter. The get operation is bounds-checked; other operations dynamically resize the array as needed. The array's length may be queried with @code{dmnsn_array_size()}, or set with @code{dmnsn_array_resize()}, and a pointer to the @code{i}'th object may be obtained with @code{dmnsn_array_at()}. @node Asynchronicity diff --git a/libdimension/array.c b/libdimension/array.c index 82588aa..a22b450 100644 --- a/libdimension/array.c +++ b/libdimension/array.c @@ -22,10 +22,6 @@ #include <pthread.h> #include <string.h> /* For memcpy */ -/* The raw implementations, which don't do any thread synchronicity */ -static void dmnsn_array_get_impl(const dmnsn_array *array, size_t i, void *obj); -static void dmnsn_array_set_impl(dmnsn_array *array, size_t i, const void *obj); - /* Allocate a new array - guaranteed not to fail if it returns */ dmnsn_array * dmnsn_new_array(size_t obj_size) @@ -41,12 +37,6 @@ dmnsn_new_array(size_t obj_size) if (!array->ptr) { dmnsn_error(DMNSN_SEVERITY_HIGH, "Array allocation failed."); } - - /* Allocate the read-write lock */ - array->rwlock = malloc(sizeof(pthread_rwlock_t)); - if (!array->rwlock || pthread_rwlock_init(array->rwlock, NULL) != 0) { - dmnsn_error(DMNSN_SEVERITY_HIGH, "Array rwlock allocation failed."); - } } return array; @@ -55,98 +45,70 @@ dmnsn_new_array(size_t obj_size) /* Delete the array */ void dmnsn_delete_array(dmnsn_array *array) { if (array) { - if (pthread_rwlock_destroy(array->rwlock) != 0) { - dmnsn_error(DMNSN_SEVERITY_LOW, "Leaking rwlock in array deallocation."); - } - - free(array->rwlock); free(array->ptr); free(array); } } -/* Push obj to the end of the array, atomically */ +/* Push obj to the end of the array */ void dmnsn_array_push(dmnsn_array *array, const void *obj) { - dmnsn_array_wrlock(array); - dmnsn_array_set_impl(array, dmnsn_array_size_unlocked(array), obj); - dmnsn_array_unlock(array); + dmnsn_array_set(array, dmnsn_array_size(array), obj); } -/* Pop obj from the end of the array, atomically */ +/* Pop obj from the end of the array */ void dmnsn_array_pop(dmnsn_array *array, void *obj) { - size_t size; - - dmnsn_array_wrlock(array); - size = dmnsn_array_size_unlocked(array); - dmnsn_array_get_impl(array, size - 1, obj); /* Copy the object */ - dmnsn_array_resize_unlocked(array, size - 1); /* Shrink the array */ - dmnsn_array_unlock(array); + size_t size = dmnsn_array_size(array); + dmnsn_array_get(array, size - 1, obj); /* Copy the object */ + dmnsn_array_resize(array, size - 1); /* Shrink the array */ } /* Get the i'th object, bailing out if i is out of range */ void dmnsn_array_get(const dmnsn_array *array, size_t i, void *obj) { - dmnsn_array_rdlock(array); - dmnsn_array_get_impl(array, i, obj); - dmnsn_array_unlock(array); + if (i >= dmnsn_array_size(array)) { + /* Range check failed */ + dmnsn_error(DMNSN_SEVERITY_HIGH, "Array index out of bounds."); + } + memcpy(obj, (char *)array->ptr + array->obj_size*i, array->obj_size); } /* Set the i'th object, expanding the array if necessary */ void dmnsn_array_set(dmnsn_array *array, size_t i, const void *obj) { - dmnsn_array_wrlock(array); - dmnsn_array_set_impl(array, i, obj); - dmnsn_array_unlock(array); -} - -/* Get the size of the array, atomically */ -size_t -dmnsn_array_size(const dmnsn_array *array) -{ - size_t size; - - dmnsn_array_rdlock(array); - size = dmnsn_array_size_unlocked(array); - dmnsn_array_unlock(array); - - return size; -} - -/* Set the size of the array, atomically */ -void -dmnsn_array_resize(dmnsn_array *array, size_t length) -{ - dmnsn_array_wrlock(array); - dmnsn_array_resize_unlocked(array, length); - dmnsn_array_unlock(array); + if (i >= dmnsn_array_size(array)) { + /* Resize if i is out of range */ + dmnsn_array_resize(array, i + 1); + } + memcpy((char *)array->ptr + array->obj_size*i, obj, array->obj_size); } -/* Thread-unsafe range-checked element access */ +/* Element access */ void * dmnsn_array_at(dmnsn_array *array, size_t i) { - if (i >= dmnsn_array_size_unlocked(array)) { - dmnsn_error(DMNSN_SEVERITY_HIGH, "Array index out of bounds."); + if (i >= dmnsn_array_size(array)) { + /* Resize if i is out of range */ + dmnsn_array_resize(array, i + 1); } return (char *)array->ptr + array->obj_size*i; } -/* Get the size non-atomically, for manual locking */ +/* Get the size of the array */ size_t -dmnsn_array_size_unlocked(const dmnsn_array *array) +dmnsn_array_size(const dmnsn_array *array) { return array->length; } -/* Set the size non-atomically, for manual locking */ +/* Set the size of the array, atomically */ void -dmnsn_array_resize_unlocked(dmnsn_array *array, size_t length) +dmnsn_array_resize(dmnsn_array *array, size_t length) { if (length > array->capacity) { /* Resize if we don't have enough capacity */ @@ -159,60 +121,3 @@ dmnsn_array_resize_unlocked(dmnsn_array *array, size_t length) array->length = length; } - -/* Set a manual read-lock */ -void -dmnsn_array_rdlock(const dmnsn_array *array) -{ - if (pthread_rwlock_rdlock(array->rwlock) != 0) { - /* Medium severity, because undefined behaviour is pretty likely if our - reads and writes aren't synced */ - dmnsn_error(DMNSN_SEVERITY_MEDIUM, - "Couldn't acquire read-lock for array."); - } -} - -/* Set a manual write-lock */ -void -dmnsn_array_wrlock(dmnsn_array *array) -{ - if (pthread_rwlock_wrlock(array->rwlock) != 0) { - /* Medium severity, because undefined behaviour is pretty likely if our - reads and writes aren't synced */ - dmnsn_error(DMNSN_SEVERITY_MEDIUM, - "Couldn't acquire write-lock for array."); - } -} - -/* Unset a manual lock */ -void -dmnsn_array_unlock(const dmnsn_array *array) -{ - if (pthread_rwlock_unlock(array->rwlock) != 0) { - /* Medium severity, because if the array is locked, we're likely to hang - the next time we try to read or write it */ - dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't unlock array."); - } -} - -/* Actual "get" implementation */ -static void -dmnsn_array_get_impl(const dmnsn_array *array, size_t i, void *obj) -{ - if (i >= dmnsn_array_size_unlocked(array)) { - /* Range check failed */ - dmnsn_error(DMNSN_SEVERITY_HIGH, "Array index out of bounds."); - } - memcpy(obj, array->ptr + array->obj_size*i, array->obj_size); -} - -/* Actual "set" implementation */ -static void -dmnsn_array_set_impl(dmnsn_array *array, size_t i, const void *obj) -{ - if (i >= dmnsn_array_size_unlocked(array)) { - /* Resize if i is out of range */ - dmnsn_array_resize_unlocked(array, i + 1); - } - memcpy(array->ptr + array->obj_size*i, obj, array->obj_size); -} diff --git a/libdimension/dimension/array.h b/libdimension/dimension/array.h index 1c8f601..5d5e50e 100644 --- a/libdimension/dimension/array.h +++ b/libdimension/dimension/array.h @@ -32,9 +32,6 @@ typedef struct { void *ptr; size_t obj_size, length, capacity; - - /* Synchronicity control (pointer so it's not const) */ - pthread_rwlock_t *rwlock; } dmnsn_array; /* Array allocation never returns NULL - if dmnsn_new_array returns, it @@ -42,24 +39,13 @@ typedef struct { dmnsn_array *dmnsn_new_array(size_t obj_size); void dmnsn_delete_array(dmnsn_array *array); -/* Thread-safe atomic array access */ - void dmnsn_array_push(dmnsn_array *array, const void *obj); void dmnsn_array_pop(dmnsn_array *array, void *obj); void dmnsn_array_get(const dmnsn_array *array, size_t i, void *obj); void dmnsn_array_set(dmnsn_array *array, size_t i, const void *obj); +void *dmnsn_array_at(dmnsn_array *array, size_t i); size_t dmnsn_array_size(const dmnsn_array *array); void dmnsn_array_resize(dmnsn_array *array, size_t length); -/* Non-atomic operations for manual locking */ -void *dmnsn_array_at(dmnsn_array *array, size_t i); -size_t dmnsn_array_size_unlocked(const dmnsn_array *array); -void dmnsn_array_resize_unlocked(dmnsn_array *array, size_t length); - -/* Manual locking */ -void dmnsn_array_rdlock(const dmnsn_array *array); -void dmnsn_array_wrlock(dmnsn_array *array); -void dmnsn_array_unlock(const dmnsn_array *array); - #endif /* DIMENSION_ARRAY_H */ diff --git a/libdimension/dimension/progress.h b/libdimension/dimension/progress.h index 7958ab9..57a38b6 100644 --- a/libdimension/dimension/progress.h +++ b/libdimension/dimension/progress.h @@ -44,6 +44,9 @@ typedef struct { /* The worker thread */ pthread_t thread; + /* Read-write synchronization */ + pthread_rwlock_t *rwlock; + /* Condition variable for waiting for a particular amount of progress */ pthread_cond_t *cond; pthread_mutex_t *mutex; diff --git a/libdimension/progress.c b/libdimension/progress.c index f25af74..1f50e4c 100644 --- a/libdimension/progress.c +++ b/libdimension/progress.c @@ -22,6 +22,11 @@ #include <pthread.h> #include <stdlib.h> /* For malloc */ +/* For thread synchronization */ +static void dmnsn_progress_rdlock(const dmnsn_progress *progress); +static void dmnsn_progress_wrlock(dmnsn_progress *progress); +static void dmnsn_progress_unlock(const dmnsn_progress *progress); + /* Allocate a new dmnsn_progress*, returning NULL on failure */ dmnsn_progress * dmnsn_new_progress() @@ -32,10 +37,18 @@ dmnsn_new_progress() progress->elements = dmnsn_new_array(sizeof(dmnsn_progress_element)); dmnsn_array_push(progress->elements, &element); - /* Allocate space for the condition variable and mutex */ + /* Allocate space for the rwlock, condition variable, and mutex */ + + progress->rwlock = malloc(sizeof(pthread_rwlock_t)); + if (!progress->rwlock) { + dmnsn_delete_array(progress->elements); + free(progress); + return NULL; + } progress->cond = malloc(sizeof(pthread_cond_t)); if (!progress->cond) { + free(progress->rwlock); dmnsn_delete_array(progress->elements); free(progress); return NULL; @@ -43,6 +56,16 @@ dmnsn_new_progress() progress->mutex = malloc(sizeof(pthread_mutex_t)); if (!progress->mutex) { + free(progress->rwlock); + free(progress->cond); + dmnsn_delete_array(progress->elements); + free(progress); + return NULL; + } + + if (pthread_rwlock_init(progress->rwlock, NULL) != 0) { + free(progress->rwlock); + free(progress->mutex); free(progress->cond); dmnsn_delete_array(progress->elements); free(progress); @@ -50,6 +73,11 @@ dmnsn_new_progress() } if (pthread_cond_init(progress->cond, NULL) != 0) { + if (pthread_rwlock_destroy(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_LOW, + "Leaking rwlock in failed allocation."); + } + free(progress->rwlock); free(progress->mutex); free(progress->cond); dmnsn_delete_array(progress->elements); @@ -57,10 +85,15 @@ dmnsn_new_progress() return NULL; } if (pthread_mutex_init(progress->mutex, NULL) != 0) { + if (pthread_rwlock_destroy(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_LOW, + "Leaking rwlock in failed allocation."); + } if (pthread_cond_destroy(progress->cond) != 0) { dmnsn_error(DMNSN_SEVERITY_LOW, "Leaking condition variable in failed allocation."); } + free(progress->rwlock); free(progress->mutex); free(progress->cond); dmnsn_delete_array(progress->elements); @@ -77,6 +110,9 @@ void dmnsn_delete_progress(dmnsn_progress *progress) { if (progress) { + if (pthread_rwlock_destroy(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_LOW, "Leaking rwlock."); + } if (pthread_mutex_destroy(progress->mutex) != 0) { dmnsn_error(DMNSN_SEVERITY_LOW, "Leaking mutex."); } @@ -124,14 +160,14 @@ dmnsn_get_progress(const dmnsn_progress *progress) double prog = 0.0; unsigned int i, size; - dmnsn_array_rdlock(progress->elements); - size = dmnsn_array_size_unlocked(progress->elements); + dmnsn_progress_rdlock(progress); + size = dmnsn_array_size(progress->elements); for (i = 0; i < size; ++i) { element = dmnsn_array_at(progress->elements, size - i - 1); prog += element->progress; prog /= element->total; } - dmnsn_array_unlock(progress->elements); + dmnsn_progress_unlock(progress); return prog; } @@ -172,15 +208,15 @@ dmnsn_increment_progress(dmnsn_progress *progress) dmnsn_progress_element *element; size_t size; - dmnsn_array_wrlock(progress->elements); - size = dmnsn_array_size_unlocked(progress->elements); + dmnsn_progress_wrlock(progress); + size = dmnsn_array_size(progress->elements); element = dmnsn_array_at(progress->elements, size - 1); ++element->progress; /* Increment the last element */ while (element->progress >= element->total && size > 1) { /* As long as the last element is complete, pop it */ --size; - dmnsn_array_resize_unlocked(progress->elements, size); + dmnsn_array_resize(progress->elements, size); element = dmnsn_array_at(progress->elements, size - 1); ++element->progress; /* Increment the next element */ } @@ -188,7 +224,7 @@ dmnsn_increment_progress(dmnsn_progress *progress) if (pthread_cond_broadcast(progress->cond) != 0) { dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't signal condition variable."); } - dmnsn_array_unlock(progress->elements); + dmnsn_progress_unlock(progress); } /* Immediately set to 100% completion */ @@ -197,13 +233,39 @@ dmnsn_done_progress(dmnsn_progress *progress) { dmnsn_progress_element *element; - dmnsn_array_wrlock(progress->elements); - dmnsn_array_resize_unlocked(progress->elements, 1); + dmnsn_progress_wrlock(progress); + dmnsn_array_resize(progress->elements, 1); element = dmnsn_array_at(progress->elements, 0); element->progress = element->total; if (pthread_cond_broadcast(progress->cond) != 0) { dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't signal condition variable."); } - dmnsn_array_unlock(progress->elements); + dmnsn_progress_unlock(progress); +} + +/* Thread synchronization */ + +static void +dmnsn_progress_rdlock(const dmnsn_progress *progress) +{ + if (pthread_rwlock_rdlock(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't acquire read-lock."); + } +} + +static void +dmnsn_progress_wrlock(dmnsn_progress *progress) +{ + if (pthread_rwlock_wrlock(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't acquire write-lock."); + } +} + +static void +dmnsn_progress_unlock(const dmnsn_progress *progress) +{ + if (pthread_rwlock_unlock(progress->rwlock) != 0) { + dmnsn_error(DMNSN_SEVERITY_MEDIUM, "Couldn't unlock read-write lock."); + } } diff --git a/libdimension/raytrace.c b/libdimension/raytrace.c index d634747..4af0a75 100644 --- a/libdimension/raytrace.c +++ b/libdimension/raytrace.c @@ -101,7 +101,7 @@ dmnsn_raytrace_scene_multithread(dmnsn_raytrace_payload *payload) dmnsn_raytrace_payload *payloads; pthread_t *threads; - /* TODO: do this portably */ + /* Find the number of processors/cores running (TODO: do this portably) */ nthreads = sysconf(_SC_NPROCESSORS_ONLN); if (nthreads < 1) { nthreads = 1; diff --git a/libdimensionxx/dimensionxx/array.hpp b/libdimensionxx/dimensionxx/array.hpp index 735e17a..4804de4 100644 --- a/libdimensionxx/dimensionxx/array.hpp +++ b/libdimensionxx/dimensionxx/array.hpp @@ -28,40 +28,6 @@ namespace Dimension { - // RAII scoped read-lock - class Array_Read_Lock - { - public: - explicit Array_Read_Lock(const dmnsn_array* array) - : m_array(new const dmnsn_array*(array)) { dmnsn_array_rdlock(*m_array); } - // Array_Read_Lock(const Array_Read_Lock& lock); - ~Array_Read_Lock() - { if (m_array.unique()) { dmnsn_array_unlock(*m_array); } } - - private: - // Copy assignment prohibited - Array_Read_Lock& operator=(const Array_Read_Lock&); - - std::tr1::shared_ptr<const dmnsn_array*> m_array; - }; - - // RAII scoped write-lock - class Array_Write_Lock - { - public: - explicit Array_Write_Lock(dmnsn_array* array) - : m_array(new dmnsn_array*(array)) { dmnsn_array_wrlock(*m_array); } - // Array_Write_Lock(const Array_Write_Lock& lock); - ~Array_Write_Lock() - { if (m_array.unique()) { dmnsn_array_unlock(*m_array); } } - - private: - // Copy assignment prohibited - Array_Write_Lock& operator=(const Array_Write_Lock&); - - std::tr1::shared_ptr<dmnsn_array*> m_array; - }; - // Array template class, wraps a dmnsn_array*. Copying is possible, but // copies refer to the same object, which is reference counted. T must be // a POD type. @@ -77,25 +43,13 @@ namespace Dimension // Array& operator=(const Array& a); - inline T at(std::size_t i) const; - void set(std::size_t i, T object) { dmnsn_array_set(dmnsn(), i, &object); } - - std::size_t size() const { return dmnsn_array_size(dmnsn()); } - void resize(std::size_t size) { dmnsn_array_resize(dmnsn(), size); } - - // For manual locking - - Array_Read_Lock read_lock() const { return Array_Read_Lock(dmnsn()); } - Array_Write_Lock write_lock() { return Array_Write_Lock(dmnsn()); } - T& operator[](std::size_t i) { return *reinterpret_cast<T*>(dmnsn_array_at(dmnsn(), i)); } const T& operator[](std::size_t i) const { return *reinterpret_cast<const T*>(dmnsn_array_at(dmnsn(), i)); } - std::size_t size_unlocked() const - { return dmnsn_array_size_unlocked(dmnsn()); } - void resize_unlocked(std::size_t size) - { dmnsn_array_resize_unlocked(dmnsn(), size); } + + std::size_t size() const { return dmnsn_array_size(dmnsn()); } + void resize(std::size_t size) { dmnsn_array_resize(dmnsn(), size); } // Access the wrapped C object. dmnsn_array* dmnsn(); @@ -139,15 +93,6 @@ namespace Dimension static_cast<void>(constraint); // Silence unused variable warning } - template <typename T> - inline T - Array<T>::at(std::size_t i) const - { - T ret; - dmnsn_array_get(dmnsn(), i, &ret); - return ret; - } - // Access the underlying dmnsn_array* template <typename T> |