git-rev-size: calculate sizes of repository

Hi,

Just created as answer to a request on IRC: a script to get the sizes of a repository and various stages. It caches all sizes it finds, so is quite fast once it has ramped up.

Example on git repo:

$ git-rev-size.rb HEAD~10..HEAD
ef75951ecabd53b5ed816eb596992f8d222d0fe3 21 694 3343495
a625daccb1750c56768481ec9a5dfd4f9053774e 21 694 3343492
55c3eb434ab6d489c632263239be15a1054df7f2 21 694 3343481
a89fccd28197fa179828c8596791ff16e2268d20 21 694 3343523
d4baf9eaf47ea1ba204f1ab5ecd22326913dd081 21 694 3343498
409d1d2053657f73a3222651111740606122aa80 21 694 3343423
076a10c7282a08f783a28c1b64d0e114a3fe3d39 21 694 3342501
8e3abd4c97b8e7e1128ad0cc44dcc267f478659a 21 694 3342485
500a99935dc157a6625b4decae0b97e896061c2c 21 692 3334754
6493cc09c2aa626ffbe6024dd705e1495c2d87e4 21 692 3334511
d78b0f3d6aa04510dd0c22c3853d3954c5f5b531 21 688 3322774
0fc82cff12a887c1e0e7e69937dbd8a82843c081 21 694 3343352
42f774063db1442fc3815f596d263f90dcd8380b 21 694 3344828
520cd3eca5743bebd217423e1fd0721f32613bb1 21 693 3344115
789a09b4874ae2616987794e0e739b8227957175 21 692 3335517
c35f4c371ac12f4d29b08e46c519ddc0a6494f6e 21 691 3330286

Numbers are SHA1 hash, number of trees, number of blobs and total number of bytes in those blobs.

You can also find it on http://www.wingding.demon.nl/git-rev-size.rb

Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

#!/usr/bin/env ruby

# Calculates sizes of repository at different commits in git #
# 20060819 Initial release
# 20060820 Pass arguments to git-rev-list
#
# (c)2006 R. Nijlunsing <[email protected]>
# License: LGPLv2

require 'set'
require 'enumerator'

if ARGV.empty?
puts "Calculates sizes of repository at different commits" puts
puts "Usage: #{$0} <arguments for git-rev-list>" puts "Example: #{$0} HEAD"
exit 1
end

class Sizes
attr_reader :trees, :blobs, :bytes
def initialize(trees, blobs, bytes); @trees = trees; @blobs = blobs; @bytes = bytes; end def add(o); @trees += o.trees; @blobs += o.blobs; @bytes += o.bytes; end
end

def tree_size(tree)
return $sha2size[tree] if $sha2size.include?(tree) size = Sizes.new(1, 0, 0)
blobs = [] # Blobs with unknown sizes
File.popen("git cat-file -p #{tree}", "r") { |io|

    while line = io.gets
      line =~ %r{^[0-9]{6} ([a-z]+) ([0-9a-f]+)}
      type, sha1 = $1, $2
      if $sha2size.include?(sha1)
        size.add($sha2size[sha1])
      elsif type == "tree"
	size.add(tree_size(sha1))
      elsif type == "blob"
	blobs << sha1
      else
        raise type
      end
    end
  }
  if blobs.size > 0
    # Do all _blobs_ at once. For this to help, git-cat-file should accept
    # more than one filename a time.
    blobs.each_slice(1) { |blobs_slice|
      File.popen("git cat-file -s #{blobs_slice.join(' ')}", "r") { |io|
        blobs_slice.each { |blob|
          blob_size = $sha2size[blob] = Sizes.new(0, 1, io.gets.to_i)
	  size.add(blob_size)
        }
      }
    }

end
$sha2size[tree] = size
end

$sha2size = {} # SHA1 -> Sizes

File.popen("git rev-list #{ARGV.join(' ')}", "r") do |cio|
while commit = cio.gets

    tree = nil			# Root tree of this commit
    commit = commit.chomp
    File.popen("git cat-file -p #{commit}", "r") do |io|
      while (line = io.gets) && !tree
        tree = $1 if line =~ %r{^tree ([a-f0-9]+)}
      end
    end
    if tree
      sizes = tree_size(tree)
      puts "#{commit} #{sizes.trees} #{sizes.blobs} #{sizes.bytes}"
    end

end
end

Hi,

Ruby is _so_ mainstream. Could I have a Haskell version, pretty please?

Ciao,
Dscho

I _knew_ it... Please go bug someone else. The only thing I did was help someone, and for that I choose my own tools since I do it for fun. I don't ask for inclusion in the git archive. I don't ask you to review it, download it, read it nor use it. Just ignore this post if Ruby offends you and this problem wasn't your itch.

Please.

Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

Hi,

Fair enough.

-- 8< --
[PATCH] Add git-rev-size

This tool spits out the number of trees, the number of blobs, and the total bytes of the blobs for a given rev range.

Most notably, it adds an object hash map structure to the library.

---
 Makefile           |    4 ++
 builtin-rev-size.c |   92 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 builtin.h          |    1 +
 git.c              |    1 +
 hash.c             |   50 ++++++++++++++++++++++++++++
 hash.h             |   12 +++++++
 6 files changed, 159 insertions(+), 1 deletions(-)

index a86f289..06c8dd9 100644
@@ -264,7 +264,8 @@ LIB_OBJS = \
 	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
 	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
 	fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
-	alloc.o merge-file.o path-list.o unpack-trees.o help.o $(DIFF_OBJS)
+	alloc.o merge-file.o path-list.o unpack-trees.o help.o \
+	hash.o $(DIFF_OBJS)
 
 BUILTIN_OBJS = \
 	builtin-add.o \

@@ -297,6 +298,7 @@ BUILTIN_OBJS = \
 	builtin-repo-config.o \
 	builtin-rev-list.o \
 	builtin-rev-parse.o \
+	builtin-rev-size.o \
 	builtin-rm.o \
 	builtin-show-branch.o \
 	builtin-stripspace.o \

index ade58c4..9848a5e 100644
@@ -46,6 +46,7 @@ extern int cmd_read_tree(int argc, const
 extern int cmd_repo_config(int argc, const char **argv, const char *prefix);
 extern int cmd_rev_list(int argc, const char **argv, const char *prefix);
 extern int cmd_rev_parse(int argc, const char **argv, const char *prefix);
+extern int cmd_rev_size(int argc, const char **argv, const char *prefix);
 extern int cmd_rm(int argc, const char **argv, const char *prefix);
 extern int cmd_show_branch(int argc, const char **argv, const char *prefix);
 extern int cmd_show(int argc, const char **argv, const char *prefix);

index bf0fe0e..4cfa6cf 100644
@@ -262,6 +262,7 @@ static void handle_internal_command(int 
 		{ "repo-config", cmd_repo_config },
 		{ "rev-list", cmd_rev_list, RUN_SETUP },
 		{ "rev-parse", cmd_rev_parse, RUN_SETUP },
+		{ "rev-size", cmd_rev_size, RUN_SETUP },
 		{ "rm", cmd_rm, RUN_SETUP },
 		{ "show-branch", cmd_show_branch, RUN_SETUP },
 		{ "show", cmd_show, RUN_SETUP | USE_PAGER },

new file mode 100644
index 0000000..0e2b67c
@@ -0,0 +1,12 @@
+#ifndef HASH_H
+#define HASH_H
+
+struct hash_map {
+	unsigned long nr, alloc;
+	struct object **map;
+};
+
+extern struct object *hash_get(struct hash_map *hash, const char *sha1);
+extern void hash_put(struct hash_map *hash, struct object *obj);
+
+#endif

1.4.2.ga5e8f-dirty

[Hm, the itch seems to be contagious. Better watch out...]

Small comments:

The 'git-rev-size' name was chosen because originally it understood the same arguments as git-rev-list. You might want to add this popen() back, or have some other way to share those (might be simple in C). Or is setup_revisions() enough to have the power of git-rev-list?

If seperate commits have to be given on the command line instead of a range, the command line limit is hit quite quickly (~780 commits). And if you'll be using xargs, the hash / cache will be less of an advantage.

The original request was 'for each commit' to get an idea of the size growth during a project.

'builtin_rev_size_usage' is not referred to in the patch, only defined.

[snip patch]

Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

Hi,

It is enough. That is the beauty of setup_revisions().

Certainly. But I doubt that you'll use this command all that often. However, it was a nice example of how easy it is to write a git builtin ;-)

Since the arguments are the same as for git-rev-list, this is easy enough.

True.

-- 8< --
[PATCH] rev-size: actually show usage

---
 builtin-rev-size.c |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

index ad88e48..184f926 100644
@@ -78,6 +78,9 @@ int cmd_rev_size(int argc, const char **
 	revs.commit_format = CMIT_FMT_UNSPECIFIED;
 	argc = setup_revisions(argc, argv, &revs, NULL);
 
+	if (revs.pending.nr == 0)
+		usage(builtin_rev_size_usage);
+
 	prepare_revision_walk(&revs);
 
 	while ((commit = get_revision(&revs))) {

1.4.2.ga5e8f-dirty

On Sunday 20 August 2006 18:09, Johannes Schindelin wrote:
Hi,

Aside from the given command of this thread, this is interesting (even more interesting would be a persistent cache for arbitrary object data). As this could be used in other contexts, some general comments:

Hi,

Actually, it does! "*(unsigned int *)sha1" means that the first 4 bytes of the sha1 are interpreted as a number.

First, you cannot put the same object multiple times. That is not what a hash does (at least in this case): it stores unique objects (identified by their sha1 in this case). If you put another object with the same sha1, the first will be replaced.

Second, since you call hash_put() once per object, hash->nr cannot grow too big, because grow_hash() doubles hash->alloc. And I call grow_hash() once the hash map is half-full; Somebody once told me that would be the optimal growing strategy.

Ciao,
Dscho

Optimal growing mainly means to be O(n) (amortized) after n inserts. That translates to at least _doubling_ (factor 2 or more) the capacity once you're too full.

Assume doubling at a percentage full. Assume realloc(s) takes O(s) (where s = number of bytes). Assume we start with 1 element.

We realloc() then when we've got 1 element, then at 2, 4, 8 etc. The size of the realloc() at each point will also be 1, 2, 4, 8 etc. However, this cost of O(s) can be amortized over the number of elements. So the work done _per insert_ is still a constant (amortized again).

Ascilly:

   x x x x x x x x x x ...  (each insert)
     R   R       R     ...  (each realloc)
   1 2 0 4 0 0 0 8 0 0 ...  (cost of those realloc())

This has also to do with the infinite series of the sum(k>0) of 2^-k being a constant.

Rutger Nijlunsing ---------------------------------- eludias ed dse.nl
never attribute to a conspiracy which can be explained by incompetence
----------------------------------------------------------------------

Ah, yes. That's fine.

I put it the wrong way; I should have said "if you call hash_put() multiple times with the same object". You get the same index, and nothing should change. However, you still increment hash->nr, but this error is not really important as you correct it in grow_hash().

So... sorry for the noise ;-)

Josef

Hi,

Talk about unintended side effects ;-)

Ciao,
Dscho

I do not speak ruby (well I suspect I could read it if I wanted to but I didn't try) so this may or may not be something Johannes inherited from the original, but I think the code overcounts blobs and trees for a top-level tree that happens to have the same blob (or tree) twice. I am not sure if that is intended.

Overcounting would give closer estimate for how big a tar archive would be, or how big an populated working tree would be, so it could be considered a feature. It all depends on what this tools is useful for, I guess.

Hi,

No, it was no rewrite. But looking at the Ruby code again, it is not really similar: the builtin uses the hash to cache the sizes even for a blob. Further, it does not unpack the objects (except for the trees, and for the revision walk if you limit by pathname). However, it inherits this:

I dunno. No idea what the original requester wanted to do with it.

For me, it was a nice distraction from my work. And a nice occasion to finally copy^H^H^H^Himplement the independent hash map code I always wanted to refactor from object.c. And a nice demonstration how easy it actually is these days to implement a builtin.

Ciao,
Dscho