Unique-ifying an image

I'm writing a program that takes an input image, and generates a set of unique colors, and repaints the image using only those colors. It takes a long time, and I'm hoping to improve the running time. It's on GitHub, if you want more context.

This is an example of the output, running from left to right:

This is the main program, which has the main logic:

```
public class Program {
private static final String IMAGE_FILE = "/Untitled.png";
// This adds more colors to choose from, more = slower
private static final float ACCURACY_COEF = 2f;

public static void main(final String[] args) throws IOException {
final JFrame frame = new JFrame();

final BufferedImage image = GraphicsUtils.loadImage(IMAGE_FILE);
final BufferedImage newImage = createNewImage(image);
saveImage(newImage);

@SuppressWarnings("serial")
final JPanel panel = new JPanel() {
@Override
public void paintComponent(final Graphics g) {
g.drawImage(newImage, 0, 0, null);
g.drawImage(image, newImage.getWidth(), 0, null);
}
};
panel.setPreferredSize(new Dimension(newImage.getWidth() * 2, newImage.getHeight()));

frame.add(panel);
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.pack();
frame.setVisible(true);
}

private static void saveImage(final BufferedImage image) {
final File outputfile = new File("image.png");
try {
ImageIO.write(image, "png", outputfile);
} catch (final IOException e) {
e.printStackTrace();
}
}

/**
* Recreates the image using only unique pixels, starting from the left of the image.
*
* @param image
* @return
*/
private static BufferedImage createNewImage(final BufferedImage image) {
System.out.println("Generating points");
final List points = generateAllPoints(image.getWidth(), i

How it runs

I started by cloning your app, setting it up and running. Then I started looking at it. I initially ran it 4 times, to see how it will work (CPU, memory - off-heap, on-heap - threads, what eats most resources etc. All runs are on same settings.

First run - little measurements

• The low resources time is when app started, I chose image and then, slightly after 10:22 I pressed "run" (and all hell broke loose... naah, kidding).

• 10:22 - 10:23 - initial spike was when all data was loaded. Heap jumped high, CPU jumped high, actual work began.

• Overall, not much!

• initial spike in CPU 65%, then less than 40%.

• GC negligible.

• the only thing to dwell on is heap graph. Consumption is too jumpy.

Clearly things are being allocated and deallocated, over and over again. Large things, or large number of things. This can happen if you have arrays. Large arrays. Or large number of not so large arrays. The heap is under 2GB, so that's nothing to be scared of.

Threads?

Threads are simple, there's one thread that does the job. It's named "Thread-x", where x is some number. Whatever AWT thread pool has currently, that gets tasked with this "run" button handling. Usual stack trace:

"Thread-17" - Thread t@56
   java.lang.Thread.State: RUNNABLE
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDNode.nnbr(KDNode.java:181)
    at kdtree.KDNode.nnbr(KDNode.java:139)
    at kdtree.KDTree.nearest(KDTree.java:229)
    at kdtree.KDTree.nearest(KDTree.java:192)
    at main.ImageTask.getAndRemoveClosestColor(ImageTask.java:77)
    at main.ImageTask.run(ImageTask.java:50)
    at java.lang.Thread.run(Thread.java:745)

So, I know now what to focus on.

2nd run, sampling

I've limited sampling to only methods from your packages. Clearly nnbr and ins are doing nearly all the work there is. What to focus on, identified!

All 4 runs and observations

So, we have initial spike every time. Then we have stabilization. 3rd run is me overdoing monitoring (sampling CPU, mem, profiling CPU and using 3 tools at the same time). Thus the initial spike. Disregard that run (10:30 - 10:35) aside from the fact it's similar enough to others.

4th run is with a different image. New image had more colors. You can see heap being nicely used up till some point, where all of a sudden much work was to be done. Unfortunately, I didn't notice where it was (how far on "completion index" that you have or where on the image itself (which part of it).

4th run - heap

Looks nice at first, then (not captured above) grows worse.
Notice GC time: you may tune it to be better. Question is: do you need it? While I wouldn't want such times in production system, I don't feel so strongly about them here. But - your call.

4th run - CPU sampling

Same two methods eat CPU the most.

4th run - heap sampling

So, you deal with graphics and use coordinates (int arrays). Big surprise. Also, KDNode is the class where it all happens. Again, big surprise.

Summarizing

These 4 runs are by no means exhaustive. They are rather preliminary. We see where to focus the efforts.

Code

Of course, I also looked at code.

Copying array

Use System.arraycopy if you want to be fast, instead of manual copying.

public HPoint(final int[] x) {

    coord = new int[x.length];
    for (int i = 0; i < x.length; ++i) {
        coord[i] = x[i];
    }
}

could be

public HPoint(final int[] x) {

    coord = new int[x.length];
    System.arraycopy(x, 0, coord, 0, x.length);
}

https://stackoverflow.com/questions/2589741/what-is-more-efficient-system-arraycopy-vs-arrays-copyof

Empty exception handling can be collapsed to 'throws'

```
} catch (final UnsupportedLookAndFeelException e) {
// handle exception
} catch (final ClassNotFoundException e) {
// handle exception
} catch (

StackExchange Code Review Q#104473, answer score: 3