Skip to contentSkip to conversation

Don't use floor() in _bitset_with_random_bits

PATCH New Przemyslaw Iskra 2 participants 3 messages Jul 30, 2010 – Aug 7, 2010

lore
Share & tools
lore

Przemyslaw Iskra

author
#0 lore raw

PATCH 1/1 Don't use floor() in _bitset_with_random_bits

Use _even_rand() function instead of floor() in _bitset_with_random_bits(). floor() function is missing in dietlibc (on architectures other than x86). Moreover using floor() to clip rand results does not assure even result distribution.
_even_rand() uses integer arithmetic only and is designed to return evenly distributed results.

Signed-off-by Przemyslaw Iskra <[email protected]>
---
 configure.in            |    3 +--
 lib/metadata/metadata.c |   16 +++++++++++++++-
 2 files changed, 16 insertions(+), 3 deletions(-)
configure.in +1 -2
index bd56136..6f6c67e 100644
@@ -125,8 +125,7 @@ AC_STRUCT_TM
 
 ################################################################################
 dnl -- Check for functions
-AC_SEARCH_LIBS([floor], [m], , [AC_MSG_ERROR(bailing out)])
-AC_CHECK_FUNCS([floor ftruncate gethostname getpagesize \
+AC_CHECK_FUNCS([ftruncate gethostname getpagesize \
   gettimeofday memset mkdir mkfifo rmdir munmap nl_langinfo setenv setlocale \
   strcasecmp strchr strcspn strspn strdup strncasecmp strerror strrchr \
   strstr strtol strtoul uname], , [AC_MSG_ERROR(bailing out)])
lib/metadata/metadata.c +15 -1
index 07222a7..6ee7731 100644
@@ -1018,6 +1018,20 @@ static int _recalc_extents(uint32_t *extents, const char *desc1,
 	return 1;
 }
 
+/* return random integer in [0,max) interval */
+static unsigned _even_rand( unsigned *seed, unsigned max )
+{
+	unsigned r, ret;
+
+	/* make sure distribution is even */
+	do {
+		r = (unsigned) rand_r( seed );
+		ret = r % max;
+	} while ( r - ret >= RAND_MAX - max );
+
+	return ret;
+}
+
 static dm_bitset_t _bitset_with_random_bits(struct dm_pool *mem, uint32_t num_bits,
 					    uint32_t num_set_bits, unsigned *seed)
 {

@@ -1040,7 +1054,7 @@ static dm_bitset_t _bitset_with_random_bits(struct dm_pool *mem, uint32_t num_bi
 	/* Perform loop num_set_bits times, selecting one bit each time */
 	while (i++ < num_bits) {
 		/* Select a random bit between 0 and (i-1) inclusive. */
-		bit_selected = (unsigned) floor(i * (rand_r(seed) / (RAND_MAX + 1.0)));
+		bit_selected = _even_rand( seed, i );
 
 		/*
 		 * If the bit was already set, set the new bit that became
Signature · 9 lines
1.7.1



-- 
 ____  Sparky{PI] -- Przemyslaw _  ___  _  _  ......... LANG...Pl,Ca,Es,En
/____) ___  ___  _ _ || Iskra  |  | _ \| |  | : WWW...ppcrcd.pld-linux.org
\____\| -_)'___| ||^'||//\\// <   |  _/| |  | : WWW2..............rsget.pl
(____/||   (_-_|_||  ||\\ ||   |_ |_|  |_| _| : [email protected]
#1 lore raw

PATCH 1/1 Don't use floor() in _bitset_with_random_bits

Hi,

Quoted 8 lines · Przemyslaw Iskra

Use _even_rand() function instead of floor() in _bitset_with_random_bits(). floor() function is missing in dietlibc (on architectures other than x86). Moreover using floor() to clip rand results does not assure even result distribution.
_even_rand() uses integer arithmetic only and is designed to return evenly distributed results.

Signed-off-by Przemyslaw Iskra <[email protected]>
Reviewed-by Petr Rockai <[email protected]>

Looks OK to me. It took a while to decipher what is the exact meaning of the loop in _even_rand (to a non-pseudorandomness-expert) but I am fairly comfortable with it now. If I understand this correctly, it rejects numbers that come from an "incomplete" slice of the RAND_MAX space (considering the number space [0, RAND_MAX] is divided into some "max"-sized slices and at most a single smaller slice, between [n*max, RAND_MAX] for suitable n -- numbers from this last slice are discarded because they could distort the distribution in favour of smaller numbers).

Quoted 5 lines
configure.in +0 -0
index bd56136..6f6c67e 100644

configure.in AC_STRUCT_TM · line 131

Quoted 9 lines
configure.in +1 -2
@@ -125,8 +125,7 @@ AC_STRUCT_TM
 
 ################################################################################
 dnl -- Check for functions
-AC_SEARCH_LIBS([floor], [m], , [AC_MSG_ERROR(bailing out)])
-AC_CHECK_FUNCS([floor ftruncate gethostname getpagesize \
+AC_CHECK_FUNCS([ftruncate gethostname getpagesize \
   gettimeofday memset mkdir mkfifo rmdir munmap nl_langinfo setenv setlocale \
   strcasecmp strchr strcspn strspn strdup strncasecmp strerror strrchr \
   strstr strtol strtoul uname], , [AC_MSG_ERROR(bailing out)])

OK, since floor is not used anywhere else in LVM.

Quoted 11 lines
lib/metadata/metadata.c +3 -0
index 07222a7..6ee7731 100644
@@ -1018,6 +1018,20 @@ static int _recalc_extents(uint32_t *extents, const char *desc1,
 	return 1;
 }
 
+/* return random integer in [0,max) interval */
+static unsigned _even_rand( unsigned *seed, unsigned max )
+{

lib/metadata/metadata.c static int _recalc_extents(uint32_t *extents, const char *desc1, · line 1033

Quoted 10 lines
lib/metadata/metadata.c +10 -0
+	unsigned r, ret;
+
+	/* make sure distribution is even */
+	do {
+		r = (unsigned) rand_r( seed );
+		ret = r % max;
+	} while ( r - ret >= RAND_MAX - max );
+
+	return ret;
+}

OK as per above.

lib/metadata/metadata.c static dm_bitset_t _bitset_with_random_bits(struct dm_pool *mem, uint32_t num_bi · line 1057

Quoted 9 lines
lib/metadata/metadata.c +1 -1
 static dm_bitset_t _bitset_with_random_bits(struct dm_pool *mem, uint32_t num_bits,
 					    uint32_t num_set_bits, unsigned *seed)
 {

@@ -1040,7 +1054,7 @@ static dm_bitset_t _bitset_with_random_bits(struct dm_pool *mem, uint32_t num_bi
 	/* Perform loop num_set_bits times, selecting one bit each time */
 	while (i++ < num_bits) {
 		/* Select a random bit between 0 and (i-1) inclusive. */
-		bit_selected = (unsigned) floor(i * (rand_r(seed) / (RAND_MAX + 1.0)));
+		bit_selected = _even_rand( seed, i );

OK. Gets a random integer from [0, i). The previous code was doing the same thing (less efficiently and less precisely).

Yours,
Petr.

author
#2 lore raw

PATCH 1/1 Don't use floor() in _bitset_with_random_bits

Quoted 14 lines · Petr Rockai

Hi,

Quoted 8 lines · Przemyslaw Iskra

Use _even_rand() function instead of floor() in _bitset_with_random_bits(). floor() function is missing in dietlibc (on architectures other than x86). Moreover using floor() to clip rand results does not assure even result distribution.
_even_rand() uses integer arithmetic only and is designed to return evenly distributed results.

Signed-off-by Przemyslaw Iskra <[email protected]>
Reviewed-by Petr Rockai <[email protected]>
Quoted 9 lines

Looks OK to me. It took a while to decipher what is the exact meaning of the loop in _even_rand (to a non-pseudorandomness-expert) but I am fairly comfortable with it now. If I understand this correctly, it rejects numbers that come from an "incomplete" slice of the RAND_MAX space (considering the number space [0, RAND_MAX] is divided into some "max"-sized slices and at most a single smaller slice, between [n*max, RAND_MAX] for suitable n -- numbers from this last slice are discarded because they could distort the distribution in favour of smaller numbers).

That's exactly what it does.

However, right now it cutts off the last slice even if it's complete. You could replace:

Quoted 1 line

lib/metadata/metadata.c static int _recalc_extents(uint32_t *extents, const char *desc1, · line 1030

Quoted 1 line
lib/metadata/metadata.c +1 -0
+	} while ( r - ret >= RAND_MAX - max );

With:

+ } while ( r - ret > (unsigned) RAND_MAX + 1 - max );

Result distribution is correct in both cases. It just avoids the branch in 0.00something %.

Przemyslaw Iskra

Signature · 4 lines
 ____  Sparky{PI] -- Przemyslaw _  ___  _  _  ......... LANG...Pl,Ca,Es,En
/____) ___  ___  _ _ || Iskra  |  | _ \| |  | : WWW...ppcrcd.pld-linux.org
\____\| -_)'___| ||^'||//\\// <   |  _/| |  | : WWW2..............rsget.pl
(____/||   (_-_|_||  ||\\ ||   |_ |_|  |_| _| : [email protected]