RE: [PATCH] Put sha1dc on a diet
Great! Keep us posted if there is anything else that you would like from the code. Or anyway we can make the process go more smoothly. Thanks, Dan -Original Message- From: Jeff King [mailto:p...@peff.net] Sent: Thursday, March 16, 2017 3:06 PM To: Marc Stevens Cc: Linus Torvalds ; Dan Shumow ; Junio C Hamano ; Git Mailing List Subject: Re: [PATCH] Put sha1dc on a diet On Thu, Mar 16, 2017 at 07:22:14PM +0100, Marc Stevens wrote: > Today I merged the perf-branch into master after code review and correctness > testing. > So master is now more performant and safe to use. Great, thank you (and Dan) so much for all your work. We're looking at integrating this version in a nearby thread. -Peff
Re: [PATCH] Put sha1dc on a diet
On Thu, Mar 16, 2017 at 07:22:14PM +0100, Marc Stevens wrote: > Today I merged the perf-branch into master after code review and correctness > testing. > So master is now more performant and safe to use. Great, thank you (and Dan) so much for all your work. We're looking at integrating this version in a nearby thread. -Peff
Re: [PATCH] Put sha1dc on a diet
Hi all, Today I merged the perf-branch into master after code review and correctness testing. So master is now more performant and safe to use. -- Marc
Re: [PATCH] Put sha1dc on a diet
I think I now understand. The Makefile indeed seems to fail to correctly rebuild when a header has changed. As the performance branch has removed the 'int bigendian' from SHA1_CTX in lib/sha1.h, the perf-branch and master-branch are binary incompatible. So the command-line utility does not get fully recompiled and instead of the value of found_collision will read a different value of SHA1_CTX. So be careful to always do a 'make clean' for now. -- Marc - Original Message - From: "Jeff King" To: "Marc Stevens" Cc: "Linus Torvalds" , "Dan Shumow" , "Junio C Hamano" , "Git Mailing List" Sent: Monday, March 13, 2017 10:00:23 PM Subject: Re: [PATCH] Put sha1dc on a diet On Mon, Mar 13, 2017 at 09:47:54PM +0100, Marc Stevens wrote: > Linus: > I would be surprised, the dependencies should be automatically determined. > > BTW Did you make local changes to this perf branch? I can reproduce it with: cd sha1collisiondetection git clean -dqfx ;# make sure we are starting from scratch git checkout 9c8e73cadb35776d3310e3f8ceda7183fa75a39f make bin/sha1dcsum $file git checkout 55d1db0980501e582f6cd103a04f493995b1df78 make bin/sha1dcsum $file The final call to sha1dcsum will report a collision, even though the first one did not. It also reproduces with the original snippet I posted. I didn't notice because I was just collecting the timings then (and I originally noticed the problem on the versions I had pulled into Git, where it works as expected; but then I am just pulling in the two source files, without all of the libtool magic). -Peff
Re: [PATCH] Put sha1dc on a diet
On Mon, Mar 13, 2017 at 09:47:54PM +0100, Marc Stevens wrote: > Linus: > I would be surprised, the dependencies should be automatically determined. > > BTW Did you make local changes to this perf branch? I can reproduce it with: cd sha1collisiondetection git clean -dqfx ;# make sure we are starting from scratch git checkout 9c8e73cadb35776d3310e3f8ceda7183fa75a39f make bin/sha1dcsum $file git checkout 55d1db0980501e582f6cd103a04f493995b1df78 make bin/sha1dcsum $file The final call to sha1dcsum will report a collision, even though the first one did not. It also reproduces with the original snippet I posted. I didn't notice because I was just collecting the timings then (and I originally noticed the problem on the versions I had pulled into Git, where it works as expected; but then I am just pulling in the two source files, without all of the libtool magic). -Peff
Re: [PATCH] Put sha1dc on a diet
Linus: I would be surprised, the dependencies should be automatically determined. BTW Did you make local changes to this perf branch? Specifically did you disable the safe hash mode that is on by default? Because if you did not, it might also be something else as all three hashes below are the same. -- Marc - Original Message - From: "Linus Torvalds" To: "Marc Stevens" Cc: "Jeff King" , "Dan Shumow" , "Junio C Hamano" , "Git Mailing List" Sent: Monday, March 13, 2017 9:20:02 PM Subject: Re: [PATCH] Put sha1dc on a diet On Mon, Mar 13, 2017 at 1:12 PM, Marc Stevens wrote: > Indeed, I've committed a fix, and a small bug fix for the new code just now. Unrelated side note: there may be some missing dependencies in the build infrastructure or something, because when I tried Jeff's script that did that "test the merge and the two parents", and used the pack-file of the kernel for testing, I got: 5611971c610143e6d38bbdca463f4c9f79a056a0 /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m2.432s user 0m2.348s sys 0m0.084s 5611971c610143e6d38bbdca463f4c9f79a056a0 /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m3.747s user 0m3.672s sys 0m0.076s 5611971c610143e6d38bbdca463f4c9f79a056a0 *coll* /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m5.061s user 0m4.984s sys 0m0.077s never mind the performace, notice the *coll* in that last case. But doing a "git clean -dqfx; make -j8" and re-testing the same tree, the issue is gone. I suspect some dependency on a header file is broken, causing some object file to not be properly re-built, which in turn then incorrectly causes the 'ctx2.found_collision' test to test the wrong bit or something. Linus
Re: [PATCH] Put sha1dc on a diet
On Mon, Mar 13, 2017 at 1:12 PM, Marc Stevens wrote: > Indeed, I've committed a fix, and a small bug fix for the new code just now. Unrelated side note: there may be some missing dependencies in the build infrastructure or something, because when I tried Jeff's script that did that "test the merge and the two parents", and used the pack-file of the kernel for testing, I got: 5611971c610143e6d38bbdca463f4c9f79a056a0 /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m2.432s user 0m2.348s sys 0m0.084s 5611971c610143e6d38bbdca463f4c9f79a056a0 /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m3.747s user 0m3.672s sys 0m0.076s 5611971c610143e6d38bbdca463f4c9f79a056a0 *coll* /home/torvalds/v2.6/linux/.git/objects/pack/pack-153bb8cd11846cf9a27ef7b1069aa9cb9f5b724f.pack real 0m5.061s user 0m4.984s sys 0m0.077s never mind the performace, notice the *coll* in that last case. But doing a "git clean -dqfx; make -j8" and re-testing the same tree, the issue is gone. I suspect some dependency on a header file is broken, causing some object file to not be properly re-built, which in turn then incorrectly causes the 'ctx2.found_collision' test to test the wrong bit or something. Linus
Re: [PATCH] Put sha1dc on a diet
Indeed, I've committed a fix, and a small bug fix for the new code just now. The merge incorrectly removed some control logic, which caused more unnecessary checks to happen. I already marked this in the PR, but committed a fix only today. BTW as noted in the Readme, the theoretic false positive probability is <<2^-90, almost non-existent. Best regards, Marc Stevens On 3/13/2017 8:48 PM, Jeff King wrote: > On Mon, Mar 13, 2017 at 07:42:17PM +, Dan Shumow wrote: > >> Marc just made a commit this morning fixing problems with the merge. >> Please give the latest in feature/performance a try, as that seems to >> eliminate the problem. > Yeah, b17728507 makes the problem go away for me. Thanks. > > FWIW, I have all sha1s on github.com running through this right now > (actually, the ad744c8b7 version), and logging any false-positives on > the collision detection. Nothing so far, after a few hours. > > -Peff
Re: [PATCH] Put sha1dc on a diet
On Mon, Mar 13, 2017 at 07:42:17PM +, Dan Shumow wrote: > Marc just made a commit this morning fixing problems with the merge. > Please give the latest in feature/performance a try, as that seems to > eliminate the problem. Yeah, b17728507 makes the problem go away for me. Thanks. FWIW, I have all sha1s on github.com running through this right now (actually, the ad744c8b7 version), and logging any false-positives on the collision detection. Nothing so far, after a few hours. -Peff
Re: [PATCH] Put sha1dc on a diet
On Sat, Mar 04, 2017 at 01:07:16AM +, Dan Shumow wrote: > You are very welcome. Thank you for the warm welcome. As it turns > out, Marc and I are working on the simplifications / removal of c99 > and performance upstream in our GitHub repo. I am happy to help for > any GitHub specific customizations that are needed as well. But for > now, lets see if we can get you everything you want upstream -- I > think that's the most simple. I've been watching the repo at: https://github.com/cr-marcstevens/sha1collisiondetection The work on the feature/performance branch seems to be producing good results. The best timings I got show sha1dc (with checks enabled) at 1.75x block-sha1, which is pretty good. That was using your ad744c8b7a841d2afcb2d4c04f8952d9005501be. Curiously, the performance gets worse after that. Even more curious, the bad performance bisects to a merge, and it performs worse than either side of the merge. Try this: # mine is a 1.2GB linux packfile, but anything big should do file=/some/large/file # the merge with the funny behavior merge=55d1db0980501e582f6cd103a04f493995b1df78 for i in $merge^ $merge^2 $merge; do git checkout $i && rm -f bin/* && make && time bin/sha1dcsum $file done I get: [$merge^, the feature/performance branch before the merge] real 0m3.391s user 0m3.304s sys 0m0.084s [$merge^2, the master branch before the merge] real 0m5.272s user 0m5.164s sys 0m0.096s [$merge, the merge of the two] real 0m7.038s user 0m6.924s sys 0m0.104s So that's odd. Looking at the diff, I don't see anything that obviously jumps out as a mis-merge. Feel free to tell me "stop looking at that branch; it's a work in progress". But I think the results from $merge^ (ad744c8b7) are getting good enough to consider moving forward with integrating it into git. -Peff
RE: [PATCH] Put sha1dc on a diet
From: Junio C Hamano [mailto:gits...@pobox.com] > As you and Marc seemed to be still working on speeding up, such a > customization work to fully adjust your code to our codebase was premature, > so I tentatively queued what we saw on the list as-is on our 'pu' branch so > that people can have a reference point. Which unfortunately solicited a > premature reaction by Johannes. Please do not worry too much about the > comment. > But if you are willing to help us by getting involved in the "customization" > part, too, that would be a very welcome news to us. >In that case, "welcome to the Git development community" ;-) > So,... from my point of view, we are OK either way. It is OK if you are a > third-party upstream that is not particularly interested in Git project's > specific requirement. We surely would be happier if you and Marc, the > upstream authors of the code in question, also act as participants in the Git > development community. > Either way, thanks for your great help. You are very welcome. Thank you for the warm welcome. As it turns out, Marc and I are working on the simplifications / removal of c99 and performance upstream in our GitHub repo. I am happy to help for any GitHub specific customizations that are needed as well. But for now, lets see if we can get you everything you want upstream -- I think that's the most simple. Thanks again, Dan
Re: [PATCH] Put sha1dc on a diet
On Thu, Mar 2, 2017 at 10:37 AM, Jeff Hostetler wrote: >> >> Now, if your _file_ index is 300-400MB (and I do think we check the >> SHA fingerprint on that even on just reading it - verify_hdr() in >> do_read_index()), then that's going to be a somewhat noticeable hit on >> every normal "git diff" etc. > > Yes, the .git/index is 450MB with ~3.1M entries. verify_hdr() is called > each time we read it into memory. Ok. So that's really just a purely historical artifact. The file index is actually the first part of git to have ever been written. You can't even see it in the history, because the initial revision from Apr 7, 2005, obviously depended on the actual object hashing. But the file index actually came first. You can _kind_ of see that in the layout of the original git tree, and how the main header file is still called "cache.h", and how the original ".git" directory was actually called ".dircache". And the two biggest files (by a fairly big margin) are "read-cache.c" and "update-cache.c". So that file index cache was in many ways _the_ central part of the original git model. The sha1 file indexing and object database was just the backing store for the file index. But part of that history is then how much I worried about corruption of that index (and, let's face it, general corruption resistance _was_ one of the primary design goals - performance was high up there too, but safety in the face of filesystem corruption was and is a primary issue). But realistically, I don't think we've *ever* hit anything serious on the index file, and it's obviously not a security issue. It also isn't even a compatibility issue, so it would be trivial to just bump the version header and saying that the signature changes the meaning of the checksum. That said: > We have been testing a patch in GfW to run the verification in a separate > thread > while the main thread parses (and mallocs) the cache_entries. This does help > offset the time. Yeah, that seems an even better solution, honestly. The patch would be cleaner without the NO_PTHREADS things. I wonder how meaningful that thing even is today. Looking at what seems to select NO_PTHREADS, I suspect that's all entirely historical. For example, you'll see it for QNX etc, which seems wrong - QNX definitely has pthreads according to their docs, for example. Linus
Re: [PATCH] Put sha1dc on a diet
On 3/2/2017 11:35 AM, Linus Torvalds wrote: On Thu, Mar 2, 2017 at 6:45 AM, Johannes Schindelin wrote: It would probably make sense to switch the index integrity check away from SHA-1 because we really only care about detecting bit flips there, and we have no need for the computational overhead of using a full-blown cryptographic hash for that purpose. Which index do you actually see as being a problem, btw? The main file index (.git/index) or the pack-file indexes? We definitely don't need the checking version of sha1 for either of those, but as Jeff already did the math, at least the pack-file index is almost negligible, because the pack-file operations that update it end up doing SHA1 over the objects - and the object SHA1 calculations are much bigger. And I don't think we even check the pack-file index hashes except on fsck. Now, if your _file_ index is 300-400MB (and I do think we check the SHA fingerprint on that even on just reading it - verify_hdr() in do_read_index()), then that's going to be a somewhat noticeable hit on every normal "git diff" etc. Yes, the .git/index is 450MB with ~3.1M entries. verify_hdr() is called each time we read it into memory. We have been testing a patch in GfW to run the verification in a separate thread while the main thread parses (and mallocs) the cache_entries. This does help offset the time. https://github.com/git-for-windows/git/pull/978/files But I'd have expected the stat() calls of all the files listed by that index to be the _much_ bigger problem in that case. Or do you just turn those off with assume-unchanged? Yeah, those stat calls are threaded when preloading, but even so.. Yes, the stat() calls are more significant percentage of the time (and having core.fscache and core.preloadindex help that greatly), but the total time for a command is just that -- the total -- so using the philosophy of "every little bit helps", the faster routines help us here. Anyway, the file index SHA1 checking could probably just be disabled entirely (with a config flag). It's a corruption check that simply isn't that important. So if that's your main SHA1 issue, that would be easy to fix. Yes, in the GVFS effort, we disabled the verification with a config setting and haven't had any incidents. Everything else - like pack-file generation etc for a big clone() may end up using a ton of SHA1 too, but the SHA1 costs all scale with the other costs that drown them out (ie zlib, network, etc). I'd love to see a profile if you have one. Linus
Re: [PATCH] Put sha1dc on a diet
On Thu, Mar 2, 2017 at 6:45 AM, Johannes Schindelin wrote: > > It would probably make sense to switch the index integrity check away from > SHA-1 because we really only care about detecting bit flips there, and we > have no need for the computational overhead of using a full-blown > cryptographic hash for that purpose. Which index do you actually see as being a problem, btw? The main file index (.git/index) or the pack-file indexes? We definitely don't need the checking version of sha1 for either of those, but as Jeff already did the math, at least the pack-file index is almost negligible, because the pack-file operations that update it end up doing SHA1 over the objects - and the object SHA1 calculations are much bigger. And I don't think we even check the pack-file index hashes except on fsck. Now, if your _file_ index is 300-400MB (and I do think we check the SHA fingerprint on that even on just reading it - verify_hdr() in do_read_index()), then that's going to be a somewhat noticeable hit on every normal "git diff" etc. But I'd have expected the stat() calls of all the files listed by that index to be the _much_ bigger problem in that case. Or do you just turn those off with assume-unchanged? Yeah, those stat calls are threaded when preloading, but even so.. Anyway, the file index SHA1 checking could probably just be disabled entirely (with a config flag). It's a corruption check that simply isn't that important. So if that's your main SHA1 issue, that would be easy to fix. Everything else - like pack-file generation etc for a big clone() may end up using a ton of SHA1 too, but the SHA1 costs all scale with the other costs that drown them out (ie zlib, network, etc). I'd love to see a profile if you have one. Linus
Re: [PATCH] Put sha1dc on a diet
Hi Duy, On Thu, 2 Mar 2017, Duy Nguyen wrote: > On Thu, Mar 2, 2017 at 6:19 AM, Jeff King wrote: > > You have to remember that some of the Git for Windows users are doing > > horrific things like using repositories with 450MB .git/index files, > > and the speed to compute the sha1 during an update is noticeable > > there. > > We probably should separate this use case from the object hashing > anyway. Here we need a better, more reliable crc32 basically, to detect > bit flips. Even if we move to SHA-something, we can keep staying with > SHA-1 here (and with the fastest implementation) I guess it was convenient to use the same hash algorithm for all hashing purposes in the beginning. The downside, of course, was that we kept talking about SHA-1s instead of commit hashes and the index checksum (i.e. using labels based on implementation details rather than semantically meaningful names). In the meantime, we use different hash algorithms where appropriate, of course, and we typically encapsulate the exact hash algorithm so that it is easy to switch when/if necessary (think the hash functions for strings in our hashtables, and the hash functions in xdiff). It would probably make sense to switch the index integrity check away from SHA-1 because we really only care about detecting bit flips there, and we have no need for the computational overhead of using a full-blown cryptographic hash for that purpose. Ciao, Johannes
Re: [PATCH] Put sha1dc on a diet
Hi Linus, On Wed, 1 Mar 2017, Linus Torvalds wrote: > On Wed, Mar 1, 2017 at 2:51 PM, Johannes Schindelin > wrote: > > > > But I think bigger than just developers on Windows OS. There are many > > developers out there working on large repositories (yes, much larger > > than Linux). Also using Macs and Linux. I am not at all sure that we > > want to give them an updated Git they cannot fail to notice to be much > > slower than before. > > Johannes, have you *tried* the patches? > > I really don't think you have. It is completely unnoticeable in any > normal situation. The two cases that it's noticeable is: > > - a full fsck is noticeable slower > > - a full non-local clone is slower (but not really noticeably so > since the network traffic dominates). > > In other words, I think you're making shit up. I don't think you > understand how little the SHA1 performance actually matters. It's > noticeable in benchmarks. It's not noticeable in any normal operation. > > .. and yes, I've actually been running the patches locally since I > posted my first version (which apparently didn't go out to the list > because of list size limits) and now running the version in 'pu'. If you think that the Linux repository is a big one, then your reaction is understandable. I have zero interest in potty language, therefore my reply is very terse: yes, I have been looking ad SHA-1 performance, and yes, it matters. Think an index file of 300-400MB. Ciao, Johannes
Re: [PATCH] Put sha1dc on a diet
Hi Peff, On Wed, 1 Mar 2017, Jeff King wrote: > I do think that could argue for turning on the collision detection only > during object-write operations, which is where it matters. It would be > really trivial to flip the "check collisions" bit on sha1dc. But I > suspect you could go faster still by compiling against two separate > implementations: the fast-as-possible one (which could be openssl or > blk-sha1), and the slower-but-careful sha1dc. Given the speed difference between OpenSSL and sha1dc, it would be a wise thing indeed to do sha1dc only where objects enter from possibly untrusted sources, and use OpenSSL for all other hashing. Ciao, Johannes
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 11:07 AM, Jeff King wrote: > > So obviously the smaller object size is nice, and the diffstat is > certainly satisfying. My only qualm would be whether this conflicts with > the optimizations that Dan is working on (probably not conceptually, but > textually). Yeah. But I'll happily just re-apply the patch on any new version that Dan posts. The patch is obviously trivial, even if size-wise it's a fair number of lines. So I wouldn't suggest using the patched version as some kind of starting point. It's much easier to just take a new version of upstream and repeat the diet patch on it. .. and obviously later versions of the upstream sha1dc code may not even need this at all since Dan and Marc are now aware of the issue. Linus
Re: [PATCH] Put sha1dc on a diet
On Thu, Mar 2, 2017 at 6:19 AM, Jeff King wrote: > You have to remember that some of the Git for Windows users are doing > horrific things like using repositories with 450MB .git/index files, and > the speed to compute the sha1 during an update is noticeable there. We probably should separate this use case from the object hashing anyway. Here we need a better, more reliable crc32 basically, to detect bit flips. Even if we move to SHA-something, we can keep staying with SHA-1 here (and with the fastest implementation) -- Duy
Re: [PATCH] Put sha1dc on a diet
Dan Shumow writes: > At this point, I would suggest that I take the C optimizations, > clean them up and fold them in with the diet changes Linus has > suggested. The slowdown is still 2x over block-sha1 and more over > OpenSSL. But it is better than nothing. And then if there is > interest Marc and I can investigate other processor specific > optimizations like ASM or SIMD and circle back with those > performance optimizations at a later date. > > Also, to Johannes Schindelin's point: >> My concern is about that unexpected turn "oh, let's just switch >> to C99 because, well, because my compiler canehandle it, and >> everybody else should just switch tn a modern compiler". That >> really sounded careless. > > While it will probably be a pain, if it is a requirement, we can > modify the code to move away from any c99 specific stuff we have > in here, if it makes adopting the code more palatable for Git. I was assuming that we would treat your code just like how we treat any other "borrowed code from elsewhere". The usual way for us to do so is to take code that was released by the "upstream" (under a license that allows us to use it---yours is MIT, which does) in the style and language of upstream's choice, and then we in the Git development community takes responsiblity for massaging the code to match our style, for trimming what we won't use and for doing any other customization to fit our needs. As you and Marc seemed to be still working on speeding up, such a customization work to fully adjust your code to our codebase was premature, so I tentatively queued what we saw on the list as-is on our 'pu' branch so that people can have a reference point. Which unfortunately solicited a premature reaction by Johannes. Please do not worry too much about the comment. But if you are willing to help us by getting involved in the "customization" part, too, that would be a very welcome news to us. In that case, "welcome to the Git development community" ;-) So,... from my point of view, we are OK either way. It is OK if you are a third-party upstream that is not particularly interested in Git project's specific requirement. We surely would be happier if you and Marc, the upstream authors of the code in question, also act as participants in the Git development community. Either way, thanks for your great help.
RE: [PATCH] Put sha1dc on a diet
I played around tweaking the code a bit more and I got our performance down to a 2.077182x slowdown with check and a 1.055961x slowdown without checking. However, that slowdown is basically with the check turned off through our API. If I rip extraneous code for storing states and checking if we are doing collision detection out, I can reach performance parity with the block-sha1 implementation in the Git codebase, which basically tells me that is about as good as I can do for optimizing the C code. SHA1 is more amenable to assembler implementation because its use of rotations, which are notoriously difficult to access through C code. And as this happens in the inner loop of the function, the inline asm tends to not cut it. This is one of the reasons that the OpenSSL SHA-1 runs like a scalded monkey, compared to the C implemenations. Marc and I have also discussed using SIMD operations to speed up the UBC checks, which could definitely help achieve better performance, but is highly dependent on processor support. It will take some time to do either a SIMD implementation of the UBC checks or an assembler implementation. At this point, I would suggest that I take the C optimizations, clean them up and fold them in with the diet changes Linus has suggested. The slowdown is still 2x over block-sha1 and more over OpenSSL. But it is better than nothing. And then if there is interest Marc and I can investigate other processor specific optimizations like ASM or SIMD and circle back with those performance optimizations at a later date. Also, to Johannes Schindelin's point: > My concern is about that unexpected turn "oh, let's just switch to C99 > because, well, because my compiler canehandle it, and everybody else should > just switch tn a modern compiler". That really sounded careless. While it will probably be a pain, if it is a requirement, we can modify the code to move away from any c99 specific stuff we have in here, if it makes adopting the code more palatable for Git. Thanks, Dan
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 12:34 PM, Jeff King wrote: > > I don't think that helps. The sha1 over the pack-file takes about 1.3s > with openssl, and 5s with sha1dc. So we already know the increase there > is only a few seconds, not a few minutes. Yeah, I did a few statistics by adding just logging of "SHA1_Init()" calls. For that network clone situation, the call distribution is 1SHA1: Init at builtin/index-pack.c:326 841228SHA1: Init at builtin/index-pack.c:450 2SHA1: Init at csum-file.c:152 4415756SHA1: Init at sha1_file.c:3218 (the line numbers are a bit off from 'pu', because I obviously have the logging code). The big number (one for every object) is from write_sha1_file_prepare(), which we'd want to be the strong collision checking version because those are things we're about to create git objects out of. It's called from - hash_sha1_file() - doesn't actually write the object, but is used to calculate the sha for incoming data after applying the delta, for example. - write_sha1_file() - many uses, actually writes the object - hash_sha1_file_literally() - git hash-object and that index-pack.c:450 is from unpack_entry_data() for the base non-delta objects (which should also be the strong kind). So all of them should check against collision attacks, so none of them seem to be things you'd want to optimize away.. So I was wrong in thinking that there were a lot of unnecessary SHA1 calculations in that load. They all look like they should be done with the slower checking code. Oh well. Linus
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 01, 2017 at 03:05:25PM -0800, Linus Torvalds wrote: > On Wed, Mar 1, 2017 at 2:51 PM, Johannes Schindelin > wrote: > > > > But I think bigger than just developers on Windows OS. There are many > > developers out there working on large repositories (yes, much larger than > > Linux). Also using Macs and Linux. I am not at all sure that we want to > > give them an updated Git they cannot fail to notice to be much slower than > > before. > > Johannes, have you *tried* the patches? > > I really don't think you have. It is completely unnoticeable in any > normal situation. The two cases that it's noticeable is: > > - a full fsck is noticeable slower > > - a full non-local clone is slower (but not really noticeably so > since the network traffic dominates). > > In other words, I think you're making shit up. I don't think you > understand how little the SHA1 performance actually matters. It's > noticeable in benchmarks. It's not noticeable in any normal operation. > > .. and yes, I've actually been running the patches locally since I > posted my first version (which apparently didn't go out to the list > because of list size limits) and now running the version in 'pu'. You have to remember that some of the Git for Windows users are doing horrific things like using repositories with 450MB .git/index files, and the speed to compute the sha1 during an update is noticeable there. IMHO that is a good sign that the right approach is to switch to an index format that doesn't require rewriting all 450MB to update one entry. But obviously that is a much harder problem than just using an optimized sha1 implementation. I do think that could argue for turning on the collision detection only during object-write operations, which is where it matters. It would be really trivial to flip the "check collisions" bit on sha1dc. But I suspect you could go faster still by compiling against two separate implementations: the fast-as-possible one (which could be openssl or blk-sha1), and the slower-but-careful sha1dc. -Peff
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 01, 2017 at 12:58:39PM -0800, Linus Torvalds wrote: >> I don't think that helps. The sha1 over the pack-file takes about 1.3s >> with openssl, and 5s with sha1dc. So we already know the increase there >> is only a few seconds, not a few minutes. > > OK. I guess what w could easily do is to just add an argument to > git_SHA1_Init() to say whether we want checking or not, and only use the > checking functions when receiving objects (which would include creating new > objects from files, and obviously deck). > > You'd still eat the cost on the receiving side of a clone, but that's when > you really want the checking anyway. At least it wouldn't be so visible on > the sending side, which is all the hosting etc, where there might be server > utilization issues. > > Would that make deployment happier? It should be an easy little flag to > add, I think. I don't think it makes all that big a difference. The sending side wastes the extra 2-3 seconds of CPU to checksum the whole packfile, but it's not inflating all the object contents in the first place (between reachability bitmaps to get the list of objects in the first place, and then verbatim reuse of pack contents). Which isn't to say it's not reasonable to limit the checking to a few spots (basically anything that's _writing_ objects). But I don't think it makes a big difference to the server side of a fetch or clone. -Peff
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 2:51 PM, Johannes Schindelin wrote: > > But I think bigger than just developers on Windows OS. There are many > developers out there working on large repositories (yes, much larger than > Linux). Also using Macs and Linux. I am not at all sure that we want to > give them an updated Git they cannot fail to notice to be much slower than > before. Johannes, have you *tried* the patches? I really don't think you have. It is completely unnoticeable in any normal situation. The two cases that it's noticeable is: - a full fsck is noticeable slower - a full non-local clone is slower (but not really noticeably so since the network traffic dominates). In other words, I think you're making shit up. I don't think you understand how little the SHA1 performance actually matters. It's noticeable in benchmarks. It's not noticeable in any normal operation. .. and yes, I've actually been running the patches locally since I posted my first version (which apparently didn't go out to the list because of list size limits) and now running the version in 'pu'. Linus
Re: [PATCH] Put sha1dc on a diet
Hi, On Wed, 1 Mar 2017, Linus Torvalds wrote: > On Wed, Mar 1, 2017 at 1:56 PM, Johannes Schindelin > wrote: > > Footnote *1*: I know, it is easy to forget that some developers cannot > > choose their tools, or even their hardware. In the past, we seemed to take > > appropriate care, though. > > I don't think you need to worry about the Windows side. I am not. I build G?t for Windows using GCC. My concern is about that unexpected turn "oh, let's just switch to C99 because, well, because my compiler canehandle it, and everybody else should just switch tn a modern compiler". That really sounded careless. > That can continue to do something else. > > When I advocated perhaps using USE_SHA1DC by default, I definitely did > not mean it in a "everywhere, regardless of issues" manner. > > For example, the conmfig.mak.uname script already explicitly asks for > "BLK_SHA1 = YesPlease" for Windows. Don't bother changing that, it's an > explicit choice. That setting is only in git.git's version, not in gxt-for-windows/git.git. We switched to OpenSSL because of speed improvements, in particular with recent Intel processors. > But the Linux rules don't actually specify which SHA1 version to use, > so the main Makefile currently defaults to just using openssl. > > So that's the "default" choice I think we might want to change. Not > the "we're windows, and explicitly want BLK_SHA1 because of > environment and build infrastructure". Since we switched away from BLOCK_SHA1, any such change would affect Git for Windews. But I think bigger than just developers on Windows OS. There are many developers out there working on large repositories (yes, much larger than Linux). Also using Macs and Linux. I am not at all sure that we want to give them an updated Git they cannot fail to notice to be much slower than before. Don't get me wrong: I *hope* that you'll manage to get sha1dc competitively fast. If you don't, well, then we simply cannot use it by default for *all* of our calls (you already pointed out that the pack index' checksum does not need collision detection, and in fact, *any* operation that works on implicitly trusted data falls into the same court, e.g. `git add`). Ciao, Johannes
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 1:56 PM, Johannes Schindelin wrote: > Footnote *1*: I know, it is easy to forget that some developers cannot > choose their tools, or even their hardware. In the past, we seemed to take > appropriate care, though. I don't think you need to worry about the Windows side. That can continue to do something else. When I advocated perhaps using USE_SHA1DC by default, I definitely did not mean it in a "everywhere, regardless of issues" manner. For example, the conmfig.mak.uname script already explicitly asks for "BLK_SHA1 = YesPlease" for Windows. Don't bother changing that, it's an explicit choice. But the Linux rules don't actually specify which SHA1 version to use, so the main Makefile currently defaults to just using openssl. So that's the "default" choice I think we might want to change. Not the "we're windows, and explicitly want BLK_SHA1 because of environment and build infrastructure". Linus
Re: [PATCH] Put sha1dc on a diet
Hi, On Wed, 1 Mar 2017, Junio C Hamano wrote: > Linus Torvalds writes: > > > That said, I think that it would be lovely to just default to > > USE_SHA1DC and just put the whole attack behind us. Yes, it's slower. > > No, it doesn't really seem to matter that much in practice. > > Yes. It would be a very good goal. So let me get this straight: not only do we now implicitly want to bump the required C compiler to C99 without any grace period worth mentioning [*1*], we are also all of a sudden no longer worried about a double digit percentage drop of speed [*2*]? Puzzled, Johannes Footnote *1*: I know, it is easy to forget that some developers cannot choose their tools, or even their hardware. In the past, we seemed to take appropriate care, though. Footnote *2*: With real-world repositories of notable size, that performance regression hurts. A lot. We just spent time to get the speed of SHA-1 down by a couple percent and it was a noticeable improvement here.
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 1:56 PM, Johannes Schindelin wrote: > Hi, > > On Wed, 1 Mar 2017, Junio C Hamano wrote: > >> Linus Torvalds writes: >> >> > That said, I think that it would be lovely to just default to >> > USE_SHA1DC and just put the whole attack behind us. Yes, it's slower. >> > No, it doesn't really seem to matter that much in practice. >> >> Yes. It would be a very good goal. > > So let me get this straight: not only do we now implicitly want to bump > the required C compiler to C99 without any grace period worth mentioning > [*1*], we are also all of a sudden no longer worried about a double digit > percentage drop of speed [*2*]? Before we get the code into shape suitable for 'next', it is more important to make sure it operates correctly, adding necessary features if any (e.g. "hash with or without check" knob) while it is in 'pu', and *1* is to allow it to progress faster without having to worry about something we could do mechanically before making it ready for 'next'. The performance thing is really "let's see how well it goes". With effort to optimize still "just has began", I think it is too early to tell if Linus's "doesn't really seem to matter" is the case or not. Queuing such a topic on 'pu' is one effective way to make sure people are working off of the same codebase.
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 01, 2017 at 12:14:34PM -0800, Linus Torvalds wrote:
> > My biggest concern is the index-pack operation. Try this:
>
> I'm mobile right now, so I can't test, but I'd this perhaps at least partly
> due to the full checksum over the pack-file?
>
> We have two very different uses of SHA1: the actual object name hash, but
> also the sha1file checksums that we do on the index file and the pack files.
>
> And the checksum code really doesn't need the collision checking at all.
I don't think that helps. The sha1 over the pack-file takes about 1.3s
with openssl, and 5s with sha1dc. So we already know the increase there
is only a few seconds, not a few minutes.
And it makes sense if you think about the index-pack operation. It has
to inflate each object, resolving deltas, and checksum the result. And
the number of inflated bytes is _much_ larger than the on-disk bytes.
You can see the difference with:
git cat-file --batch-all-objects \
--batch-check='%(objectsize:disk) %(objectsize)' |
perl -alne '
$disk += $F[0]; $raw += $F[1];
END { print "$disk $raw" }
'
On linux.git that yields:
1210521959 63279680406
That's over a 50x increase in the bytes we have to sha1 for objects
versus pack-checksums.
-Peff
Re: [PATCH] Put sha1dc on a diet
Linus Torvalds writes: > That said, I think that it would be lovely to just default to > USE_SHA1DC and just put the whole attack behind us. Yes, it's slower. > No, it doesn't really seem to matter that much in practice. Yes. It would be a very good goal.
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 01, 2017 at 10:49:55AM -0800, Linus Torvalds wrote: > That said, I think that it would be lovely to just default to > USE_SHA1DC and just put the whole attack behind us. Yes, it's slower. > No, it doesn't really seem to matter that much in practice. My biggest concern is the index-pack operation. Try this: time git clone --no-local --bare linux tmp.git with and without USE_SHA1DC. I get: [w/ openssl] real 1m52.307s user 2m47.928s sys 0m14.992s [w/ sha1dc] real 3m4.043s user 6m16.412s sys 0m13.772s That's real latency the user will see. It's hard to break it down, though. The actual "receiving" phase is generally going to be network bound. The delta-resolution that happens afterwards is totally local and CPU-bound (but does run in parallel). And of course this repository tends to the larger side (though certainly there are bigger ones), and you only feel the pain on clone or when doing an initial push, not day-to-day. So maybe we just suck it up and accept that it's a bit slower. -Peff
Re: [PATCH] Put sha1dc on a diet
On Tue, Feb 28, 2017 at 04:30:26PM -0800, Linus Torvalds wrote: > From: Linus Torvalds > Date: Tue, 28 Feb 2017 16:12:32 -0800 > Subject: [PATCH] Put sha1dc on a diet > > This removes the unnecessary parts of the sha1dc code, shrinking things from > [...] So obviously the smaller object size is nice, and the diffstat is certainly satisfying. My only qualm would be whether this conflicts with the optimizations that Dan is working on (probably not conceptually, but textually). -Peff
Re: [PATCH] Put sha1dc on a diet
On Wed, Mar 1, 2017 at 10:42 AM, Junio C Hamano wrote:
> I see //c99 comments
sha1dc is already full of // style comments. I just followed the
existing practice.
> and also T array[] = { [58] = val } both of
> which I think we stay away from (and the former is from the initial
> import), so some people on other platforms MAY have trouble with
> this topic.
Hmm. The "{ [58] = val; }" kind of initialization would be easy to
work around by just filling in everything else with NULL, but it would
make for a pretty nasty readability issue.
That said, if you mis-count the NULL's, the end result will pretty
immediately SIGSEGV, so I guess it wouldn't be much of a maintenance
problem.
But if you're just willing to take the "let's see" approach, I think
the explicitly numbered initializer is much better.
The main people who I assume would really want to use the sha1dc
library are hosting places. And they won't be using crazy compilers
from the last century.
That said, I think that it would be lovely to just default to
USE_SHA1DC and just put the whole attack behind us. Yes, it's slower.
No, it doesn't really seem to matter that much in practice.
Linus
Re: [PATCH] Put sha1dc on a diet
Linus Torvalds writes:
> I notice that sha1dc is in the 'pu' branch now, so let's put my money
> where my mouth is, and send in the sha1dc diet patch.
I see //c99 comments and also T array[] = { [58] = val } both of
which I think we stay away from (and the former is from the initial
import), so some people on other platforms MAY have trouble with
this topic.
Let's see what happens by queuing it on 'pu' ;-)
Thanks.
