{"thread":{"id":"4568","subject":"Add specialized object allocator","startedAt":"2006-06-19T17:44:15Z","lastAt":"2006-06-19T21:38:45Z","messageCount":5,"participants":["Linus Torvalds","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"22068","messageId":"Pine.LNX.4.64.0606191028540.5498@g5.osdl.org","threadId":"4568","inReplyTo":null,"subject":"Add specialized object allocator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-19T17:44:15Z","receivedAt":"2006-06-19T17:44:15Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\nThis creates a simple specialized object allocator for basic\nobjects.\n\nThis avoids wasting space with malloc overhead (metadata and\nextra alignment), since the specialized allocator knows the\nalignment, and that objects, once allocated, are never freed.\n\nIt also allows us to track some basic statistics about object\nallocations. For example, for the mozilla import, it shows\nobject usage as follows:\n\n     blobs:   627629 (14710 kB)\n     trees:  1119035 (34969 kB)\n   commits:   196423  (8440 kB)\n      tags:     1336    (46 kB)\n\nand the simpler allocator shaves off about 2.5% off the memory\nfootprint off a \"git-rev-list --all --objects\", and is a bit\nfaster too.\n\n[ Side note: this concludes the series of \"save memory in object storage\". \n  The thing is, there simply isn't much more to be saved on the objects.\n\n  Doing \"git-rev-list --all --objects\" on the mozilla archive has a final \n  total RSS of 131498 pages for me: that's about 513MB. Of that, the \n  object overhead is now just 56MB, the rest is going somewhere else (put \n  another way: the fact that this patch shaves off 2.5% of the total \n  memory overhead, considering that objects are now not much more than 10% \n  of the total shows how big the wasted space really was: this makes \n  object allocations much more memory- and time-efficient).\n\n  I haven't looked at where the rest is, but I suspect the bulk of it is \n  just the pack-file loading. It may be that we should pack the tree \n  objects separately from the blob objects: for git-rev-list --objects, we \n  don't actually ever need to even look at the blobs, but since trees and \n  blobs are interspersed in the pack-file, we end up not being dense in \n  the tree accesses, so we end up looking at more pages than we strictly \n  need to.\n\n  So with a 535MB pack-file, it's entirely possible - even likely - that \n  most of the remaining RSS is just the mmap of the pack-file itself. We \n  don't need to map in _all_ of it, but we do end up mapping a fair \n  amount. ]\n\nSigned-off-by: Linus Torvalds <torvalds@osdl.org>\n---\n\n\n Makefile |    2 +-\n alloc.c  |   51 +++++++++++++++++++++++++++++++++++++++++++++++++++\n blob.c   |    2 +-\n cache.h  |   11 +++++++++++\n commit.c |    2 +-\n tag.c    |    2 +-\n tree.c   |    2 +-\n 7 files changed, 67 insertions(+), 5 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex ea8cd28..0887945 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -216,7 +216,7 @@ LIB_OBJS = \\\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 \\\n-\t$(DIFF_OBJS)\n+\talloc.o $(DIFF_OBJS)\n \n BUILTIN_OBJS = \\\n \tbuiltin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \\\ndiff --git a/alloc.c b/alloc.c\nnew file mode 100644\nindex 0000000..65ec0cc\n--- /dev/null\n+++ b/alloc.c\n@@ -0,0 +1,51 @@\n+/*\n+ * alloc.c  - specialized allocator for internal objects\n+ *\n+ * Copyright (C) 2006 Linus Torvalds\n+ *\n+ * The standard malloc/free wastes too much space for objects, partly because\n+ * it maintains all the allocation infrastructure (which isn't needed, since\n+ * we never free an object descriptor anyway), but even more because it ends\n+ * up with maximal alignment because it doesn't know what the object alignment\n+ * for the new allocation is.\n+ */\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"blob.h\"\n+#include \"tree.h\"\n+#include \"commit.h\"\n+#include \"tag.h\"\n+\n+#define BLOCKING 1024\n+\n+#define DEFINE_ALLOCATOR(name)\t\t\t\t\t\\\n+static unsigned int name##_allocs;\t\t\t\t\\\n+struct name *alloc_##name##_node(void)\t\t\t\t\\\n+{\t\t\t\t\t\t\t\t\\\n+\tstatic int nr;\t\t\t\t\t\t\\\n+\tstatic struct name *block;\t\t\t\t\\\n+\t\t\t\t\t\t\t\t\\\n+\tif (!nr) {\t\t\t\t\t\t\\\n+\t\tnr = BLOCKING;\t\t\t\t\t\\\n+\t\tblock = xcalloc(BLOCKING, sizeof(struct name));\t\\\n+\t}\t\t\t\t\t\t\t\\\n+\tnr--;\t\t\t\t\t\t\t\\\n+\tname##_allocs++;\t\t\t\t\t\\\n+\treturn block++;\t\t\t\t\t\t\\\n+}\n+\n+DEFINE_ALLOCATOR(blob);\n+DEFINE_ALLOCATOR(tree);\n+DEFINE_ALLOCATOR(commit);\n+DEFINE_ALLOCATOR(tag);\n+\n+#define REPORT(name)\t\\\n+\tfprintf(stderr, \"%10s: %8u (%zu kB)\\n\", #name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)\n+\n+void alloc_report(void)\n+{\n+\tREPORT(blob);\n+\tREPORT(tree);\n+\tREPORT(commit);\n+\tREPORT(tag);\n+}\ndiff --git a/blob.c b/blob.c\nindex 7377008..496f270 100644\n--- a/blob.c\n+++ b/blob.c\n@@ -8,7 +8,7 @@ struct blob *lookup_blob(const unsigned \n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj) {\n-\t\tstruct blob *ret = xcalloc(1, sizeof(struct blob));\n+\t\tstruct blob *ret = alloc_blob_node();\n \t\tcreated_object(sha1, &ret->object);\n \t\tret->object.type = TYPE_BLOB;\n \t\treturn ret;\ndiff --git a/cache.h b/cache.h\nindex 7fcb6d4..eaa5c0c 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -384,4 +384,15 @@ extern void setup_pager(void);\n int decode_85(char *dst, char *line, int linelen);\n void encode_85(char *buf, unsigned char *data, int bytes);\n \n+/* alloc.c */\n+struct blob;\n+struct tree;\n+struct commit;\n+struct tag;\n+extern struct blob *alloc_blob_node(void);\n+extern struct tree *alloc_tree_node(void);\n+extern struct commit *alloc_commit_node(void);\n+extern struct tag *alloc_tag_node(void);\n+extern void alloc_report(void);\n+\n #endif /* CACHE_H */\ndiff --git a/commit.c b/commit.c\nindex 5914200..0fa1198 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -84,7 +84,7 @@ struct commit *lookup_commit(const unsig\n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj) {\n-\t\tstruct commit *ret = xcalloc(1, sizeof(struct commit));\n+\t\tstruct commit *ret = alloc_commit_node();\n \t\tcreated_object(sha1, &ret->object);\n \t\tret->object.type = TYPE_COMMIT;\n \t\treturn ret;\ndiff --git a/tag.c b/tag.c\nindex 9191333..5f70a5b 100644\n--- a/tag.c\n+++ b/tag.c\n@@ -19,7 +19,7 @@ struct tag *lookup_tag(const unsigned ch\n {\n         struct object *obj = lookup_object(sha1);\n         if (!obj) {\n-                struct tag *ret = xcalloc(1, sizeof(struct tag));\n+                struct tag *ret = alloc_tag_node();\n                 created_object(sha1, &ret->object);\n                 ret->object.type = TYPE_TAG;\n                 return ret;\ndiff --git a/tree.c b/tree.c\nindex 64422fd..1023655 100644\n--- a/tree.c\n+++ b/tree.c\n@@ -129,7 +129,7 @@ struct tree *lookup_tree(const unsigned \n {\n \tstruct object *obj = lookup_object(sha1);\n \tif (!obj) {\n-\t\tstruct tree *ret = xcalloc(1, sizeof(struct tree));\n+\t\tstruct tree *ret = alloc_tree_node();\n \t\tcreated_object(sha1, &ret->object);\n \t\tret->object.type = TYPE_TREE;\n \t\treturn ret;\n"},{"id":"22069","messageId":"Pine.LNX.4.64.0606191101380.5498@g5.osdl.org","threadId":"4568","inReplyTo":"Pine.LNX.4.64.0606191028540.5498@g5.osdl.org","subject":"Re: Add specialized object allocator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-19T18:10:58Z","receivedAt":"2006-06-19T18:10:58Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Jun 2006, Linus Torvalds wrote:\n> \n> It also allows us to track some basic statistics about object\n> allocations. For example, for the mozilla import, it shows\n> object usage as follows:\n> \n>      blobs:   627629 (14710 kB)\n>      trees:  1119035 (34969 kB)\n>    commits:   196423  (8440 kB)\n>       tags:     1336    (46 kB)\n\nBtw, this is the trivial additional patch to allow you to say\n\n\tgit --report rev-list --all --objects > /dev/null\n\nand have it report object allocation usage after the op.\n\nUseful? Probably not. It was useful for me to verify that everything \nlooked ok (and while I knew we had more trees than blobs, it's actually \ninteresting to see how projects differ.\n\nThe \"git\" tree, for example, has more blobs than trees: because it's a \nfairly flat development tree, a commit that changes more than one file \nwill generate more new blobs than it generates trees.\n\nIn contrast, the kernel has about 30% more trees than blobs (but since \ntrees have the extra data/size fields, 30% extra trees take 75% more space \nthan blobs).\n\nThe mozilla import has a _lot_ more trees than blobs (80% more trees, and \nthey use up more than twice as much memory). It's probably a pretty deep \ntree structure and/or they often commit changes to single files deep into \nthe tree).\n\n\t\tLinus\n\n----\ndiff --git a/git.c b/git.c\nindex 329ebec..6149499 100644\n--- a/git.c\n+++ b/git.c\n@@ -271,6 +271,10 @@ int main(int argc, const char **argv, ch\n \t\t\tputs(git_exec_path());\n \t\t\texit(0);\n \t\t}\n+\t\tif (!strcmp(cmd, \"report\")) {\n+\t\t\tatexit(alloc_report);\n+\t\t\tcontinue;\n+\t\t}\n \t\tcmd_usage(0, NULL, NULL);\n \t}\n \targv[0] = cmd;\n"},{"id":"22072","messageId":"7vejxl9bi0.fsf@assigned-by-dhcp.cox.net","threadId":"4568","inReplyTo":"Pine.LNX.4.64.0606191028540.5498@g5.osdl.org","subject":"Re: Add specialized object allocator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-19T19:44:07Z","receivedAt":"2006-06-19T19:44:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Impressed.  I wonder if we want to deal with any_object\nstructure as well.\n"},{"id":"22074","messageId":"Pine.LNX.4.64.0606191327240.5498@g5.osdl.org","threadId":"4568","inReplyTo":"7vejxl9bi0.fsf@assigned-by-dhcp.cox.net","subject":"Re: Add specialized object allocator","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2006-06-19T20:30:29Z","receivedAt":"2006-06-19T20:30:29Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 19 Jun 2006, Junio C Hamano wrote:\n>\n> Impressed.  I wonder if we want to deal with any_object\n> structure as well.\n\nWell, it would certainly be very easily doable, but none of the core code \nactually uses it, so it wasn't even on my radar. \n\n\t\tLinus\n"},{"id":"22076","messageId":"7vhd2g966y.fsf@assigned-by-dhcp.cox.net","threadId":"4568","inReplyTo":"Pine.LNX.4.64.0606191327240.5498@g5.osdl.org","subject":"Re: Add specialized object allocator","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-06-19T21:38:45Z","receivedAt":"2006-06-19T21:38:45Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Mon, 19 Jun 2006, Junio C Hamano wrote:\n>>\n>> Impressed.  I wonder if we want to deal with any_object\n>> structure as well.\n>\n> Well, it would certainly be very easily doable, but none of the core code \n> actually uses it, so it wasn't even on my radar. \n\nI think the definition of \"the core\" in your earlier message was\n\"stuff I [jc: Linus] use myself\", and I think the above\nstatement is in line with that definition.\n\nIt is hereby officially declared that commit walkers are not\npart of the core ;-).\n\nEven the commit walker uses lookup_unknown only for the starting\nobject and all the rest are of known type, so it does not help\neven if we did \"union any_object\" that much.\n"}]}