On Tue, Apr 29, 2014 at 4:44 PM, Ivan Zhakov <ivan_at_visualsvn.com> wrote:
> On 29 April 2014 17:53, <stefan2_at_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
>
Received on 2014-05-05 01:03:36 CEST