{"thread":{"id":"4563","subject":"Remove \"refs\" field from \"struct object\"","startedAt":"2006-06-18T18:45:02Z","lastAt":"2006-06-18T18:57:40Z","messageCount":2,"participants":["Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22034","messageId":"Pine.LNX.4.64.0606181137380.5498@g5.osdl.org","threadId":"4563","inReplyTo":null,"subject":"Remove \"refs\" field from \"struct object\"","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-18T18:45:02Z","receivedAt":"2006-06-18T18:45:02Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis shrinks \"struct object\" to the absolutely minimal size possible.\nIt now contains /only/ the object flags and the SHA1 hash name of the\nobject.\n\nThe \"refs\" field, which is really needed only for fsck, is maintained in\na separate hashed lookup-table, allowing all normal users to totally\nignore it.\n\nThis helps memory usage, although not as much as I hoped: it looks like \nthe allocation overhead of malloc (and the alignment constraints in \nparticular) means that while the structure size shrinks, the actual \nallocation overhead mostly does not.\n\n[ That said: memory usage is actually down, but not as much as it should\n  be: I suspect just one of the object types actually ended up shrinking\n  its effective allocation size.\n\n  To get to the next level, we probably need specialized allocators that\n  don't pad the allocation more than necessary. ]\n\nThe separation makes for some code cleanup, though, and makes the ref\ntracking that fsck wants a clearly separate thing.\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\nIt turns out that removing the refs member wasn't as hard as I \nanticipated: the refs usage by git-fsck-objects was very well defined, and \nthe actual patch to do this all is mostly the addition of the hashed \nlookup and insertion (same logic as for the objects themselves), and some \nvery small cosmetic changes to anything that set/read the object->refs \nfield.\n\nHalf of the patch is moving the refs-related code to a file of its own.\n\nI'd like to clean up some things later (make the object re-hashing be as \nclean and simple as the refs re-hashing is), but wanted to keep this patch \nfairly minimal and do just the refs-related changes.\n\nThe alignment problem is because the objects actually need just 4-byte \nalignment on 32-bit architectures, but \"malloc()\" will return 8- or \n16-byte aligned allocations, so we will have totally unnecessary overhead \nthere. \n\nThis patch will be necessary regardless - the alloction alignment is a \nseparate issue that just hides much of the shrinkage win.\n\n Makefile       |    2 -\n fsck-objects.c |    5 +-\n object-refs.c  |  142 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n object.c       |   70 ----------------------------\n object.h       |    4 +-\n 5 files changed, 149 insertions(+), 74 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex 2a1e639..244a4d1 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -212,7 +212,7 @@ LIB_OBJS = \\\n \tblob.o commit.o connect.o csum-file.o cache-tree.o base85.o \\\n \tdate.o diff-delta.o entry.o exec_cmd.o ident.o lockfile.o \\\n \tobject.o pack-check.o patch-delta.o path.o pkt-line.o \\\n-\tquote.o read-cache.o refs.o run-command.o dir.o \\\n+\tquote.o read-cache.o refs.o run-command.o dir.o object-refs.o \\\n \tserver-info.o setup.o sha1_file.o sha1_name.o strbuf.o \\\n \ttag.o tree.o usage.o config.o environment.o ctype.o copy.o \\\n \tfetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \\\ndiff --git a/fsck-objects.c b/fsck-objects.c\nindex 2b1aab4..769bb2a 100644\n--- a/fsck-objects.c\n+++ b/fsck-objects.c\n@@ -64,6 +64,7 @@ static void check_connectivity(void)\n \n \t/* Look up all the requirements, warn about missing objects.. */\n \tfor (i = 0; i < obj_allocs; i++) {\n+\t\tconst struct object_refs *refs;\n \t\tstruct object *obj = objs[i];\n \n \t\tif (!obj)\n@@ -78,8 +79,8 @@ static void check_connectivity(void)\n \t\t\tcontinue;\n \t\t}\n \n-\t\tif (obj->refs) {\n-\t\t\tconst struct object_refs *refs = obj->refs;\n+\t\trefs = lookup_object_refs(obj);\n+\t\tif (refs) {\n \t\t\tunsigned j;\n \t\t\tfor (j = 0; j < refs->count; j++) {\n \t\t\t\tstruct object *ref = refs->ref[j];\ndiff --git a/object-refs.c b/object-refs.c\nnew file mode 100644\nindex 0000000..8afa227\n--- /dev/null\n+++ b/object-refs.c\n@@ -0,0 +1,142 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+\n+int track_object_refs = 0;\n+\n+static unsigned int refs_hash_size, nr_object_refs;\n+static struct object_refs **refs_hash;\n+\n+static unsigned int hash_obj(struct object *obj, unsigned int n)\n+{\n+\tunsigned int hash = *(unsigned int *)obj->sha1;\n+\treturn hash % n;\n+}\n+\n+static void grow_refs_hash(void)\n+{\n+\tint i;\n+\tint new_hash_size = (refs_hash_size + 1000) * 3 / 2;\n+\tstruct object_refs **new_hash;\n+\n+\tnew_hash = calloc(new_hash_size, sizeof(struct object_refs *));\n+\tfor (i = 0; i < refs_hash_size; i++) {\n+\t\tint j;\n+\t\tstruct object_refs *ref = refs_hash[i];\n+\t\tif (!ref)\n+\t\t\tcontinue;\n+\t\tj = hash_obj(ref->base, new_hash_size);\n+\t\tnew_hash[j] = ref;\n+\t}\n+\tfree(refs_hash);\n+\trefs_hash = new_hash;\n+\trefs_hash_size = new_hash_size;\n+}\n+\n+static void insert_ref_hash(struct object_refs *ref)\n+{\n+\tint j = hash_obj(ref->base, refs_hash_size);\n+\n+\twhile (refs_hash[j]) {\n+\t\tj++;\n+\t\tif (j >= refs_hash_size)\n+\t\t\tj = 0;\n+\t}\n+\trefs_hash[j] = ref;\n+}\n+\n+static void add_object_refs(struct object *obj, struct object_refs *ref)\n+{\n+\tint nr = nr_object_refs + 1;\n+\n+\tif (nr > refs_hash_size * 2 / 3)\n+\t\tgrow_refs_hash();\n+\tref->base = obj;\n+\tinsert_ref_hash(ref);\n+\tnr_object_refs = nr;\n+}\n+\n+struct object_refs *lookup_object_refs(struct object *obj)\n+{\n+\tint j = hash_obj(obj, refs_hash_size);\n+\tstruct object_refs *ref;\n+\n+\twhile ((ref = refs_hash[j]) != NULL) {\n+\t\tif (ref->base == obj)\n+\t\t\tbreak;\n+\t\tj++;\n+\t\tif (j >= refs_hash_size)\n+\t\t\tj = 0;\n+\t}\n+\treturn ref;\n+}\n+\n+struct object_refs *alloc_object_refs(unsigned count)\n+{\n+\tstruct object_refs *refs;\n+\tsize_t size = sizeof(*refs) + count*sizeof(struct object *);\n+\n+\trefs = xcalloc(1, size);\n+\trefs->count = count;\n+\treturn refs;\n+}\n+\n+static int compare_object_pointers(const void *a, const void *b)\n+{\n+\tconst struct object * const *pa = a;\n+\tconst struct object * const *pb = b;\n+\tif (*pa == *pb)\n+\t\treturn 0;\n+\telse if (*pa < *pb)\n+\t\treturn -1;\n+\telse\n+\t\treturn 1;\n+}\n+\n+void set_object_refs(struct object *obj, struct object_refs *refs)\n+{\n+\tunsigned int i, j;\n+\n+\t/* Do not install empty list of references */\n+\tif (refs->count < 1) {\n+\t\tfree(refs);\n+\t\treturn;\n+\t}\n+\n+\t/* Sort the list and filter out duplicates */\n+\tqsort(refs->ref, refs->count, sizeof(refs->ref[0]),\n+\t      compare_object_pointers);\n+\tfor (i = j = 1; i < refs->count; i++) {\n+\t\tif (refs->ref[i] != refs->ref[i - 1])\n+\t\t\trefs->ref[j++] = refs->ref[i];\n+\t}\n+\tif (j < refs->count) {\n+\t\t/* Duplicates were found - reallocate list */\n+\t\tsize_t size = sizeof(*refs) + j*sizeof(struct object *);\n+\t\trefs->count = j;\n+\t\trefs = xrealloc(refs, size);\n+\t}\n+\n+\tfor (i = 0; i < refs->count; i++)\n+\t\trefs->ref[i]->used = 1;\n+\tadd_object_refs(obj, refs);\n+}\n+\n+void mark_reachable(struct object *obj, unsigned int mask)\n+{\n+\tconst struct object_refs *refs;\n+\n+\tif (!track_object_refs)\n+\t\tdie(\"cannot do reachability with object refs turned off\");\n+\t/* If we've been here already, don't bother */\n+\tif (obj->flags & mask)\n+\t\treturn;\n+\tobj->flags |= mask;\n+\trefs = lookup_object_refs(obj);\n+\tif (refs) {\n+\t\tunsigned i;\n+\t\tfor (i = 0; i < refs->count; i++)\n+\t\t\tmark_reachable(refs->ref[i], mask);\n+\t}\n+}\n+\n+\ndiff --git a/object.c b/object.c\nindex 0f70890..e26e319 100644\n--- a/object.c\n+++ b/object.c\n@@ -13,8 +13,6 @@ const char *type_names[] = {\n \t\"none\", \"blob\", \"tree\", \"commit\", \"bad\"\n };\n \n-int track_object_refs = 0;\n-\n static int hashtable_index(const unsigned char *sha1)\n {\n \tunsigned int i;\n@@ -55,7 +53,6 @@ void created_object(const unsigned char \n \tobj->parsed = 0;\n \tmemcpy(obj->sha1, sha1, 20);\n \tobj->type = TYPE_NONE;\n-\tobj->refs = NULL;\n \tobj->used = 0;\n \n \tif (obj_allocs - 1 <= nr_objs * 2) {\n@@ -84,73 +81,6 @@ void created_object(const unsigned char \n \tnr_objs++;\n }\n \n-struct object_refs *alloc_object_refs(unsigned count)\n-{\n-\tstruct object_refs *refs;\n-\tsize_t size = sizeof(*refs) + count*sizeof(struct object *);\n-\n-\trefs = xcalloc(1, size);\n-\trefs->count = count;\n-\treturn refs;\n-}\n-\n-static int compare_object_pointers(const void *a, const void *b)\n-{\n-\tconst struct object * const *pa = a;\n-\tconst struct object * const *pb = b;\n-\tif (*pa == *pb)\n-\t\treturn 0;\n-\telse if (*pa < *pb)\n-\t\treturn -1;\n-\telse\n-\t\treturn 1;\n-}\n-\n-void set_object_refs(struct object *obj, struct object_refs *refs)\n-{\n-\tunsigned int i, j;\n-\n-\t/* Do not install empty list of references */\n-\tif (refs->count < 1) {\n-\t\tfree(refs);\n-\t\treturn;\n-\t}\n-\n-\t/* Sort the list and filter out duplicates */\n-\tqsort(refs->ref, refs->count, sizeof(refs->ref[0]),\n-\t      compare_object_pointers);\n-\tfor (i = j = 1; i < refs->count; i++) {\n-\t\tif (refs->ref[i] != refs->ref[i - 1])\n-\t\t\trefs->ref[j++] = refs->ref[i];\n-\t}\n-\tif (j < refs->count) {\n-\t\t/* Duplicates were found - reallocate list */\n-\t\tsize_t size = sizeof(*refs) + j*sizeof(struct object *);\n-\t\trefs->count = j;\n-\t\trefs = xrealloc(refs, size);\n-\t}\n-\n-\tfor (i = 0; i < refs->count; i++)\n-\t\trefs->ref[i]->used = 1;\n-\tobj->refs = refs;\n-}\n-\n-void mark_reachable(struct object *obj, unsigned int mask)\n-{\n-\tif (!track_object_refs)\n-\t\tdie(\"cannot do reachability with object refs turned off\");\n-\t/* If we've been here already, don't bother */\n-\tif (obj->flags & mask)\n-\t\treturn;\n-\tobj->flags |= mask;\n-\tif (obj->refs) {\n-\t\tconst struct object_refs *refs = obj->refs;\n-\t\tunsigned i;\n-\t\tfor (i = 0; i < refs->count; i++)\n-\t\t\tmark_reachable(refs->ref[i], mask);\n-\t}\n-}\n-\n struct object *lookup_object_type(const unsigned char *sha1, const char *type)\n {\n \tif (!type) {\ndiff --git a/object.h b/object.h\nindex f4ee2e5..c537b4b 100644\n--- a/object.h\n+++ b/object.h\n@@ -9,6 +9,7 @@ struct object_list {\n \n struct object_refs {\n \tunsigned count;\n+\tstruct object *base;\n \tstruct object *ref[FLEX_ARRAY]; /* more */\n };\n \n@@ -28,7 +29,6 @@ struct object {\n \tunsigned type : TYPE_BITS;\n \tunsigned flags : FLAG_BITS;\n \tunsigned char sha1[20];\n-\tstruct object_refs *refs;\n };\n \n extern int track_object_refs;\n@@ -41,6 +41,8 @@ static inline const char *typename(unsig\n \treturn type_names[type > TYPE_TAG ? TYPE_BAD : type];\n }\n \n+extern struct object_refs *lookup_object_refs(struct object *);\n+\n /** Internal only **/\n struct object *lookup_object(const unsigned char *sha1);\n \n"},{"id":"22035","messageId":"Pine.LNX.4.64.0606181147080.5498@g5.osdl.org","threadId":"4563","inReplyTo":"Pine.LNX.4.64.0606181137380.5498@g5.osdl.org","subject":"Re: Remove \"refs\" field from \"struct object\"","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-18T18:57:40Z","receivedAt":"2006-06-18T18:57:40Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sun, 18 Jun 2006, Linus Torvalds wrote:\n>\n> The \"refs\" field, which is really needed only for fsck, is maintained in\n> a separate hashed lookup-table, allowing all normal users to totally\n> ignore it.\n\nBtw, in case people wondered: the cost to git-fsck-objects seems to be \nzero and sometimes apparently even negative.\n\nIn order to remove \"refs\" from \"struct object\", I had to add it to the \nobject_refs structure instead, and so you'd think that the memory usage \nfor git-fsck-objects (which needs the object refs) should be unchanged, \nwhile the hashed lookup should be more expensive than just the direct \npointer lookup.\n\nActually testing it, though, implies that isn't the case. Lots of objects \n(every single blob object, in fact) have no refs at all, and for that case \nwe don't create any \"object_refs\" structure at all, so we don't actually \nend up with a 1:1 relationship, and we win a small amount of memory.\n\nAnd the hashing seems to be effective enough that it's no costlier than \nlooking up the ref pointer directly from the object. There's probably \nsome bad cache behaviour from the hashing, but it didn't show up in the \nbenchmarking I did (ie fsck took as long before as it did afterwards, \nboth for git and for the kernel archive).\n\nIt may be (probably is) that the reachability analysis is just a very \nsmall portion of the overall costs, and it's just not very noticeable. It \nmay also be that whatever bad cache behaviours you get from the extra hash \nlookup are just balanced out by the objects themselves being slightly \ndenser and better in the cache (although that is probably partly hidden \nagain by the extra malloc padding).\n\nRegardless, there doesn't really seem to be any downsides, but I didn't \ntest it _that_ exhaustively.\n\n\t\tLinus\n"}]}