* [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing
@ 2007-04-17 4:12 Linus Torvalds
2007-04-17 4:13 ` [PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
` (3 more replies)
0 siblings, 4 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 4:12 UTC (permalink / raw)
To: Git Mailing List, Junio C Hamano
This is a series of three patches that changes the low-level object
hashing to use a "object index" rather than the pointer to a "struct
object" in the hash-tables. It's something I've been thinking about for a
long time, so I just decided to do it.
The reason to do it is that on 64-bit architectures the object hash table
is actually a fairly sizeable entity, and not for a very good reason. It
has a ton of pointers to the objects we have allocated, so each hash-table
entry is 64-bits, even though obviously we aren't likely to ever have that
many objects.
So instead, we could use a 32-bit index into an object table - and in
fact, since we already do all normal object allocations using a special
dense allocatory that allocates 1024 objects in one go, we already kind of
were set up for this, with the low 10 bits of the object index being a
very natural index into each allocation block.
Could we ever want more than 4 billion objects? Unlikely, since you'd
actually need 80GB of memory just to keep track of the object names in
such a hash table, but hey, if that day ever comes, we can certainly
trivially make the index be 64-bit instead (or more likely, make it be
48-bit and use 16 bits of the hash table entry as an extended hash value
or something).
Anyway, the before-and-after numbers are somewhat debatable, so this is
purely a request for discussion..
Before:
[torvalds@woody linux]$ /usr/bin/time git-rev-list --all --objects | wc -l
5.66user 0.46system 0:06.12elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+44389minor)pagefaults 0swaps
445065
After:
[torvalds@woody linux]$ /usr/bin/time ~/git/git-rev-list --all --objects | wc -l
6.96user 0.36system 0:07.36elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+40240minor)pagefaults 0swaps
445065
ie it's actually slightly slower, but it uses almost 10% less memory
(minor page faults). Is it worth it? Probably not, but since I made the
patches, I thought I'd post them anyway. And the two first patches are
probably worth applying regardless - it's only the third patch that
actually changes things to use a hash index.
Anyway, the three patches are:
0001-Use-proper-object-allocators-for-unknown-object-node.patch
0002-Clean-up-object-creation-to-use-more-common-code.patch
0003-Make-the-object-lookup-hash-use-a-object-index-ins.patch
where 1-2 are pretty much just cleanups.
Comments?
Linus
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 1/3] Use proper object allocators for unknown object nodes too
2007-04-17 4:12 [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Linus Torvalds
@ 2007-04-17 4:13 ` Linus Torvalds
2007-04-17 4:13 ` [PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
` (2 subsequent siblings)
3 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 4:13 UTC (permalink / raw)
To: Git Mailing List, Junio C Hamano
We used to use a different allocator scheme for when we didn't know the
object type. That meant that objects that were created without any
up-front knowledge of the type would not go through the same allocation
paths as normal object allocations, and would miss out on the statistics.
But perhaps more importantly than the statistics (that are useful when
looking at memory usage but not much else), if we want to make the
object hash tables use a denser object pointer representation, we need
to make sure that they all go through the same blocking allocator.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
alloc.c | 21 +++++++++++++++------
cache.h | 1 +
object.c | 15 +++------------
3 files changed, 19 insertions(+), 18 deletions(-)
diff --git a/alloc.c b/alloc.c
index 460db19..c73aeec 100644
--- a/alloc.c
+++ b/alloc.c
@@ -18,7 +18,7 @@
#define BLOCKING 1024
-#define DEFINE_ALLOCATOR(name) \
+#define DEFINE_ALLOCATOR(name, type) \
static unsigned int name##_allocs; \
struct name *alloc_##name##_node(void) \
{ \
@@ -27,17 +27,26 @@ struct name *alloc_##name##_node(void) \
\
if (!nr) { \
nr = BLOCKING; \
- block = xcalloc(BLOCKING, sizeof(struct name)); \
+ block = xcalloc(BLOCKING, sizeof(type)); \
} \
nr--; \
name##_allocs++; \
return block++; \
}
-DEFINE_ALLOCATOR(blob)
-DEFINE_ALLOCATOR(tree)
-DEFINE_ALLOCATOR(commit)
-DEFINE_ALLOCATOR(tag)
+union any_object {
+ struct object object;
+ struct blob blob;
+ struct tree tree;
+ struct commit commit;
+ struct tag tag;
+};
+
+DEFINE_ALLOCATOR(blob, struct blob)
+DEFINE_ALLOCATOR(tree, struct tree)
+DEFINE_ALLOCATOR(commit, struct commit)
+DEFINE_ALLOCATOR(tag, struct tag)
+DEFINE_ALLOCATOR(object, union any_object)
#ifdef NO_C99_FORMAT
#define SZ_FMT "%u"
diff --git a/cache.h b/cache.h
index b1bd9e4..aa72791 100644
--- a/cache.h
+++ b/cache.h
@@ -484,6 +484,7 @@ extern struct blob *alloc_blob_node(void);
extern struct tree *alloc_tree_node(void);
extern struct commit *alloc_commit_node(void);
extern struct tag *alloc_tag_node(void);
+extern struct object *alloc_object_node(void);
extern void alloc_report(void);
/* trace.c */
diff --git a/object.c b/object.c
index 78a44a6..153ebac 100644
--- a/object.c
+++ b/object.c
@@ -120,22 +120,13 @@ void created_object(const unsigned char *sha1, struct object *obj)
nr_objs++;
}
-union any_object {
- struct object object;
- struct commit commit;
- struct tree tree;
- struct blob blob;
- struct tag tag;
-};
-
struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
if (!obj) {
- union any_object *ret = xcalloc(1, sizeof(*ret));
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_NONE;
- return &ret->object;
+ obj = alloc_object_node();
+ created_object(sha1, obj);
+ obj->type = OBJ_NONE;
}
return obj;
}
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 2/3] Clean up object creation to use more common code
2007-04-17 4:12 [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Linus Torvalds
2007-04-17 4:13 ` [PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
@ 2007-04-17 4:13 ` Linus Torvalds
2007-04-17 4:14 ` [PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
2007-04-17 4:21 ` [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Junio C Hamano
3 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 4:13 UTC (permalink / raw)
To: Git Mailing List, Junio C Hamano
This replaces the fairly odd "created_object()" function that did _most_
of the object setup with a more complete "create_object()" function that
also has a more natural calling convention.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
alloc.c | 2 +-
blob.c | 8 ++------
cache.h | 14 +++++---------
commit.c | 8 ++------
object.c | 14 +++++++-------
object.h | 2 +-
tag.c | 10 +++-------
tree.c | 8 ++------
8 files changed, 23 insertions(+), 43 deletions(-)
diff --git a/alloc.c b/alloc.c
index c73aeec..70f3c32 100644
--- a/alloc.c
+++ b/alloc.c
@@ -20,7 +20,7 @@
#define DEFINE_ALLOCATOR(name, type) \
static unsigned int name##_allocs; \
-struct name *alloc_##name##_node(void) \
+void *alloc_##name##_node(void) \
{ \
static int nr; \
static struct name *block; \
diff --git a/blob.c b/blob.c
index 0a9ea41..bd7d078 100644
--- a/blob.c
+++ b/blob.c
@@ -6,12 +6,8 @@ const char *blob_type = "blob";
struct blob *lookup_blob(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct blob *ret = alloc_blob_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_BLOB;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_BLOB, alloc_blob_node());
if (!obj->type)
obj->type = OBJ_BLOB;
if (obj->type != OBJ_BLOB) {
diff --git a/cache.h b/cache.h
index aa72791..4de25cc 100644
--- a/cache.h
+++ b/cache.h
@@ -476,15 +476,11 @@ int decode_85(char *dst, const char *line, int linelen);
void encode_85(char *buf, const unsigned char *data, int bytes);
/* alloc.c */
-struct blob;
-struct tree;
-struct commit;
-struct tag;
-extern struct blob *alloc_blob_node(void);
-extern struct tree *alloc_tree_node(void);
-extern struct commit *alloc_commit_node(void);
-extern struct tag *alloc_tag_node(void);
-extern struct object *alloc_object_node(void);
+extern void *alloc_blob_node(void);
+extern void *alloc_tree_node(void);
+extern void *alloc_commit_node(void);
+extern void *alloc_tag_node(void);
+extern void *alloc_object_node(void);
extern void alloc_report(void);
/* trace.c */
diff --git a/commit.c b/commit.c
index 952095f..10466c4 100644
--- a/commit.c
+++ b/commit.c
@@ -98,12 +98,8 @@ struct commit *lookup_commit_reference(const unsigned char *sha1)
struct commit *lookup_commit(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct commit *ret = alloc_commit_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_COMMIT;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
if (!obj->type)
obj->type = OBJ_COMMIT;
return check_commit(obj, sha1, 0);
diff --git a/object.c b/object.c
index 153ebac..7bd3fec 100644
--- a/object.c
+++ b/object.c
@@ -105,11 +105,13 @@ static void grow_object_hash(void)
obj_hash_size = new_hash_size;
}
-void created_object(const unsigned char *sha1, struct object *obj)
+void *create_object(const unsigned char *sha1, int type, void *o)
{
+ struct object *obj = o;
+
obj->parsed = 0;
obj->used = 0;
- obj->type = OBJ_NONE;
+ obj->type = type;
obj->flags = 0;
hashcpy(obj->sha1, sha1);
@@ -118,16 +120,14 @@ void created_object(const unsigned char *sha1, struct object *obj)
insert_obj_hash(obj, obj_hash, obj_hash_size);
nr_objs++;
+ return obj;
}
struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- obj = alloc_object_node();
- created_object(sha1, obj);
- obj->type = OBJ_NONE;
- }
+ if (!obj)
+ obj = create_object(sha1, OBJ_NONE, alloc_object_node());
return obj;
}
diff --git a/object.h b/object.h
index bdbf0fa..c0a5fd3 100644
--- a/object.h
+++ b/object.h
@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);
/** Internal only **/
struct object *lookup_object(const unsigned char *sha1);
-void created_object(const unsigned char *sha1, struct object *obj);
+extern void *create_object(const unsigned char *sha1, int type, void *obj);
/** Returns the object, having parsed it to find out what it is. **/
struct object *parse_object(const unsigned char *sha1);
diff --git a/tag.c b/tag.c
index 56a49f4..330d287 100644
--- a/tag.c
+++ b/tag.c
@@ -20,13 +20,9 @@ struct object *deref_tag(struct object *o, const char *warn, int warnlen)
struct tag *lookup_tag(const unsigned char *sha1)
{
- struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct tag *ret = alloc_tag_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_TAG;
- return ret;
- }
+ struct object *obj = lookup_object(sha1);
+ if (!obj)
+ return create_object(sha1, OBJ_TAG, alloc_tag_node());
if (!obj->type)
obj->type = OBJ_TAG;
if (obj->type != OBJ_TAG) {
diff --git a/tree.c b/tree.c
index d188c0f..e5bfbce 100644
--- a/tree.c
+++ b/tree.c
@@ -127,12 +127,8 @@ int read_tree(struct tree *tree, int stage, const char **match)
struct tree *lookup_tree(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct tree *ret = alloc_tree_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_TREE;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_TREE, alloc_tree_node());
if (!obj->type)
obj->type = OBJ_TREE;
if (obj->type != OBJ_TREE) {
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer
2007-04-17 4:12 [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Linus Torvalds
2007-04-17 4:13 ` [PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
2007-04-17 4:13 ` [PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
@ 2007-04-17 4:14 ` Linus Torvalds
2007-04-17 4:21 ` [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Junio C Hamano
3 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 4:14 UTC (permalink / raw)
To: Git Mailing List, Junio C Hamano
This uses less memory on 64-bit architectures (a 32-bit object index
rather than a full 64-bit pointer), but could also allow for some other
optimizations (like hiding part of the hash in unused bits of the index).
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
alloc.c | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++-----------
cache.h | 11 ++++---
object.c | 50 ++++++++++++++++++++++-------------
object.h | 2 +-
4 files changed, 108 insertions(+), 41 deletions(-)
diff --git a/alloc.c b/alloc.c
index 70f3c32..bc6aa30 100644
--- a/alloc.c
+++ b/alloc.c
@@ -16,24 +16,78 @@
#include "commit.h"
#include "tag.h"
-#define BLOCKING 1024
+/*
+ * We allocate 1024 object nodes at a time.
+ *
+ * This not only avoids any fragmentation in the system "malloc()"
+ * libraries, it also means that we can generate a denser "object
+ * index" that does not need a full pointer: we can use an integer
+ * with the low bits indicating the object node ID within an
+ * allocation block, and the high bits indicating the allocation
+ * block number.
+ */
+#define BLOCKING_BITS 10
+#define BLOCKING_SIZE (1u << BLOCKING_BITS)
+#define BLOCKING_MASK (BLOCKING_SIZE-1)
-#define DEFINE_ALLOCATOR(name, type) \
-static unsigned int name##_allocs; \
-void *alloc_##name##_node(void) \
-{ \
- static int nr; \
- static struct name *block; \
- \
- if (!nr) { \
- nr = BLOCKING; \
- block = xcalloc(BLOCKING, sizeof(type)); \
- } \
- nr--; \
- name##_allocs++; \
- return block++; \
+struct alloc_descriptor {
+ unsigned int size, nr;
+ unsigned int block;
+};
+
+struct block_descriptor {
+ unsigned int size;
+ unsigned char *base;
+};
+
+static struct block_descriptor *block_allocations;
+static unsigned int nr_block_allocations;
+
+static unsigned int alloc_new_block(unsigned int size)
+{
+ static unsigned int index;
+ unsigned int i = ++index;
+
+ if (i >= nr_block_allocations) {
+ unsigned int old = nr_block_allocations;
+ unsigned int nr = alloc_nr(i);
+ block_allocations = xrealloc(block_allocations, nr * sizeof(*block_allocations));
+ memset(block_allocations + old, 0, (nr - old) * sizeof(*block_allocations));
+ nr_block_allocations = nr;
+ }
+ block_allocations[i].size = size;
+ block_allocations[i].base = xcalloc(BLOCKING_SIZE, size);
+ return i;
+}
+
+static unsigned int allocate_one_index(struct alloc_descriptor *desc)
+{
+ unsigned int nr = desc->nr++;
+ unsigned int index = nr & BLOCKING_MASK;
+ if (!index)
+ desc->block = alloc_new_block(desc->size);
+ return (desc->block << BLOCKING_BITS) + index;
+}
+
+struct object *object_index_address(unsigned int index)
+{
+ unsigned int block = index >> BLOCKING_BITS;
+ struct block_descriptor *desc;
+
+ index &= BLOCKING_MASK;
+ if (!block || block >= nr_block_allocations)
+ die("invalid object index (block = %u/%u)", block, nr_block_allocations);
+ desc = block_allocations + block;
+ if (!desc->size || !desc->base)
+ die("bad object block index entry %u:%p", desc->size, desc->base);
+ return (struct object *)(index * desc->size + desc->base);
}
+#define DEFINE_ALLOCATOR(name, type) \
+static struct alloc_descriptor name##_desc = { sizeof(type) }; \
+unsigned int alloc_##name##_node(void) \
+{ return allocate_one_index(&name##_desc); }
+
union any_object {
struct object object;
struct blob blob;
@@ -62,7 +116,7 @@ static void report(const char* name, unsigned int count, size_t size)
#undef SZ_FMT
#define REPORT(name) \
- report(#name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)
+ report(#name, name##_desc.nr, name##_desc.nr*sizeof(struct name) >> 10)
void alloc_report(void)
{
diff --git a/cache.h b/cache.h
index 4de25cc..9342980 100644
--- a/cache.h
+++ b/cache.h
@@ -476,12 +476,13 @@ int decode_85(char *dst, const char *line, int linelen);
void encode_85(char *buf, const unsigned char *data, int bytes);
/* alloc.c */
-extern void *alloc_blob_node(void);
-extern void *alloc_tree_node(void);
-extern void *alloc_commit_node(void);
-extern void *alloc_tag_node(void);
-extern void *alloc_object_node(void);
+extern unsigned int alloc_blob_node(void);
+extern unsigned int alloc_tree_node(void);
+extern unsigned int alloc_commit_node(void);
+extern unsigned int alloc_tag_node(void);
+extern unsigned int alloc_object_node(void);
extern void alloc_report(void);
+extern struct object *object_index_address(unsigned int index);
/* trace.c */
extern int nfasprintf(char **str, const char *fmt, ...);
diff --git a/object.c b/object.c
index 7bd3fec..a91d238 100644
--- a/object.c
+++ b/object.c
@@ -5,7 +5,11 @@
#include "commit.h"
#include "tag.h"
-static struct object **obj_hash;
+struct hash_entry {
+ unsigned int index;
+};
+
+static struct hash_entry *obj_hash;
static int nr_objs, obj_hash_size;
unsigned int get_max_object_index(void)
@@ -13,9 +17,11 @@ unsigned int get_max_object_index(void)
return obj_hash_size;
}
+/* Purely for external object walkers (like fsck) */
struct object *get_indexed_object(unsigned int idx)
{
- return obj_hash[idx];
+ unsigned int object_index = obj_hash[idx].index;
+ return object_index ? object_index_address(object_index) : NULL;
}
static const char *object_type_strings[] = {
@@ -49,16 +55,16 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)
return hash % n;
}
-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
+static void insert_obj_hash(unsigned int object_index, struct object *object, struct hash_entry *hash, unsigned int size)
{
- int j = hash_obj(obj, size);
+ int j = hash_obj(object, size);
- while (hash[j]) {
+ while (hash[j].index) {
j++;
if (j >= size)
j = 0;
}
- hash[j] = obj;
+ hash[j].index = object_index;
}
static int hashtable_index(const unsigned char *sha1)
@@ -71,43 +77,49 @@ static int hashtable_index(const unsigned char *sha1)
struct object *lookup_object(const unsigned char *sha1)
{
int i;
- struct object *obj;
if (!obj_hash)
return NULL;
i = hashtable_index(sha1);
- while ((obj = obj_hash[i]) != NULL) {
- if (!hashcmp(sha1, obj->sha1))
+ for (;;) {
+ struct hash_entry *entry = obj_hash + i;
+ unsigned int index = entry->index;
+ struct object *obj;
+
+ if (!index)
break;
+ obj = object_index_address(index);
+ if (!hashcmp(sha1, obj->sha1))
+ return obj;
i++;
if (i == obj_hash_size)
i = 0;
}
- return obj;
+ return NULL;
}
static void grow_object_hash(void)
{
int i;
int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;
- struct object **new_hash;
+ struct hash_entry *new_hash;
- new_hash = xcalloc(new_hash_size, sizeof(struct object *));
+ new_hash = xcalloc(new_hash_size, sizeof(struct hash_entry));
for (i = 0; i < obj_hash_size; i++) {
- struct object *obj = obj_hash[i];
- if (!obj)
+ unsigned int index = obj_hash[i].index;
+ if (!index)
continue;
- insert_obj_hash(obj, new_hash, new_hash_size);
+ insert_obj_hash(index, object_index_address(index), new_hash, new_hash_size);
}
free(obj_hash);
obj_hash = new_hash;
obj_hash_size = new_hash_size;
}
-void *create_object(const unsigned char *sha1, int type, void *o)
+void *create_object(const unsigned char *sha1, int type, unsigned int index)
{
- struct object *obj = o;
+ struct object *obj = object_index_address(index);
obj->parsed = 0;
obj->used = 0;
@@ -118,7 +130,7 @@ 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);
+ insert_obj_hash(index, obj, obj_hash, obj_hash_size);
nr_objs++;
return obj;
}
@@ -127,7 +139,7 @@ struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
if (!obj)
- obj = create_object(sha1, OBJ_NONE, alloc_object_node());
+ return create_object(sha1, OBJ_NONE, alloc_object_node());
return obj;
}
diff --git a/object.h b/object.h
index c0a5fd3..099bbdb 100644
--- a/object.h
+++ b/object.h
@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);
/** Internal only **/
struct object *lookup_object(const unsigned char *sha1);
-extern void *create_object(const unsigned char *sha1, int type, void *obj);
+extern void *create_object(const unsigned char *sha1, int type, unsigned int object_index);
/** Returns the object, having parsed it to find out what it is. **/
struct object *parse_object(const unsigned char *sha1);
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing
2007-04-17 4:12 [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Linus Torvalds
` (2 preceding siblings ...)
2007-04-17 4:14 ` [PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
@ 2007-04-17 4:21 ` Junio C Hamano
2007-04-17 5:06 ` Linus Torvalds
3 siblings, 1 reply; 9+ messages in thread
From: Junio C Hamano @ 2007-04-17 4:21 UTC (permalink / raw)
To: Linus Torvalds; +Cc: Git Mailing List
Linus Torvalds <torvalds@linux-foundation.org> writes:
> This is a series of three patches that changes the low-level object
> hashing to use a "object index" rather than the pointer to a "struct
> object" in the hash-tables. It's something I've been thinking about for a
> long time, so I just decided to do it.
>
> The reason to do it is that on 64-bit architectures the object hash table
> is actually a fairly sizeable entity, and not for a very good reason. It
> has a ton of pointers to the objects we have allocated, so each hash-table
> entry is 64-bits, even though obviously we aren't likely to ever have that
> many objects.
I was thinking about revamping that "keeping track of all
objects" stuff for some time, too, but in a different direction.
Glad I have not touched that area ;-).
I think this makes sense, although the numbers are somewhat
dissapointing.
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing
2007-04-17 4:21 ` [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Junio C Hamano
@ 2007-04-17 5:06 ` Linus Torvalds
2007-04-17 5:10 ` [FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 5:06 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
On Mon, 16 Apr 2007, Junio C Hamano wrote:
>
> I was thinking about revamping that "keeping track of all
> objects" stuff for some time, too, but in a different direction.
> Glad I have not touched that area ;-).
Well, I obviously shouldn't have touched it either. I introduced a bug in
the first patch of the series (and the bug got removed by the third patch,
but since the third patch was not worth applying yet, it means that
patches 1 and 2 shouldn't be applied either, because of the bug).
The bug was that when I modified the generic object allocator framework to
work with "union any_object", it would still do
static struct name *block; /* where "name" was "object" */
...
return block++;
so while we *allocated* a block of "union any_objects", the patch would
then end up doling them out as "struct object" (which is *wrong* - we
don't know which kind of object it is yet, so we need to allocate the
maximum size!).
So it *should* have been
static type *block;
...
return block++;
but it actually turns out that my timings seem to say that it's better to
do the memset of the object just before returning it, so I changed it to
use "xmalloc()" instead of "xcalloc()" for the block allocation, and then
use
static type *block;
void *ret;
...
ret = block++;
memset(ret, 0, sizeof(type));
return ret;
instead.
> I think this makes sense, although the numbers are somewhat
> dissapointing.
Well, with just patches 1&2, the numbers don't go down, and the code looks
cleaner (and it removes more lines than it adds). So let me re-send the
series, and while I will re-send the final patch#3, only #1/#2 are
actually meant to be considered for actual inclusion at this point.
Linus
^ permalink raw reply [flat|nested] 9+ messages in thread
* [FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too
2007-04-17 5:06 ` Linus Torvalds
@ 2007-04-17 5:10 ` Linus Torvalds
2007-04-17 5:11 ` [FIXED PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
2007-04-17 5:13 ` [DUBIOUS PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
2 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 5:10 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
We used to use a different allocator scheme for when we didn't know the
object type. That meant that objects that were created without any
up-front knowledge of the type would not go through the same allocation
paths as normal object allocations, and would miss out on the statistics.
But perhaps more importantly than the statistics (that are useful when
looking at memory usage but not much else), if we want to make the
object hash tables use a denser object pointer representation, we need
to make sure that they all go through the same blocking allocator.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
Gaah. So this should be the properly working version. Not a lot of code
actually uses the "allocate unknown object", which is why nothing obvious
broke with the previous version that effectively only allocated a "struct
object", but it was still a bad bug.
Somebody should triple-check that I didn't screw up *again*.
alloc.c | 28 ++++++++++++++++++++--------
cache.h | 1 +
object.c | 15 +++------------
3 files changed, 24 insertions(+), 20 deletions(-)
diff --git a/alloc.c b/alloc.c
index 460db19..53eba37 100644
--- a/alloc.c
+++ b/alloc.c
@@ -18,26 +18,38 @@
#define BLOCKING 1024
-#define DEFINE_ALLOCATOR(name) \
+#define DEFINE_ALLOCATOR(name, type) \
static unsigned int name##_allocs; \
struct name *alloc_##name##_node(void) \
{ \
static int nr; \
- static struct name *block; \
+ static type *block; \
+ void *ret; \
\
if (!nr) { \
nr = BLOCKING; \
- block = xcalloc(BLOCKING, sizeof(struct name)); \
+ block = xmalloc(BLOCKING * sizeof(type)); \
} \
nr--; \
name##_allocs++; \
- return block++; \
+ ret = block++; \
+ memset(ret, 0, sizeof(type)); \
+ return ret; \
}
-DEFINE_ALLOCATOR(blob)
-DEFINE_ALLOCATOR(tree)
-DEFINE_ALLOCATOR(commit)
-DEFINE_ALLOCATOR(tag)
+union any_object {
+ struct object object;
+ struct blob blob;
+ struct tree tree;
+ struct commit commit;
+ struct tag tag;
+};
+
+DEFINE_ALLOCATOR(blob, struct blob)
+DEFINE_ALLOCATOR(tree, struct tree)
+DEFINE_ALLOCATOR(commit, struct commit)
+DEFINE_ALLOCATOR(tag, struct tag)
+DEFINE_ALLOCATOR(object, union any_object)
#ifdef NO_C99_FORMAT
#define SZ_FMT "%u"
diff --git a/cache.h b/cache.h
index b1bd9e4..aa72791 100644
--- a/cache.h
+++ b/cache.h
@@ -484,6 +484,7 @@ extern struct blob *alloc_blob_node(void);
extern struct tree *alloc_tree_node(void);
extern struct commit *alloc_commit_node(void);
extern struct tag *alloc_tag_node(void);
+extern struct object *alloc_object_node(void);
extern void alloc_report(void);
/* trace.c */
diff --git a/object.c b/object.c
index 78a44a6..153ebac 100644
--- a/object.c
+++ b/object.c
@@ -120,22 +120,13 @@ void created_object(const unsigned char *sha1, struct object *obj)
nr_objs++;
}
-union any_object {
- struct object object;
- struct commit commit;
- struct tree tree;
- struct blob blob;
- struct tag tag;
-};
-
struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
if (!obj) {
- union any_object *ret = xcalloc(1, sizeof(*ret));
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_NONE;
- return &ret->object;
+ obj = alloc_object_node();
+ created_object(sha1, obj);
+ obj->type = OBJ_NONE;
}
return obj;
}
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [FIXED PATCH 2/3] Clean up object creation to use more common code
2007-04-17 5:06 ` Linus Torvalds
2007-04-17 5:10 ` [FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
@ 2007-04-17 5:11 ` Linus Torvalds
2007-04-17 5:13 ` [DUBIOUS PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
2 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 5:11 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
This replaces the fairly odd "created_object()" function that did _most_
of the object setup with a more complete "create_object()" function that
also has a more natural calling convention.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
Should be identical to last version, except for the context around the
fix.. It removes 20 lines of code. Yay.
alloc.c | 2 +-
blob.c | 8 ++------
cache.h | 14 +++++---------
commit.c | 8 ++------
object.c | 14 +++++++-------
object.h | 2 +-
tag.c | 10 +++-------
tree.c | 8 ++------
8 files changed, 23 insertions(+), 43 deletions(-)
diff --git a/alloc.c b/alloc.c
index 53eba37..216c23a 100644
--- a/alloc.c
+++ b/alloc.c
@@ -20,7 +20,7 @@
#define DEFINE_ALLOCATOR(name, type) \
static unsigned int name##_allocs; \
-struct name *alloc_##name##_node(void) \
+void *alloc_##name##_node(void) \
{ \
static int nr; \
static type *block; \
diff --git a/blob.c b/blob.c
index 0a9ea41..bd7d078 100644
--- a/blob.c
+++ b/blob.c
@@ -6,12 +6,8 @@ const char *blob_type = "blob";
struct blob *lookup_blob(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct blob *ret = alloc_blob_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_BLOB;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_BLOB, alloc_blob_node());
if (!obj->type)
obj->type = OBJ_BLOB;
if (obj->type != OBJ_BLOB) {
diff --git a/cache.h b/cache.h
index aa72791..4de25cc 100644
--- a/cache.h
+++ b/cache.h
@@ -476,15 +476,11 @@ int decode_85(char *dst, const char *line, int linelen);
void encode_85(char *buf, const unsigned char *data, int bytes);
/* alloc.c */
-struct blob;
-struct tree;
-struct commit;
-struct tag;
-extern struct blob *alloc_blob_node(void);
-extern struct tree *alloc_tree_node(void);
-extern struct commit *alloc_commit_node(void);
-extern struct tag *alloc_tag_node(void);
-extern struct object *alloc_object_node(void);
+extern void *alloc_blob_node(void);
+extern void *alloc_tree_node(void);
+extern void *alloc_commit_node(void);
+extern void *alloc_tag_node(void);
+extern void *alloc_object_node(void);
extern void alloc_report(void);
/* trace.c */
diff --git a/commit.c b/commit.c
index 952095f..10466c4 100644
--- a/commit.c
+++ b/commit.c
@@ -98,12 +98,8 @@ struct commit *lookup_commit_reference(const unsigned char *sha1)
struct commit *lookup_commit(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct commit *ret = alloc_commit_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_COMMIT;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_COMMIT, alloc_commit_node());
if (!obj->type)
obj->type = OBJ_COMMIT;
return check_commit(obj, sha1, 0);
diff --git a/object.c b/object.c
index 153ebac..7bd3fec 100644
--- a/object.c
+++ b/object.c
@@ -105,11 +105,13 @@ static void grow_object_hash(void)
obj_hash_size = new_hash_size;
}
-void created_object(const unsigned char *sha1, struct object *obj)
+void *create_object(const unsigned char *sha1, int type, void *o)
{
+ struct object *obj = o;
+
obj->parsed = 0;
obj->used = 0;
- obj->type = OBJ_NONE;
+ obj->type = type;
obj->flags = 0;
hashcpy(obj->sha1, sha1);
@@ -118,16 +120,14 @@ void created_object(const unsigned char *sha1, struct object *obj)
insert_obj_hash(obj, obj_hash, obj_hash_size);
nr_objs++;
+ return obj;
}
struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- obj = alloc_object_node();
- created_object(sha1, obj);
- obj->type = OBJ_NONE;
- }
+ if (!obj)
+ obj = create_object(sha1, OBJ_NONE, alloc_object_node());
return obj;
}
diff --git a/object.h b/object.h
index bdbf0fa..c0a5fd3 100644
--- a/object.h
+++ b/object.h
@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);
/** Internal only **/
struct object *lookup_object(const unsigned char *sha1);
-void created_object(const unsigned char *sha1, struct object *obj);
+extern void *create_object(const unsigned char *sha1, int type, void *obj);
/** Returns the object, having parsed it to find out what it is. **/
struct object *parse_object(const unsigned char *sha1);
diff --git a/tag.c b/tag.c
index 56a49f4..330d287 100644
--- a/tag.c
+++ b/tag.c
@@ -20,13 +20,9 @@ struct object *deref_tag(struct object *o, const char *warn, int warnlen)
struct tag *lookup_tag(const unsigned char *sha1)
{
- struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct tag *ret = alloc_tag_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_TAG;
- return ret;
- }
+ struct object *obj = lookup_object(sha1);
+ if (!obj)
+ return create_object(sha1, OBJ_TAG, alloc_tag_node());
if (!obj->type)
obj->type = OBJ_TAG;
if (obj->type != OBJ_TAG) {
diff --git a/tree.c b/tree.c
index d188c0f..e5bfbce 100644
--- a/tree.c
+++ b/tree.c
@@ -127,12 +127,8 @@ int read_tree(struct tree *tree, int stage, const char **match)
struct tree *lookup_tree(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
- if (!obj) {
- struct tree *ret = alloc_tree_node();
- created_object(sha1, &ret->object);
- ret->object.type = OBJ_TREE;
- return ret;
- }
+ if (!obj)
+ return create_object(sha1, OBJ_TREE, alloc_tree_node());
if (!obj->type)
obj->type = OBJ_TREE;
if (obj->type != OBJ_TREE) {
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
* [DUBIOUS PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer
2007-04-17 5:06 ` Linus Torvalds
2007-04-17 5:10 ` [FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
2007-04-17 5:11 ` [FIXED PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
@ 2007-04-17 5:13 ` Linus Torvalds
2 siblings, 0 replies; 9+ messages in thread
From: Linus Torvalds @ 2007-04-17 5:13 UTC (permalink / raw)
To: Junio C Hamano; +Cc: Git Mailing List
This uses less memory on 64-bit architectures (a 32-bit object index
rather than a full 64-bit pointer), but could also allow for some other
optimizations. However, most of them would require that we actually
expose the object index to other parts of the system, which we currently
don't.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
As mentioned, the overhead of doing the index->object pointer conversion
seems to be big enough that this isn't worth it.
Admittedly part of that overhead is the debugging code I added, so this
may not be that bad an idea after all, but still..
alloc.c | 89 ++++++++++++++++++++++++++++++++++++++++++++++++-------------
cache.h | 11 ++++---
object.c | 50 +++++++++++++++++++++-------------
object.h | 2 +-
4 files changed, 108 insertions(+), 44 deletions(-)
diff --git a/alloc.c b/alloc.c
index 216c23a..bc6aa30 100644
--- a/alloc.c
+++ b/alloc.c
@@ -16,27 +16,78 @@
#include "commit.h"
#include "tag.h"
-#define BLOCKING 1024
+/*
+ * We allocate 1024 object nodes at a time.
+ *
+ * This not only avoids any fragmentation in the system "malloc()"
+ * libraries, it also means that we can generate a denser "object
+ * index" that does not need a full pointer: we can use an integer
+ * with the low bits indicating the object node ID within an
+ * allocation block, and the high bits indicating the allocation
+ * block number.
+ */
+#define BLOCKING_BITS 10
+#define BLOCKING_SIZE (1u << BLOCKING_BITS)
+#define BLOCKING_MASK (BLOCKING_SIZE-1)
-#define DEFINE_ALLOCATOR(name, type) \
-static unsigned int name##_allocs; \
-void *alloc_##name##_node(void) \
-{ \
- static int nr; \
- static type *block; \
- void *ret; \
- \
- if (!nr) { \
- nr = BLOCKING; \
- block = xmalloc(BLOCKING * sizeof(type)); \
- } \
- nr--; \
- name##_allocs++; \
- ret = block++; \
- memset(ret, 0, sizeof(type)); \
- return ret; \
+struct alloc_descriptor {
+ unsigned int size, nr;
+ unsigned int block;
+};
+
+struct block_descriptor {
+ unsigned int size;
+ unsigned char *base;
+};
+
+static struct block_descriptor *block_allocations;
+static unsigned int nr_block_allocations;
+
+static unsigned int alloc_new_block(unsigned int size)
+{
+ static unsigned int index;
+ unsigned int i = ++index;
+
+ if (i >= nr_block_allocations) {
+ unsigned int old = nr_block_allocations;
+ unsigned int nr = alloc_nr(i);
+ block_allocations = xrealloc(block_allocations, nr * sizeof(*block_allocations));
+ memset(block_allocations + old, 0, (nr - old) * sizeof(*block_allocations));
+ nr_block_allocations = nr;
+ }
+ block_allocations[i].size = size;
+ block_allocations[i].base = xcalloc(BLOCKING_SIZE, size);
+ return i;
+}
+
+static unsigned int allocate_one_index(struct alloc_descriptor *desc)
+{
+ unsigned int nr = desc->nr++;
+ unsigned int index = nr & BLOCKING_MASK;
+ if (!index)
+ desc->block = alloc_new_block(desc->size);
+ return (desc->block << BLOCKING_BITS) + index;
+}
+
+struct object *object_index_address(unsigned int index)
+{
+ unsigned int block = index >> BLOCKING_BITS;
+ struct block_descriptor *desc;
+
+ index &= BLOCKING_MASK;
+ if (!block || block >= nr_block_allocations)
+ die("invalid object index (block = %u/%u)", block, nr_block_allocations);
+ desc = block_allocations + block;
+ if (!desc->size || !desc->base)
+ die("bad object block index entry %u:%p", desc->size, desc->base);
+ return (struct object *)(index * desc->size + desc->base);
}
+#define DEFINE_ALLOCATOR(name, type) \
+static struct alloc_descriptor name##_desc = { sizeof(type) }; \
+unsigned int alloc_##name##_node(void) \
+{ return allocate_one_index(&name##_desc); }
+
union any_object {
struct object object;
struct blob blob;
@@ -65,7 +116,7 @@ static void report(const char* name, unsigned int count, size_t size)
#undef SZ_FMT
#define REPORT(name) \
- report(#name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)
+ report(#name, name##_desc.nr, name##_desc.nr*sizeof(struct name) >> 10)
void alloc_report(void)
{
diff --git a/cache.h b/cache.h
index 4de25cc..9342980 100644
--- a/cache.h
+++ b/cache.h
@@ -476,12 +476,13 @@ int decode_85(char *dst, const char *line, int linelen);
void encode_85(char *buf, const unsigned char *data, int bytes);
/* alloc.c */
-extern void *alloc_blob_node(void);
-extern void *alloc_tree_node(void);
-extern void *alloc_commit_node(void);
-extern void *alloc_tag_node(void);
-extern void *alloc_object_node(void);
+extern unsigned int alloc_blob_node(void);
+extern unsigned int alloc_tree_node(void);
+extern unsigned int alloc_commit_node(void);
+extern unsigned int alloc_tag_node(void);
+extern unsigned int alloc_object_node(void);
extern void alloc_report(void);
+extern struct object *object_index_address(unsigned int index);
/* trace.c */
extern int nfasprintf(char **str, const char *fmt, ...);
diff --git a/object.c b/object.c
index 7bd3fec..a91d238 100644
--- a/object.c
+++ b/object.c
@@ -5,7 +5,11 @@
#include "commit.h"
#include "tag.h"
-static struct object **obj_hash;
+struct hash_entry {
+ unsigned int index;
+};
+
+static struct hash_entry *obj_hash;
static int nr_objs, obj_hash_size;
unsigned int get_max_object_index(void)
@@ -13,9 +17,11 @@ unsigned int get_max_object_index(void)
return obj_hash_size;
}
+/* Purely for external object walkers (like fsck) */
struct object *get_indexed_object(unsigned int idx)
{
- return obj_hash[idx];
+ unsigned int object_index = obj_hash[idx].index;
+ return object_index ? object_index_address(object_index) : NULL;
}
static const char *object_type_strings[] = {
@@ -49,16 +55,16 @@ static unsigned int hash_obj(struct object *obj, unsigned int n)
return hash % n;
}
-static void insert_obj_hash(struct object *obj, struct object **hash, unsigned int size)
+static void insert_obj_hash(unsigned int object_index, struct object *object, struct hash_entry *hash, unsigned int size)
{
- int j = hash_obj(obj, size);
+ int j = hash_obj(object, size);
- while (hash[j]) {
+ while (hash[j].index) {
j++;
if (j >= size)
j = 0;
}
- hash[j] = obj;
+ hash[j].index = object_index;
}
static int hashtable_index(const unsigned char *sha1)
@@ -71,43 +77,49 @@ static int hashtable_index(const unsigned char *sha1)
struct object *lookup_object(const unsigned char *sha1)
{
int i;
- struct object *obj;
if (!obj_hash)
return NULL;
i = hashtable_index(sha1);
- while ((obj = obj_hash[i]) != NULL) {
- if (!hashcmp(sha1, obj->sha1))
+ for (;;) {
+ struct hash_entry *entry = obj_hash + i;
+ unsigned int index = entry->index;
+ struct object *obj;
+
+ if (!index)
break;
+ obj = object_index_address(index);
+ if (!hashcmp(sha1, obj->sha1))
+ return obj;
i++;
if (i == obj_hash_size)
i = 0;
}
- return obj;
+ return NULL;
}
static void grow_object_hash(void)
{
int i;
int new_hash_size = obj_hash_size < 32 ? 32 : 2 * obj_hash_size;
- struct object **new_hash;
+ struct hash_entry *new_hash;
- new_hash = xcalloc(new_hash_size, sizeof(struct object *));
+ new_hash = xcalloc(new_hash_size, sizeof(struct hash_entry));
for (i = 0; i < obj_hash_size; i++) {
- struct object *obj = obj_hash[i];
- if (!obj)
+ unsigned int index = obj_hash[i].index;
+ if (!index)
continue;
- insert_obj_hash(obj, new_hash, new_hash_size);
+ insert_obj_hash(index, object_index_address(index), new_hash, new_hash_size);
}
free(obj_hash);
obj_hash = new_hash;
obj_hash_size = new_hash_size;
}
-void *create_object(const unsigned char *sha1, int type, void *o)
+void *create_object(const unsigned char *sha1, int type, unsigned int index)
{
- struct object *obj = o;
+ struct object *obj = object_index_address(index);
obj->parsed = 0;
obj->used = 0;
@@ -118,7 +130,7 @@ 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);
+ insert_obj_hash(index, obj, obj_hash, obj_hash_size);
nr_objs++;
return obj;
}
@@ -127,7 +139,7 @@ struct object *lookup_unknown_object(const unsigned char *sha1)
{
struct object *obj = lookup_object(sha1);
if (!obj)
- obj = create_object(sha1, OBJ_NONE, alloc_object_node());
+ return create_object(sha1, OBJ_NONE, alloc_object_node());
return obj;
}
diff --git a/object.h b/object.h
index c0a5fd3..099bbdb 100644
--- a/object.h
+++ b/object.h
@@ -47,7 +47,7 @@ extern struct object_refs *lookup_object_refs(struct object *);
/** Internal only **/
struct object *lookup_object(const unsigned char *sha1);
-extern void *create_object(const unsigned char *sha1, int type, void *obj);
+extern void *create_object(const unsigned char *sha1, int type, unsigned int object_index);
/** Returns the object, having parsed it to find out what it is. **/
struct object *parse_object(const unsigned char *sha1);
--
1.5.1.1.107.g7a15
^ permalink raw reply related [flat|nested] 9+ messages in thread
end of thread, other threads:[~2007-04-17 5:13 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2007-04-17 4:12 [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Linus Torvalds
2007-04-17 4:13 ` [PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
2007-04-17 4:13 ` [PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
2007-04-17 4:14 ` [PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
2007-04-17 4:21 ` [RFD PATCH 0/3] Use "object index" rather than pointers in the object hashing Junio C Hamano
2007-04-17 5:06 ` Linus Torvalds
2007-04-17 5:10 ` [FIXED PATCH 1/3] Use proper object allocators for unknown object nodes too Linus Torvalds
2007-04-17 5:11 ` [FIXED PATCH 2/3] Clean up object creation to use more common code Linus Torvalds
2007-04-17 5:13 ` [DUBIOUS PATCH 3/3] Make the object lookup hash use a "object index" instead of a pointer Linus Torvalds
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).