{"thread":{"id":"5335","subject":"[ANNOUNCE] git-rev-size: calculate sizes of repository","startedAt":"2006-08-20T10:54:52Z","lastAt":"2006-08-20T23:36:36Z","messageCount":13,"participants":["Rutger Nijlunsing","Johannes Schindelin","Josef Weidendorfer","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"25640","messageId":"20060820105452.GA19630@nospam.com","threadId":"5335","inReplyTo":null,"subject":"[ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Rutger Nijlunsing","fromEmail":"rutger@nospam.com","sentAt":"2006-08-20T10:54:52Z","receivedAt":"2006-08-20T10:54:52Z","isPatch":false,"sender":{"key":"rutger.nijlunsing@gmail.com","avatar":null},"body":"Hi,\n\nJust created as answer to a request on IRC: a script to get the sizes\nof a repository and various stages. It caches all sizes it finds, so\nis quite fast once it has ramped up.\n\nExample on git repo:\n\n$ git-rev-size.rb HEAD~10..HEAD\nef75951ecabd53b5ed816eb596992f8d222d0fe3 21 694 3343495\na625daccb1750c56768481ec9a5dfd4f9053774e 21 694 3343492\n55c3eb434ab6d489c632263239be15a1054df7f2 21 694 3343481\na89fccd28197fa179828c8596791ff16e2268d20 21 694 3343523\nd4baf9eaf47ea1ba204f1ab5ecd22326913dd081 21 694 3343498\n409d1d2053657f73a3222651111740606122aa80 21 694 3343423\n076a10c7282a08f783a28c1b64d0e114a3fe3d39 21 694 3342501\n8e3abd4c97b8e7e1128ad0cc44dcc267f478659a 21 694 3342485\n500a99935dc157a6625b4decae0b97e896061c2c 21 692 3334754\n6493cc09c2aa626ffbe6024dd705e1495c2d87e4 21 692 3334511\nd78b0f3d6aa04510dd0c22c3853d3954c5f5b531 21 688 3322774\n0fc82cff12a887c1e0e7e69937dbd8a82843c081 21 694 3343352\n42f774063db1442fc3815f596d263f90dcd8380b 21 694 3344828\n520cd3eca5743bebd217423e1fd0721f32613bb1 21 693 3344115\n789a09b4874ae2616987794e0e739b8227957175 21 692 3335517\nc35f4c371ac12f4d29b08e46c519ddc0a6494f6e 21 691 3330286\n\n\nNumbers are SHA1 hash, number of trees, number of blobs and total\nnumber of bytes in those blobs.\n\nYou can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n\n#!/usr/bin/env ruby\n\n# Calculates sizes of repository at different commits in git\n#\n# 20060819 Initial release\n# 20060820 Pass arguments to git-rev-list\n#\n# (c)2006 R. Nijlunsing <git@tux.tmfweb.nl>\n# License: LGPLv2\n\nrequire 'set'\nrequire 'enumerator'\n\nif ARGV.empty?\n  puts \"Calculates sizes of repository at different commits\"\n  puts\n  puts \"Usage: #{$0} <arguments for git-rev-list>\"\n  puts \"Example: #{$0} HEAD\"\n  exit 1\nend\n\nclass Sizes\n  attr_reader :trees, :blobs, :bytes\n  def initialize(trees, blobs, bytes); @trees = trees; @blobs = blobs; @bytes = bytes; end\n  def add(o); @trees += o.trees; @blobs += o.blobs; @bytes += o.bytes; end\nend\n\ndef tree_size(tree)\n  return $sha2size[tree] if $sha2size.include?(tree)\n  size = Sizes.new(1, 0, 0)\n  blobs = []\t\t\t# Blobs with unknown sizes\n  File.popen(\"git cat-file -p #{tree}\", \"r\") { |io|\n    while line = io.gets\n      line =~ %r{^[0-9]{6} ([a-z]+) ([0-9a-f]+)}\n      type, sha1 = $1, $2\n      if $sha2size.include?(sha1)\n        size.add($sha2size[sha1])\n      elsif type == \"tree\"\n\tsize.add(tree_size(sha1))\n      elsif type == \"blob\"\n\tblobs << sha1\n      else\n        raise type\n      end\n    end\n  }\n  if blobs.size > 0\n    # Do all _blobs_ at once. For this to help, git-cat-file should accept\n    # more than one filename a time.\n    blobs.each_slice(1) { |blobs_slice|\n      File.popen(\"git cat-file -s #{blobs_slice.join(' ')}\", \"r\") { |io|\n        blobs_slice.each { |blob|\n          blob_size = $sha2size[blob] = Sizes.new(0, 1, io.gets.to_i)\n\t  size.add(blob_size)\n        }\n      }\n    }\n  end\n  $sha2size[tree] = size\nend\n\n$sha2size = {}\t\t\t# SHA1 -> Sizes\n\nFile.popen(\"git rev-list #{ARGV.join(' ')}\", \"r\") do |cio|\n  while commit = cio.gets\n    tree = nil\t\t\t# Root tree of this commit\n    commit = commit.chomp\n    File.popen(\"git cat-file -p #{commit}\", \"r\") do |io|\n      while (line = io.gets) && !tree\n        tree = $1 if line =~ %r{^tree ([a-f0-9]+)}\n      end\n    end\n    if tree\n      sizes = tree_size(tree)\n      puts \"#{commit} #{sizes.trees} #{sizes.blobs} #{sizes.bytes}\"\n    end\n  end\nend\n"},{"id":"25645","messageId":"Pine.LNX.4.63.0608201519360.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"20060820105452.GA19630@nospam.com","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T13:20:19Z","receivedAt":"2006-08-20T13:20:19Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n\n> You can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n\nRuby is _so_ mainstream. Could I have a Haskell version, pretty please?\n\nCiao,\nDscho\n"},{"id":"25646","messageId":"20060820152404.GA5679@nospam.com","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201519360.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Rutger Nijlunsing","fromEmail":"git@wingding.demon.nl","sentAt":"2006-08-20T15:24:04Z","receivedAt":"2006-08-20T15:24:04Z","isPatch":false,"sender":{"key":"git@wingding.demon.nl","avatar":null},"body":"On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:\n> Hi,\n> \n> On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> \n> > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n> \n> Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?\n\nI _knew_ it... Please go bug someone else. The only thing I did was\nhelp someone, and for that I choose my own tools since I do it for\nfun. I don't ask for inclusion in the git archive. I don't ask you to\nreview it, download it, read it nor use it. Just ignore this post if\nRuby offends you and this problem wasn't your itch.\n\nPlease.\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n"},{"id":"25647","messageId":"Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"20060820152404.GA5679@nospam.com","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T16:09:34Z","receivedAt":"2006-08-20T16:09:34Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n\n> On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> > \n> > > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n> > \n> > Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?\n> \n> I _knew_ it... Please go bug someone else. The only thing I did was\n> help someone, and for that I choose my own tools since I do it for\n> fun.\n\nFair enough.\n\n-- 8< --\n[PATCH] Add git-rev-size\n\nThis tool spits out the number of trees, the number of blobs, and the total\nbytes of the blobs for a given rev range.\n\nMost notably, it adds an object hash map structure to the library.\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n---\n Makefile           |    4 ++\n builtin-rev-size.c |   92 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n builtin.h          |    1 +\n git.c              |    1 +\n hash.c             |   50 ++++++++++++++++++++++++++++\n hash.h             |   12 +++++++\n 6 files changed, 159 insertions(+), 1 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a86f289..06c8dd9 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -264,7 +264,8 @@ 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-\talloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)\n+\talloc.o merge-file.o path-list.o unpack-trees.o help.o \\\n+\thash.o $(DIFF_OBJS)\n \n BUILTIN_OBJS = \\\n \tbuiltin-add.o \\\n@@ -297,6 +298,7 @@ BUILTIN_OBJS = \\\n \tbuiltin-repo-config.o \\\n \tbuiltin-rev-list.o \\\n \tbuiltin-rev-parse.o \\\n+\tbuiltin-rev-size.o \\\n \tbuiltin-rm.o \\\n \tbuiltin-show-branch.o \\\n \tbuiltin-stripspace.o \\\ndiff --git a/builtin-rev-size.c b/builtin-rev-size.c\nnew file mode 100644\nindex 0000000..ad88e48\n--- /dev/null\n+++ b/builtin-rev-size.c\n@@ -0,0 +1,92 @@\n+/*\n+ * \"git rev-size\" builtin command\n+ *\n+ * Copyright (C) 2006 Johannes Schindelin\n+ */\n+\n+#include \"cache.h\"\n+#include \"builtin.h\"\n+#include \"object.h\"\n+#include \"tree.h\"\n+#include \"tree-walk.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+#include \"hash.h\"\n+\n+static const char builtin_rev_size_usage[] =\n+\"git-rev-size <commit-id>...\";\n+\n+struct rev_size {\n+\tstruct object object;\n+\tsize_t trees, blobs, bytes;\n+};\n+\n+struct hash_map rev_size_hash = { 0, 0, NULL };\n+\n+static struct rev_size *get_rev_size(const char *sha1)\n+{\n+\tstruct rev_size *rev_size =\n+\t\t(struct rev_size *)hash_get(&rev_size_hash, sha1);\n+\n+\tif (rev_size == NULL) {\n+\t\tchar type[64];\n+\t\tunsigned long size;\n+\n+\t\trev_size = xcalloc(1, sizeof(struct rev_size));\n+\n+\t\tif (sha1_object_info(sha1, type, &size))\n+\t\t\tdie(\"Cannot get info for %s\", sha1_to_hex(sha1));\n+\n+\t\tif (!strcmp(type, \"blob\")) {\n+\t\t\trev_size->blobs = 1;\n+\t\t\trev_size->bytes = size;\n+\t\t} else if (!strcmp(type, \"tree\")) {\n+\t\t\tstruct tree *tree = (struct tree *)parse_object(sha1);\n+\t\t\tstruct tree_desc desc;\n+\t\t\tstruct name_entry entry;\n+\n+\t\t\tdesc.buf = tree->buffer;\n+\t\t\tdesc.size = tree->size;\n+\n+\t\t\twhile (tree_entry(&desc, &entry)) {\n+\t\t\t\tstruct rev_size *r = get_rev_size(entry.sha1);\n+\n+\t\t\t\trev_size->trees += r->trees;\n+\t\t\t\trev_size->blobs += r->blobs;\n+\t\t\t\trev_size->bytes += r->bytes;\n+\t\t\t}\n+\n+\t\t\trev_size->trees++;\n+\t\t} else\n+\t\t\tdie(\"Cannot calculate size for type %s\", type);\n+\n+\t\tmemcpy(rev_size->object.sha1, sha1, 20);\n+\t\thash_put(&rev_size_hash, &rev_size->object);\n+\t}\n+\n+\treturn rev_size;\n+}\n+\n+int cmd_rev_size(int argc, const char **argv, const char *prefix)\n+{\n+\tstruct rev_info revs;\n+\tstruct commit *commit;\n+\n+\tinit_revisions(&revs, prefix);\n+\trevs.abbrev = 0;\n+\trevs.commit_format = CMIT_FMT_UNSPECIFIED;\n+\targc = setup_revisions(argc, argv, &revs, NULL);\n+\n+\tprepare_revision_walk(&revs);\n+\n+\twhile ((commit = get_revision(&revs))) {\n+\t\tstruct rev_size *rev_size =\n+\t\t\tget_rev_size(commit->tree->object.sha1);\n+\n+\t\tprintf(\"%s %d %d %d\\n\", sha1_to_hex(commit->object.sha1),\n+\t\t\t\trev_size->trees, rev_size->blobs, rev_size->bytes);\n+\t}\n+\n+\treturn 0;\n+}\ndiff --git a/builtin.h b/builtin.h\nindex ade58c4..9848a5e 100644\n--- a/builtin.h\n+++ b/builtin.h\n@@ -46,6 +46,7 @@ extern int cmd_read_tree(int argc, const\n extern int cmd_repo_config(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_list(int argc, const char **argv, const char *prefix);\n extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);\n+extern int cmd_rev_size(int argc, const char **argv, const char *prefix);\n extern int cmd_rm(int argc, const char **argv, const char *prefix);\n extern int cmd_show_branch(int argc, const char **argv, const char *prefix);\n extern int cmd_show(int argc, const char **argv, const char *prefix);\ndiff --git a/git.c b/git.c\nindex bf0fe0e..4cfa6cf 100644\n--- a/git.c\n+++ b/git.c\n@@ -262,6 +262,7 @@ static void handle_internal_command(int \n \t\t{ \"repo-config\", cmd_repo_config },\n \t\t{ \"rev-list\", cmd_rev_list, RUN_SETUP },\n \t\t{ \"rev-parse\", cmd_rev_parse, RUN_SETUP },\n+\t\t{ \"rev-size\", cmd_rev_size, RUN_SETUP },\n \t\t{ \"rm\", cmd_rm, RUN_SETUP },\n \t\t{ \"show-branch\", cmd_show_branch, RUN_SETUP },\n \t\t{ \"show\", cmd_show, RUN_SETUP | USE_PAGER },\ndiff --git a/hash.c b/hash.c\nnew file mode 100644\nindex 0000000..12d1e65\n--- /dev/null\n+++ b/hash.c\n@@ -0,0 +1,50 @@\n+#include \"cache.h\"\n+#include \"object.h\"\n+#include \"hash.h\"\n+\n+static unsigned int hash_index(struct hash_map *hash, const char *sha1)\n+{\n+\tunsigned int index = *(unsigned int *)sha1;\n+\twhile (1) {\n+\t\tif (index >= hash->alloc)\n+\t\t\tindex = index % hash->alloc;\n+\t\tif (hash->map[index] == NULL ||\n+\t\t\t\t!hashcmp(sha1, hash->map[index]->sha1))\n+\t\t\treturn index;\n+\t\tindex++;\n+\t}\n+}\n+\n+static void grow_hash(struct hash_map *hash)\n+{\n+\tint i;\n+\tint old_alloc = hash->alloc;\n+\tstruct object **old_map = hash->map;\n+\n+\thash->alloc = hash->alloc < 32 ? 32 : 2 * hash->alloc;\n+\thash->map = xcalloc(hash->alloc, sizeof(struct object *));\n+\thash->nr = 0;\n+\n+\tfor (i = 0; i < old_alloc; i++) {\n+\t\tstruct object *obj = old_map[i];\n+\t\tif (!obj)\n+\t\t\tcontinue;\n+\t\thash_put(hash, obj);\n+\t}\n+\tfree(old_map);\n+}\n+\n+void hash_put(struct hash_map *hash, struct object *obj)\n+{\n+\tif (++hash->nr > hash->alloc / 2)\n+\t\tgrow_hash(hash);\n+\n+\thash->map[hash_index(hash, obj->sha1)] = obj;\n+}\n+\n+struct object *hash_get(struct hash_map *hash, const char *sha1)\n+{\n+\tif (hash->alloc == 0)\n+\t\treturn NULL;\n+\treturn hash->map[hash_index(hash, sha1)];\n+}\ndiff --git a/hash.h b/hash.h\nnew file mode 100644\nindex 0000000..0e2b67c\n--- /dev/null\n+++ b/hash.h\n@@ -0,0 +1,12 @@\n+#ifndef HASH_H\n+#define HASH_H\n+\n+struct hash_map {\n+\tunsigned long nr, alloc;\n+\tstruct object **map;\n+};\n+\n+extern struct object *hash_get(struct hash_map *hash, const char *sha1);\n+extern void hash_put(struct hash_map *hash, struct object *obj);\n+\n+#endif\n-- \n1.4.2.ga5e8f-dirty\n"},{"id":"25648","messageId":"200608201837.33577.Josef.Weidendorfer@gmx.de","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2006-08-20T16:37:33Z","receivedAt":"2006-08-20T16:37:33Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:\nHi,\n\n> Most notably, it adds an object hash map structure to the library.\n\nAside from the given command of this thread, this is interesting\n(even more interesting would be a persistent cache for arbitrary object data).\nAs this could be used in other contexts, some general comments:\n\n> +static unsigned int hash_index(struct hash_map *hash, const char *sha1)\n> +{\n> +\tunsigned int index = *(unsigned int *)sha1;\n\nIf you have the same SHA1, stored at different addresses, you get different\nindexes for the same SHA1. Index probably should be calculated from the\nSHA1 string.\n\n> +void hash_put(struct hash_map *hash, struct object *obj)\n> +{\n> +\tif (++hash->nr > hash->alloc / 2)\n> +\t\tgrow_hash(hash);\n\nIf you insert the same object multiple times, hash->nr will get too big.\n\nJosef\n"},{"id":"25649","messageId":"Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"200608201837.33577.Josef.Weidendorfer@gmx.de","subject":"Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T16:51:52Z","receivedAt":"2006-08-20T16:51:52Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Josef Weidendorfer wrote:\n\n> On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:\n> \n> > +static unsigned int hash_index(struct hash_map *hash, const char *sha1)\n> > +{\n> > +\tunsigned int index = *(unsigned int *)sha1;\n> \n> If you have the same SHA1, stored at different addresses, you get different\n> indexes for the same SHA1. Index probably should be calculated from the\n> SHA1 string.\n\nActually, it does! \"*(unsigned int *)sha1\" means that the first 4 bytes \nof the sha1 are interpreted as a number.\n\n> > +void hash_put(struct hash_map *hash, struct object *obj)\n> > +{\n> > +\tif (++hash->nr > hash->alloc / 2)\n> > +\t\tgrow_hash(hash);\n> \n> If you insert the same object multiple times, hash->nr will get too big.\n\nFirst, you cannot put the same object multiple times. That is not what a \nhash does (at least in this case): it stores unique objects (identified by \ntheir sha1 in this case). If you put another object with the same sha1, \nthe first will be replaced.\n\nSecond, since you call hash_put() once per object, hash->nr cannot grow \ntoo big, because grow_hash() doubles hash->alloc. And I call grow_hash() \nonce the hash map is half-full; Somebody once told me that would be the \noptimal growing strategy.\n\nCiao,\nDscho\n \n"},{"id":"25650","messageId":"20060820172458.GA21362@nospam.com","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Rutger Nijlunsing","fromEmail":"rutger@nospam.com","sentAt":"2006-08-20T17:24:58Z","receivedAt":"2006-08-20T17:24:58Z","isPatch":false,"sender":{"key":"rutger.nijlunsing@gmail.com","avatar":null},"body":"On Sun, Aug 20, 2006 at 06:09:34PM +0200, Johannes Schindelin wrote:\n> Hi,\n> \n> On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> \n> > On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:\n> > > Hi,\n> > > \n> > > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> > > \n> > > > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n> > > \n> > > Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?\n> > \n> > I _knew_ it... Please go bug someone else. The only thing I did was\n> > help someone, and for that I choose my own tools since I do it for\n> > fun.\n> \n> Fair enough.\n> \n> -- 8< --\n> [PATCH] Add git-rev-size\n> \n> This tool spits out the number of trees, the number of blobs, and the total\n> bytes of the blobs for a given rev range.\n> \n> Most notably, it adds an object hash map structure to the library.\n> \n> Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n\n\n[Hm, the itch seems to be contagious. Better watch out...]\n\nSmall comments:\n\nThe 'git-rev-size' name was chosen because originally it understood\nthe same arguments as git-rev-list. You might want to add this popen()\nback, or have some other way to share those (might be simple in C). Or\nis setup_revisions() enough to have the power of git-rev-list?\n\nIf seperate commits have to be given on the command line instead of a\nrange, the command line limit is hit quite quickly (~780 commits). And\nif you'll be using xargs, the hash / cache will be less of an advantage.\n\nThe original request was 'for each commit' to get an idea of the size\ngrowth during a project.\n\n'builtin_rev_size_usage' is not referred to in the patch, only defined.\n\nSigned-off-by: Rutger Nijlunsing <git@tux.tmfweb.nl>\n\n\n> ---\n>  Makefile           |    4 ++\n>  builtin-rev-size.c |   92 ++++++++++++++++++++++++++++++++++++++++++++++++++++\n>  builtin.h          |    1 +\n>  git.c              |    1 +\n>  hash.c             |   50 ++++++++++++++++++++++++++++\n>  hash.h             |   12 +++++++\n>  6 files changed, 159 insertions(+), 1 deletions(-)\n[snip patch]\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n"},{"id":"25651","messageId":"20060820174054.GB21362@nospam.com","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)","fromName":"Rutger Nijlunsing","fromEmail":"rutger@nospam.com","sentAt":"2006-08-20T17:40:54Z","receivedAt":"2006-08-20T17:40:54Z","isPatch":false,"sender":{"key":"rutger.nijlunsing@gmail.com","avatar":null},"body":"> Second, since you call hash_put() once per object, hash->nr cannot grow \n> too big, because grow_hash() doubles hash->alloc. And I call grow_hash() \n> once the hash map is half-full; Somebody once told me that would be the \n> optimal growing strategy.\n\nOptimal growing mainly means to be O(n) (amortized) after n\ninserts. That translates to at least _doubling_ (factor 2 or more) the\ncapacity once you're too full.\n\nAssume doubling at a percentage full. Assume realloc(s) takes O(s)\n(where s = number of bytes). Assume we start with 1 element.\n\nWe realloc() then when we've got 1 element, then at 2, 4, 8 etc. The\nsize of the realloc() at each point will also be 1, 2, 4, 8\netc. However, this cost of O(s) can be amortized over the number of\nelements. So the work done _per insert_ is still a constant (amortized\nagain).\n\nAscilly:\n\n   x x x x x x x x x x ...  (each insert)\n     R   R       R     ...  (each realloc)\n   1 2 0 4 0 0 0 8 0 0 ...  (cost of those realloc())\n\nThis has also to do with the infinite series of the sum(k>0) of 2^-k\nbeing a constant.\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n"},{"id":"25654","messageId":"200608202041.19644.Josef.Weidendorfer@gmx.de","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201846110.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)","fromName":"Josef Weidendorfer","fromEmail":"josef.weidendorfer@gmx.de","sentAt":"2006-08-20T18:41:19Z","receivedAt":"2006-08-20T18:41:19Z","isPatch":false,"sender":{"key":"josef.weidendorfer@gmx.de","avatar":null},"body":"On Sunday 20 August 2006 18:51, Johannes Schindelin wrote:\n> > > +static unsigned int hash_index(struct hash_map *hash, const char *sha1)\n> > > +{\n> > > +\tunsigned int index = *(unsigned int *)sha1;\n> > \n> > If you have the same SHA1, stored at different addresses, you get different\n> > indexes for the same SHA1. Index probably should be calculated from the\n> > SHA1 string.\n> \n> Actually, it does! \"*(unsigned int *)sha1\" means that the first 4 bytes \n> of the sha1 are interpreted as a number.\n\nAh, yes. That's fine.\n\n> > > +void hash_put(struct hash_map *hash, struct object *obj)\n> > > +{\n> > > +\tif (++hash->nr > hash->alloc / 2)\n> > > +\t\tgrow_hash(hash);\n> > \n> > If you insert the same object multiple times, hash->nr will get too big.\n> \n> First, you cannot put the same object multiple times. That is not what a  \n> hash does (at least in this case): it stores unique objects (identified by \n> their sha1 in this case).\n\nI put it the wrong way; I should have said \"if you call hash_put() multiple\ntimes with the same object\". You get the same index, and nothing should\nchange. However, you still increment hash->nr, but this error is not really\nimportant as you correct it in grow_hash().\n\nSo... sorry for the noise ;-)\n\nJosef\n"},{"id":"25655","messageId":"Pine.LNX.4.63.0608202038430.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"20060820172458.GA21362@nospam.com","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T18:44:29Z","receivedAt":"2006-08-20T18:44:29Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n\n> On Sun, Aug 20, 2006 at 06:09:34PM +0200, Johannes Schindelin wrote:\n> > Hi,\n> > \n> > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> > \n> > > On Sun, Aug 20, 2006 at 03:20:19PM +0200, Johannes Schindelin wrote:\n> > > > Hi,\n> > > > \n> > > > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> > > > \n> > > > > You can also find it on http://www.wingding.demon.nl/git-rev-size.rb\n> > > > \n> > > > Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?\n> > > \n> > > I _knew_ it... Please go bug someone else. The only thing I did was\n> > > help someone, and for that I choose my own tools since I do it for\n> > > fun.\n> > \n> > Fair enough.\n> > \n> > -- 8< --\n> > [PATCH] Add git-rev-size\n> > \n> > This tool spits out the number of trees, the number of blobs, and the total\n> > bytes of the blobs for a given rev range.\n> > \n> > Most notably, it adds an object hash map structure to the library.\n> > \n> > Signed-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n> \n> \n> [Hm, the itch seems to be contagious. Better watch out...]\n> \n> Small comments:\n> \n> The 'git-rev-size' name was chosen because originally it understood\n> the same arguments as git-rev-list. You might want to add this popen()\n> back, or have some other way to share those (might be simple in C). Or\n> is setup_revisions() enough to have the power of git-rev-list?\n\nIt is enough. That is the beauty of setup_revisions().\n\n> If seperate commits have to be given on the command line instead of a\n> range, the command line limit is hit quite quickly (~780 commits). And\n> if you'll be using xargs, the hash / cache will be less of an advantage.\n\nCertainly. But I doubt that you'll use this command all that often. \nHowever, it was a nice example of how easy it is to write a git builtin ;-)\n\n> The original request was 'for each commit' to get an idea of the size\n> growth during a project.\n\nSince the arguments are the same as for git-rev-list, this is easy enough.\n\n> 'builtin_rev_size_usage' is not referred to in the patch, only defined.\n\nTrue.\n\n-- 8< --\n[PATCH] rev-size: actually show usage\n\nSigned-off-by: Johannes Schindelin <Johannes.Schindelin@gmx.de>\n---\n builtin-rev-size.c |    3 +++\n 1 files changed, 3 insertions(+), 0 deletions(-)\n\ndiff --git a/builtin-rev-size.c b/builtin-rev-size.c\nindex ad88e48..184f926 100644\n--- a/builtin-rev-size.c\n+++ b/builtin-rev-size.c\n@@ -78,6 +78,9 @@ int cmd_rev_size(int argc, const char **\n \trevs.commit_format = CMIT_FMT_UNSPECIFIED;\n \targc = setup_revisions(argc, argv, &revs, NULL);\n \n+\tif (revs.pending.nr == 0)\n+\t\tusage(builtin_rev_size_usage);\n+\n \tprepare_revision_walk(&revs);\n \n \twhile ((commit = get_revision(&revs))) {\n-- \n1.4.2.ga5e8f-dirty\n"},{"id":"25657","messageId":"Pine.LNX.4.63.0608202047010.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"200608202041.19644.Josef.Weidendorfer@gmx.de","subject":"Re: Object hash (was: Re: [ANNOUNCE] git-rev-size: calculate sizes of repository)","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T18:47:30Z","receivedAt":"2006-08-20T18:47:30Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Josef Weidendorfer wrote:\n\n> On Sunday 20 August 2006 18:51, Johannes Schindelin wrote:\n> \n> > > > +void hash_put(struct hash_map *hash, struct object *obj)\n> > > > +{\n> > > > +\tif (++hash->nr > hash->alloc / 2)\n> > > > +\t\tgrow_hash(hash);\n> > > \n> > > If you insert the same object multiple times, hash->nr will get too big.\n> > \n> > First, you cannot put the same object multiple times. That is not what a  \n> > hash does (at least in this case): it stores unique objects (identified by \n> > their sha1 in this case).\n> \n> I put it the wrong way; I should have said \"if you call hash_put() multiple\n> times with the same object\". You get the same index, and nothing should\n> change. However, you still increment hash->nr, but this error is not really\n> important as you correct it in grow_hash().\n\nTalk about unintended side effects ;-)\n\nCiao,\nDscho\n"},{"id":"25660","messageId":"7vlkpjytnj.fsf@assigned-by-dhcp.cox.net","threadId":"5335","inReplyTo":"Pine.LNX.4.63.0608201805070.28360@wbgn013.biozentrum.uni-wuerzburg.de","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-08-20T21:38:40Z","receivedAt":"2006-08-20T21:38:40Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n\n> On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n>\n>> I _knew_ it... Please go bug someone else. The only thing I did was\n>> help someone, and for that I choose my own tools since I do it for\n>> fun.\n>\n> Fair enough.\n>\n> -- 8< --\n> [PATCH] Add git-rev-size\n>\n> This tool spits out the number of trees, the number of blobs, and the total\n> bytes of the blobs for a given rev range.\n\nI do not speak ruby (well I suspect I could read it if I wanted\nto but I didn't try) so this may or may not be something\nJohannes inherited from the original, but I think the code\novercounts blobs and trees for a top-level tree that happens to\nhave the same blob (or tree) twice.  I am not sure if that is\nintended.\n\nOvercounting would give closer estimate for how big a tar\narchive would be, or how big an populated working tree would be,\nso it could be considered a feature.  It all depends on what\nthis tools is useful for, I guess.\n"},{"id":"25665","messageId":"Pine.LNX.4.63.0608210130010.28360@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"5335","inReplyTo":"7vlkpjytnj.fsf@assigned-by-dhcp.cox.net","subject":"Re: [ANNOUNCE] git-rev-size: calculate sizes of repository","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-08-20T23:36:36Z","receivedAt":"2006-08-20T23:36:36Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 20 Aug 2006, Junio C Hamano wrote:\n\n> Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:\n> \n> > On Sun, 20 Aug 2006, Rutger Nijlunsing wrote:\n> >\n> >> I _knew_ it... Please go bug someone else. The only thing I did was\n> >> help someone, and for that I choose my own tools since I do it for\n> >> fun.\n> >\n> > Fair enough.\n> >\n> > -- 8< --\n> > [PATCH] Add git-rev-size\n> >\n> > This tool spits out the number of trees, the number of blobs, and the total\n> > bytes of the blobs for a given rev range.\n> \n> I do not speak ruby (well I suspect I could read it if I wanted\n> to but I didn't try) so this may or may not be something\n> Johannes inherited from the original,\n\nNo, it was no rewrite. But looking at the Ruby code again, it is not \nreally similar: the builtin uses the hash to cache the sizes even for a \nblob. Further, it does not unpack the objects (except for the trees, and \nfor the revision walk if you limit by pathname). However, it inherits \nthis:\n\n> but I think the code overcounts blobs and trees for a top-level tree \n> that happens to have the same blob (or tree) twice.  I am not sure if \n> that is intended.\n> \n> Overcounting would give closer estimate for how big a tar\n> archive would be, or how big an populated working tree would be,\n> so it could be considered a feature.  It all depends on what\n> this tools is useful for, I guess.\n\nI dunno. No idea what the original requester wanted to do with it.\n\nFor me, it was a nice distraction from my work. And a nice occasion to \nfinally copy^H^H^H^Himplement the independent hash map code I always \nwanted to refactor from object.c. And a nice demonstration how easy it \nactually is these days to implement a builtin.\n\nCiao,\nDscho\n"}]}