[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [PATCH 4/7] libihash: use fast binary scaling to determine the load
From: |
Neal H. Walfield |
Subject: |
Re: [PATCH 4/7] libihash: use fast binary scaling to determine the load |
Date: |
Wed, 14 May 2014 13:25:10 +0200 |
User-agent: |
Wanderlust/2.14.0 (Africa) SEMI/1.14.6 (Maruoka) FLIM/1.14.9 (Gojō) APEL/10.8 Emacs/23.4 (x86_64-pc-linux-gnu) MULE/6.0 (HANACHIRUSATO) |
At Tue, 13 May 2014 21:02:53 +0200,
Justus Winter wrote:
> diff --git a/libihash/ihash.c b/libihash/ihash.c
> index d628d75..f529a17 100644
> --- a/libihash/ihash.c
> +++ b/libihash/ihash.c
> if (ht->size)
> {
> - /* Only fill the hash table up to its maximum load factor. */
> - if ((ht->nr_items * 100) >> __builtin_ctz (ht->size) <= ht->max_load)
> + /* Only fill the hash table up to its maximum load factor given
> + as "binary percent", where 128b% corresponds to 100%. As the
> + size is always a power of two, and 128 is also, the quotient
> + of both is also a power of two. Therefore, we can use bit
> + shifts to scale the number of items.
This comment describing binary percent needs to be in the interface.
> diff --git a/libihash/ihash.h b/libihash/ihash.h
> index 8829e51..809166f 100644
> --- a/libihash/ihash.h
> +++ b/libihash/ihash.h
> @@ -79,7 +79,7 @@ struct hurd_ihash
> /* The offset of the location pointer from the hash value. */
> intptr_t locp_offset;
>
> - /* The maximum load factor in percent. */
> + /* The maximum load factor in binary percent. */
> unsigned int max_load;
Either here.
>
> -/* Set the maximum load factor in percent to MAX_LOAD, which should be
> - between 50 and 100. The default is HURD_IHASH_MAX_LOAD_DEFAULT.
> - New elements are only added to the hash table while the number of
> - hashed elements is that much percent of the total size of the hash
> - table. If more elements are added, the hash table is first
> - expanded and reorganized. A MAX_LOAD of 100 will always fill the
> - whole table before enlarging it, but note that this will increase
> - the cost of operations significantly when the table is almost full.
> +/* Set the maximum load factor in binary percent to MAX_LOAD, which
> + should be between 64 and 128. The default is
> + HURD_IHASH_MAX_LOAD_DEFAULT. New elements are only added to the
> + hash table while the number of hashed elements is that much binary
> + percent of the total size of the hash table. If more elements are
> + added, the hash table is first expanded and reorganized. A
> + MAX_LOAD of 128 will always fill the whole table before enlarging
> + it, but note that this will increase the cost of operations
> + significantly when the table is almost full.
>
> If the value is set to a smaller value than the current load
> factor, the next reorganization will happen when a new item is
Or here.
Neal
- [PATCH 1/7] libihash: fix type of max_load, Justus Winter, 2014/05/13
- [PATCH 3/7] libihash: use linear probing and fast modulo operation, Justus Winter, 2014/05/13
- [PATCH 2/7] libihash: use an integer hash function on the keys, Justus Winter, 2014/05/13
- [PATCH 4/7] libihash: use fast binary scaling to determine the load, Justus Winter, 2014/05/13
- [PATCH 5/7] include: add lock-less reference counting primitives, Justus Winter, 2014/05/13
- [PATCH 7/7] libtrivfs: lock-less reference counting for trivfs_peropen objects, Justus Winter, 2014/05/13
- [PATCH 6/7] libdiskfs: lock-less reference counting for peropen objects, Justus Winter, 2014/05/13
- Re: [PATCH 1/7] libihash: fix type of max_load, Samuel Thibault, 2014/05/13