[PATCH 07/11] object: try naive cuckoo hashing
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
../+v/65c71a61547aecd8a6830391fda31ed5d18e0529/git-pack-objects
Counting objects: 2139209, done.
32.04user 3.43system 0:35.58elapsed 99%CPU (0avgtext+0avgdata 8178672maxresident)k
0inputs+0outputs (0major+1206546minor)pagefaults 0swaps
Counting objects: 2139209, done.
33.41user 3.15system 0:36.67elapsed 99%CPU (0avgtext+0avgdata 8178688maxresident)k
0inputs+0outputs (0major+1206547minor)pagefaults 0swaps
Counting objects: 2139209, done.
32.24user 3.17system 0:35.51elapsed 99%CPU (0avgtext+0avgdata 8179968maxresident)k
0inputs+0outputs (0major+1206598minor)pagefaults 0swaps
---
object.c | 99 ++++++++++++++++++++++++++++++++++++++++++--------------------
1 files changed, 67 insertions(+), 32 deletions(-)
diff --git a/object.c b/object.c
index c2c0a7d..7624c48 100644
--- a/object.c
+++ b/object.c
@@ -50,33 +50,52 @@ static unsigned int hash_val(const unsigned char *sha1)
return hash;
}
-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
-{
- unsigned int j = hash_val(obj->sha1) & (size-1);
- while (hash[j]) {
- j++;
- if (j >= size)
- j = 0;
- }
- hash[j] = obj;
-}
+#define H1(sha1) (hash_val(sha1) % obj_hash_size)
+#define H2(sha1) (hash_val((sha1) + sizeof(unsigned int)) % obj_hash_size)
struct object *lookup_object(const unsigned char *sha1)
{
- unsigned int i;
struct object *obj;
if (!obj_hash)
return NULL;
- i = hash_val(sha1) & (obj_hash_size-1);
- while ((obj = obj_hash[i]) != NULL) {
- if (!hashcmp(sha1, obj->sha1))
- break;
- i++;
- if (i == obj_hash_size)
- i = 0;
+ if ((obj = obj_hash[H1(sha1)]) && !hashcmp(sha1, obj->sha1))
+ return obj;
+ if ((obj = obj_hash[H2(sha1)]) && !hashcmp(sha1, obj->sha1))
+ return obj;
+ return NULL;
+}
+
+static void grow_object_hash(void); /* forward */
+
+/*
+ * A naive single-table cuckoo hashing implementation.
+ * Return NULL when "obj" is successfully inserted. Otherwise
+ * return a pointer to the object to be inserted (which may
+ * be different from the original obj). The caller is expected
+ * to grow the hash table and re-insert the returned object.
+ */
+static struct object *insert_obj_hash(struct object *obj)
+{
+ int loop;
+
+ for (loop = obj_hash_size / 2; 0 <= loop; loop--) {
+ struct object *tmp_obj;
+ unsigned int ix;
+
+ ix = H1(obj->sha1);
+ if (!obj_hash[ix]) {
+ obj_hash[ix] = obj;
+ return NULL;
+ }
+ ix = H2(obj->sha1);
+ tmp_obj = obj_hash[ix];
+ obj_hash[ix] = obj;
+ if (!tmp_obj)
+ return NULL;
+ obj = tmp_obj;
}
return obj;
}
@@ -89,25 +108,36 @@ static int next_size(int sz)
static void grow_object_hash(void)
{
- int i;
- int new_hash_size = next_size(obj_hash_size);
- struct object **new_hash;
-
- new_hash = xcalloc(new_hash_size, sizeof(struct object *));
- for (i = 0; i < obj_hash_size; i++) {
- struct object *obj = obj_hash[i];
- if (!obj)
+ struct object **current_hash;
+ int current_size;
+
+ current_hash = obj_hash;
+ current_size = obj_hash_size;
+ while (1) {
+ int i;
+ obj_hash_size = next_size(obj_hash_size);
+ obj_hash = xcalloc(obj_hash_size, sizeof(struct object *));
+
+ for (i = 0; i < current_size; i++) {
+ if (!current_hash[i])
+ continue;
+ if (insert_obj_hash(current_hash[i]))
+ break;
+ }
+ if (i < current_size) {
+ /* too small - grow and retry */
+ free(obj_hash);
continue;
- insert_obj_hash(obj, new_hash, new_hash_size);
+ }
+ free(current_hash);
+ return;
}
- free(obj_hash);
- obj_hash = new_hash;
- obj_hash_size = new_hash_size;
}
void *create_object(const unsigned char *sha1, int type, void *o)
{
struct object *obj = o;
+ struct object *to_insert;
obj->parsed = 0;
obj->used = 0;
@@ -117,8 +147,13 @@ void *create_object(const unsigned char *sha1, int type, void *o)
if (obj_hash_size - 1 <= nr_objs * 2)
grow_object_hash();
-
- insert_obj_hash(obj, obj_hash, obj_hash_size);
+ to_insert = obj;
+ while (1) {
+ to_insert = insert_obj_hash(to_insert);
+ if (!to_insert)
+ break;
+ grow_object_hash();
+ }
nr_objs++;
return obj;
}
--
1.7.6.433.g1421f
Junio C Hamano <gitster@pobox.com>