2:31 p.m.
Angus,
I have found that loop_poll uses qb_array_create() (which does not
autogrow). Wouldn't this result in a ERANGE error on index for the poll
array?
I also noticed a full bin size is allocated. This makes sense (don't
want to realloc this array) but 256 elements (MAX_BIN_ELEMENTS) * a
large element size (such as 1k = very large memory consumption.
Seems like there is a determinism tradeoff between MAX_BIN and autogrow.
Are there other considerations?
I'd prefer lower memory usage for something like the loop_poll operation.
What are you thoughts about the tradeoff here (ie: do you have a strong
preference)?
One thing I also noticed was that the bin array was hard specified.
This makes sense if bin is small (256) but a reallocing bin would make
more sense if BIN_MAX was increased to something larger (like 2048 bin
elements).
4:40 a.m.
On 21/02/12 13:31 -0700, Steven Dake wrote:
Angus,
I have found that loop_poll uses qb_array_create() (which does not
autogrow). Wouldn't this result in a ERANGE error on index for the poll
array?
Sure, but it calls qb_array_grow() so that is not a problem.
I also noticed a full bin size is allocated. This makes sense (don't
want to realloc this array) but 256 elements (MAX_BIN_ELEMENTS) * a
large element size (such as 1k = very large memory consumption.
I agree the MAX_BIN_ELEMENTS is quite high.
Seems like there is a determinism tradeoff between MAX_BIN and autogrow.
Are there other considerations?
One thing I want to add is to allow holes in the array (so don't alloc
unneeded bins.
I'd prefer lower memory usage for something like the loop_poll operation.
That would be good.
What are you thoughts about the tradeoff here (ie: do you have a strong
preference)?
One thing I also noticed was that the bin array was hard specified.
This makes sense if bin is small (256) but a reallocing bin would make
more sense if BIN_MAX was increased to something larger (like 2048 bin
elements).
The main purpose of the array is to replace realloc style arrays
so you can hold references to memory and be guarenteed it won't move
about.
I think we can improve by doing a couple of things:
- make the MAX_BIN_ELEMENTS smaller.
- dynamically allocate the bin array (array of pointers used
internally) and realloc as needed.
- don't alloc bins that aren't needed.
I'll post a patch soon and you can see if it helps.
-Angus
_______________________________________________
quarterback-devel mailing list
quarterback-devel(a)lists.fedorahosted.org
https://fedorahosted.org/mailman/listinfo/quarterback-devel
5:02 a.m.
New subject: [PATCH] ARRAY: save memory (in the bins array) and allow holes in the array
Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
examples/ipcserver.c | 2 +-
lib/array.c | 84 ++++++++++++++++++++++++++++++-------------------
lib/log_dcs.c | 4 +-
lib/loop_poll.c | 2 +-
lib/loop_timerlist.c | 2 +-
5 files changed, 56 insertions(+), 38 deletions(-)
diff --git a/examples/ipcserver.c b/examples/ipcserver.c
index 14364a7..6e2fc6a 100644
--- a/examples/ipcserver.c
+++ b/examples/ipcserver.c
@@ -316,7 +316,7 @@ main(int32_t argc, char *argv[])
} else {
#ifdef HAVE_GLIB
glib_loop = g_main_loop_new(NULL, FALSE);
- gio_map = qb_array_create_2(64, sizeof(struct gio_to_qb_poll), 1);
+ gio_map = qb_array_create_2(16, sizeof(struct gio_to_qb_poll), 1);
qb_ipcs_poll_handlers_set(s1, &glib_ph);
qb_ipcs_run(s1);
g_main_loop_run(glib_loop);
diff --git a/lib/array.c b/lib/array.c
index a3a1e5c..79aa696 100644
--- a/lib/array.c
+++ b/lib/array.c
@@ -22,14 +22,14 @@
#include <qb/qbarray.h>
-#define MAX_BIN_ELEMENTS 256
-#define MAX_BINS 256
+#define MAX_ELEMENTS_PER_BIN 16
+#define MAX_BINS 4096
-#define BIN_NUM_GET(_idx_) (_idx_ >> 8)
-#define ELEM_NUM_GET(_idx_) (_idx_ & 0xff)
+#define BIN_NUM_GET(_idx_) (_idx_ >> 4)
+#define ELEM_NUM_GET(_idx_) (_idx_ & 0x0F)
struct qb_array {
- void *bin[MAX_BINS];
+ void **bin;
size_t max_elements;
size_t element_size;
size_t num_bins;
@@ -42,14 +42,34 @@ qb_array_create(size_t max_elements, size_t element_size)
return qb_array_create_2(max_elements, element_size, 0);
}
+static int32_t
+_grow_bin_array(struct qb_array * a, int32_t new_bin_size)
+{
+ void *p[1];
+ int32_t b;
+
+ p[0] = NULL;
+
+ a->bin = realloc(a->bin, sizeof(p) * new_bin_size);
+ if (a->bin == NULL) {
+ return -ENOMEM;
+ }
+ for (b = a->num_bins; b < new_bin_size; b++) {
+ a->bin[b] = NULL;
+ }
+ a->num_bins = new_bin_size;
+
+ return 0;
+}
+
qb_array_t *
qb_array_create_2(size_t max_elements, size_t element_size,
size_t autogrow_elements)
{
- int32_t i;
struct qb_array *a = NULL;
+ int32_t b;
- if (max_elements > (MAX_BIN_ELEMENTS * MAX_BINS)) {
+ if (max_elements > (MAX_ELEMENTS_PER_BIN * MAX_BINS)) {
errno = -EINVAL;
return NULL;
}
@@ -57,7 +77,7 @@ qb_array_create_2(size_t max_elements, size_t element_size,
errno = -EINVAL;
return NULL;
}
- if (autogrow_elements > MAX_BIN_ELEMENTS) {
+ if (autogrow_elements > MAX_ELEMENTS_PER_BIN) {
errno = -EINVAL;
return NULL;
}
@@ -67,15 +87,12 @@ qb_array_create_2(size_t max_elements, size_t element_size,
}
a->element_size = element_size;
a->max_elements = max_elements;
- a->num_bins = QB_MIN((max_elements / MAX_BIN_ELEMENTS) + 1, MAX_BINS);
+ b = QB_MIN((max_elements / MAX_ELEMENTS_PER_BIN) + 1, MAX_BINS);
a->autogrow_elements = autogrow_elements;
-
- for (i = 0; i < MAX_BINS; i++) {
- if (i < a->num_bins) {
- a->bin[i] = calloc(MAX_BIN_ELEMENTS, element_size);
- } else {
- a->bin[i] = NULL;
- }
+ a->bin = NULL;
+ if (_grow_bin_array(a, b) < 0) {
+ free(a);
+ return NULL;
}
return a;
}
@@ -94,20 +111,27 @@ qb_array_index(struct qb_array * a, int32_t idx, void **element_out)
return -ERANGE;
}
if (idx >= a->max_elements) {
- elem = idx + a->autogrow_elements;
if (a->autogrow_elements == 0) {
return -ERANGE;
} else {
- int32_t rc = qb_array_grow(a, elem);
+ int32_t rc = qb_array_grow(a, idx + 1);
if (rc != 0) {
return rc;
}
}
}
b = BIN_NUM_GET(idx);
- assert(b < a->num_bins);
+ assert(b < MAX_BINS);
+ if (b >= a->num_bins) {
+ if (_grow_bin_array(a, b) < 0) {
+ return -ENOMEM;
+ }
+ }
+ if (a->bin[b] == NULL) {
+ a->bin[b] = calloc(MAX_ELEMENTS_PER_BIN, a->element_size);
+ }
elem = ELEM_NUM_GET(idx);
- assert(elem < MAX_BIN_ELEMENTS);
+ assert(elem < MAX_ELEMENTS_PER_BIN);
bin = a->bin[b];
*element_out = (bin + (a->element_size * elem));
@@ -129,30 +153,24 @@ qb_array_elems_per_bin_get(struct qb_array * a)
if (a == NULL) {
return -EINVAL;
}
- return MAX_BIN_ELEMENTS;
+ return MAX_ELEMENTS_PER_BIN;
}
int32_t
qb_array_grow(struct qb_array * a, size_t max_elements)
{
- int32_t i;
- int32_t old_bins;
-
- if (a == NULL || max_elements > (MAX_BIN_ELEMENTS * MAX_BINS)) {
+ int32_t b;
+ if (a == NULL || max_elements > (MAX_ELEMENTS_PER_BIN * MAX_BINS)) {
return -EINVAL;
}
if (max_elements <= a->max_elements) {
return 0;
}
a->max_elements = max_elements;
- if (a->num_bins >= ((max_elements / MAX_BIN_ELEMENTS) + 1)) {
- return 0;
- }
- old_bins = a->num_bins;
- a->num_bins = QB_MIN((max_elements / MAX_BIN_ELEMENTS) + 1, MAX_BINS);
- for (i = old_bins; i < a->num_bins; i++) {
- if (a->bin[i] == NULL) {
- a->bin[i] = calloc(MAX_BIN_ELEMENTS, a->element_size);
+ b = QB_MIN((max_elements / MAX_ELEMENTS_PER_BIN) + 1, MAX_BINS);
+ if (b > a->num_bins) {
+ if (_grow_bin_array(a, b) < 0) {
+ return -ENOMEM;
}
}
return 0;
diff --git a/lib/log_dcs.c b/lib/log_dcs.c
index 73ca2d8..dde7c60 100644
--- a/lib/log_dcs.c
+++ b/lib/log_dcs.c
@@ -176,8 +176,8 @@ cleanup:
void
qb_log_dcs_init(void)
{
- lookup_arr = qb_array_create_2(256, sizeof(struct callsite_list), 256);
- callsite_arr = qb_array_create_2(256, sizeof(struct qb_log_callsite), 256);
+ lookup_arr = qb_array_create_2(16, sizeof(struct callsite_list), 16);
+ callsite_arr = qb_array_create_2(16, sizeof(struct qb_log_callsite), 16);
arr_next_lock = qb_thread_lock_create(QB_THREAD_LOCK_SHORT);
diff --git a/lib/loop_poll.c b/lib/loop_poll.c
index 7663101..5218c8e 100644
--- a/lib/loop_poll.c
+++ b/lib/loop_poll.c
@@ -412,7 +412,7 @@ qb_loop_poll_create(struct qb_loop *l)
s->s.dispatch_and_take_back = _poll_dispatch_and_take_back_;
s->s.poll = _poll_and_add_to_jobs_;
- s->poll_entries = qb_array_create(128, sizeof(struct qb_poll_entry));
+ s->poll_entries = qb_array_create_2(16, sizeof(struct qb_poll_entry), 16);
s->poll_entry_count = 0;
s->low_fds_event_fn = NULL;
s->not_enough_fds = 0;
diff --git a/lib/loop_timerlist.c b/lib/loop_timerlist.c
index dc28a55..0cadc18 100644
--- a/lib/loop_timerlist.c
+++ b/lib/loop_timerlist.c
@@ -102,7 +102,7 @@ qb_loop_timer_create(struct qb_loop *l)
my_src->s.poll = expire_the_timers;
timerlist_init(&my_src->timerlist);
- my_src->timers = qb_array_create(64, sizeof(struct qb_loop_timer));
+ my_src->timers = qb_array_create_2(16, sizeof(struct qb_loop_timer), 16);
my_src->timer_entry_count = 0;
return (struct qb_loop_source *)my_src;
--
1.7.7.6
10:31 p.m.
New subject: [PATCH] ARRAY: save memory (in the bins array) and allow holes in the array
Big improvement
85k less memory used in cape-sshd
corosync has no performance reduction.
Regards
-steve
5On 02/22/2012 04:02 AM, Angus Salkeld wrote:
Signed-off-by: Angus Salkeld <asalkeld(a)redhat.com>
---
examples/ipcserver.c | 2 +-
lib/array.c | 84 ++++++++++++++++++++++++++++++-------------------
lib/log_dcs.c | 4 +-
lib/loop_poll.c | 2 +-
lib/loop_timerlist.c | 2 +-
5 files changed, 56 insertions(+), 38 deletions(-)
diff --git a/examples/ipcserver.c b/examples/ipcserver.c
index 14364a7..6e2fc6a 100644
--- a/examples/ipcserver.c
+++ b/examples/ipcserver.c
@@ -316,7 +316,7 @@ main(int32_t argc, char *argv[])
} else {
#ifdef HAVE_GLIB
glib_loop = g_main_loop_new(NULL, FALSE);
- gio_map = qb_array_create_2(64, sizeof(struct gio_to_qb_poll), 1);
+ gio_map = qb_array_create_2(16, sizeof(struct gio_to_qb_poll), 1);
qb_ipcs_poll_handlers_set(s1, &glib_ph);
qb_ipcs_run(s1);
g_main_loop_run(glib_loop);
diff --git a/lib/array.c b/lib/array.c
index a3a1e5c..79aa696 100644
--- a/lib/array.c
+++ b/lib/array.c
@@ -22,14 +22,14 @@
#include <qb/qbarray.h>
-#define MAX_BIN_ELEMENTS 256
-#define MAX_BINS 256
+#define MAX_ELEMENTS_PER_BIN 16
+#define MAX_BINS 4096
-#define BIN_NUM_GET(_idx_) (_idx_ >> 8)
-#define ELEM_NUM_GET(_idx_) (_idx_ & 0xff)
+#define BIN_NUM_GET(_idx_) (_idx_ >> 4)
+#define ELEM_NUM_GET(_idx_) (_idx_ & 0x0F)
struct qb_array {
- void *bin[MAX_BINS];
+ void **bin;
size_t max_elements;
size_t element_size;
size_t num_bins;
@@ -42,14 +42,34 @@ qb_array_create(size_t max_elements, size_t element_size)
return qb_array_create_2(max_elements, element_size, 0);
}
+static int32_t
+_grow_bin_array(struct qb_array * a, int32_t new_bin_size)
+{
+ void *p[1];
+ int32_t b;
+
+ p[0] = NULL;
+
+ a->bin = realloc(a->bin, sizeof(p) * new_bin_size);
+ if (a->bin == NULL) {
+ return -ENOMEM;
+ }
+ for (b = a->num_bins; b < new_bin_size; b++) {
+ a->bin[b] = NULL;
+ }
+ a->num_bins = new_bin_size;
+
+ return 0;
+}
+
qb_array_t *
qb_array_create_2(size_t max_elements, size_t element_size,
size_t autogrow_elements)
{
- int32_t i;
struct qb_array *a = NULL;
+ int32_t b;
- if (max_elements > (MAX_BIN_ELEMENTS * MAX_BINS)) {
+ if (max_elements > (MAX_ELEMENTS_PER_BIN * MAX_BINS)) {
errno = -EINVAL;
return NULL;
}
@@ -57,7 +77,7 @@ qb_array_create_2(size_t max_elements, size_t element_size,
errno = -EINVAL;
return NULL;
}
- if (autogrow_elements > MAX_BIN_ELEMENTS) {
+ if (autogrow_elements > MAX_ELEMENTS_PER_BIN) {
errno = -EINVAL;
return NULL;
}
@@ -67,15 +87,12 @@ qb_array_create_2(size_t max_elements, size_t element_size,
}
a->element_size = element_size;
a->max_elements = max_elements;
- a->num_bins = QB_MIN((max_elements / MAX_BIN_ELEMENTS) + 1, MAX_BINS);
+ b = QB_MIN((max_elements / MAX_ELEMENTS_PER_BIN) + 1, MAX_BINS);
a->autogrow_elements = autogrow_elements;
-
- for (i = 0; i < MAX_BINS; i++) {
- if (i < a->num_bins) {
- a->bin[i] = calloc(MAX_BIN_ELEMENTS, element_size);
- } else {
- a->bin[i] = NULL;
- }
+ a->bin = NULL;
+ if (_grow_bin_array(a, b) < 0) {
+ free(a);
+ return NULL;
}
return a;
}
@@ -94,20 +111,27 @@ qb_array_index(struct qb_array * a, int32_t idx, void
**element_out)
return -ERANGE;
}
if (idx >= a->max_elements) {
- elem = idx + a->autogrow_elements;
if (a->autogrow_elements == 0) {
return -ERANGE;
} else {
- int32_t rc = qb_array_grow(a, elem);
+ int32_t rc = qb_array_grow(a, idx + 1);
if (rc != 0) {
return rc;
}
}
}
b = BIN_NUM_GET(idx);
- assert(b < a->num_bins);
+ assert(b < MAX_BINS);
+ if (b >= a->num_bins) {
+ if (_grow_bin_array(a, b) < 0) {
+ return -ENOMEM;
+ }
+ }
+ if (a->bin[b] == NULL) {
+ a->bin[b] = calloc(MAX_ELEMENTS_PER_BIN, a->element_size);
+ }
elem = ELEM_NUM_GET(idx);
- assert(elem < MAX_BIN_ELEMENTS);
+ assert(elem < MAX_ELEMENTS_PER_BIN);
bin = a->bin[b];
*element_out = (bin + (a->element_size * elem));
@@ -129,30 +153,24 @@ qb_array_elems_per_bin_get(struct qb_array * a)
if (a == NULL) {
return -EINVAL;
}
- return MAX_BIN_ELEMENTS;
+ return MAX_ELEMENTS_PER_BIN;
}
int32_t
qb_array_grow(struct qb_array * a, size_t max_elements)
{
- int32_t i;
- int32_t old_bins;
-
- if (a == NULL || max_elements > (MAX_BIN_ELEMENTS * MAX_BINS)) {
+ int32_t b;
+ if (a == NULL || max_elements > (MAX_ELEMENTS_PER_BIN * MAX_BINS)) {
return -EINVAL;
}
if (max_elements <= a->max_elements) {
return 0;
}
a->max_elements = max_elements;
- if (a->num_bins >= ((max_elements / MAX_BIN_ELEMENTS) + 1)) {
- return 0;
- }
- old_bins = a->num_bins;
- a->num_bins = QB_MIN((max_elements / MAX_BIN_ELEMENTS) + 1, MAX_BINS);
- for (i = old_bins; i < a->num_bins; i++) {
- if (a->bin[i] == NULL) {
- a->bin[i] = calloc(MAX_BIN_ELEMENTS, a->element_size);
+ b = QB_MIN((max_elements / MAX_ELEMENTS_PER_BIN) + 1, MAX_BINS);
+ if (b > a->num_bins) {
+ if (_grow_bin_array(a, b) < 0) {
+ return -ENOMEM;
}
}
return 0;
diff --git a/lib/log_dcs.c b/lib/log_dcs.c
index 73ca2d8..dde7c60 100644
--- a/lib/log_dcs.c
+++ b/lib/log_dcs.c
@@ -176,8 +176,8 @@ cleanup:
void
qb_log_dcs_init(void)
{
- lookup_arr = qb_array_create_2(256, sizeof(struct callsite_list), 256);
- callsite_arr = qb_array_create_2(256, sizeof(struct qb_log_callsite), 256);
+ lookup_arr = qb_array_create_2(16, sizeof(struct callsite_list), 16);
+ callsite_arr = qb_array_create_2(16, sizeof(struct qb_log_callsite), 16);
arr_next_lock = qb_thread_lock_create(QB_THREAD_LOCK_SHORT);
diff --git a/lib/loop_poll.c b/lib/loop_poll.c
index 7663101..5218c8e 100644
--- a/lib/loop_poll.c
+++ b/lib/loop_poll.c
@@ -412,7 +412,7 @@ qb_loop_poll_create(struct qb_loop *l)
s->s.dispatch_and_take_back = _poll_dispatch_and_take_back_;
s->s.poll = _poll_and_add_to_jobs_;
- s->poll_entries = qb_array_create(128, sizeof(struct qb_poll_entry));
+ s->poll_entries = qb_array_create_2(16, sizeof(struct qb_poll_entry), 16);
s->poll_entry_count = 0;
s->low_fds_event_fn = NULL;
s->not_enough_fds = 0;
diff --git a/lib/loop_timerlist.c b/lib/loop_timerlist.c
index dc28a55..0cadc18 100644
--- a/lib/loop_timerlist.c
+++ b/lib/loop_timerlist.c
@@ -102,7 +102,7 @@ qb_loop_timer_create(struct qb_loop *l)
my_src->s.poll = expire_the_timers;
timerlist_init(&my_src->timerlist);
- my_src->timers = qb_array_create(64, sizeof(struct qb_loop_timer));
+ my_src->timers = qb_array_create_2(16, sizeof(struct qb_loop_timer), 16);
my_src->timer_entry_count = 0;
return (struct qb_loop_source *)my_src;
4450
days inactive
4452
days old
quarterback-devel@lists.fedorahosted.org
3 comments
2 participants
participants (2)
-
Angus Salkeld -
Steven Dake