[commits] [tarantool] 01/04: bloom: use malloc for bitmap allocations
Konstantin Osipov
kostja at tarantool.org
Tue Mar 27 23:39:16 MSK 2018
* Vladimir Davydov <vdavydov.dev at gmail.com> [18/03/21 16:36]:
> bloom: use malloc for bitmap allocations
It's not only pointless, it's harmful, since mmap() is ~100 times
slower than malloc().
The patch is OK to push, after explaining to me why had to add an
extra memset().
In a follow up patch you could use slab_arena though.
> There's absolutely no point in using mmap() instead of malloc() for
> bitmap allocation - malloc() will fallback on mmap() anyway provided
> the allocation is large enough.
> ---
> src/lib/salad/bloom.c | 65 ++++++++++++++++++++++----------------------------
> test/unit/bloom.cc | 7 +++---
> test/unit/bloom.result | 4 ++--
> test/vinyl/info.result | 16 ++++++-------
> 4 files changed, 41 insertions(+), 51 deletions(-)
>
> diff --git a/src/lib/salad/bloom.c b/src/lib/salad/bloom.c
> index 642024d..dec9d2a 100644
> --- a/src/lib/salad/bloom.c
> +++ b/src/lib/salad/bloom.c
> @@ -30,8 +30,10 @@
> */
>
> #include "bloom.h"
> -#include <unistd.h>
> -#include <sys/mman.h>
> +#include <stdbool.h>
> +#include <stddef.h>
> +#include <stdint.h>
> +#include <stdlib.h>
> #include <limits.h>
> #include <math.h>
> #include <assert.h>
> @@ -42,41 +44,33 @@ bloom_create(struct bloom *bloom, uint32_t number_of_values,
> double false_positive_rate, struct quota *quota)
> {
> /* Optimal hash_count and bit count calculation */
> - bloom->hash_count = (uint32_t)
> - (log(false_positive_rate) / log(0.5) + 0.99);
> - /* Number of bits */
> - uint64_t m = (uint64_t)
> - (number_of_values * bloom->hash_count / log(2) + 0.5);
> - /* mmap page size */
> - uint64_t page_size = sysconf(_SC_PAGE_SIZE);
> - /* Number of bits in one page */
> - uint64_t b = page_size * CHAR_BIT;
> - /* number of pages, round up */
> - uint64_t p = (uint32_t)((m + b - 1) / b);
> - /* bit array size in bytes */
> - size_t mmap_size = p * page_size;
> - bloom->table_size = p * page_size / sizeof(struct bloom_block);
> - if (quota_use(quota, mmap_size) < 0) {
> - bloom->table = NULL;
> + uint16_t hash_count = ceil(log(false_positive_rate) / log(0.5));
> + uint64_t bit_count = ceil(number_of_values * hash_count / log(2));
> + uint32_t block_bits = CHAR_BIT * sizeof(struct bloom_block);
> + uint32_t block_count = (bit_count + block_bits - 1) / block_bits;
> +
> + size_t size = block_count * sizeof(struct bloom_block);
> + if (quota_use(quota, size) < 0)
> return -1;
> - }
> - bloom->table = (struct bloom_block *)
> - mmap(NULL, mmap_size, PROT_READ | PROT_WRITE,
> - MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> - if (bloom->table == MAP_FAILED) {
> - bloom->table = NULL;
> - quota_release(quota, mmap_size);
> +
> + bloom->table = malloc(size);
> + if (bloom->table == NULL) {
> + quota_release(quota, size);
> return -1;
> }
> +
> + bloom->table_size = block_count;
> + bloom->hash_count = hash_count;
> + memset(bloom->table, 0, size);
Why do you need this memset()?
> return 0;
> }
>
> void
> bloom_destroy(struct bloom *bloom, struct quota *quota)
> {
> - size_t mmap_size = bloom->table_size * sizeof(struct bloom_block);
> - munmap(bloom->table, mmap_size);
> - quota_release(quota, mmap_size);
> + size_t size = bloom->table_size * sizeof(struct bloom_block);
> + quota_release(quota, size);
> + free(bloom->table);
> }
>
> size_t
> @@ -96,20 +90,17 @@ bloom_store(const struct bloom *bloom, char *table)
> int
> bloom_load_table(struct bloom *bloom, const char *table, struct quota *quota)
> {
> - size_t mmap_size = bloom->table_size * sizeof(struct bloom_block);
> - if (quota_use(quota, mmap_size) < 0) {
> + size_t size = bloom->table_size * sizeof(struct bloom_block);
> + if (quota_use(quota, size) < 0) {
> bloom->table = NULL;
> return -1;
> }
> - bloom->table = (struct bloom_block *)
> - mmap(NULL, mmap_size, PROT_READ | PROT_WRITE,
> - MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
> - if (bloom->table == MAP_FAILED) {
> - bloom->table = NULL;
> - quota_release(quota, mmap_size);
> + bloom->table = malloc(size);
> + if (bloom->table == NULL) {
> + quota_release(quota, size);
> return -1;
> }
> - memcpy(bloom->table, table, mmap_size);
> + memcpy(bloom->table, table, size);
> return 0;
> }
>
> diff --git a/test/unit/bloom.cc b/test/unit/bloom.cc
> index 5e387f7..e78ab73 100644
> --- a/test/unit/bloom.cc
> +++ b/test/unit/bloom.cc
> @@ -7,7 +7,7 @@ using namespace std;
>
> uint32_t h(uint32_t i)
> {
> - return i;
> + return i * 2654435761;
> }
Wow, you used Knuth's multiplicative hash in a test just for the
sake of ..mmm. what? Making me think, I guess... Maybe fix assoc.h
then as well? A nice property of "identity" hash function is that
it doesn't scramble auto-increment ids, which is easier to debug,
but the one you chose adds more randomness. On the other hand
mhash.h uses prime numbers for hash table size, which should be
pretty random. So, you do need more randomness if your hash table
size is a power of two, if you use prime numbers it's perhaps not
worth it. Resolution: OK, nothing to do.
> }
> double fp_rate = (double)false_positive / tests;
> - double excess = fp_rate / p;
> - if (fp_rate > p)
> + if (fp_rate > p + 0.001)
> fp_rate_too_big++;
> }
> cout << "error_count = " << error_count << endl;
> @@ -95,7 +94,7 @@ store_load_test()
> }
> double fp_rate = (double)false_positive / tests;
> double excess = fp_rate / p;
> - if (fp_rate > p)
> + if (fp_rate > p + 0.001)
> fp_rate_too_big++;
> }
> cout << "error_count = " << error_count << endl;
> diff --git a/test/unit/bloom.result b/test/unit/bloom.result
> index a7d5a5b..39177f5 100644
> --- a/test/unit/bloom.result
> +++ b/test/unit/bloom.result
> @@ -9,10 +9,10 @@ fp_rate_too_big = 0
> memory after destruction = 0
>
> *** spectrum_test ***
> -bloom table size = 128
> +bloom table size = 79
> error_count = 0
> fpr_rate_is_good = 1
> -bloom table size = 128
> +bloom table size = 106
> error_count = 0
> fpr_rate_is_good = 1
> memory after destruction = 0
> diff --git a/test/vinyl/info.result b/test/vinyl/info.result
> index 0212360..4ca0f7f 100644
> --- a/test/vinyl/info.result
> +++ b/test/vinyl/info.result
> @@ -266,7 +266,7 @@ stat_diff(istat(), st)
> bytes: 26049
> index_size: 294
> rows: 25
> - bloom_size: 4096
> + bloom_size: 64
> pages: 7
> bytes: 26049
> bytes_compressed: <bytes_compressed>
> @@ -982,7 +982,7 @@ istat()
> bytes: 0
> pages: 25
> bytes_compressed: <bytes_compressed>
> - bloom_size: 8192
> + bloom_size: 128
> txw:
> bytes: 0
> rows: 0
> @@ -1120,8 +1120,8 @@ i1:len(), i2:len()
> ...
> i1:bsize(), i2:bsize()
> ---
> -- 4390
> -- 4946
> +- 358
> +- 914
> ...
> s:bsize() == st1.disk.bytes
> ---
> @@ -1166,8 +1166,8 @@ i1:len(), i2:len()
> ...
> i1:bsize(), i2:bsize()
> ---
> -- 53542
> -- 54098
> +- 49510
> +- 50066
> ...
> s:bsize() == st1.memory.bytes + st1.disk.bytes
> ---
> @@ -1216,8 +1216,8 @@ i1:len(), i2:len()
> ...
> i1:bsize(), i2:bsize()
> ---
> -- 4390
> -- 4946
> +- 358
> +- 914
Ah, no mmap() so no extra bytes.
> ...
> s:bsize() == st1.disk.bytes
--
Konstantin Osipov, Moscow, Russia, +7 903 626 22 32
http://tarantool.io - www.twitter.com/kostja_osipov
More information about the Tarantool-patches
mailing list