Messages in this thread Patch in this message | | | Subject | [RFC][PATCH] flex_array: conditionally optimize out divides | From | Dave Hansen <> | Date | Mon, 17 Aug 2009 13:43:51 -0700 |
| |
There are three flex_array operations that require divides: 1. figuring out into which "part" we should access 2. figuring out where into that part we fit 3. figuring out in how many elements fit into a part
Division can get expensive, and we may incur one or two divides for each put() or get() that is performed. If we rounded the elements to a power-of-two and stored shifts and masks, we could rid ourselves of the divides, but we would lose storage space with oddly-sized objects. We could code the implementation to handle divides and special- case the shifts when they can be used, but that would complicate the code.
This is an alternative. We introduce variants of flex_array_get() and flex_array_put() since they are the most common operations. We append an _es() to their names (for Element Size) and get flex_array_get_es() and flex_array_put_es(). The allocation and free functions remain unoptimized since they're not indended to be hot paths.
Passing the element size into each operation, and using it like this:
flex_array_get(fa, nr, sizeof(struct my_struct));
lets the compiler turn the divides into shifts if 'my_struct' is a power-of-two in size.
It seems that only gcc 4.1 and up are smart enough to figure this out, though.
---
linux-2.6.git-dave/include/linux/flex_array.h | 54 ++++++++++++++++++++++++++ linux-2.6.git-dave/lib/flex_array.c | 52 +++++++++++++------------ 2 files changed, 82 insertions(+), 24 deletions(-)
diff -puN include/linux/flex_array.h~precalc include/linux/flex_array.h --- linux-2.6.git/include/linux/flex_array.h~precalc 2009-08-17 13:13:21.000000000 -0700 +++ linux-2.6.git-dave/include/linux/flex_array.h 2009-08-17 13:34:45.000000000 -0700 @@ -1,6 +1,7 @@ #ifndef _FLEX_ARRAY_H #define _FLEX_ARRAY_H +#include <linux/errno.h> #include <linux/types.h> #include <asm/page.h> @@ -36,6 +37,59 @@ struct flex_array { .total_nr_elements = (total), \ } } } +/* + * The 'unsigned' here seems to make gcc more happy + * to optimize the divide. + */ +static inline unsigned int __elements_per_part(int element_size) +{ + return FLEX_ARRAY_PART_SIZE / element_size; +} + +static inline int __fa_element_to_part_nr(int element_size, int element_nr) +{ + return element_nr / __elements_per_part(element_size); +} + +static inline int __fa_index_inside_part(int element_size, int element_nr) +{ + return element_nr % __elements_per_part(element_size); +} + +int flex_array_put_precalc(struct flex_array *fa, int part_nr, + int index_inside_part, void *src, gfp_t flags); +void *flex_array_get_precalc(struct flex_array *fa, int part_nr, + int index_inside_part); + +/* + * Use the _es() variants when you want the compiler to + * be able to optimize the divides like when you have a + * power-of-two element_size. + */ +static inline void *flex_array_get_es(struct flex_array *fa, + int element_nr, int element_size) +{ + int part_nr = __fa_element_to_part_nr(element_size, element_nr); + int index_inside = __fa_index_inside_part(element_size, element_nr); + + if (element_nr >= fa->total_nr_elements) + return NULL; + + return flex_array_get_precalc(fa, part_nr, index_inside); +} + +static inline int flex_array_put_es(struct flex_array *fa, int element_nr, + int element_size, void *src, gfp_t flags) +{ + int part_nr = __fa_element_to_part_nr(element_size, element_nr); + int index_inside = __fa_index_inside_part(element_size, element_nr); + + if (element_nr >= fa->total_nr_elements) + return -ENOSPC; + + return flex_array_put_precalc(fa, part_nr, index_inside, src, flags); +} + struct flex_array *flex_array_alloc(int element_size, int total, gfp_t flags); int flex_array_prealloc(struct flex_array *fa, int start, int end, gfp_t flags); void flex_array_free(struct flex_array *fa); diff -puN lib/flex_array.c~precalc lib/flex_array.c --- linux-2.6.git/lib/flex_array.c~precalc 2009-08-17 13:13:21.000000000 -0700 +++ linux-2.6.git-dave/lib/flex_array.c 2009-08-17 13:41:24.000000000 -0700 @@ -28,11 +28,6 @@ struct flex_array_part { char elements[FLEX_ARRAY_PART_SIZE]; }; -static inline int __elements_per_part(int element_size) -{ - return FLEX_ARRAY_PART_SIZE / element_size; -} - static inline int bytes_left_in_base(void) { int element_offset = offsetof(struct flex_array, parts); @@ -115,11 +110,6 @@ struct flex_array *flex_array_alloc(int return ret; } -static int fa_element_to_part_nr(struct flex_array *fa, int element_nr) -{ - return element_nr / __elements_per_part(fa->element_size); -} - /** * flex_array_free_parts - just free the second-level pages * @src: address of data to copy into the array @@ -151,12 +141,6 @@ static int fa_index_inside_part(struct f return element_nr % __elements_per_part(fa->element_size); } -static int index_inside_part(struct flex_array *fa, int element_nr) -{ - int part_offset = fa_index_inside_part(fa, element_nr); - return part_offset * fa->element_size; -} - static struct flex_array_part * __fa_get_part(struct flex_array *fa, int part_nr, gfp_t flags) { @@ -176,6 +160,12 @@ __fa_get_part(struct flex_array *fa, int return part; } + +static int fa_element_to_part_nr(struct flex_array *fa, int element_nr) +{ + return __fa_element_to_part_nr(fa->element_size, element_nr); +} + /** * flex_array_put - copy data into the array at @element_nr * @src: address of data to copy into the array @@ -186,23 +176,30 @@ __fa_get_part(struct flex_array *fa, int * the array. If you are trying to store an array of * pointers, make sure to pass in &ptr instead of ptr. * + * The _es() variant is if you want to pass in the element + * size yourself. This allows the compiler to do some more + * optimization and possibly eliminate all the divides. + * * Locking must be provided by the caller. */ int flex_array_put(struct flex_array *fa, int element_nr, void *src, gfp_t flags) { - int part_nr = fa_element_to_part_nr(fa, element_nr); + return flex_array_put_es(fa, element_nr, fa->element_size, src, flags); +} + +int flex_array_put_precalc(struct flex_array *fa, int part_nr, + int index_inside_part, void *src, gfp_t flags) +{ struct flex_array_part *part; void *dst; - if (element_nr >= fa->total_nr_elements) - return -ENOSPC; if (elements_fit_in_base(fa)) part = (struct flex_array_part *)&fa->parts[0]; else part = __fa_get_part(fa, part_nr, flags); if (!part) return -ENOMEM; - dst = &part->elements[index_inside_part(fa, element_nr)]; + dst = &part->elements[index_inside_part]; memcpy(dst, src, fa->element_size); return 0; } @@ -248,20 +245,27 @@ int flex_array_prealloc(struct flex_arra * that this is a copy of the data that was passed in. If you * are using this to store pointers, you'll get back &ptr. * + * The _es() variant is if you want to pass in the element + * size yourself. This allows the compiler to do some more + * optimization and possibly eliminate all the divides. + * * Locking must be provided by the caller. */ void *flex_array_get(struct flex_array *fa, int element_nr) { - int part_nr = fa_element_to_part_nr(fa, element_nr); + return flex_array_get_es(fa, element_nr, fa->element_size); +} + +void *flex_array_get_precalc(struct flex_array *fa, int part_nr, + int index_inside_part) +{ struct flex_array_part *part; - if (element_nr >= fa->total_nr_elements) - return NULL; if (!fa->parts[part_nr]) return NULL; if (elements_fit_in_base(fa)) part = (struct flex_array_part *)&fa->parts[0]; else part = fa->parts[part_nr]; - return &part->elements[index_inside_part(fa, element_nr)]; + return &part->elements[index_inside_part]; } diff -L include/linux/flex_array.hcd -puN /dev/null /dev/null _
| |