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.
[...]
>
> 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-04-29 16:45:30 CEST