[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[hurd] 38/61: libihash: use fast binary scaling to determine the load
From: |
Samuel Thibault |
Subject: |
[hurd] 38/61: libihash: use fast binary scaling to determine the load |
Date: |
Tue, 27 May 2014 08:32:12 +0000 |
This is an automated email from the git hooks/post-receive script.
sthibault pushed a commit to branch upstream
in repository hurd.
commit e2be8995642cd962b7d61c9c231980de88302d50
Author: Justus Winter <address@hidden>
Date: Tue May 13 18:59:10 2014 +0200
libihash: use fast binary scaling to determine the load
Expressing the maximum load in binary percent (where 128b% corresponds
to 100%) allows us to use fast binary scaling to determine if the
maximum load has been reached without losing precision.
Furthermore, the previously used expression 'ht->nr_items * 100'
overflows int at 2^25 (unsigned int at 2^26). When a hash table
reached that limit, it would fail to resize and fill up the table.
This change fixes that.
* libihash/ihash.c (hurd_ihash_set_max_load): Update the comment.
(hurd_ihash_add): Use fast binary scaling to determine the current
load.
* libihash/ihash.h (struct hurd_ihash): Update comment for max_load.
(hurd_ihash_set_max_load): Update the comment.
---
libihash/ihash.c | 37 +++++++++++++++++++++++++++----------
libihash/ihash.h | 24 +++++++++++++-----------
2 files changed, 40 insertions(+), 21 deletions(-)
diff --git a/libihash/ihash.c b/libihash/ihash.c
index 249f488..151c1a7 100644
--- a/libihash/ihash.c
+++ b/libihash/ihash.c
@@ -180,14 +180,15 @@ hurd_ihash_set_cleanup (hurd_ihash_t ht,
hurd_ihash_cleanup_t cleanup,
}
-/* Set the maximum load factor in percent to MAX_LOAD, which should be
- between 1 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
@@ -272,8 +273,24 @@ hurd_ihash_add (hurd_ihash_t ht, hurd_ihash_key_t key,
hurd_ihash_value_t item)
if (ht->size)
{
- /* Only fill the hash table up to its maximum load factor. */
- if ((ht->nr_items * 100) >> __builtin_ctzl (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.
+
+ load = nr_items * 128 / size
+ = nr_items * 2^{log2 (128) - log2 (size)}
+ = nr_items >> (log2 (size) - log2 (128))
+ -- if size >= 128
+ = nr_items << (log2 (128) - log2 (size))
+ -- otherwise
+ */
+ int d = __builtin_ctzl (ht->size) - 7;
+ unsigned int load = d >= 0
+ ? ht->nr_items >> d
+ : ht->nr_items << -d;
+ if (load <= ht->max_load)
if (add_one (ht, key, item))
return 0;
}
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;
/* When freeing or overwriting an element, this function is called
@@ -97,8 +97,9 @@ typedef struct hurd_ihash *hurd_ihash_t;
be a power of two. */
#define HURD_IHASH_MIN_SIZE 32
-/* The default value for the maximum load factor in percent. */
-#define HURD_IHASH_MAX_LOAD_DEFAULT 75
+/* The default value for the maximum load factor in binary percent.
+ 96b% is equivalent to 75%, 128b% to 100%. */
+#define HURD_IHASH_MAX_LOAD_DEFAULT 96
/* The LOCP_OFFS to use if no location pointer is available. */
#define HURD_IHASH_NO_LOCP INTPTR_MIN
@@ -143,14 +144,15 @@ void hurd_ihash_free (hurd_ihash_t ht);
void hurd_ihash_set_cleanup (hurd_ihash_t ht, hurd_ihash_cleanup_t cleanup,
void *cleanup_data);
-/* 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
--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-hurd/hurd.git
- [hurd] 61/61: Merge remote-tracking branch 'upstream/master' into upstream, (continued)
- [hurd] 61/61: Merge remote-tracking branch 'upstream/master' into upstream, Samuel Thibault, 2014/05/27
- [hurd] 43/61: libihash: fix typo, Samuel Thibault, 2014/05/27
- [hurd] 56/61: ext2fs: fix diskfs_pager_users, Samuel Thibault, 2014/05/27
- [hurd] 57/61: trans/mtab: fix initialization, Samuel Thibault, 2014/05/27
- [hurd] 55/61: libpager: drop unused fields from struct pager, Samuel Thibault, 2014/05/27
- [hurd] 49/61: libdiskfs: lock-less reference counting for peropen objects, Samuel Thibault, 2014/05/27
- [hurd] 30/61: ext2fs: use two distinct pager buckets for the disk and file pager, Samuel Thibault, 2014/05/27
- [hurd] 45/61: include: add lock-less reference counting primitives, Samuel Thibault, 2014/05/27
- [hurd] 58/61: libdiskfs: fix node leak in the name cache, Samuel Thibault, 2014/05/27
- [hurd] 51/61: pfinet: add missing include, Samuel Thibault, 2014/05/27
- [hurd] 38/61: libihash: use fast binary scaling to determine the load,
Samuel Thibault <=
- [hurd] 53/61: Avoid compiler warning about empty bodies, Samuel Thibault, 2014/05/27
- [hurd] 60/61: libtrivfs: lock-less reference counting for trivfs_peropen objects, Samuel Thibault, 2014/05/27
- [hurd] 59/61: libihash: do not use an integer hash function by default, Samuel Thibault, 2014/05/27
- [hurd] 15/61: Include the MIG-generated server header files, Samuel Thibault, 2014/05/27