{"thread":{"id":"7768","subject":"Why SHA are 40 bytes? (aka looking for flames)","startedAt":"2007-04-21T13:35:35Z","lastAt":"2007-04-24T16:19:25Z","messageCount":18,"participants":["Marco Costalba","Andy Parkins","Jon Smirl","Karl Hasselström","Nicolas Pitre","H. Peter Anvin","Shawn O. Pearce","Andreas Ericsson"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"40050","messageId":"e5bfff550704210635r4008c3c6tf5f55f970bf85e44@mail.gmail.com","threadId":"7768","inReplyTo":null,"subject":"Why SHA are 40 bytes? (aka looking for flames)","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-04-21T13:35:35Z","receivedAt":"2007-04-21T13:35:35Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"Well, why to store always the full length SHA?\n\nI know that looking at the code it is better then asking, but indeed\nasking is better then guessing and in my case looking at the scary sha\nlow level code is almost like (bad) guessing.\n\nWe use 40 bytes to disambiguate two unlucky revisions or it is due to\nUI concerns?\n\nIn case it is the former does this apply?\n\n40bytes-sha1 + 40bytes-sha2 == 7**bytes-sha1 + 7bytes-sha2 + \"a way to\ndisambiguate the two\"*\n\n(*) as example calculating on the fly the full length sha in the\nunlikely event it is needed, or storing complete 40bytes sha when\nneeded.\n\n(**) 7 is my lucky number ;-)\n\nIf in the packed tree truncated sha are stored, togheter of course\nwith corresponding revision data, does it is enough to keep the *same*\ninformation of a complete pack?\n\nFor performance reasons, probably the inflating should be done only\nwhen necessary, it means all git code should use shrinked sha-s,\nleaving inflating as a remote and unlikely event. What are the real\nwalls about using small length sha everywhere in git code?\n\nOk. It's enough for collecting a long list of very bad answers. I\nthink I've done my day now!\n\nThanks for your *kind* reply\nMarco\n"},{"id":"40052","messageId":"200704211608.06171.andyparkins@gmail.com","threadId":"7768","inReplyTo":"e5bfff550704210635r4008c3c6tf5f55f970bf85e44@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Andy Parkins","fromEmail":"andyparkins@gmail.com","sentAt":"2007-04-21T15:08:01Z","receivedAt":"2007-04-21T15:08:01Z","isPatch":false,"sender":{"key":"andyparkins@gmail.com","avatar":null},"body":"On Saturday 2007, April 21, Marco Costalba wrote:\n> Well, why to store always the full length SHA?\n\nWell apart from being easier than working out the optimum size for every \nsingle object write, one really good reason would be that there is no \nway to predict that an object in the future won't have a conflicting \nSHA - every object /has/ to be stored with its full hash, because you \nare preventing conflicts with everything object now, in the past and \nall possible futures.\n\nWow - git is like a time machine.\n\n\nAndy\n\n-- \nDr Andy Parkins, M Eng (hons), MIET\nandyparkins@gmail.com\n"},{"id":"40053","messageId":"9e4733910704210837y3ac3654ekb60654ef6fc397fc@mail.gmail.com","threadId":"7768","inReplyTo":"e5bfff550704210635r4008c3c6tf5f55f970bf85e44@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-04-21T15:37:36Z","receivedAt":"2007-04-21T15:37:36Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 4/21/07, Marco Costalba wrote:\n> Well, why to store always the full length SHA?\n\nWhen Shawn gets done with full compression the SHAs would get stored\nin the packfile once and then be replaced with a token generated from\nthe compression algorithm. Compression tokens are designed to use the\nminimal number of bits depending on frequency of occurrence.\n\nThis doesn't happen with the current compression code since it doesn't\nhave a global dictionary.\n\nThere are many other things that would benefit from a global\ndictionary. For example when working on the Mozilla repository the\nMozilla license has gone through four major revisions. Each of these\nlicenses is in the repository thousands of times. Making a copy of\neach license to a global dictionary and then replacing them with a\ntoken would yield megabytes of savings in the pack.\n\nI would think that it is better to wait for a general compression\nsolution rather than do a specific one for SHAs.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"40055","messageId":"20070421165331.GA5080@diana.vm.bytemark.co.uk","threadId":"7768","inReplyTo":"200704211608.06171.andyparkins@gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Karl Hasselström","fromEmail":"kha@treskal.com","sentAt":"2007-04-21T16:53:31Z","receivedAt":"2007-04-21T16:53:31Z","isPatch":false,"sender":{"key":"kha@treskal.com","avatar":"https://gravatar.com/avatar/f0120c734b5279b345075a28521e1ac66acb20c9913ffe9bf6ae97e53f7f3f13?d=mp&s=160"},"body":"On 2007-04-21 16:08:01 +0100, Andy Parkins wrote:\n\n> On Saturday 2007, April 21, Marco Costalba wrote:\n>\n> > Well, why to store always the full length SHA?\n>\n> Well apart from being easier than working out the optimum size for\n> every single object write, one really good reason would be that\n> there is no way to predict that an object in the future won't have a\n> conflicting SHA - every object /has/ to be stored with its full\n> hash, because you are preventing conflicts with everything object\n> now, in the past and all possible futures.\n\nWell, any hash is \"incomplete\" or \"not long enough\" inasmuch as it's\ntheoretically possible to find collisions. The choice of the full 160\nbits (note: this is 20 bytes, not 40) is arbitrary -- it's just \"long\nenough\". 128 bits would have been enough to prevent any naturally\noccurring collisions, too (maybe even 96 bits would be enough, I'm too\nlazy to do the math). The only reason to go as high as 160 is to\nprevent any possible collision created by a malicious adversary, too,\nso that it's possible to e.g. sign just a commit and be able to trust\neverything it points to. The SHA1 designers felt that 160 bits was a\ngood compromise between size and robustness, and we just trust that\ntheir (and the cryptographic community's) guess is good enough.\n\n-- \nKarl Hasselström, kha@treskal.com\n www.treskal.com/kalle\n"},{"id":"40056","messageId":"e5bfff550704210958j5506d533wa20834b9862457fd@mail.gmail.com","threadId":"7768","inReplyTo":"200704211608.06171.andyparkins@gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-04-21T16:58:29Z","receivedAt":"2007-04-21T16:58:29Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 4/21/07, Andy Parkins wrote:\n> On Saturday 2007, April 21, Marco Costalba wrote:\n> > Well, why to store always the full length SHA?\n>\n> Well apart from being easier than working out the optimum size for every\n> single object write, one really good reason would be that there is no\n> way to predict that an object in the future won't have a conflicting\n> SHA - every object /has/ to be stored with its full hash, because you\n> are preventing conflicts with everything object now, in the past and\n> all possible futures.\n>\n\nWell, this is true also with 40 bytes sha, also if less probable.\n\nApart from this, when, in the future you are going to add an object\nthat conflicts with an existing one you will handle that situation for\nthe *new* object, as example storing with longer sha, without touching\nthe existing one anymore.\n\nWell I admit I don't know exacting what I'm saying, but sometimes\ningenuity (a kind word to say ignorance) could lead to some surprises.\n\nMarco\n"},{"id":"40057","messageId":"e5bfff550704211006t59cb49h179685d694a1d75a@mail.gmail.com","threadId":"7768","inReplyTo":"9e4733910704210837y3ac3654ekb60654ef6fc397fc@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-04-21T17:06:52Z","receivedAt":"2007-04-21T17:06:52Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 4/21/07, Jon Smirl wrote:\n> On 4/21/07, Marco Costalba wrote:\n> > Well, why to store always the full length SHA?\n>\n> When Shawn gets done with full compression the SHAs would get stored\n> in the packfile once and then be replaced with a token generated from\n> the compression algorithm. Compression tokens are designed to use the\n> minimal number of bits depending on frequency of occurrence.\n>\n\nCurrently in Lunux tree there are about 445.424 objects (git\ncount-objects -v), if each object has his 40 bytes name it is about\n20MB to store sha *once*, probably with no real disambiguate need to\nbe that much.\n\nMarco\n"},{"id":"40059","messageId":"e5bfff550704211009v119595d1x440be5ad0f95ee1c@mail.gmail.com","threadId":"7768","inReplyTo":"20070421165331.GA5080@diana.vm.bytemark.co.uk","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-04-21T17:09:54Z","receivedAt":"2007-04-21T17:09:54Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 4/21/07, Karl Hasselström wrote:\n\n> bits (note: this is 20 bytes, not 40)\n\nYes ;-) Of course. Sorry!!\n"},{"id":"40063","messageId":"9e4733910704211059h16c06e11k967d0bdd3e4970fc@mail.gmail.com","threadId":"7768","inReplyTo":"e5bfff550704211006t59cb49h179685d694a1d75a@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-04-21T17:59:24Z","receivedAt":"2007-04-21T17:59:24Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 4/21/07, Marco Costalba wrote:\n> On 4/21/07, Jon Smirl wrote:\n> > On 4/21/07, Marco Costalba wrote:\n> > > Well, why to store always the full length SHA?\n> >\n> > When Shawn gets done with full compression the SHAs would get stored\n> > in the packfile once and then be replaced with a token generated from\n> > the compression algorithm. Compression tokens are designed to use the\n> > minimal number of bits depending on frequency of occurrence.\n> >\n>\n> Currently in Lunux tree there are about 445.424 objects (git\n> count-objects -v), if each object has his 40 bytes name it is about\n> 20MB to store sha *once*, probably with no real disambiguate need to\n> be that much.\n\nYou have to store the full SHAs at least once since they are the\nsignature against data corruption.\n\n> Marco\n>\n\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"40065","messageId":"e5bfff550704211128i12035947i7597e920a0eca163@mail.gmail.com","threadId":"7768","inReplyTo":"9e4733910704211059h16c06e11k967d0bdd3e4970fc@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Marco Costalba","fromEmail":"mcostalba@gmail.com","sentAt":"2007-04-21T18:28:57Z","receivedAt":"2007-04-21T18:28:57Z","isPatch":false,"sender":{"key":"mcostalba@gmail.com","avatar":null},"body":"On 4/21/07, Jon Smirl wrote:\n>\n> You have to store the full SHAs at least once since they are the\n> signature against data corruption.\n>\n\nThis is interesting.\n\nSo until know I learnt 3 uses of sha:\n\n- Reference an object\n- Check against object data corruption\n- Prevent any possible collision among objects\n\n\nKarl says that we need 160 bits to prevent collisions:\n\n>prevent any possible collision created by a malicious adversary, too,\n>so that it's possible to e.g. sign just a commit and be able to trust\n>everything it points to. The SHA1 designers felt that 160 bits was a\n>good compromise between size and robustness, and we just trust that\n>their (and the cryptographic community's) guess is good enough.\n\nProbably we don't need 160bits to reference an object. I really don't\nknow how many bit we need to be robust against data corruption.\n\nSomeone more versed then me in SHA1 could tell the probablity to find\na corrupted object calculating his hash and checking against his\nstored 160bits known good signature and *FAIL* to find as corrupt *the\nsame object* calculating his hash and checking against a truncated sha\nto say 20bits.\n\nI would say this probability is veery veery low in random case (not a\nmalicious attack of course, but I think this is not the case with git\nrepository as it was with SHA1 designers).\n\nMarco\n"},{"id":"40067","messageId":"9e4733910704211236m7f88aef2r76a1c4a3b72b1c75@mail.gmail.com","threadId":"7768","inReplyTo":"e5bfff550704211128i12035947i7597e920a0eca163@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Jon Smirl","fromEmail":"jonsmirl@gmail.com","sentAt":"2007-04-21T19:36:52Z","receivedAt":"2007-04-21T19:36:52Z","isPatch":false,"sender":{"key":"jonsmirl@gmail.com","avatar":"https://gravatar.com/avatar/cff3bf5bfdfa6708b905712ff91f0f9b8aaca161659f38c02b787920d5d28b7e?d=mp&s=160"},"body":"On 4/21/07, Marco Costalba wrote:\n> I would say this probability is veery veery low in random case (not a\n> malicious attack of course, but I think this is not the case with git\n> repository as it was with SHA1 designers).\n\nThe SHA is also a security signature against tampering. All commits\nhaving an SHA. These SHAs are repeated into a check-in entry, which\nthen gets an SHA. Releases are identified by publishing an SHA.\n\nYou take the release SHA and use it to find/verify the commit record.\nOpening the commit record gives you the SHA of all of the pieces of\nthe commit. (I simplified this by ignoring trees).\n\nThis stops some one from altering a file in a git repo as a way of\ninserting malicious code. If you alter a file all of the SHAs that\ndepend on it will change. It is very, very difficult to figure out how\nto patch a file and not change the SHA for it.\n\nThis is a real problem and people have tried to secretly insert code\ninto the Linux kernel in the past.\n\n-- \nJon Smirl\njonsmirl@gmail.com\n"},{"id":"40115","messageId":"alpine.LFD.0.98.0704220925420.28339@xanadu.home","threadId":"7768","inReplyTo":"e5bfff550704211006t59cb49h179685d694a1d75a@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-22T13:27:13Z","receivedAt":"2007-04-22T13:27:13Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 21 Apr 2007, Marco Costalba wrote:\n\n> On 4/21/07, Jon Smirl wrote:\n> > On 4/21/07, Marco Costalba wrote:\n> > > Well, why to store always the full length SHA?\n> > \n> > When Shawn gets done with full compression the SHAs would get stored\n> > in the packfile once and then be replaced with a token generated from\n> > the compression algorithm. Compression tokens are designed to use the\n> > minimal number of bits depending on frequency of occurrence.\n> > \n> \n> Currently in Lunux tree there are about 445.424 objects (git\n> count-objects -v), if each object has his 40 bytes name it is about\n> 20MB to store sha *once*, probably with no real disambiguate need to\n> be that much.\n\nObject names aren't 40 bytes. They are 20 bytes.\n\nIt is their hex representation that takes 40 bytes.\n\n\nNicolas\n"},{"id":"40271","messageId":"462D5370.8040905@zytor.com","threadId":"7768","inReplyTo":"alpine.LFD.0.98.0704220925420.28339@xanadu.home","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2007-04-24T00:46:40Z","receivedAt":"2007-04-24T00:46:40Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Nicolas Pitre wrote:\n> \n> Object names aren't 40 bytes. They are 20 bytes.\n> It is their hex representation that takes 40 bytes.\n> \n\nSure, but that's the way they're stored in *most* git objects, in \nparticular in commit objects.\n\n\t-hpa\n"},{"id":"40283","messageId":"20070424023035.GK17480@spearce.org","threadId":"7768","inReplyTo":"462D5370.8040905@zytor.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-04-24T02:30:35Z","receivedAt":"2007-04-24T02:30:35Z","isPatch":false,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"\"H. Peter Anvin\" wrote:\n> Nicolas Pitre wrote:\n> >\n> >Object names aren't 40 bytes. They are 20 bytes.\n> >It is their hex representation that takes 40 bytes.\n> >\n> \n> Sure, but that's the way they're stored in *most* git objects, in \n> particular in commit objects.\n\nBut OBJ_TREE occurs more often, and its 20 bytes binary for a SHA-1\nin those. They are only ASCII hex in OBJ_COMMIT and OBJ_TAG.\n\nIf Nico and I ever get pack v4 done, all SHA-1s drop to 24 bytes\nworst case, or 20 + (4 * n_references) best case. Typically we\nfound that n_references was large enough, frequently enough, that\nwe shaved 5% or so off linux-2.6.git. And I don't think that's\nincluding the 20 * n_objects saved out of the .idx files...\n\n-- \nShawn.\n"},{"id":"40284","messageId":"alpine.LFD.0.98.0704232236250.12375@xanadu.home","threadId":"7768","inReplyTo":"462D5370.8040905@zytor.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-24T02:44:30Z","receivedAt":"2007-04-24T02:44:30Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 23 Apr 2007, H. Peter Anvin wrote:\n\n> Nicolas Pitre wrote:\n> > \n> > Object names aren't 40 bytes. They are 20 bytes.\n> > It is their hex representation that takes 40 bytes.\n> > \n> \n> Sure, but that's the way they're stored in *most* git objects, in particular\n> in commit objects.\n\nCommit objects aren't *most* objects. They usually are blob and tree \nobjects, and for the later the SHA1 references are stored as 20 byte \nbinary.\n\n\nNicolas\n"},{"id":"40331","messageId":"462E18C8.4070001@op5.se","threadId":"7768","inReplyTo":"e5bfff550704211128i12035947i7597e920a0eca163@mail.gmail.com","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-04-24T14:48:40Z","receivedAt":"2007-04-24T14:48:40Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Marco Costalba wrote:\n> \n> Someone more versed then me in SHA1 could tell the probablity to find\n> a corrupted object calculating his hash and checking against his\n> stored 160bits known good signature and *FAIL* to find as corrupt *the\n> same object* calculating his hash and checking against a truncated sha\n> to say 20bits.\n> \n\nThe probability of finding a collision when only 20 bits are used is\n1 in 1048575. In other words, repositories would already be exhibiting\ncollisions with only 20 bits of hash, even with a perfect dispersion.\n\n> I would say this probability is veery veery low in random case (not a\n> malicious attack of course, but I think this is not the case with git\n> repository as it was with SHA1 designers).\n> \n\nI believe the KDE repo is the biggest one in git today, with its several\nhundred thousand revisions (and thus most likely several million objects).\n\nThe reason it's not much use to cut down the hash-size is that it already\nreflects a very small percentage of the total size of the repo, and since\nusing the full hash allows git to handle up to\n1461501637330902918203684832716283019655932542976 objects without\nencountering conflicts (it doesn't really, but that's 2 to the power of 160),\nthis works as a nice size for a hash to be.\n\nIf the hash is reduced to 80 bits, the maximum number of unique hashes shrinks\nto 1208925819614629174706176 (less than 1% of 160 bits) while only saving 10\nbytes of storage per object. Using a more efficient compression algorithm for\nthe objects themselves (bzip2, anyone?) will most likely reduce storage size\nan order of magnitude more than reducing the size of the hash, although at the\nexpense of CPU-efficiency.\n\nOne must also factor in the code-changes necessary to support abbreviated hashes\nand ask oneself \"is it worth it?\". Since using a smaller portion of the hash\ndoesn't only have upsides, I'd say \"no, definitely not\".\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"40337","messageId":"alpine.LFD.0.98.0704241058490.12375@xanadu.home","threadId":"7768","inReplyTo":"462E18C8.4070001@op5.se","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-24T15:04:34Z","receivedAt":"2007-04-24T15:04:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 24 Apr 2007, Andreas Ericsson wrote:\n\n> Using a more efficient compression algorithm for the objects \n> themselves (bzip2, anyone?) will most likely reduce storage size an \n> order of magnitude more than reducing the size of the hash, although \n> at the expense of CPU-efficiency.\n\nAn order of magnitude I really doubt it. Maybe 20% could be a really \noptimistic prediction. But if bzip2 could reduce the repo by 20%, it \nwill slow runtime usage of that repo by maybe 100%. That is not worth \nit.\n\nThis is also the reason why we changed the default zlib compression \nlevel from \"best\" to \"default\".\n\n\nNicolas\n"},{"id":"40338","messageId":"462E1FBA.9020109@op5.se","threadId":"7768","inReplyTo":"alpine.LFD.0.98.0704241058490.12375@xanadu.home","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Andreas Ericsson","fromEmail":"ae@op5.se","sentAt":"2007-04-24T15:18:18Z","receivedAt":"2007-04-24T15:18:18Z","isPatch":false,"sender":{"key":"ae@op5.se","avatar":"https://gravatar.com/avatar/426e89595c75a8f5252dd0c989e5fabe5bcac616e68557427ad9aef6b0ca342a?d=mp&s=160"},"body":"Nicolas Pitre wrote:\n> On Tue, 24 Apr 2007, Andreas Ericsson wrote:\n> \n>> Using a more efficient compression algorithm for the objects \n>> themselves (bzip2, anyone?) will most likely reduce storage size an \n>> order of magnitude more than reducing the size of the hash, although \n>> at the expense of CPU-efficiency.\n> \n> An order of magnitude I really doubt it. Maybe 20% could be a really \n> optimistic prediction. But if bzip2 could reduce the repo by 20%, it \n> will slow runtime usage of that repo by maybe 100%. That is not worth \n> it.\n> \n> This is also the reason why we changed the default zlib compression \n> level from \"best\" to \"default\".\n> \n\n... order of magnitude *more than reducing the size of the hash*.\n\n-- \nAndreas Ericsson andreas.ericsson@op5.se\nOP5 AB www.op5.se\nTel: +46 8-230225 Fax: +46 8-230231\n"},{"id":"40344","messageId":"alpine.LFD.0.98.0704241208460.12375@xanadu.home","threadId":"7768","inReplyTo":"462E1FBA.9020109@op5.se","subject":"Re: Why SHA are 40 bytes? (aka looking for flames)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2007-04-24T16:19:25Z","receivedAt":"2007-04-24T16:19:25Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Tue, 24 Apr 2007, Andreas Ericsson wrote:\n\n> Nicolas Pitre wrote:\n> > On Tue, 24 Apr 2007, Andreas Ericsson wrote:\n> > \n> >> Using a more efficient compression algorithm for the objects \n> >> themselves (bzip2, anyone?) will most likely reduce storage size an \n> >> order of magnitude more than reducing the size of the hash, although \n> >> at the expense of CPU-efficiency.\n> > \n> > An order of magnitude I really doubt it. Maybe 20% could be a really \n> > optimistic prediction. But if bzip2 could reduce the repo by 20%, it \n> > will slow runtime usage of that repo by maybe 100%. That is not worth \n> > it.\n> > \n> > This is also the reason why we changed the default zlib compression \n> > level from \"best\" to \"default\".\n> > \n> \n> ... order of magnitude *more than reducing the size of the hash*.\n\nAh, sorry. Still I wanted to advise against it nevertheless.\n\nAnyway, if you compare packing with repack.usedeltabaseoffset set to \ntrue, then to false, you'll have a pretty good approximation of the SHA1 \nstorage cost. With most objects as deltas, in the first case the \nreference to the base object is stored as an offset in the pack while in \nthe second case the full SHA1 is used. You can deduce from the size \ndifference that the SHA1 doesn't constitute a terrible storage cost \nindeed.\n\n\nNicolas\n"}]}