Efficient Java Programming

[Alex]

Hi All,

I am hoping someone will be able to recommend a book to me. I have
been programming in Java for about a year now so I have a reasonable
knowledge of the basics. I use it for making command line programs
which are generally reasonably computationally intensive. However, I
definitely feel that my code is quite inefficient. Are there good
books aimed at people who already know the Java language to a
reasonable level that discuss good coding practice and how to write
fast, efficient code? I have looked at "Better, Faster, Lighter Java"
but it doesn't seem very appropriate for what I am after.

Any pointers would be appreciated.

Alex

 

[Roedy Green]

I am hoping someone will be able to recommend a book to me.

see http://mindprod.com/jgloss/optimising.html

 

[Dirk Michaelsen]

Hi Roedy,

see http://mindprod.com/jgloss/optimising.html

you maybe should add the following two very good books to the list:

- "Effective Java", Joshua Bloch, Addison Wesley
- "Java puzzlers", Joshua Bloch & Neal Gafter, Addison Wesley

Dirk

 

[Lew]

Hi Roedy,


you maybe should add the following two very good books to the list:

- "Effective Java", Joshua Bloch, Addison Wesley
- "Java puzzlers", Joshua Bloch & Neal Gafter, Addison Wesley

Excellent books. I don't know how the OP defines "efficient", but Bloch, et
al., will help you write better code more quickly with fewer problems, one
reasonable definition of being efficient.

 

[bugbear]

Hi All,

I am hoping someone will be able to recommend a book to me. I have
been programming in Java for about a year now so I have a reasonable
knowledge of the basics. I use it for making command line programs
which are generally reasonably computationally intensive.

In that case, I would expect choice of algorithm
(big O analysis and all that) to be vastly
more important than minor language tweaks.

BugBear

 

[Eric Sosman]

In that case, I would expect choice of algorithm
(big O analysis and all that) to be vastly
more important than minor language tweaks.

Sometimes, though, the language can hide a few O's.
For example, this classic Java blunder *looks* like an
O(N) algorithm:

String all = "";
for (String s : collection_of_N_Strings)
all += s;

.... but in fact it's more like O(N*N), depending on the
lengths of the collected Strings. This replacement:

StringBuilder buff = new StringBuilder();
for (String s : collection_of_N_Strings)
buff.append(s);
String all = buff.toString();

.... turns out to be an order-of-magnitude "minor tweak."

Encapsulation is not an unalloyed absolute good; now
and then you've got to kick down a few doors.

 

[Alex]

In that case, I would expect choice of algorithm
(big O analysis and all that) to be vastly
more important than minor language tweaks.

BugBear

That is almost certainly true. However, I am using fairly standard
algorithms (e.g a Forwards Backwards algorithm) since they are all I
know of, but I am just slightly worried that the way in which I've
coded it up may be full of bad practices that cause it to be slower
than it need be.

Alex

 

[Nigel Wade]

Hi All,

I am hoping someone will be able to recommend a book to me. I have
been programming in Java for about a year now so I have a reasonable
knowledge of the basics. I use it for making command line programs
which are generally reasonably computationally intensive. However, I
definitely feel that my code is quite inefficient. Are there good
books aimed at people who already know the Java language to a
reasonable level that discuss good coding practice and how to write
fast, efficient code? I have looked at "Better, Faster, Lighter Java"
but it doesn't seem very appropriate for what I am after.

Any pointers would be appreciated.

Alex

Here is some useful advice:

"Rules of Optimisation,
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet."
- M. A. Jackson

"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including blind
stupidity."
- W.A. Wulf

"We should forget about small efficiencies, say about 97% of the time: premature
optimization is the root of all evil."
- Donald Knuth

 

[Lew]

Here is some useful advice:

"Rules of Optimisation,
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet."
- M. A. Jackson

"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including blind
stupidity."
- W.A. Wulf

"We should forget about small efficiencies, say about 97% of the time: premature
optimization is the root of all evil."
- Donald Knuth

Classics.

There are two other goals more important than "efficiency" (whatever that is)
or performance, correctness and stability.

By the latter I mean things like getting over errors (or better, not having
them) and handling all inputs without fubaring.

 

[David Gourley]

Classics.

There are two other goals more important than "efficiency" (whatever
that is) or performance, correctness and stability.

By the latter I mean things like getting over errors (or better, not
having them) and handling all inputs without fubaring.

Although often stability problems can come as a direct consequence of
performance issues..... (e.g. excessive memory usage can trigger
worsening garbage collection behaviour and eventually lead to
OutOfMemoryExceptions).

Having at least some kind of idea what order of magnitude memory your
algorithm will use is probably a good idea... (at least on large
server-side implementations, especially since triggering paging for big
JVMs is *not* a good idea....)

Dave

 

[bencoe]

Although often stability problems can come as a direct consequence of
performance issues..... (e.g. excessive memory usage can trigger
worsening garbage collection behaviour and eventually lead to
OutOfMemoryExceptions).

Having at least some kind of idea what order of magnitude memory your
algorithm will use is probably a good idea... (at least on large
server-side implementations, especially since triggering paging for big
JVMs is *not* a good idea....)

Dave

Make sure you use StringBuffer instead of Strings, if you're doing
much with text

 

[David Gourley]

Make sure you use StringBuffer instead of Strings, if you're doing
much with text

For string concatenation... yes

And make sure you don't end up with a heap containing thousands/millions
of copies of the same string..... (each as a separate object instance).

Dave

 

[EricF]

Here is some useful advice:

"Rules of Optimisation,
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet."
- M. A. Jackson

"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including blind
stupidity."
- W.A. Wulf

"We should forget about small efficiencies, say about 97% of the time:
premature
optimization is the root of all evil."
- Donald Knuth

Hmm - let's look at the context before deciding optimization is evil. Knuth
gets it right - he says premature optimization.

If I'm writing a tool for my personal use, I may not care if it takes 30
seconds when it could be done in 5.

If I'm working on an enterprise application that is supporting a large number
of transactions, shaving 25 seconds off the time is likely a big deal.

Don't ignore optimization - just know where and when you need to worry about
it. Use the appropriate alogorithm, write clear and maintainable code, and get
the right results. If it's too slow, tune it.

If you are working on a distributed application (J2EE), more up front tuning
may be needed. This is not premature optimization. Network hops are expensive,
and if you wait until the end to reduce them it may be too late. Not that this
applies to the OP's question.

Eric

 

[bencoe]

Hmm - let's look at the context before deciding optimization is evil. Knuth
gets it right - he says premature optimization.

If I'm writing a tool for my personal use, I may not care if it takes 30
seconds when it could be done in 5.

If I'm working on an enterprise application that is supporting a large number
of transactions, shaving 25 seconds off the time is likely a big deal.

Don't ignore optimization - just know where and when you need to worry about
it. Use the appropriate alogorithm, write clear and maintainable code, and get
the right results. If it's too slow, tune it.

If you are working on a distributed application (J2EE), more up front tuning
may be needed. This is not premature optimization. Network hops are expensive,
and if you wait until the end to reduce them it may be too late. Not that this
applies to the OP's question.

Eric

Most things require optimization, it's a ridiculous thing to ignore. I
think a previous poster suggested, you should at the very least try to
minimize the order of operation for tasks... For instance, if you're
sorting, make sure you use something like quick sort that's nlogn, if
you're searching a large list, try to use binary search which is
logn... I strongly disagree with people who would suggest structure
over efficiency, since these two things have no reason to be ad odds
with each other.

A lot of reading isn't a necessity to get started writing efficient
code, just learn a bit about the order of operation of common tasks...
especially when you're working with large datasets.

Ben Coe.

 

[Roedy Green]

ou maybe should add the following two very good books to the list:

- "Effective Java", Joshua Bloch, Addison Wesley
- "Java puzzlers", Joshua Bloch & Neal Gafter, Addison Wesley

I had them mentioned in other sections of the glossary. I have added
them under optimising too.

 

[Roedy Green]

"Rules of Optimisation,
Rule 1: Don't do it.
Rule 2 (for experts only): Don't do it yet."
- M. A. Jackson

"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including blind
stupidity."
- W.A. Wulf

"We should forget about small efficiencies, say about 97% of the time: premature
optimization is the root of all evil."
- Donald Knuth

Giving generic advice gets you in trouble. I recall a story about a
guru who was advising his followers. One follower said "Why do you
tell me one thing, and George another?" The guru relied "Well if you
were both walking down the road and one was about to fall off into the
ditch on the right, I would say "go left", and the other about to fall
into the ditch on the left, I would say "go right"."

Jackson's nostrum was sound generic advice about a decade ago. However
I think people have gone too far in the other direction, deliberately
totally closing their eyes to efficiency and feeling profoundly
virtuous. If you at least understand how the machine works inside,
you can when it is reasonably effortless, write more efficient code
the first time out. You KNOW what won't scale.

You should not waste you time doing optimisations a compiler can
without destroying readability, but you might as well write efficient
code. It is often simpler too.

 

[Lew]

If I'm working on an enterprise application that is supporting a large number
of transactions, shaving 25 seconds off the time is likely a big deal.

That might be the wrong kind of optimization. Shaving 25 seconds off
individual response times might reduce overall throughput, perhaps reducing
the ability to handle concurrent clients. Often optimization of an enterprise
application requires /increasing/ the response time for individual clients.

 

[Lew]

Most things require optimization, it's a ridiculous thing to ignore. I
think a previous poster suggested, you should at the very least try to
minimize the order of operation for tasks... For instance, if you're
sorting, make sure you use something like quick sort that's nlogn, if
you're searching a large list, try to use binary search which is
logn... I strongly disagree with people who would suggest structure
over efficiency, since these two things have no reason to be ad odds
with each other.

A lot of reading isn't a necessity to get started writing efficient
code, just learn a bit about the order of operation of common tasks...
especially when you're working with large datasets.

But there's good optimization and bad optimization. I had a boss refuse to
let me fix an O(n-squared) algorithm and insisted that I optimize without
changing the algorithm. He then tried to withhold my fee because the program
was too slow.

The problem was that I wanted to fix the algorithm (good optimization) and he
wanted to speed up the bad algorithm (bad optimization).

When the company realized that I had provided a solution, trained the other
programmer in it, and that someone else had caused the problem, I got my fee.

The problem with saying, "I want my program to be efficient" is that people
focus on micro-optimization. You might buy 10% improvement by
micro-optimization after the fact, but of course the JVM is probably already
taking care of that kind of optimization for you. You might buy 10,000%
improvement over some data sets by the correct choice of algorithm in the
design phase.

 

[Martin Gregorie]

For instance, if you're
sorting, make sure you use something like quick sort that's nlogn,
>

That rule is too prescriptive for my taste. You need to know a lot more
about the problem being solved, and in particular about data volumes and
behavior, before making that decision. As examples:

- There may be hidden gotchas. For instance, quicksort is only faster
than shellsort if swapping items is more expensive than comparing
them.

- If you're using a binary search on a large data set and adding missing
items rather than just returning "not found", then modifying the
binary search to say where the missing item should be and using that
information to slot the new item into the right place may well be
faster than using a sort. The best solution will depend on the miss
percentage.

- if the data set is very large and/or searches have a high miss
frequency you don't use either a binary search or any type of sort:
you use a black-red binary tree if inserts tend to cluster, the
growth is large compared to the initial data set or if you need to
read out the data set in key sequence. Otherwise a hashtable may be
better.

In short, spend time understanding the problem and its behavior before
designing or implementing anything. Build well-instrumented throw-away
models if you need to.

I strongly disagree with people who would suggest structure
over efficiency, since these two things have no reason to be ad odds
with each other.

Well put.

 

[Twisted]

- if the data set is very large and/or searches have a high miss
frequency you don't use either a binary search or any type of sort:
you use a black-red binary tree if inserts tend to cluster, the
growth is large compared to the initial data set or if you need to
read out the data set in key sequence. Otherwise a hashtable may be
better.

In the case of Java, this boils down to the decision of which to use,
TreeSet/Map or HashSet/Map.