Why git is so fast (or why Java is not as fast as C)

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

by ssp • 17 years ago

139 107 17 years ago

mhansen• 17 years ago

Good article, but it seems to ignore the elephant in the room: the JVM's cold start times.

For me, git's use case is being called from the command line, often interactively, between code editing sessions. It needs to start fast and finish fast, to not interrupt my workflow.

The JVM's cold start times are huge. On the order of a second. Noticeably slow. So slow, that in the common case of committing a few files, the JVM startup time would totally dwarf the time spent actually doing work.

strlen• 17 years ago

The point of JGit was to provide a Git plugin for Eclipse. In this case the start-time is "outsourced" to Eclipse.

Seems like there are many other potential uses for this: other Java IDEs, web applications, integration into Java SCM tools - places where Git would be very useful and start-time can be neglected.

jorgeortiz85• 17 years ago

JGit isn't meant to be a replacement for git on the command-line. It's meant to be used inside IDEs and web servers that 1) are already running on a JVM, 2) need to interact with git, and 3) don't want to pay JNI costs. JVM start-up times are a non-issue for these use cases.

DarkShikari3• 17 years ago

Is the cost of JNI really that high? I'm curious--I haven't used it myself, but a client of mine is using it in a very latency-sensitive Java applet that uses JNI to call libavcodec to decode a video stream and then immediately display it through Java's own native libraries, so I would think the cost isn't that high.

10ren• 17 years ago

Run the java app as a server.

I did this with javac, and went from 5000ms (ant) to 200ms (averages). It gets faster each time it runs, enormous speedup after the first run; but still very significant for the next 10; and continuing at a slower rate from then on.

The client needs to be non-java, to avoid the startup cost there. I run it as a console, so that is the "client" (wrapped in rlwrap, for filename completion/editing etc). My workflow is to compile in a separate shell; that's why I did it this way.

berntb3• 17 years ago

Disclaimer: I'm very much not a Java/C# guy, so this might be totally barking up the wrong tree. :-)

Would it be a speed win to keep some JVM processes "half-started" if load and memory use allowed? The next started Java app will use one of the already half started JVMs.

You wouldn't need to do anything fancy to keep the JVMs around; if a half-started JVM wasn't used for so many seconds that it might be swapped out, you half-start another JVM and throw away the timed out one.

(Hmm.. I don't remember, but another process could take over stdin/-out/-err? Or you could just limit this to non-console applications.)

How much of the work time is in initializing the JVM and how much is specific for initializing the application? Could the JVM data structures (JIT etc) for an app be cached between runs?

Edit: Made a little clearer. Moved disclaimer to the top, so people know they can stop reading if I'm in the wrong forest..

Edit 2: I probably have read and unconsciously copied a similar idea that some Perl guy implemented?

pronoiac• 17 years ago

Apache in pre-forking mode might have inspired you. High availability Java might be relevant.

jwinter2• 17 years ago

Check out nailgun if you're interested in using the JVM as a command-line tool without a cold-start.

http://martiansoftware.com/nailgun/index.html

dschobel2• 17 years ago

I was looking at this the other day and am concerned that it hasn't been updated since February, 2005. That's practically ancient in terms of software.

DarkShikari3• 17 years ago

This has always been true and will continue to be true.

It's possible to build a high level language that's as fast as C? Sure--but only if you restrict the programmer to the same amount of effort in both languages. If your application is one where it's worthwhile applying a great deal of extra programmer time in order to improve performance, a low level language will always win because it exposes more of the native machine.

The goal of a high-performance high-level language should be to provide C-like performance for a reasonably unoptimized application. Once one starts to optimize a program down to the last instruction, staying on par with a low level language becomes simply impossible for a high level language.

In my experience, every level of abstraction one creates away from the machine limits your performance by some amount. This can be demonstrated without even leaving assembly language!

Fastest possible: raw assembly code in a NASM-like assembler. With this, you can write basically any code possible with no limitations, at the cost of extremely high programmer time costs.

Shortcut: Use inline assembler instead of NASM to simplify calling convention and other niceties.

Cost: There's now a whole bunch of stuff, like calling convention optimization and computed jumps, which you can no longer do.

Shortcut: Use compiler intrinsics instead of raw assembly.

Cost: You can no longer tweak your algorithm to minimize register spills because you aren't directly controlling spills anymore.

Shortcut: Use a set of macros (like my project does) for handling calling convention, MMX/SSE abstraction, and other such simplifications.

Cost: You tend to overlook optimizations that apply to one possible output of the abstraction and not others, resulting in either messes of ifdefs or suboptimal code--the former of which is of course violating the abstraction.

Shortcut: Use a framework like liboil to write SIMD assembly instead of native code.

Cost: By using generic SIMD operators, you lose access to specialized architecture-specific operations, along with the aforementioned issue of register spills.

Here we haven't even gotten beyond assembler and we're already losing performance. Now scale this up to C and beyond: abstraction inherently comes at a performance cost. It isn't even merely a function of language: abstractions within a language reduce performance as well.

Locke16892• 17 years ago

Couldn't agree more. One thing to remember though: "Premature optimization is the root of all evil." C Git is optimized and fast. Mercurial, with a combination of Python and C, is almost as fast. Maybe not quite as fast, but fast enough for me. A lot of the time those optimizations just don't pay off in terms of programmer time.

DarkShikari3• 17 years ago

Slightly tangential, but I think "Premature optimization is the root of all evil." is the most misquoted statement in the history of computer science. Most importantly, people tend to misinterpret "premature" to mean "any time before the software is done" or similar.

I can't even count the number of times where I've worked on or watched a project where performance is important and the following series of events occurs:

1. Module is designed with that quote in mind: it must be simple to implement and performance is unimportant. Note that this isn't a prototype: this is a plan for the actual final product.

2. Module is built and finished, then submitted for a review. The reviewers, knowing the importance of performance for this module, point out a number of ways that the module is extremely suboptimal.

3. Because of the assumptions so heavily ingrained into the module, implementing these performance improvements--which could have been foreseen as necessary far earlier--requires a near-complete rewrite of a large part of the module.

It's exactly as if we finished our software and our customer decided that his requirements were actually totally different--except in this situation, it's entirely our fault, because performance was a requirement and we ignored it because we didn't want to optimize "prematurely". If you want performance, you have to design with performance in mind; if you don't, and then decide later you want performance, the cost of your earlier decision is magnified a hundredfold.

I have almost never seen that quote used correctly.

rikthevik• 17 years ago

...Maybe not quite as fast, but fast enough for me...

Given how fast computers are these days, the powerful standard libraries high level languages give you and the fact that bugs per line is constant regardless of language - high level languages start to look pretty good. Programs don't need to be fast as possible, they just need to be fast enough.

rdtsc• 17 years ago

Another thing to keep in mind before optimizing is the 80/20 rule. Usually only a small part of the program (20%) needs optimizing.

Of course one needs actual performance numbers (via profiling for example) before knowing what to optimize. There is nothing worse than faith-based performance assumptions. I have seen months being wasted re-writing code in a lower level language to "make things faster" only to find out that it didn't make a difference, the code was disk or network bound and not CPU bound.

barrkel7• 17 years ago

Of course, managed languages can buy you other things, such as inlining indirect method calls by rewriting the call site (polymorphic inline caching), dynamic profile-guided optimization, not to mention the fact that garbage collection is often faster than manual deallocation, depending on the nature of the problem and the pattern of allocations. (Of course, design of managed applications can benefit greatly from awareness of how the GC works).

WRT SIMD operators, I'll point you to Mono.Simd.

blasdel2• 17 years ago

I found that I had to read your comment carefully to realize that I agreed with you, because I'd already flipped the bozo bit 3 words in when you unnecessarily used parochial microsoft nomenclature.

vii• 17 years ago

This completely misses the point. The reason JGit cannot compete with Git is not that it is using an extra cycle or two to make function calls. The problem is that Java cripples you in the sort of data-representations you can use -- no mmap, no value types -- forcing lots of extra copying. There's no reason a language can't provide these features, and I don't know that they require significant extra programmer effort. C# does it, etc.

barrkel7• 17 years ago

I find it interesting to read that every single one of his criticisms of JGit would not need to apply to a C# implementation. Unsigned types, unmanaged memory allocation (Marshal.Alloc), unsafe code with pointers, native P/Invoke access, value types (e.g. fixed arrays for his SHA-1 point), and an IDisposable convention for managing all the unmanaged trickery, C# has pretty much all the needed features.

When optimizing C# for space use in particular (which ends up being a time optimization for I/O heavy loads), I've leaned heavily on arrays of structs, and even bit-packed arrays (e.g. an Int32 array storing 14-bit integers, packed so that they don't align on index boundaries).

Programming at the level of C in C# loses most of the benefits, of course, but at least you can hide the optimizations behind pretty APIs, and write the non-critical parts in terms of an easier to work with lower layer.

j_baker2• 17 years ago

I actually believe they're accessible in Java as well through JNI and JNA. But I'm hardly a Java expert.

barrkel7• 17 years ago

Not at the same level of abstraction, IMO. To take a representative example, pointer arithmetic simply isn't really available to you from Java, unless you pretend your integers are pointers and go through JNI functions for indirection, etc., which is going to be slow enough to defeat the purpose.

thibaut_barrere• 17 years ago

From the last line:

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

Rings the 'good enough' bell to me.

axod9• 17 years ago

Agree. If your bottleneck is your source control tool, you're doing something wrong.

DougBTX2• 17 years ago

Discussing bottlenecks oversimplifies, it assumes everything goes down one pipeline. Small changes can make big differences. If your tool feels a little bit snappier, you might make two commits instead of one, then six months down the line someone saves half an hour tracking down a bug because the blame messages are more relevant.

JulianMorrison3• 17 years ago

Speed changes your workflow. With slow or fussy source control, you're more likely to do "branches" by just not checking in your changes for awhile. With near-instant source control, you don't feel burdened by making a feature branch, switching, editing and committing a few times, and merging back.

Deestan• 17 years ago

Anything that is part of the programming routine should be severely optimized.

Every little bit not only adds up, it often multiplies in big enough projects.

In one of our big products, we have several build steps that touch upon the source control systems. 10 second VCS delay X 6 build steps, 1 second lazily written c++-header slowdown X 300 files, etc. and before you know it something that should take 10-15 minutes for a clean build now takes ~1 hour. True story. :(

Luckily, enough of us got so annoyed about this that it got fixed after a few weeks of dedicated effort. We now have a constant conscious effort to keep build times down.

kelnos• 17 years ago

I'm actually a bit curious as to why they're using JGit as a git server. Is there something lacking in git-daemon, etc.?

adw• 17 years ago

Most likely they can drop it into their existing systems for deploying Java apps.

emerose• 17 years ago

They use it in Gerrit — http://code.google.com/p/gerrit/ — which is an open-source code review system built to mimic Google Mondrian, but which uses Git rather than Perforce. Shawn Pearce, the author of the linked email, is also the primary maintainer of Gerrit.

-sq

axod9• 17 years ago

>> "why Java is not as fast as C"

Not actually true in reality. Modern JVMs can make on the fly optimizations based on the runtime profile, which would need to be done by hand in C.

As said elsewhere though, Java excels when used for long running tasks - servers - backends etc where it can optimize for the long term. It doesn't excel when you try and start up the jvm loads of times for quick individual jobs.

I don't understand why people are optimizing source control :/ fast vs fast meh I don't think it's an issue really.

fauigerzigerk4• 17 years ago

The post specifically mentiones Java's implementation of memory mapped files, Java's lack of value types and Java's lack of unsigned types. These are very different areas but none of them can be solved by on the fly optimizations or longer running processes.

riffraff• 17 years ago

wrt value types, shouldn't it be partially solved by escape analisys? Cfr: http://weblogs.java.net/blog/forax/archive/2009/10/06/jdk7-d...

not that it would matter much in the case anyway, I guess.

richardw3• 17 years ago

'Modern JVMs can make on the fly optimizations based on the runtime profile'

That's something I've heard ever since hotspot came out, but it's not a silver bullet to beating C/C++ etc. Here are some server tests. Some are comparable, some are definitely not: http://shootout.alioth.debian.org/u64q/java.php

jbellis• 17 years ago

"Sometimes no-warmup is important (see comments above about pacemakers), but more often a short warmup period is irrelevant to the overall application. If I'm using an IDE, I expect a largish loading period... but then I'm using the IDE all day. I don't use an IDE for 0.1 sec. If warmup is NOT important to the application, then allow the JVM a warmup period before comparing performance numbers. Many of the benchmarks in the language shootout at http://shootout.alioth.debian.org fall into this camp: too short to measure something interesting. Nearly all complete in 1 minute or less." http://blogs.azulsystems.com/cliff/2009/09/java-vs-c-perform...

fauigerzigerk4• 17 years ago

What you link to are tests using the server VM but without warmup. You need to select "Java 6 steady-state" to get the warmup.

[Edit] Actually the state-state one averages over multiples restarts including JITed and non-JITed runs.

jerf• 17 years ago

You're bringing theory to a shootout based on facts. Hypothesizing that Java might be faster with a strong enough headwind doesn't make the actual, factual JGit run faster or C-git run slower.

I mention this because programmers seem prone to this, and letting theory trump fact is a great way to make sure that you never learn anything.

zootm• 17 years ago

It's a pretty specific shootout, of course; the reasons brought up for JGit's relative slowness are not issues present in most applications, they're specific to certain realms of system. Unsigned number support is a major headache about Java when doing low-level work, in particular.

I think it's also important to note that the slowness is relative to an incredibly fast C implementation - taking twice the time sounds painful, but in reality the pauses caused by Git are barely perceptible as-is, and double of that is not likely to be very annoying.

axod9• 17 years ago

I was countering the headline, which wasn't correct. Java isn't slower than C in general. It may be in specific cases, for specific programmers, etc but that's not what the headline stated.

The title takes one specific application in a particular niche, used in a certain way which a particular programmer can't get to run fast enough, and concludes that Java isn't fast enough. Faulty logic.

The argument about JGit vs C-git for me isn't something I feel you can learn anything from.

richardw3• 17 years ago

While I'd never claim Java is comparable to C, I'd like to note that the C codebase has, by their admission, 4 years of work in it. I'd be surprised if the JGit codebase isn't much faster in 3/4 years.

bad_user2• 17 years ago

The Git codebase has been heavily-optimized from the start. Its speed when branching/merging was its main selling point, ever since Linus started talking about it.

The only way JGit would ever be equal-to or faster than Git is by using better algorithms. And somehow, I don't see this happening ;)

richardw3• 17 years ago

Nobody's claiming equal-to or faster - currently JGit is twice as slow so there's a lot of room for improvement. Faster than now, not faster than C.

fauigerzigerk4• 17 years ago

Of the three issues mentioned in the post Java's lack of value types is the important one in my view. That's what causes Java programs to use hugely more memory than C, C++, C# or Go programs. Using more memory translates into an orders of magnitude drop in performance for memory intensive applications.

bad_user2• 17 years ago

Not only memory, but there's also a performance penalty related to boxing/unboxing of primitives. That's why the author of that email described how he hasn't used the standard data-structures from Java, like HashMap ... preferring to write his own specialized implementation.

jrockway2• 17 years ago

They use the word "high-level languages" and then use Java as the example. This is going to lead to some very wrong conclusions; the problems listed in the article are problems with Java, not problems with high-level languages.

I imagine a Git-in-Haskell would be very close in performance to the C git. (Then why is Darcs so slow? Because it uses an icky imperative, mutable model, whereas git uses a immutable functional model.)

j_baker2• 17 years ago

In strictly language terms, C will always be faster than Java. However, I would dispute that one could say on a general basis that C programs will always be faster than Java programs.

In fact, I would argue that all things being equal, the Java program is more likely to be faster (and yes, I realize there are a metric ton of potential caveats to what I just said). Why? Because Java allows you to focus on the "big picture" optimizations that really make all the difference.

On the other hand, given an infinite amount of development time and experienced developers, the C program will likely be much faster. In some cases this is necessary. But for most cases, I personally would rather just ship something than try to squeeze every ounce of efficiency out of it.

houseabsolute• 17 years ago

One thing I have been wondering as a non-git user: is git really CPU-bound in most operations? Maybe someone who is a regular git user can answer me this question. If it's not, I wouldn't expect Java to matter too much to its performance.

ErrantX• 17 years ago

Im not wholly convinced that version control is an area where microsecond speed advantages matter. Rather versatility, portability and compatibility :)

Why git is so fast (or why Java is not as fast as C)

Related Stories