[4191] in java-interest
Re: Optimized Future Performance of Java (bleak?)
daemon@ATHENA.MIT.EDU (Jeremy Fitzhardinge)
Wed Dec 13 06:04:52 1995
From: "Jeremy Fitzhardinge" <jeremy@suede.sw.oz.au>
Date: Wed, 13 Dec 1995 16:41:43 -0500
In-Reply-To: Kelvin Nilsen <kelvin@kickapoo.catd.iastate.edu>
"Optimized Future Performance of Java (bleak?)" (Dec 12, 12:24pm)
To: Kelvin Nilsen <kelvin@kickapoo.catd.iastate.edu>
Cc: java-porting@java.sun.com, java-interest@java.sun.com
On Dec 12, 12:24pm, Kelvin Nilsen wrote on java-porting:
> Right now, there is so much room for improvement that nobody is pondering
> the future performance barriers that we might face once we begin to
> tune the results of just-in-time compilation.
On the contrary, I've put quite a lot of thought into it, and came to
opposite conclusions to you. However its all speculative for the
moment - there's going to be lots of opportunity for
experimentation...
> By the way, where is the best place to carry out such
> discussion?
Probably java-interest, which is supposed to be for discussion about the
Java language and bytecode. I've sent this reply there, as well as to
java-porting.
> We really haven't seen very much discussion on implementation techniques
> and performance of future Java systems. Sun has claimed that optimized
> Java programs will offer performance that is close to the speed of C.
> I view this as somewhat doubtful, at least on what we currently consider
> to be stock hardware. Here's why:
>
> 1. The design of Java prevents programmers from implementing many of
> optimizations that are quite straightforward in C and C++. Some
> examples include:
>
> a. stack allocation of structures and arrays
I presume you mean that this is something C/C++ has and Java doesn't.
Well, stack allocation is certainly quick and very good for memory
locality, but is it used that much? Certainly you could so some local
analysis to determine whether an object is short lived and can be
allocated on the stack, but as soon as you "leak" a reference to it you
have to put it on the heap anyway. You could do interprocedural
analysis, but that is likely to be too cumbersome to do.
> b. multi-dimensional array indexing (and induction variable
> optimizations)
I think arrays are one area where Java has the potential to do much better
than C/C++, because Java has a much stronger notion of arrays.
> c. the language-defined requirement that all automatic variables
> be assigned an initial default value. (The official Java
> language specification requires that implementations
> initialize all local variables to zero, but the same document
> also states that it is a programmer error to not provide
> explicit initialization before use... It appears that this
> is one aspect of Java that has not yet been totally settled.)
I think you're confusing two issues. Class members have a default
value if not explicitly initialized. Local variables must be
unambigiously assigned to before they are used. Insisting that local
variables are initialized will have no performance hit over any correct
C/C++ program, so I can't see it being a problem. Initializing class
members is not very expensive - no more than a bzero or bcopy at new
time, and which would eliminate a lot of assignments in the constructor
which would be required in C++.
Anyway, I think any hit from this would be marginal.
> Furthermore, the right place for this analysis
> would be in the front-end (Java to Java byte code translator), but
> I do not believe the byte code is "rich" enough to allow object
> representations to be encoded onto the stack. Is it?
Even if it were, the runtime would have to verify it for itself. If a
piece of bytecode said "allocate this object just within the method
scope", then the runtime would have to make sure that there are no
leaks of the instance of the object, because otherwise the integrety
of the virtual machine would be violated (references to unallocated space).
This is a general point. There's lots of traditional optimisations which
javac could do in principle, but there's no way of representing them in
the bytecode. For example, the compiler may prove to its own satisfation
that a particular array index will never exceed its array's bounds. It
could put that into the bytecode in some form (either as a new opcode or
as an attribute of the method), but the runtime couldn't trust it - it
would have to do the proof itself in order to be sure. Perhaps a better
way of looking at it is to have javac suggest that certain indicies are
worth looking at to eliminate bounds checks, and the runtime would only
exert effort on those indicies. If the hint is wrong, no harm is done,
it's just slightly slower code.
> I'm curious
> as to what other language implementors think of Java:
>
> a. do you really expect future Java applications to run as fast as C?
> 30% slower? twice as slow? worse?
There several reasons why Java may be slower than C/C++:
- completely GC heap allocated
This could be resolved with some lifetime analysis and better allocator
technology.
- array bounds checks and null pointer checks
Its possible to eliminate many of these checks from simple analysis.
More complex analysis can remove almost all of them.
- constraints on compilation time
I expect there'll be two major fronts in compiler technology for Java:
- traditional "heavy" compilation which saves native code to disk
- dynamic compilation for methods on demand ("JIT")
Heavy compilation will tend to be used for very commonly executed code
(the standard class library) and compuatationally expensive code. It
will be too slow to run during an interactive session. JIT compilation
will generate poorer code, but compiles at about the same speed as it
takes to interpret once. Once compiled it will be ~10-20 times faster
than a good interpreter. In addition, it can provide runtime feedback
to itself and the "heavy" compiler to generate better code.
Of course, there may not be two separate compilers, but just one with
a continuum of optimisation techniques.
- interface invocation
This will be a slow point compared to C++ - however, since C++ doesn't
provide any language mechanism to do the same thing, its not really
comparable. Type flow analysis and target caching, like the Self
compiler does, would help a lot in bringing the overhead down to
something similar to a direct call.
On the other hand, there's reasons why Java can go faster than C/C++:
- better arrays
- strongly typed memory
Because you can't do any kind of type punning by fooling with
pointers, it makes it much easier to do alias analysis than C.
In C, if you write through a pointer, the compiler has to make
the pessimistic assumption that pretty much anything could have
changed, and therefore kills things it has in register so they
have to be reloaded from memory. Complex alias analysis can
help, but very few commercial C compilers implement it. In
Java, on the other hand, you can use the type system to help
with this and make it much quicker. You can easily tell an
alias - if two pointers are the same, the point to the same
object. There's no need to worry about pointers to overlapping
objects and so on. Similarly, if you write to memory of one
type, you know that only pointers to that type of memory can be
affected. Subclassing complicates this somewhat, but not too
much.
Similarly, because arrays are first class types, and not just a
pointer to a chunk of memory, you can easily tell whether an
array access to one array will potentially alias with elements
in another array - it won't. No overlaps, so an alias only
happens with the same array with the same index.
If you implement normal simple array index calculation strength
reduction and can eliminate bounds checks, then I can't see any
particular reason why Java can't be as good an array processing
language as Fortran - certainly potentially much faster than C.
Also, because Java runtimes must support multithreading, we could be
seeing compilers which generate multithreaded code from linear code.
This would be helped by good array analysis.
- more implementer freedom
- more opportunities for optimisation
Because details like class layouts and so on are up to the implementer,
you ca potentially be really clever about laying them out. You can
look at the code as its running and rearrange things so that the class
is better layed out for cache performance.
So, I don't know how fast Java can be made to run. I'd say, depending on
the actual nature of the program, somewhere between 80-110% the speed of
an equivalent C/C++ program. If a Java runtime managed to parallelize
code which the C compiler couldn't then we'd be seeing n00%, where n
is the number of CPUs it can use.
> b. what techniques would you propose for handling the performance
> bottlenecks mentioned above? how likely is it that these
> techniques will be implemented in commercial products within
> the next year? two years? five years?
I'd say we'll be getting good quality machine code generated from Java
within the next year (good quality = ~gcc -O). If people start using Java
for computationally intensive things, we'll be seeing very high quality
multithreaded MP machine code being generated from Java in 2-3 years.
> 3. Having done quite a bit of research on accurate garbage collection of
> C++, I feel obligated to contribute some insight regarding garbage
> collection performance.
This is all very interesting. Ultimately, noone can say how applicable these
figures are to Java until 1) there's a reasonable amount of Java code to study
and 2) there are comparable implementations. At the moment the best one can
do is try to instrument the Sun runtime and extrapolate.
Regardless, I'll opine without much basis...
> a. do you expect higher rates of heap-memory allocation in Java
> than in C?
Than C yes, but probably about the same as C++. C++ makes using stack memory
harder (though of course that depends on your class libraries, coding style
and so on). There's certainly no need for a Java runtime to be using the
heap for things like stack activation records or local variables.
> b. do you expect dynamic memory management in Java (automatic
> garbage collection) to be more or less efficient than dynamic
> memory management in C++ (programmer controlled, often tuned
> to the needs of individual applications)?
More efficient. It will tend to use more memory than a 100% correct
C++ program. On the other hand, memory leaks are probably one of the
more common bugs (because it is not harmful in the short term), and
most large C/C++ systems have some form of memory leak bug, unless
GC-like tools have been used to track them down. Only bechmarking will
show how GC compares with manual storage management, but my impression
is that a good conservative GC will start winning as soon you're
reduced to using reference counting in your manually managed
allocators.
> a. When Sun tells us that optimized Java runs as fast as C, are
> they planning to employee this "trick"?
I suspect that when Sun say "Java can run as fast as optimised C", they
mean individual loops and small fragments will run as fast - not
necessarily a whole Java program. Who knows how a complete system will
behave? The biggest Java program I know of, Hotjava, certainly has
performance comparable to netscape, even with the interpreted runtime.
Javac, on the other hand, is pretty slow, probably because its more
CPU bound (and IO bound, which isn't going to be helped by a faster
runtime).
I expect that a given Java program will use 50-100% more memory than a C
one with no memory leaks.
> c. Do we really expect Java to provide performance that is competitive
> with C in terms of both memory and time utilization?
> simultaneously?
I think Sun expect so, in good faith. Comments made by members of the
Java team indicate that they expect an improvement in GC technology
which will solve all the existing allocator problems. It's not an
unreasonable expectation, but I wouldn't want to be waiting for it
in the critical path of a project.
> a. Has anyone done any measurements of the impact of tag maintenance
> for "typical" Java applications?
Well, I don't think there is a typical Java application yet. And I doubt
anyone has done the research yet.
> b. Do you expect that future high-performance Java implementations
> will use conservative, accurate, or hybrid garbage collection
> techniques?
Conservative/hybrid. Any non-trivial implementation has to be able to
cope with native code, which may or may not do the "correct things"
with pointers. Its all very well to insist on careful handling of
pointers and declaration of roots within C code explicitly written to
interface with Java code, but I'd prefer not to have to copy data
between "accruate GC" and malloc heaps just so I can pass pointers to a
third-party binary-only library.
For an entirely imbedded implementation I'd expect you could use an
accurate GC with some success. Whether it actually ends up using
less memory than a conservative one is another question.
> c. Do you expect that all future "internet appliances" will require
> "swap space" in order to operate reliably in the presence of memory
> leaks and fragmentation that might be introduced by the use of
> conservative or partially conservative garbage collection
> techniques?
I expect there'd be more leaks from C code interfacing to an accurate
GC than from a conservative one. Boehm repeatedly asserts that leaked
memory from misidentified pointers is very rare in his conservative
allocator, and given the effort it goes to to prevent pointer-like
things from being identified as pointers I can believe it.
In other words, I don't think a conservative GC will contribute much
to the resident set of a Java program - if it needs more memory than
you have, you'll need to swap, regardless of the allocator (to within
10-20%, perhaps).
> Don't get me wrong. I am a believer in Java, and I would like to see it
> succeed. I also recognize that it is often very appropriate to trade some
> performance for improved programmer productivity and software quality.
> Nevertheless, I think it's important to recognize where we stand, and where
> we need to go. And now is the time to begin mapping out the intended course.
These are very good questions, particularly because they are mostly
unanswerable at this point. Perhaps there's been more research into
these matters than I know of (quite possible), but if there has its been
kept quiet.
J
-
This message was sent to the java-interest mailing list
Info: send 'help' to java-interest-request@java.sun.com
