On Wed, Mar 01, 2017 at 12:14:34PM -0800, Linus Torvalds wrote:
quoted
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
On Wed, Mar 1, 2017 at 12:34 PM, Jeff King [off-list ref] 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
1 SHA1: Init at builtin/index-pack.c:326
841228 SHA1: Init at builtin/index-pack.c:450
2 SHA1: Init at csum-file.c:152
4415756 SHA1: 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
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