On Tue, Apr 29, 2014 at 4:44 PM, Ivan Zhakov <i...@visualsvn.com> wrote:
> On 29 April 2014 17:53, <stef...@apache.org> wrote: > > Author: stefan2 > > Date: Tue Apr 29 13:53:06 2014 > > New Revision: 1590982 > > > > URL: http://svn.apache.org/r1590982 > > Log: > > Make the svn_bit_array__* code use less memory when accessed sparsely. > > This also reduces the initialization overhead when bits are set at > > high indexes. > > > > The basic idea is to replace the one-dimensional array with a two- > > dimensional one where the second dimension ("blocks") gets lazily > > allocated - allowing for a sparse layout. > > > Hi Stefan, > > See my small suggestions inline. > Hi Ivan, Thanks for the review! r1591872 should address all points. -- Stefan^2. > [...] > > > > > Modified: subversion/trunk/subversion/libsvn_subr/bit_array.c > > URL: > http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_subr/bit_array.c?rev=1590982&r1=1590981&r2=1590982&view=diff > > > ============================================================================== > > --- subversion/trunk/subversion/libsvn_subr/bit_array.c (original) > > +++ subversion/trunk/subversion/libsvn_subr/bit_array.c Tue Apr 29 > 13:53:06 2014 > [...] > > > @@ -71,15 +101,17 @@ svn_bit_array__set(svn_bit_array__t *arr > > apr_size_t idx, > > svn_boolean_t value) > > { > > + unsigned char *block; > > + > > /* If IDX is outside the allocated range, we _may_ have to grow it. > > * > > * Be sure to use division instead of multiplication as we need to > cover > > * the full value range of APR_SIZE_T for the bit indexes. > > */ > > - if (idx / 8 >= array->data_size) > > + if (idx / BLOCK_SIZE_BITS >= array->block_count) > May be block_idx local variable will make code more readable. > > > { > > - apr_size_t new_size; > > - unsigned char *new_data; > > + apr_size_t new_count; > > + unsigned char **new_blocks; > > > > /* Unallocated indexes are implicitly 0, so no actual allocation > > * required in that case. > > @@ -87,34 +119,57 @@ svn_bit_array__set(svn_bit_array__t *arr > > if (!value) > > return; > > > > - /* Grow data buffer to cover IDX. > > - * Clear the new buffer to guarantee our array[idx]==0 default. > > + /* Grow block list to cover IDX. > > + * Clear the new entries to guarantee our array[idx]==0 default. > > */ > > - new_size = select_data_size(idx); > > - new_data = apr_pcalloc(array->pool, new_size); > > - memcpy(new_data, array->data, array->data_size); > > - array->data = new_data; > > - array->data_size = new_size; > > + new_count = select_data_size(idx); > > + new_blocks = apr_pcalloc(array->pool, new_count * > sizeof(*new_blocks)); > > + memcpy(new_blocks, array->blocks, new_count * > sizeof(*new_blocks)); > It looks like a bug here. It think it should be. > [[[ > memcpy(new_blocks, array->blocks, array->block_count * > sizeof(*new_blocks)); > ]]] > > Otherwise you're reading unallocated memory. > > > + array->blocks = new_blocks; > > + array->block_count = new_count; > > } > > > > - /* IDX is covered by ARRAY->DATA now. */ > > + /* IDX is covered by ARRAY->BLOCKS now. */ > > + > > + /* Get the block that contains IDX. Auto-allocate it if missing. */ > > + block = array->blocks[idx / BLOCK_SIZE_BITS]; > > + if (block == NULL) > > + { > > + /* Unallocated indexes are implicitly 0, so no actual allocation > > + * required in that case. > > + */ > > + if (!value) > > + return; > > + > > + /* Allocate the previously missing block and clear it for our > > + * array[idx] == 0 default. */ > > + block = apr_pcalloc(array->pool, BLOCK_SIZE); > > + array->blocks[idx / BLOCK_SIZE_BITS] = block; > > + } > > > > /* Set / reset one bit. Be sure to use unsigned shifts. */ > > if (value) > > - array->data[idx / 8] |= (unsigned char)(1u << (idx % 8)); > > + block[(idx % BLOCK_SIZE_BITS) / 8] |= (unsigned char)(1u << (idx % > 8)); > It looks this code have assumption that BLOCK_SIZE_BITS is > multiplication of '8'. I mean that strictly speaking right expression > should be "1u << ((idx % BLOCK_SIZE_BITS) % 8)" or I didn't understand > something? It also may be worth to add inline function /macro > 'bit_mask(int bit)' > > > else > > - array->data[idx / 8] &= (unsigned char)(255u - (1u << (idx % 8))); > > + block[(idx % BLOCK_SIZE_BITS) / 8] &= (unsigned char)(255u - (1u << > (idx % 8))); > What do you think about using binary negate for right expression i.e.: > '~(unsigned char)(1u << (idx % 8));'? > > > } > > > > svn_boolean_t > > svn_bit_array__get(svn_bit_array__t *array, > > apr_size_t idx) > > { > > - /* Indexes outside the allocated range are implictly 0. */ > > - if (idx / 8 >= array->data_size) > > + unsigned char *block; > > + > > + /* Indexes outside the allocated range are implicitly 0. */ > > + if (idx / BLOCK_SIZE_BITS >= array->block_count) > > + return 0; > The same suggestion for block_idx local and may be block_offset variable. > > > + > > + /* Same if the respective block has not been allocated. */ > > + block = array->blocks[idx / BLOCK_SIZE_BITS]; > > + if (block == NULL) > > return 0; > > > > /* Extract one bit (get the byte, shift bit to LSB, extract it). */ > > - return (array->data[idx / 8] >> (idx % 8)) & 1; > > + return (block[(idx % BLOCK_SIZE_BITS) / 8] >> (idx % 8)) & 1; > > } > > > > > > Modified: subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c > > URL: > http://svn.apache.org/viewvc/subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c?rev=1590982&r1=1590981&r2=1590982&view=diff > > > ============================================================================== > > --- subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c > (original) > > +++ subversion/trunk/subversion/tests/libsvn_subr/bit-array-test.c Tue > Apr 29 13:53:06 2014 > > @@ -44,8 +44,8 @@ test_zero_defaults(apr_pool_t *pool) > > svn_bit_array__t *array = svn_bit_array__create(0, pool); > > > > /* Test (default) allocation boundaries */ > > - SVN_TEST_ASSERT(svn_bit_array__get(array, 127) == 0); > > - SVN_TEST_ASSERT(svn_bit_array__get(array, 128) == 0); > > + SVN_TEST_ASSERT(svn_bit_array__get(array, 0x7ffff) == 0); > > + SVN_TEST_ASSERT(svn_bit_array__get(array, 0x80000) == 0); > > > > /* Test address boundaries */ > > SVN_TEST_ASSERT(svn_bit_array__get(array, 0) == 0); > > @@ -58,7 +58,7 @@ static svn_error_t * > > test_get_set(apr_pool_t *pool) > > { > > svn_bit_array__t *array = svn_bit_array__create(0, pool); > > - apr_size_t i = 0, min = 0, max = 1025; > > + apr_size_t i, min = 0x7ff00, max = 0x7ff00 + 1025; > > > > /* All values default to 0. */ > > for (i = min; i < max; ++i) > > > > > > > > -- > Ivan Zhakov > CTO | VisualSVN | http://www.visualsvn.com >
