Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why is C faster than Java: git vs JGit

marc.info

Post reply on HN
Print view View original

81–90 of 106 posts

Re: Why is C faster than Java: git vs JGit

#81

Post by chubot »

gelliott wrote: post #74
zxypoo wrote: post #63

This is an old email... there's been many improvements to both JGit, Java/JVM and other areas of interest. Shawn and I gave a presentation at the Googleplex not so long ago about JGit [1]. In particular, you may be interested in the 'JGit at Google' section. There are some cases where JGit is faster than CGit, but the benefits of JGit are that it's easy to embed. There are projects like gitblit and other IDEs that us…

That's really interesting - according to this presentation JGit clone is significantly faster than native git clone (2.3x in the example). I'd love to hear more about any code changes that lead to this result.

Total speculation... but maybe because C git clone always reads from local disk (?). jgit clone appears to read from Bigtable/GFS, and those systems have in-memory caches, or columns can reside totally in memory. Also you could probably make use of parallelism in I/O with cluster of servers, where as with local disk you are probably limited by there being a single disk head that has to move around.

So I doubt it has anything to with Java, but the underlying storage. If I'm wrong I'd also like to hear about it!

Re: Why is C faster than Java: git vs JGit

#82

Post by oelewapperke »

ced wrote: post #34
kmm wrote: post #28

Earlier quoted context omitted.

I've heard the argument before that in need, one can use a FFI to optimize bottlenecks in high-level code, but I've never understood. Won't using a high-level language incur an omnipresent speed slump? And even if a bottleneck exists, how would using a FFI remedy crucial problems in the language, like the absence of unsigned types or that all types are boxed. The types will have to be unboxed anyway, so whether that…

You're right that the FFI can create significant friction, but once you're in C-land, you get C-level performance. So you need to move whole algorithms into C. In a O(n²) algorithm, the O(n) FFI friction will be negligible for a large enough value of n. like the absence of unsigned types or that all types are boxed FFIs often provide access to C arrays.

That's the sad part of all these performance things. I lose several dozen places in an algorithm competition due to using python. Why ? The N=100 cases didn't finish before the competition bot killed it (2seconds I believe).

My algorithm was involved, but it was O(N), which took a lot of effort. The winning C++ program had O(N^2) algorithms. It finished in less than 0.02 seconds.

Re: Why is C faster than Java: git vs JGit

#83

Post by njs12345 »

gwern wrote: post #62
njs12345 wrote: post #7

I find it kind of interesting that in Haskell, which is arguably even higher level than Java, most of these optimisations are eminently possible.. EDIT: This obviously came across a bit as language fanboyism, so I guess I should mention that the language features that let you do many of them let you shoot yourself in the foot just as easily as you can in C, and you can certainly argue that with a strong FFI you might…

That may be, but what good is it if no one uses it? Hadn't heard that http://hackage.haskell.org/package/git-object or http://hackage.haskell.org/package/ght or http://hackage.haskell.org/package/hit or gat http://evan-tech.livejournal.com/254793.html were especially fast.

No one uses Haskell, or no one uses those optimisations?

Haskell has plenty of industrial users and quite a few very large programs as well. Those libraries hardly look mature - I know that many of the container libraries on Haskell make extensive use of unpacking, for instance.

Here is a good set of slides on Haskell and optimisation: http://www.slideshare.net/tibbe/highperformance-haskell

Re: Why is C faster than Java: git vs JGit

#84

Post by dkarl »

ced wrote: post #34
kmm wrote: post #28

Earlier quoted context omitted.

I've heard the argument before that in need, one can use a FFI to optimize bottlenecks in high-level code, but I've never understood. Won't using a high-level language incur an omnipresent speed slump? And even if a bottleneck exists, how would using a FFI remedy crucial problems in the language, like the absence of unsigned types or that all types are boxed. The types will have to be unboxed anyway, so whether that…

You're right that the FFI can create significant friction, but once you're in C-land, you get C-level performance. So you need to move whole algorithms into C. In a O(n²) algorithm, the O(n) FFI friction will be negligible for a large enough value of n. like the absence of unsigned types or that all types are boxed FFIs often provide access to C arrays.

It isn't always that straightforward. With Java, if you move your code into C you may also need to keep all of your data in C-land to avoid the overhead of copying it back and forth. Then the data is harder to access from Java, plus you can't rely on garbage collection to free that memory when you're done with it.

Re: Why is C faster than Java: git vs JGit

#85

Post by dkarl »

gwern wrote: post #62
njs12345 wrote: post #7

I find it kind of interesting that in Haskell, which is arguably even higher level than Java, most of these optimisations are eminently possible.. EDIT: This obviously came across a bit as language fanboyism, so I guess I should mention that the language features that let you do many of them let you shoot yourself in the foot just as easily as you can in C, and you can certainly argue that with a strong FFI you might…

That may be, but what good is it if no one uses it? Hadn't heard that http://hackage.haskell.org/package/git-object or http://hackage.haskell.org/package/ght or http://hackage.haskell.org/package/hit or gat http://evan-tech.livejournal.com/254793.html were especially fast.

It seems that for almost any popular piece of C or C++ software there are people who are motivated to produce a pure Java implementation. For whatever reason, you don't see that motivation in other language communities. Outside of Java-land, most feature-for-feature copies of existing software seem to be undertaken for the sake of learning or linguistic patriotism, which are not sufficient drivers to sustain such a project to completion.

My guess is that this phenomenon reflects the fact that other language communities have greater comfort and facility with C libraries, or to look at it another way, the fact that complete independence from native libraries is actually a feasible goal for most Java projects.

Re: Why is C faster than Java: git vs JGit

#86

Post by rogerbinns »

oconnor0 wrote: post #79
erichocean wrote: post #71

Earlier quoted context omitted.

Although Sqlite is highly optimized, it's got what amounts to its own VM internally, and doesn't really use C to the fullest. It's not surprising to me that the C# version of that VM does as well (or better) for this particular codebase.

Can you explain more what you mean about SQLite having roughly its own VM?

There are also details and examples at http://www.sqlite.org/vdbe.html

Things have changed a bit since then, but not much. SQLite's API is very different than regular databases because it is a library operating in the same process. In particular it does not calculate all result rows for a query up front (that wouldn't be very 'Lite') but instead calculates the next matching row as you ask for it.

Consequently the internals have to be able to record their state, return a row, and then resume from that state to get the next matching row. There is a also a fair amount of query optimisation that goes on, which again means the need for expressing queries in a variety of different building blocks. Combine the state machine with building blocks and you have a special purpose VM.

Re: Why is C faster than Java: git vs JGit

#87

Post by Stormbringer »

jaylevitt wrote: post #41
snprbob86 wrote: post #4

I almost skipped this link; I assumed it was typical borring blog noise. It's not. This is an insightful post from the git mailing list which shows some of the real limitations that a top tier developer hits when trying to write Java code as fast as neatly optimized C code. Definitely worth reading.

Yep. The usual "Program X is faster in C than Java" gets a barrage of "That's because you know C better". Shawn is a performance-obsessed Java expert, Eclipse committer and longtime Google coder who works on JGit. If he says Java is slower than C at this, then Java is slower than C at this. EDIT: but as wcoenen points out, this was written in 2009 and Java 1.7 does a better job with some of this.

He's an expert you say? That was certainly not my expectation from the article.

(1) Blind faith in Generics.

This alone screams newb to me. He says that he got better performance with a custom data structure (no shit sherlock) but then seems deeply surprised by this. Duh. Okay, well, obviously he's relatively new to Java, but hey, he could still be a performance expert.

(2) Never mentions the biggest weapon in the C vs Java arsenal. The thing is that C is only able to make optimisations up to a certain point, but there are optimisations that can only be made at run time not at compile time. So Java starts off behind, but can catch up some or even all of that distance.

People have used this to demonstrate Java code running faster than C code, but that is old news, a newb might not know this.

(3) Does not mention the second biggest weapon in Java's arsenal in the Java vs C speed argument. That being that more recent versions of garbage collection allow for super fast memory allocation - enormously much faster than what you get with malloc.

(4) Never quantifies how much slower Java is. If Java is 5 or 10% slower, then Meh, is that really news? If Java is 2x slower than carefully hand-tuned C by guys with actual code writing credentials like Linus, then that is still pretty good. 2x screamingly fast is still more than good enough for most people. If the difference is an order of magnitude, then that is not so good. If the difference is two orders of magnitude, then you might as well be using some scripting language.

A proper expert would certainly have quantified the speed difference.

Re: Why is C faster than Java: git vs JGit

#88

Post by elehack »

killedbydeath wrote: post #61
SeanLuke wrote: post #43

I build fairly high-performance Java code. And get hit with three major gotchas which prevent it from approaching C code. - There's no way to do array access without null pointer and index checks each and every time. - Generics with basic types, and their unfortunate embedding into syntax (like the new for() syntax), are awful. Boxing and unboxing incur a ludicrously high penalty, and generics push coders away from u…

I would also add inability to create objects in stack, if you are doing anything recursive. The overhead of heap object creation is pretty visible. So I had to either reuse objects and essentially create my own memory management layer or try to stick data into primitive types which obfuscated code logic quite a bit.

Java 7 uses escape analysis to do stack allocation by default. So, if you play along and write code for which the escape analyzer can activate stack allocation (I don't know what the rules are for this), you can get those benefits.

Re: Why is C faster than Java: git vs JGit

#89

Post by adpowers »

axlelonghorn wrote: post #46
wh-uws wrote: post #42

Earlier quoted context omitted.

Can you elaborate on the storage abstraction and the repository setup? Just curious about what advantages there are to make you sacrifice the performance of the cgit binaries. Mostly out of ignorance on the subject.

There was a google talk on this posted to HN recently, but I can't find it. In it, one of the directors of the build / testing / code review system at google was talking about how they get things working at scale. Since everyone works out of the HEAD of one Perforce repo, they end up using the map-reduce infrastructure to perform tests in the cloud for each checkout. In line with this, there are too many files, that…

That sounds like some of the posts on this blog: http://google-engtools.blogspot.com/

Also, related to source control but not Git, a few years ago Google had a tech talk about writing a Mercurial storage system on top of BigTable: http://www.google.com/events/io/2009/sessions/MercurialBigTa...

Re: Why is C faster than Java: git vs JGit

#90

Post by buff-a »

More specifically, the problem of trying to write a binary compatible java implementation of a neatly optimized solution written in C. So, the program in question is executed, reads a whole bunch of binary data from a whole bunch of different files, does some calculations on that data and then exits.

The questions are, if you had to develop a distributed version control system in java: a) would you solve it the same way, b) would your solution be faster or slower, and c) would it take more or less time to write it and be easier to maintain?

Clearly you would not solve it the same way, for example it might stick around in memory as you worked. Could it then appear faster, from a user's perspective? Possibly. Might it be easier to maintain. Also possible.

Pretty much by definition, if you are writing it in C, a binary compatible solution is not going to run as fast if you port it to java.

I don't think that is a conclusion that has much value.

Post reply on HN