Why is C faster than Java: git vs JGit

http://marc.info/?l=git&m=124111702609723&w=2

by acqq • 15 years ago

325 102 15 years ago

marc.info

willvarfar• 15 years ago

So why do they write and use jgit at google instead of just git?

unwind• 15 years ago

From the project page:

The original goal of JGit/EGit was to provide an Eclipse plugin for working with software using the Git SCM. The Eclipse plugin is still the main goal of many of the developers, but we are open to anyone wanting to interface with other tools, Netbeans, Ant, Maven etc. For those, the JGit part provides a high performance API for working with Git repositories. The main other user of JGit, besides EGit, is Gerrit Code Review, which used by projects such as JGit (ofcourse), EGit (by implication) and Android.

Not sure if that provides a very good motivation, but there you go. :)

masklinn• 15 years ago

It's a java library, making it much easier to use from java code than a command-line utility and all the ensuing parsing and munging of string data (which is not java's forte either)

aurelianito• 15 years ago

As they wrote at the end of the article:

"But, JGit performs reasonably well; well enough that we use internally at Google as a git server."

He is not advocating to never use Java. He is just pointing out some things that may or may not be important when choosing a language to write a program.

tommorris• 15 years ago

There is a few things that require jgit: a while back, I found a really nice library (I'd look it up, but am on 3G on a train) that let you use Amazon S3 as a git remote. The author had just written some bridge code between jgit and an AWS library. Works suprisingly well, you just have to remember to use `jgit push` rather than `git push`.

durin42• 15 years ago

Because cgit is a bunch of binaries that expect to call each other. That makes it harder to abstract out the storage layer, and we don't use vanilla repositories sitting on a filesystem. Things are backed by some other storage abstraction, which isn't always very posix-filesystem like.

wh-uws• 15 years ago

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.

obtu• 15 years ago

Didn't you turn to Dulwich rather than JGit for storage abstraction?

Yrlec2• 15 years ago

I had a similar experience when I was doing some Galois Field arithmetic in Java. You pay a huge penalty because of the absence of unsigned types. In our case we had to use long instead of int, which is extra costly, since many basic operations in Java return int by default.

adobriyan• 15 years ago

Why does signedness matter?

Addition is XOR which is sign-agnostic. Multiplication has to be done via table lookups to be fast which also makes it sign agnostic.

Well, at least for p=2.

Yrlec2• 15 years ago

I was doing it in GF(2^32-5). Your statement is true for GF(2^n) where n is small enough to keep the entire multiplication-table in memory (usually n <= 8). When it's bigger you keep log-tables in memory then sign matters. However when n=16 you get lucky and can use char as an unsigned 16 bit int.

snprbob86• 15 years ago

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.

nickik• 15 years ago

Same here. Nothing groundbreaing about Java vs C threw.

Edit: I mean most of the problems (maybe features) of java are known.

kokey• 15 years ago

Actually, it also makes me want to get into another project in C again.

jgw• 15 years ago

So this.

It's truly liberating to get back to C after having programmed in something higher level for a long time. It actually makes me appreciate C more. I mean, at first, I shoot myself in the foot, elbow and groin with alarming regularity, but it's nice to actually have access to the bullets. :) [EDIT: dodgy grammar]

jaylevitt• 15 years ago

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.

huherto• 15 years ago

> "If he says Java is slower than C at this, then Java is slower than C at this."

Yes. I like how you qualify the statement. Furthermore, on the C side you have Linus and other C gurus that really, really know how to exploit the strengths of the C language.

Stormbringer• 15 years ago

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.

pconf• 15 years ago

I wonder why none of these benchmarks measure the performance of _optimized_ Java? All of our builds use Proguard optimization and some of the resulting bytecode is noticeably faster.

njs123454• 15 years ago

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 as well just call into C if you really need that kind of low level performance..

kmm• 15 years ago

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 happens in foreign code or in the interpreter/JIT code won't matter.

ced• 15 years ago

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.

njs123454• 15 years ago

> Won't using a high-level language incur an omnipresent speed slump?

Yes, but most programs don't require high performance everywhere - in a library like JGit for instance, most operations are probably plenty fast written in Java even for very large projects; it's likely only a few are problematic.

> 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.

That's maybe an argument to allow more control over memory layout and machine representation in high level languages - although there are ways around this, like defining your data types as a C++ class and then providing a high level binding.

dons• 15 years ago

At least in Haskell you have unboxed primitive types, memory mapped IO, bump-pointer allocation, and compilation to direct loops that are often identical to what GCC produces (or very close).

akg• 15 years ago

> Won't using a high-level language incur an omnipresent speed slump?

Not sure that is true. Just look at pypy(http://pypy.org/) which claims that run-time optimizations in the interpreted interpreter outperforms the C interpreter, and quite significantly in many cases. So I don't think it's true that high-level languages are always slower. It has a lot to do with the optimizations you can do at run-time. There is also an interesting paper on developing an OS based on run-time code synthesis for optimizing performance (http://valerieaurora.org/synthesis/SynthesisOS/). The major drawback of languages like C is that it can only optimize things at compile-time. I think as projects get larger and we move towards parallel structures and algorithms the need for languages that support run-time optimizations will be greeter.

gwern• 15 years ago

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.

njs123454• 15 years ago

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

dkarl2• 15 years ago

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.

bajsejohannes• 15 years ago

> when you do use Java NIO MappedByteBuffer, we still have to copy to a temporary byte[] in order to do any real processing

Does anyone know why this is the case?

shin_lao• 15 years ago

mmap uses the virtual memory manager to map a file into virtual memory as it does for swapping.

The memory you have is therefore allocated by the kernel of your operating system and oblivious to any garbage collector you might have.

nvarsj2• 15 years ago

Well, with a MappedByteBuffer (or any DirectByteBuffer), if you want to manipulate the data as a Java type (e.g. byte[]) you have to copy the data into the heap. byte[] cannot exist outside of the heap.

Still, I wonder why they're using a MappedByteBuffer in the first place if they're working with the data in the Java heap.

alpb2• 15 years ago

I wonder where do Shawn work at Google and in which product they use jgit.

airlineuser• 15 years ago

http://code.google.com/p/gerrit/

(a code review tool used by Android.)

zxypoo2• 15 years ago

You look at this presentation which talks about JGit at Google, if you skip the first few slides...

https://docs.google.com/present/edit?id=0ATM14GNiXaXfZGZkeHp...

alpb2• 15 years ago

I don't have access to this doc somehow.

verroq2• 15 years ago

Page is down?

rsneekes• 15 years ago

http://viewtext.org/article?url=http%3A%2F%2Fmarc.info%2F%3F...

verroq2• 15 years ago

Appreciate it.

screwt• 15 years ago

My soln to "HN-linked page is down" is just to search cache:<link> from Google. Works fine 95% of the time.

cookiecaper• 15 years ago

Note the date: 2009-04-30 18:43:19

Many of us have already read this and it's been submitted to HN several times before. This, of course, does not mean that it's not worth reposting, but interested parties may want to dig up some of the past discussions.

njs123454• 15 years ago

Here's one: http://news.ycombinator.com/item?id=1026909

nknight• 15 years ago

In cases where performance actually matters, just avoid bit-twiddle in high-level languages. It sucks too much. You'll probably waste less time on optimizations by offloading the biggest bottlenecks to C/C++ with the native/extension interfaces in your high-level language of choice.

Be careful and stay standards-compliant and you can keep most of the portability and maintenance advantages while picking up some significant speed.

mbell• 15 years ago

>You'll probably waste less time on optimizations by offloading the biggest bottlenecks to C/C++ with the native/extension interfaces in your high-level language of choice.

In reality this often requires a heavy refactor to actually work. In Java with JNI for instance the overhead of calling native methods is actually rather high, over 200 cpu cycles in many cases. The stack often has to be re-arranged, a CPU stall is usually caused and in the case of most data types passed to the native function, they have to be copied (last i knew java.nio buffers were the only types that weren't copied).

Point is, just moving your "hot function" to C / C++ and calling with JNI doesn't work unless that function is rarely called and does a lot of work internally. More often the "hot function" is something that is called thousands of times and moving something like that to JNI is just as likely to kill performance as help it. You'd have to abstract away an entire module of work and minimize its call surface to JNI to achieve your goal.

ot3• 15 years ago

All the points are valid but they are peculiar to Java, not to all managed high-level languages. C#/.NET, for example, have unsigned types, value-type arrays and structs, memory mapped files and specialized collections.

As an example, the C# port of Sqlite is sometimes faster than the C version on queries, although updates are slower, despite Sqlite is a highly optimized C library.

EDIT: link http://code.google.com/p/csharp-sqlite/wiki/Benchmarks

kevingadd• 15 years ago

It's also worth pointing out that the C# port of SQlite omits using certain C mechanisms (like pointers) in favor of passing copies of byte arrays around. You'd expect this to make it slower, but in many cases, it doesn't! (C# supports pointers, but the port doesn't use them so that it'll work in limited environments like Silverlight)

gaius• 15 years ago

The .NET runtime is well optimized for that sort of thing, as it needed to be for F#.

alexchamberlain• 15 years ago

This is slightly off topic, but a good read... http://cpp-next.com/archive/2009/08/want-speed-pass-by-value...

zokier• 15 years ago

Slightly offtopic, but I wonder how much overhead in those benchmarks comes from calling native code from .NET runtime? An interesting data point could be benchmarking equivalent implementation in C or C++, avoiding the overhead of native-managed transition.

ot3• 15 years ago

In my experience, interfacing native code via C++/CLI has negligible overhead, unless arguments are big and complex data types, which have to be converted to .NET types.

Otherwise, unsafe regions have practically zero overhead, and they are close enough to the metal.

mdeicaza• 15 years ago

Additionally, C# collections do not need to box.

List<int> uses an actual array of integers as its backing store instead of an array of objects that contain boxed copies of the integers.

There is a port of JGit to .NET called NGit, which is what we use for MonoDevelop.

The port is maintained with an automatic tool that converts Java code to C# code, you can find it here:

https://github.com/slluis/ngit

ot3• 15 years ago

> List<int> uses an actual array of integers as its backing store instead of an array of objects that contain boxed copies of the integers.

Yes, that's what I meant with specialized collections :)

BTW, I didn't know about the awesome NGit, automatic conversion from Java is really impressive!

stcredzero• 15 years ago

I heard about related stuff happening while I was working at a Smalltalk vendor. The programmer who was implementing the network cryptography library would just call up the VM engineer and ask for goodies like support for large bit arrays, and he'd get them in for the next VM release. The programmer was able to beat some of RSA data security's (poorly implemented) reference DLL's written in C by 3% with a Smalltalk program.

In the Smalltalk environments, it's easy to implement "primitives" coded in C, just in case you weren't internal to the vendor. With open VMs like Squeak, you can add your own bytecode to support optimizations if you want to.

erichocean3• 15 years ago

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.

oconnor02• 15 years ago

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

wcoenen• 15 years ago

This was posted in 2009. I think that some of the arguments are no longer valid, e.g. Java 1.7 now uses escape analysis to eliminate heap allocations where possible: http://weblogs.java.net/blog/forax/archive/2009/10/06/jdk7-d...

jshen• 15 years ago

"I think that some of the arguments are no longer valid"

Has anyone measured it?

babebridou• 15 years ago

I've had the issue using maps with primitive keys. I solved it by isolating the performance critical functionality and not using the Collections framework there, instead writing my own data structure for it (with heavy influence from the hashmap one).

This tends to be my general philosophy, by the way. Reuse code to get something working fast, isolate what really causes bad performances, then solve only those problems by going under the hood. If the performance issues remain, cheat by pretending it doesn't exist, by making sure we're never in a worst case scenario and handling the worst case scenario differently.

In my "IntHashMap" case, the worst case scenario was gathering the keySet. I made sure that I'd only call it when I really really needed it. The rest was "fast enough" once I had removed the underlying Integer Object on the key.

tomandersen• 15 years ago

Ahh, getting to the metal. Only in C do I get that feeling. For some reason even C++ just fails on that 'fresh metallic taste' test.

Most code should not be C.

m0shen• 15 years ago

Mirror ( Google Cache ) : https://webcache.googleusercontent.com/search?q=cache:marc.i...

SeanLuke3• 15 years ago

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 using arrays. Unlike in C++, generics have been the enemy of performance.

- Poor quality collections classes (ArrayList and HashMap are notoriously bad)

Sure there's a few other things like pointer walking etc. in C, and Java's poor floating point, but the big three above are the killers.

soc88• 15 years ago

> - There's no way to do array access without null pointer and index checks each and every time.

That's not happening anymore for years already.

SeanLuke3• 15 years ago

??? There are easy ways to miscode your way around the optimizations.

jcdavis• 15 years ago

> - There's no way to do array access without null pointer and index checks each and every time.

Actually there is. Have you checked out the sun.misc.Unsafe class? Lots of very dangerous gems in there, among them the ability to calculate array offsets and access the array elements directly. (check out arrayBaseOffset + arrayIndexScale + getObject/getLong/etc)

killedbydeath• 15 years ago

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.

elehack• 15 years ago

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.

CountHackulus• 15 years ago

I'd just like to point out that your complaints are specific to the Oracle JVM (except for the new for() syntax obviously).

Even the collection classes can change between JVM versions. I'm not saying that they're all necessarily better, just that different versions are different. So the Dalvik or IBM J9 versions might do what you want better.

malkia• 15 years ago

I wonder if mercurial gets rewritten in "C" whether there would be any speedup.

dochtman• 15 years ago

I'm sure there would be some speedup, the question is whether it would be worth it (and I suppose that can only be adequately be assessed by the developers, who now have to maintain C code instead of Python).

But for some perspective from a former Mercurial developer: lots of the more performance-sensitive code has already been rewritten in C. Rewriting the rest of it would simply be a question of diminishing returns. One thing that would improve is hg's startup time; starting up Python just takes a while, which kind of sucks for command-line programs like VCS clients that tend to have many short-running invocations.

azakai• 15 years ago

> One thing that would improve is hg's startup time; starting up Python just takes a while

Python starts up very fast for a language runtime (much much faster than Java). But yes, if you run a large amount of extremely short tasks, the startup might become significant I guess.

ExpiredLink• 15 years ago

Amateurs - they should have chosen Fortran http://news.ycombinator.com/item?id=3455883

zxypoo2• 15 years ago

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 use the library. On top of that, you have crazy folks like NGit [2] who cross compile the library using Sharpen so it can be used by the .NET community...

[1] https://docs.google.com/present/edit?id=0ATM14GNiXaXfZGZkeHp... [2] - https://github.com/slluis/ngit

gelliott• 15 years ago

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.

chubot• 15 years ago

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!

cube13• 15 years ago

>So. Yes, its practical to build Git in a higher level language, but you just can't get the same performance, or tight memory utilization, that C Git gets. That's what that higher level language abstraction costs you. But, JGit performs reasonably well; well enough that we use internally at Google as a git server.

I think that this is the key takeaway for the entire post.

One of the reasons I generally dislike any of the "X IS BETTER THAN Y" bakeoffs is that performance is now so implementation dependent that these comparisons are pretty much moot. Given that basically any non-trivial implementation can be improved, it's difficult to say that anything is faster, especially when one considers developer skill.

Developers should not be chasing the abstract, absolute best performance. Instead, the language used should be the one that delivers performance that is good enough for their client's needs. If they can get it with something that we're familiar with, that's great. If they need to learn a new tool, that's also good. But it doesn't make much sense to throw away all the knowledge that a developer has about a certain language to chase "better performance" with a different one. Most likely, the first effort implementations on a new language won't be nearly as good as the implementations on the more familiar language.

It's generally true that optimized Java won't ever be as fast as optimized C. But for the vast majority of cases, it doesn't need to. Java's speed is enough for those cases. And in the small minority where it's not sufficient, C is still around.

rayiner• 15 years ago

A lot of this is poor API design, and the product of Java's baggage as something that needs to have well-defined safety semantics for internet applications. It is not a necessary constraint of high-level languages that they don't offer the ability to get down to the metal. SBCL, for example, offers a lot of mechanisms for unboxed primitive arrays, unsafe declarations, and these days even SSE intrinsics.

erichocean3• 15 years ago

So does Factor: http://factorcode.org

buff-a• 15 years ago

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.

itmag4• 15 years ago

I remember a post on here recently which said that sometimes a high-level language can be faster than C, because you can convey more of your algorithmic intent and thus the compiler can optimize better for you.

It gave an example where the compiler's knowledge that something is an immutable array means better optimization. Which you can't express in C.

Why is C faster than Java: git vs JGit

Related Stories