How to create Memory Leaks by using Inner Classes.

The most recent Java Specialists Newsletter finally convinced me to start this post that I was having in mind for quite some time.

One of the really huge advantages of Java is that you almost do not have to care about cleaning up your memory as the Garbage Collector usually does this for you as soon as Objects are no more referenced. Usually this works really really well so that you really don’t have to care about annything! But maybe once in a while you may be observing something like a memory leak. Some people then call the Garbage explicitly – which is usually just a bad idea and possibly also doesn’t help either so that the “leak” remains. The better solution in this case would be profiling so that you can see why some classes are not cleaned up.

A nice source for memory leaks can be the use of anonymous inner classes. Assume the following class where you want to compute s.th and return a Result-Object which derives from an Interface:

interface Result{}
class Outer {
    int[] data = null;
    public Outer(int s) { data = new int[s]; }
    Object getResult() { return new Result(){}; }
}

So if you call new Outer(1).getResult(), you will still have an instance of Outer in memory even though you did not keep an explicit reference. As explained in the Java Specialists Newsletter, each instance of an anoymous inner class always keeps a reference to the outer class! This is not a big deal as long as

  • you don’t keep a lot of data in the Outer instance or
  • if the lifetime of the Result object is not long or
  • if you won’t create a lot of results anyways.

Let’s have an example. If you execute

ArrayList l = new ArrayList();
int i = 0;
while(true){
    l.add(new Outer(0).getResult());
    System.out.println(i++);
}

with the above classes without memory constraints (-Xmx), this will run for quite some time because you are only holding 2 class references (Outer, Result) 1 field (the emtpty data array) and an implicit reference from Result to Outer. Which makes a total of 48 bytes on my Win7 64bit machine (according to this measurement).

Now change the parameter in the constructor of Outer from 0 to 100000 and execute the code again. In my case I am getting an OutOfMemoryException after a bit more than 2000 created instances as now suddenly each iteration consumes 400.048 bytes (48 bytes as before + 100.000*4 bytes for the int-array) even though we only keep the explicit reference to the Result objects!

So – if you are creating an inner class the next time – you might have a brief look at the outer class as well and think about memory consumption and lifetime.

Performanceanalyse mit JVisualVM – evil synchronized

In einem meiner kleinen Projekte werden an einer Stelle etliche Threads gestartet, die jeweils ein Bild einlesen, skalieren und wieder auf die Platte schreiben. – Die ganze Zeit hat mich schon das Gefühl beschlichen, dass das zu langsam läuft, untersucht hatte ich das bisher nur nie. Nachdem genau diese Funktionalität heute definitv zu langsam war, kam ich um eine Analyse wohl doch nicht mehr herum. Also erst mal untersuchen, was da vor sich geht:

  • Programm gestartet,
  • JVisualVM gestartet (zu finden im bin-Verzeichnis einer JDK-Installation),
  • VisualVM auf das laufende Programm verbunden, und die Threads anzeigen lassen
  • kritische Funktion im Programm gestartet

Und siehe da: die Threads werden gestartet, aber nur immer genau einer ausgeführt (siehe Bild). Alle anderen Threads die laufen sollten stehen auf “Monitor”. Das ist leicht daran zu erkennen, dass zwar alle PictureScaleWorker ausgeführt werden, aber niemals gleichzeitig alle grün (also im Running State) sind sondern immer nur einer. Na das sollte ja nicht so sein!

Aber was machen die eigentlich und worauf warten die? Also erst mal einen Thread Dump erstellen (Button oben rechts), vielleicht bringt der ja ein paar Infos:

Dann zu einem der betreffenden Threads scrollen und nachsehen, ob dort etwas auffällig ist.

Thread.State: BLOCKED (on object monitor)
at de.locked.gallery.utils.ImageUtils.read (ImageUtils.java:83)

Blocked on object monitor – das sieht nach einem synchronized aus. Und betreffende Zeile 83 ist tatsächlich synchronized – was ich bei einem der letzten Refactorings offenbar übersehen habe. Mittlerweile ist die Synchronisierung auf dieser Methode zum Glück nicht mehr nötig und ich kann die Einschränkung ohne Gewissenbisse entfernen. Und siehe da, auf einmal laufen auch alle Threads gleichzeitig, was auf 8 Kernen doch einen spürbaren Unterschied macht. – Willkommen im Multi-Core Zeitalter.

Ohne die JVisualVM wäre ich früher oder später wohl auch an die Stelle gekommen – aber ich bezweifle ernsthaft dass ich die Stelle innerhalb weniger Minuten gefunden hätte.

Dazu auch ein interessantes Video.

Speicherverbrauch in Java oder “Size does matter!”

Eines der Vorurteile gegenüber Java ist ja der (angeblich) enorme Speicherverbrauch. Frage ich dann, ob denn die entsprechende Applikation schon mal auf Speicherverbrauch geprofiled wurde und welcher Profiler verwendet wurde, gibt es große Augen und Gestammel über HeapSize, OutOfMemoryExceptions und dass in C ja eh alles besser sei. Na, da weiß man doch gleich dass nicht nur Java schuld sein muss. – Hat man mal mit ImageJ gearbeitet, ist man ab und an schon äußerst verwundert, wie schnell Java sein kann – und fühlt sich auch angespornt seine eigenen Kenntnisse  zu erweitern.

Generell gibt es zur Speicherdiskussion (mindestens) zwei Szenarien.

  1. Die Diskussion, wieviel Speicher eine Datenstruktur verbraucht und ob nicht eine andere Speicherstruktur besser ist.
  2. Wir haben eine OOME und müssen sie beseitigen.

Wieviel Speicher verbraucht meine Datenstruktur?

DAS ist jetzt mal wirklich ein Nachteil von Java wie er im Buche steht, denn es gibt per se keine wirklich einfache Möglichkeit, den Speicherverbrauch einer Struktur oder eines Objektes zu ermitteln. Der Artikel From Java code to Java heap ist hier definitiv anzuraten. Hier wird detailierter über den Speicherverbrauch von Klassen eingegangen.

Im Java Specialists Newsletter von 2001(!!) gibt es einen einen Workaround und ein paar weitere Erklärungen – es folgt eine teils Übersetzung aus dem Newsletter:

  1. Jede Klasse belegt mindestens 8 Bytes auf dem Heap (also auch ein new Object()).
  2. Jeder Datentyp belegt 4 Bytes, außer long und double, die 8 Bytes belegen. Achtung, das heißt, auch ein Datentyp byte benötigt dann 4 Bytes. Außerdem wird der Speicherverbrauch nur in 8 Byte Schritten erhöht. D.h eine Klasse mit einem byte Datentyp belegt 8 Byte für die Klasse + 8 Byte für die Daten = 16 Byte.
  3. Arrays sind speicherschonender  – der geneigte Leser darf das gerne selbst nachlesen.
  4. String#intern() kann ordentlich Speicher sparen.
  5. Boolean.TRUE und Boolean.FALSE benötigen weniger als new Boolean(true).

Okay, alles schön und gut. Aber eine komplexere Struktur benötigt dann wieviel genau? Im Java Specialists Newsletter ist dazu eine kleine aber feine Klasse, die hier weiterhilft:

public class MemoryTestBench {

    public long calculateMemoryUsage(ObjectFactory factory) {
        Object handle = factory.makeObject();
        long mem0 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        long mem1 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        handle = null;
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        mem0 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        handle = factory.makeObject();
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        System.gc();System.gc();System.gc();
        mem1 = Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory();
        return mem1 - mem0;
    }

    public void showMemoryUsage(ObjectFactory factory) {
        long mem = calculateMemoryUsage(factory);
        System.out.println(factory.getClass().getName() + " produced " + factory.makeObject().getClass().getName() + " which took " + mem + " bytes");
    }
}

Die ObjectFactory sieht so aus:

public interface ObjectFactory { public Object makeObject(); }

Und am Beispiel einer ByteFactory sieht das wiederum so aus:

public class ByteFactory implements ObjectFactory { 
   public Object makeObject() { return new Byte((byte)33); } 
}

Jup, etwas aufwändig. Aber immerhin ein Ausweg aus dem Dilemma um hypothetische Diskussionen was wohl besser sein könnte. Und ja, DAS ist in C wirklich einfacher – und trotzdem will ich weiter Java verwenden 😀

OMG, OOME – was tun?!

Regel 1: NICHT blindwütig irgendwo irgendwas irgendwie anders machen.
Regel 2: Auch nicht nachdenken und glauben zu wissen wo es weh tut.

Sondern? Messen!
Zum Beispiel mit der JVisualVM, die bei neueren SUN/Oracle JDKs (nicht JRE) bereits im bin-Verzeichnis der JVM mitgeliefert wird. Ist man eh mit NetBeans unterwegs, kann man das Programm auch nochmal von dort direkt profilen. Ich persönlich setze den erlaubten Speicher (also -Xmx) dann gleich kleiner an, damit die OOME schneller eintritt und weniger Daten betrachtet werden müssen.

Mit etwas Glück sieht man dann recht schnell, welche Datenstrukturen (zu) oft im Speicher sind und kann dann gezielter nach den Referenzen suchen, die es eigentlich gar nicht geben sollte.

LinkedList 33x schneller als ArrayList oder “Kenne deine API!”

Für meine Arbeit schreibe ich zum Test gerade ein kleines Plugin für ImageJ, indem ich unter anderem einen Region-Fill Algorithmus brauche – leider tut’s der filler von ImageJ hier nicht – also schnell was selbst zusammengehackt:

Startpunkt initialisieren und in eine Liste damit
while (Liste nicht leer) {
   hole ersten Punkt P aus der Liste
   prüfe Eigenschaften von p.x/p.y auf dem Bild
   if (Eigenschaften erfüllt){
      füge der Liste die Punkte darüber, darunter, rechts und links hinzu
   }
}

Vorher eine ArrayList entsprechend groß initialisiert, damit die nicht dynamisch wachsen muss und gut ist’s.

Moment – in vielen Iterationen werden hinten an der Liste 4 Punkte angefügt. Das geht mit der ArrayList schön schnell, wie man im ArrayList Quellcode unschwer erkennt (wenn die Liste groß genug ist). Aber in jeder Iteration wird vorne das erste Element entnommen. – Ein Blick in den ArrayList-Quellcode offenbart ein “System.arraycopy(elementData, index+1,  elementData, index, numMoved);“. Oha – das riecht eigentlich eher nach einer LinkedList.

Also: Methode profilen, Listentyp ändern, nochmal profilen (mit dem NetBeans Profiler ja kein Thema). Ergebnis: LinkedList ist wie erwartet viel schneller. Ohne meinen ganzen sonstigen Code reduziert sich der Testfall in etwa auf folgende Testklasse:

public class ListTest {

    public static void main(String[] args) {
        List al = new ArrayList(31000);
        List ll = new LinkedList();
        long a = System.currentTimeMillis();
        testWith(al);
        long b = System.currentTimeMillis();
        testWith(ll);
        long c = System.currentTimeMillis();

        System.out.println("ArrayList: "+(b - a) + " ms");
        System.out.println("LinkedList: "+(c - b) + " ms");
    }

    private static void testWith(List list) {
        list.add(new Point(0, 0));
        int i = 10000;
        Point p;
        while (!list.isEmpty()) {
            p = list.remove(0);
            if (i-- > 0) {
                list.add(new Point(p.x, p.y - 1));
                list.add(new Point(p.x - 1, p.y));
                list.add(new Point(p.x + 1, p.y));
                list.add(new Point(p.x, p.y + 1));
            }
        }
    }
}

Das Speedstepping am Notebook nicht vergessen, sonst fährt die CPU am anfang ja noch nicht auf Vollgas und schon rennt der Test. Die ArrayList habe ich auch extra noch mit mehr Elementen initialisiert, als jemals reinkommen. Ausserdem geht die Initialisierung auch nicht in die Messung ein (ist im Vergeich mit dem Rest zwar eh vernachlässigbar klein, aber damit niemand auf die Idee kommt, der Vergleich wäre unfair …).

Ausgabe:
ArrayList: 860 ms  = 100%
LinkedList: 31 ms  = 3,6%

Sieht man sich die API und den Quellcode der beiden Klassen an, verwundert das Ergebnis nicht wirklich. Der unterschied skaliert natürlich auch mit der Anzahl der Iterationen.

Fazit

Ist ArrayList also schlecht? – Klares NEIN! Nur für genau diesen Anwendungfall (vielfaches Einfügen am Ende, vielfaches Herausnehmen am Anfang, kein Zugriff auf Elemente irgendwo dazwischen nötig) ist die ArrayList der Speicherstruktur der LinkedList einfach unterlegen, die genau auf diesen Punkten optimal funktioniert.

Ergo: Know your API! Man sollte sein Handwerkszeug kennen und nicht blindlings einfach das verwenden was man sonnst auch immer nimmt und hoffen, dass Java ein allmächtiges Werkzeug ist, das einem alle Arbeit abnimmt (und dann nacher groß jammern, dass in C++ ja eh alles viel schneller geht). Und wenn man Zweifel hat, ruhig mal einen Blick in den Sourcecode werfen und ausprobieren 😉

Java Heap-Implementierung / Avoid too much sorting II

Im Artikel Avoid too much sorting habe ich ja schon kurz skizziert, dass man es generell vermeiden sollte seine Daten unnötig oft zu sortieren, weil das einfach (je nachdem wie oft der entsprechende Code aufgerufen wird) ziemlich in die Rechenzeit gehen kann.

Manchmal muss man seine Daten aber eben sortiert halten. – Dann sollte man sich aber überlegen, ob man wirklich die ganzen Daten sortieren muss, oder ob es nicht einfach reicht, immer das kleinste/größte Element einer Menge zu bekommen. Ein gutes Beispiel ist zum Beispiel der altbekannte Dijkstra-Algorithmus. Dort benötigt man in jeder Iteration z.B. den Weg mit den bisher kleinsten Kosten.

Das schreit ja schon nach Sortieren. Bzw. eigentlich sollte einem da gleich die Heap-Datenstruktur einfallen, da dort alle Operaionen maximal in O(log n) erledigt sind, und nicht (wie beim Sortieren) in bis zu O(n²). Das schöne daran ist, dass es das in Java auch schon gibt, da heißt es nur nicht Heap (da man dabei vermutlich zu sehr an die Speicherverwaltung denken könnte), sondern PriorityQueue.

Wenn man jetzt aber Objekte sortieren will die nicht per se Comparable sind, benötigt man noch eine kleine Comparator-Implementierung mit einem SimpleEntry, damit man einem beliebigem Objekt auch seine Kosten zuweisen kann. Klingt jetzt recht aufwändig – ist es aber bei weitem nicht:

import java.util.AbstractMap.SimpleEntry;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<SimpleEntry> heap =
                new PriorityQueue<SimpleEntry>(10, new FooCmp());
        heap.add(new SimpleEntry(1d, new Foo(1)));
        heap.add(new SimpleEntry(5d, new Foo(2)));
        heap.add(new SimpleEntry(2d, new Foo(3)));
        while (!heap.isEmpty()) {
            System.out.println(heap.poll().getValue().i);
        }
    }
}

class FooCmp implements Comparator<SimpleEntry> {
    @Override
    public int compare(SimpleEntry o1, SimpleEntry o2) {
        return Double.compare(o1.getKey(), o2.getKey());
    }
}

class Foo {
    int i;
    Foo(int i) { this.i = i; }
}

Avoid too much sorting

“Java is slow” is the sentence that I heard very often when I began studying computer science – and I forunately never really believed it. But why the predjudice? Well Java CAN be slow if it’s just handeled wrong. Often it’s just convenience of just the missing knowledge of implemntations that makes code slow, so I’ll try to post once in a while whenever I come across such code parts in my hobby programming or at my programmings at work.

So my first issue is about sorting and autoboxing: About last week we profiled some code that felt just sloooow. It turned out that we lost most of the time within a certain loop that was executed very often. The critical part of the code was (stripped from all other stuff) like this :

ArrayList<Double> list = new ArrayList<Double>(20); // keep 20 smallest calculated values
while (condition) {
  double value = calculate(args);
  if (list.size < 20 || value < list.get(19)){
    list.add(value);
    Collections.sort(list)
  }
  // strip elements if size is > 20
}

So what’s the issue here?

  1. condition holds true for a LOT of iterations (well, can’t change this)
  2. the list is small (just 20) BUT it is to be sorted completely for each insert
  3. could autoboxing be an issue here?

Okay, what did we change?

We changed the ArrayList to a SortedDoubleArray (an implementation that I coded some time ago) that inserts the value already in the correct place using Arrays#binaraySearch() and System.arrayCopy(). As I wasn’t quite sure whether or not autoboxing could be an issue here, I created a copy of the class that operates on Doubles instead of the double primitives.

The Test

In order to compare the 3 methods (using Collections.sort(), and the SortedArrays using double and Double), I inserted 1,000,000 random double values into the structures and measured the times. The results are:

  • Collection.sort(): 2907 ms (=100%)
  • SortedDoubleArray (with Double-autoboxed values):  93 ms (~3%)
  • SortedDoubleArray (with double primitives):  94 ms (~3%)

Conclusion

  • Using Collections.sort() is convenient and in most cases absolutely okay! But if you use it in critical locations within the code (for example in loops that are executed very often), you might want to check if there isn’t a better solution.
  • Autoboxing does not hurt in our case

But never forget: Profile first, then tune. Otherwise you might tune code that has almost no impact to the overall execution time (for example, if the for-loop above is just executed 10 times).  And just change one issue after the other and perform measurements between each step so that you can identify the changes with the most impact.
If you have no profiler at hand, you might want to try the NetBeans profier.

value

Bilder in Java schnell skalieren / Fast Image Scaling / Resizing in Java

I’m recognizing, that this article faced quite some hits – if you’re a non-german user and want this article to be translated, please leave me a comment – maybe I’m gonna translate it if that is what people want.
Bilder in Java skalieren ist ein Thema für sich…

Intro

Verführerisch ist sie ja, die Image.getScaledImage()-Methode. Und ebenso fatal, denn sie ist eine heißer Kandidat den Code elends langsam zu machen. Wie geht’s schneller/besser? Ein wertvoller Link zum Einstieg ist The Perils of Image.getScaledInstance() und die dortigen Links.

Die obige Aussage (bzgl. langsam) ist ohne Zahlen quasi wertfrei. Gerade eben habe ich wieder ein Stück Code vor mir, indem Bilder skaliert werden müssen – und das schnell, da der Benutzer wartet! Ich habe also über den Daumen nicht mehr als 100-200ms Zeit, dem Benutzer  ein Ergebnis zu präsentieren, bevor die Anwendung langsam wirkt. Also:  meinen eigenen ImageScaler verwenden, den ich vor Zeiten mal geschrieben habe oder auf JAI (Java Advanced Imaging) zurückgreifen?
Der Plan ist klar: eine Performance-Messung muss her (da ich noch weiß, dass ich damals nicht mit JAI verglichen habe).

Messung / Ergebnisse

Input: Ein Jpeg 4008 x 2443 Pixel / 2,47 MB
Output: Das Bild soll in max. 400 x 400 Pixel eingebettet werden, Seitenverhältnis soll beibehalten werden (also ~400 x 243 Pixel).
Kandidaten:

  1. Image.getScaledInstance()
  2. mein eigener Scaler
  3. JAI

Setup: Bild ausserhalb der Zeitmessung einlesen, jeweils 20x skalieren und die benötigte Zeit ausgeben. JAI wird dabei mit nativen DLLs getestet ().

Ergebnis 1:

  1. Image.getScaledInstance(): ~30 ms
  2. mein eigener Scaler: ~234 ms
  3. JAI: ~500 ms

Moment – das ist NICHT was erwartet war.
Image img = src.getScaledInstance(400, -1, Image.SCALE_FAST);
Sieht aus als könnte man nicht viel falsch machen. – Aber wird da überhaupt etwas gemacht?
Verändern wir den Aufruf:
img.getSource().startProduction(new ImageConsumer() { … leere Methodenrümpfe… }

Ergebnis 2:

  1. Image.getScaledInstance(): 35781 ms
  2. mein Scaler:  ~234 ms
  3. JAI: ~500 ms

Aha. So sieht das aus wie erwartet. getScaledInstance() skaliert das Bild also erst bei Bedarf – leider sehr langsam.

Ergebnis 3 – 1x, 5x und 50x kleinskalieren:

  1. mein Scaler:  ~ 60 ms, ~ 90 ms, ~460 ms
  2. JAI: ~500 ms, 500 ms, 500 ms

Ahja – JAI cached offenbar. Interessant zu wissen – bei entsprechendem Szenario also sicher die bessere Wahl – diesmal gewinnt aber mein Scaler, da hier nur kleinskaliert werden soll und die restlichen JAI-Features eh ungenutzt bleiben.

Fazit

Das Key Feature meines Skalers ist die Essenz aus vielen Blogs und JavaOne-Folien:

  1. Solange das Bild größer als die doppelte Zielgröße ist: Bild mit Faktor 0.5 und Nearest Neighbor Interpolation skalieren. – Um nicht duzende Zwischenbilder erzeugen zu müssen (was bei großen Eingangsbildern richtig viel Speicher kosten kann, da die Bilder ja im Speicher dekomprimiert werden müssen!), skaliere ich in einem Schritt auf das kleinste Bild, das noch größer als das Zielbild ist.
  2. letzten Skalierungsschritt mit Bilinearer Interpolation skalieren.

Code:

public class ImageScaler {

    public BufferedImage scaleImage(BufferedImage img, Dimension d) {
        img = scaleByHalf(img, d);
        img = scaleExact(img, d);
        return img;
    }

    private BufferedImage scaleByHalf(BufferedImage img, Dimension d) {
        int w = img.getWidth();
        int h = img.getHeight();
        float factor = getBinFactor(w, h, d);

        // make new size
        w *= factor;
        h *= factor;
        BufferedImage scaled = new BufferedImage(w, h,
                BufferedImage.TYPE_INT_RGB);
        Graphics2D g = scaled.createGraphics();
        g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
                RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR);
        g.drawImage(img, 0, 0, w, h, null);
        g.dispose();
        return scaled;
    }

    private BufferedImage scaleExact(BufferedImage img, Dimension d) {
        float factor = getFactor(img.getWidth(), img.getHeight(), d);

        // create the image
        int w = (int) (img.getWidth() * factor);
        int h = (int) (img.getHeight() * factor);
        BufferedImage scaled = new BufferedImage(w, h,
                BufferedImage.TYPE_INT_RGB);

        Graphics2D g = scaled.createGraphics();
        g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
                RenderingHints.VALUE_INTERPOLATION_BILINEAR);
        g.drawImage(img, 0, 0, w, h, null);
        g.dispose();
        return scaled;
    }

    float getBinFactor(int width, int height, Dimension dim) {
        float factor = 1;
        float target = getFactor(width, height, dim);
        if (target <= 1) { while (factor / 2 > target) { factor /= 2; }
        } else { while (factor * 2 < target) { factor *= 2; }         }
        return factor;
    }

    float getFactor(int width, int height, Dimension dim) {
        float sx = dim.width / (float) width;
        float sy = dim.height / (float) height;
        return Math.min(sx, sy);
    }
}

Nützliche Links:
public class ImageScaler {public BufferedImage scaleImage(BufferedImage img, Dimension d) {
img = scaleByHalf(img, d);
img = scaleExact(img, d);
return img;
}

private BufferedImage scaleByHalf(BufferedImage img, Dimension d) {
int w = img.getWidth();
int h = img.getHeight();
float factor = getBinFactor(w, h, d);

// make new size
w *= factor;
h *= factor;
BufferedImage scaled = new BufferedImage(w, h,
BufferedImage.TYPE_INT_RGB);
Graphics2D g = scaled.createGraphics();
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
RenderingHints.VALUE_INTERPOLATION_NEAREST_NEIGHBOR);
g.drawImage(img, 0, 0, w, h, null);
g.dispose();
return scaled;
}

private BufferedImage scaleExact(BufferedImage img, Dimension d) {
float factor = getFactor(img.getWidth(), img.getHeight(), d);

// create the image
int w = (int) (img.getWidth() * factor);
int h = (int) (img.getHeight() * factor);
BufferedImage scaled = new BufferedImage(w, h,
BufferedImage.TYPE_INT_RGB);

Graphics2D g = scaled.createGraphics();
g.setRenderingHint(RenderingHints.KEY_INTERPOLATION,
RenderingHints.VALUE_INTERPOLATION_BILINEAR);
g.drawImage(img, 0, 0, w, h, null);
g.dispose();
return scaled;
}

float getBinFactor(int width, int height, Dimension dim) {
float factor = 1;
float target = getFactor(width, height, dim);
if (target <= 1) { while (factor / 2 > target) { factor /= 2; }
} else { while (factor * 2 < target) { factor *= 2; }         }
return factor;
}

float getFactor(int width, int height, Dimension dim) {
float sx = dim.width / (float) width;
float sy = dim.height / (float) height;
return Math.min(sx, sy);
}
}