From: Keith P. <ke...@ke...> - 2012-04-27 20:41:23
|
Ical arrays are allocated as a monolithic block of data, which is nice and space efficient. However, because ical exposes pointers to arrays to applications, it's important for these pointers to remain stable across array reallocation, especially for timezone information. Here's a patch which changes how arrays are managed, allocating a new block of data for each increment of new objects. This retains the O(1) behaviour of fetching and storing data, amortizes allocation overhead for multiple objects and makes inserting objects nominally faster (copying only the array of pointers to chunks, and not the data itself). It does introduce a performance regression for sort, when sorting more objects than can be held in a single chunk. This keeps evolution from crashing... ---------------------- Description: Allocate icalarray data in chunks Allocating the icalarray data in chunks makes the pointers to the data stable across resize. . libical (0.48-2) unstable; urgency=low . * Change icalarray to chunks Author: Keith Packard <ke...@ke...> Origin: author Bug: http://sourceforge.net/tracker/?func=detail&aid=3514871&group_id=16077&atid=116077 --- --- libical-0.48.orig/src/libical/icalarray.c +++ libical-0.48/src/libical/icalarray.c @@ -38,7 +38,6 @@ #include "icalarray.h" #include "icalerror.h" - static void icalarray_expand (icalarray *array, int space_needed); @@ -61,15 +60,25 @@ icalarray_new (int element_size, array->increment_size = increment_size; array->num_elements = 0; array->space_allocated = 0; - array->data = NULL; + array->chunks = NULL; return array; } +static void * +icalarray_alloc_chunk(icalarray *array) +{ + void *chunk = malloc(array->element_size * array->increment_size); + if (!chunk) + icalerror_set_errno(ICAL_NEWFAILED_ERROR); + return chunk; +} icalarray *icalarray_copy (icalarray *originalarray) { icalarray *array = icalarray_new(originalarray->element_size, originalarray->increment_size); + int chunks = originalarray->space_allocated / originalarray->increment_size; + int chunk; if (!array) return NULL; @@ -77,15 +86,18 @@ icalarray *icalarray_copy (icalarray *or array->num_elements = originalarray->num_elements; array->space_allocated = originalarray->space_allocated; - array->data = malloc(array->space_allocated * array->element_size); - - if (array->data) { - memcpy(array->data, originalarray->data, - array->element_size*array->space_allocated); + array->chunks = malloc(chunks * sizeof (void *)); + if (array->chunks) { + for (chunk = 0; chunk < chunks; chunk++) { + array->chunks[chunk] = icalarray_alloc_chunk(array); + if (array->chunks[chunk]) + memcpy(array->chunks[chunk], originalarray->chunks[chunk], + array->increment_size * array->element_size); + } } else { icalerror_set_errno(ICAL_ALLOCATION_ERROR); } - + return array; } @@ -96,9 +108,13 @@ icalarray *icalarray_copy (icalarray *or void icalarray_free (icalarray *array) { - if (array->data) { - free (array->data); - array->data = 0; + if (array->chunks) { + int chunks = array->space_allocated / array->increment_size; + int chunk; + for (chunk = 0; chunk < chunks; chunk++) + free(array->chunks[chunk]); + free (array->chunks); + array->chunks = 0; } free (array); array = 0; @@ -109,12 +125,12 @@ void icalarray_append (icalarray *array, const void *element) { + int pos; if (array->num_elements >= array->space_allocated) icalarray_expand (array, 1); - memcpy ((char *)(array->data) + ( array->num_elements * array->element_size ), element, - array->element_size); - array->num_elements++; + pos = array->num_elements++; + memcpy (icalarray_element_at(array, pos), element, array->element_size); } @@ -122,10 +138,12 @@ void* icalarray_element_at (icalarray *array, int position) { + int chunk = position / array->increment_size; + int offset = position % array->increment_size; assert (position >= 0); assert ((unsigned int)position < array->num_elements); - return (char *)(array->data) + (position * array->element_size); + return (char *)(array->chunks[chunk]) + (offset * array->element_size); } @@ -139,13 +157,12 @@ icalarray_remove_element_at (icalarray * assert (position >= 0); assert ((unsigned int)position < array->num_elements); - dest = (char *)array->data + (position * array->element_size); - elements_to_move = array->num_elements - position - 1; - - if (elements_to_move > 0) - memmove (dest, (char *)dest + array->element_size, - elements_to_move * array->element_size); - + while (position < array->num_elements - 1) { + memmove(icalarray_element_at(array, position), + icalarray_element_at(array, position + 1), + array->element_size); + position++; + } array->num_elements--; } @@ -155,7 +172,22 @@ icalarray_sort (icalarray *array, int (*compare) (const void *, const void *)) { - qsort (array->data, array->num_elements, array->element_size, compare); + if (array->num_elements <= array->increment_size) { + qsort(array->chunks[0], array->num_elements, array->element_size, compare); + } else { + int pos; + void *tmp = malloc (array->num_elements * array->element_size); + if (!tmp) + return; + for (pos = 0; pos < array->num_elements; pos++) + memcpy((char *) tmp + array->element_size * pos, icalarray_element_at(array, pos), array->element_size); + + qsort (tmp, array->num_elements, array->element_size, compare); + + for (pos = 0; pos < array->num_elements; pos++) + memcpy(icalarray_element_at(array, pos), (char *) tmp + array->element_size * pos, array->element_size); + free (tmp); + } } @@ -163,31 +195,27 @@ static void icalarray_expand (icalarray *array, int space_needed) { - int new_space_allocated; - void *new_data; - - new_space_allocated = array->space_allocated + array->increment_size; - - if ((unsigned int)space_needed > array->increment_size) - new_space_allocated += space_needed; - - /* - new_data = realloc (array->data, - new_space_allocated * array->element_size); - */ - new_data = malloc(new_space_allocated * array->element_size); - - if (new_data) { - memcpy(new_data,array->data,array->element_size*array->space_allocated); - if (array->data) { - free(array->data); - array->data = 0; - } - array->data = new_data; - array->space_allocated = new_space_allocated; - } else { + int num_chunks = array->space_allocated / array->increment_size; + int num_new_chunks; + int c; + void **new_chunks; + + num_new_chunks = (space_needed + array->increment_size - 1) / array->increment_size; + if (!num_new_chunks) + num_new_chunks = 1; + + new_chunks = malloc ((num_chunks + num_new_chunks) * sizeof (void *)); + + if (new_chunks) { + memcpy(new_chunks, array->chunks, num_chunks * sizeof (void *)); + for (c = 0; c < num_new_chunks; c++) + new_chunks[c + num_chunks] = icalarray_alloc_chunk(array); + if (array->chunks) + free (array->chunks); + array->chunks = new_chunks; + array->space_allocated = array->space_allocated + num_new_chunks * array->increment_size; + } else icalerror_set_errno(ICAL_ALLOCATION_ERROR); - } } --- libical-0.48.orig/src/libical/icalarray.h +++ libical-0.48/src/libical/icalarray.h @@ -39,7 +39,7 @@ struct _icalarray { unsigned int increment_size; unsigned int num_elements; unsigned int space_allocated; - void *data; + void **chunks; }; -- kei...@in... |
From: Allen W. <wi...@kd...> - 2012-10-07 17:11:43
|
Thanks Keith, I just committed this in r1134 On Friday 27 April 2012 01:22:29 PM Keith Packard wrote: > > Ical arrays are allocated as a monolithic block of data, which is nice > and space efficient. However, because ical exposes pointers to arrays to > applications, it's important for these pointers to remain stable across > array reallocation, especially for timezone information. > > Here's a patch which changes how arrays are managed, allocating a new > block of data for each increment of new objects. This retains the O(1) > behaviour of fetching and storing data, amortizes allocation overhead > for multiple objects and makes inserting objects nominally faster > (copying only the array of pointers to chunks, and not the data itself). > > It does introduce a performance regression for sort, when sorting more > objects than can be held in a single chunk. > > This keeps evolution from crashing... > > ---------------------- > > Description: Allocate icalarray data in chunks > Allocating the icalarray data in chunks makes the pointers > to the data stable across resize. > . > libical (0.48-2) unstable; urgency=low > . > * Change icalarray to chunks > Author: Keith Packard <ke...@ke...> > Origin: author > Bug: http://sourceforge.net/tracker/?func=detail&aid=3514871&group_id=16077&atid=116077 > > --- > --- libical-0.48.orig/src/libical/icalarray.c > +++ libical-0.48/src/libical/icalarray.c > @@ -38,7 +38,6 @@ > #include "icalarray.h" > #include "icalerror.h" > > - > static void icalarray_expand (icalarray *array, > int space_needed); > > @@ -61,15 +60,25 @@ icalarray_new (int element_size, > array->increment_size = increment_size; > array->num_elements = 0; > array->space_allocated = 0; > - array->data = NULL; > + array->chunks = NULL; > > return array; > } > > +static void * > +icalarray_alloc_chunk(icalarray *array) > +{ > + void *chunk = malloc(array->element_size * array->increment_size); > + if (!chunk) > + icalerror_set_errno(ICAL_NEWFAILED_ERROR); > + return chunk; > +} > > icalarray *icalarray_copy (icalarray *originalarray) > { > icalarray *array = icalarray_new(originalarray->element_size, originalarray->increment_size); > + int chunks = originalarray->space_allocated / originalarray->increment_size; > + int chunk; > > if (!array) > return NULL; > @@ -77,15 +86,18 @@ icalarray *icalarray_copy (icalarray *or > array->num_elements = originalarray->num_elements; > array->space_allocated = originalarray->space_allocated; > > - array->data = malloc(array->space_allocated * array->element_size); > - > - if (array->data) { > - memcpy(array->data, originalarray->data, > - array->element_size*array->space_allocated); > + array->chunks = malloc(chunks * sizeof (void *)); > + if (array->chunks) { > + for (chunk = 0; chunk < chunks; chunk++) { > + array->chunks[chunk] = icalarray_alloc_chunk(array); > + if (array->chunks[chunk]) > + memcpy(array->chunks[chunk], originalarray->chunks[chunk], > + array->increment_size * array->element_size); > + } > } else { > icalerror_set_errno(ICAL_ALLOCATION_ERROR); > } > - > + > return array; > } > > @@ -96,9 +108,13 @@ icalarray *icalarray_copy (icalarray *or > void > icalarray_free (icalarray *array) > { > - if (array->data) { > - free (array->data); > - array->data = 0; > + if (array->chunks) { > + int chunks = array->space_allocated / array->increment_size; > + int chunk; > + for (chunk = 0; chunk < chunks; chunk++) > + free(array->chunks[chunk]); > + free (array->chunks); > + array->chunks = 0; > } > free (array); > array = 0; > @@ -109,12 +125,12 @@ void > icalarray_append (icalarray *array, > const void *element) > { > + int pos; > if (array->num_elements >= array->space_allocated) > icalarray_expand (array, 1); > > - memcpy ((char *)(array->data) + ( array->num_elements * array->element_size ), element, > - array->element_size); > - array->num_elements++; > + pos = array->num_elements++; > + memcpy (icalarray_element_at(array, pos), element, array->element_size); > } > > > @@ -122,10 +138,12 @@ void* > icalarray_element_at (icalarray *array, > int position) > { > + int chunk = position / array->increment_size; > + int offset = position % array->increment_size; > assert (position >= 0); > assert ((unsigned int)position < array->num_elements); > > - return (char *)(array->data) + (position * array->element_size); > + return (char *)(array->chunks[chunk]) + (offset * array->element_size); > } > > > @@ -139,13 +157,12 @@ icalarray_remove_element_at (icalarray * > assert (position >= 0); > assert ((unsigned int)position < array->num_elements); > > - dest = (char *)array->data + (position * array->element_size); > - elements_to_move = array->num_elements - position - 1; > - > - if (elements_to_move > 0) > - memmove (dest, (char *)dest + array->element_size, > - elements_to_move * array->element_size); > - > + while (position < array->num_elements - 1) { > + memmove(icalarray_element_at(array, position), > + icalarray_element_at(array, position + 1), > + array->element_size); > + position++; > + } > array->num_elements--; > } > > @@ -155,7 +172,22 @@ icalarray_sort (icalarray *array, > int (*compare) (const void *, > const void *)) > { > - qsort (array->data, array->num_elements, array->element_size, compare); > + if (array->num_elements <= array->increment_size) { > + qsort(array->chunks[0], array->num_elements, array->element_size, compare); > + } else { > + int pos; > + void *tmp = malloc (array->num_elements * array->element_size); > + if (!tmp) > + return; > + for (pos = 0; pos < array->num_elements; pos++) > + memcpy((char *) tmp + array->element_size * pos, icalarray_element_at(array, pos), array->element_size); > + > + qsort (tmp, array->num_elements, array->element_size, compare); > + > + for (pos = 0; pos < array->num_elements; pos++) > + memcpy(icalarray_element_at(array, pos), (char *) tmp + array->element_size * pos, array->element_size); > + free (tmp); > + } > } > > > @@ -163,31 +195,27 @@ static void > icalarray_expand (icalarray *array, > int space_needed) > { > - int new_space_allocated; > - void *new_data; > - > - new_space_allocated = array->space_allocated + array->increment_size; > - > - if ((unsigned int)space_needed > array->increment_size) > - new_space_allocated += space_needed; > - > - /* > - new_data = realloc (array->data, > - new_space_allocated * array->element_size); > - */ > - new_data = malloc(new_space_allocated * array->element_size); > - > - if (new_data) { > - memcpy(new_data,array->data,array->element_size*array->space_allocated); > - if (array->data) { > - free(array->data); > - array->data = 0; > - } > - array->data = new_data; > - array->space_allocated = new_space_allocated; > - } else { > + int num_chunks = array->space_allocated / array->increment_size; > + int num_new_chunks; > + int c; > + void **new_chunks; > + > + num_new_chunks = (space_needed + array->increment_size - 1) / array->increment_size; > + if (!num_new_chunks) > + num_new_chunks = 1; > + > + new_chunks = malloc ((num_chunks + num_new_chunks) * sizeof (void *)); > + > + if (new_chunks) { > + memcpy(new_chunks, array->chunks, num_chunks * sizeof (void *)); > + for (c = 0; c < num_new_chunks; c++) > + new_chunks[c + num_chunks] = icalarray_alloc_chunk(array); > + if (array->chunks) > + free (array->chunks); > + array->chunks = new_chunks; > + array->space_allocated = array->space_allocated + num_new_chunks * array->increment_size; > + } else > icalerror_set_errno(ICAL_ALLOCATION_ERROR); > - } > } > > > --- libical-0.48.orig/src/libical/icalarray.h > +++ libical-0.48/src/libical/icalarray.h > @@ -39,7 +39,7 @@ struct _icalarray { > unsigned int increment_size; > unsigned int num_elements; > unsigned int space_allocated; > - void *data; > + void **chunks; > }; > > |