10
\$\begingroup\$

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:

output

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<Point> points = generateAllPoints(image.getWidth(), image.getHeight());

        System.out.println("Generating colors");
        final KDTree colors = generateAllColors((int) (image.getWidth() * image.getHeight() * ACCURACY_COEF));

        System.out.println("Number of points: " + points.size() + ", Number of colors: " + colors.size());

        return createNewImage(image, points, colors);
    }

    /**
     * Creates the new image
     *
     * @param preImage
     *            the original image
     * @param points
     * @param colors
     * @return
     */
    private static BufferedImage createNewImage(final BufferedImage preImage, final List<Point> points, KDTree colors) {
        final long start = System.currentTimeMillis();
        final BufferedImage newImage = GraphicsUtils.createImage(preImage.getWidth(), preImage.getHeight(), Transparency.OPAQUE);

        System.out.println("Creating image");
        int i = 1;
        long time = System.currentTimeMillis();
        // prints debug information and rebalances tree every so many iterations
        final int iterationsPerPrint = 5000;
        for (final Point p : points) {

            final Color c = getAndRemoveClosestColor(new Color(preImage.getRGB(p.x, p.y)), colors);
            newImage.setRGB(p.x, p.y, c.getRGB());

            if (i++ % iterationsPerPrint == 0) {
                final long timeTaken = System.currentTimeMillis() - time;
                final int remaining = points.size() - i;
                final long remainingMillis = (long) (remaining * (timeTaken / (double) iterationsPerPrint));
                System.out.println(remaining + " points remaining. Time taken for " + iterationsPerPrint + " iterations: " + timeTaken + " ms, or "
                        + (float) timeTaken / iterationsPerPrint + " ms per iteration. Projected remaining time: " + extractTime(remainingMillis)
                        + "\nTime elapsed: " + extractTime(System.currentTimeMillis() - start) + ", percent finished: " + (float) i / points.size()
                        * 100f);
                time = System.currentTimeMillis();
                // PRUNING STEP
                colors = colors.pruneAndRebalance(new HPoint(new int[] { c.getRed(), c.getGreen(), c.getBlue() }));
            }
        }
        System.out.println("Finished!");
        return newImage;
    }

    private static String extractTime(final long millis) {
        return String.format("%d min, %d sec", TimeUnit.MILLISECONDS.toMinutes(millis),
                TimeUnit.MILLISECONDS.toSeconds(millis) - TimeUnit.MINUTES.toSeconds(TimeUnit.MILLISECONDS.toMinutes(millis)));
    }

    /**
     * Finds the color most similar to a specified color in the tree, removes it, and returns it.
     *
     * @param color
     * @param colors
     * @return
     */
    private static Color getAndRemoveClosestColor(final Color color, final KDTree colors) {
        try {
            final Color nearest = (Color) colors.nearest(new int[] { color.getRed(), color.getGreen(), color.getBlue() });
            colors.delete(new int[] { nearest.getRed(), nearest.getGreen(), nearest.getBlue() });
            return nearest;
        } catch (final KeySizeException | KeyMissingException e) {
            throw new RuntimeException(e);
        }
    }

    /**
     * Generates a list of all points in a rectangle
     *
     * @param width
     * @param height
     * @return
     */
    private static List<Point> generateAllPoints(final int width, final int height) {
        final List<Point> points = new ArrayList<>(width * height);
        for (int x = 0; x < width; x++) {
            for (int y = 0; y < height; y++) {
                points.add(new Point(x, y));
            }
        }
        return points;
    }

    private static KDTree generateAllColors(final int i) {
        if (i > 255 * 255 * 255 && i >= 0) {
            throw new IllegalArgumentException();
        }
        final float perColor = (float) Math.cbrt(i);
        assert perColor >= 0 && perColor <= 255;
        System.out.println("Generating with this many per channel: " + perColor);

        final KDTree tree = new KDTree(3);

        final float step = 255f / perColor;

        for (float r = 0; r < 255; r += step) {
            for (float g = 0; g < 255; g += step) {
                for (float b = 0; b < 255; b += step) {
                    try {
                        tree.insert(new int[] { (int) r, (int) g, (int) b }, new Color((int) r, (int) g, (int) b));
                    } catch (KeySizeException | KeyDuplicateException e) {
                        e.printStackTrace();
                    }
                }
            }
        }
        return tree;
    }
}

I took a KD Tree implementation from the java-ml library, but I added my own rebalancing features in order to make it run quickly with a lot of deletions. I'm not sure if the way I implemented balancing is logical or optimal, but it improved performance; I profiled it and got this graph (the without pruning line was taking too long, so I ended it early):

enter image description here

public class KDTree {

    // K = number of dimensions
    private final int m_K;

    // root of KD-tree
    private KDNode m_root;

    // count of nodes
    private int m_count;

    /**
     * Creates a KD-tree with specified number of dimensions.
     *
     * @param k
     *            number of dimensions
     */
    public KDTree(final int k) {

        m_K = k;
        m_root = null;
    }

    /**
     * Insert a node in a KD-tree. Uses algorithm translated from 352.ins.c of
     *
     * <PRE>
     *   &#064;Book{GonnetBaezaYates1991,
     *     author =    {G.H. Gonnet and R. Baeza-Yates},
     *     title =     {Handbook of Algorithms and Data Structures},
     *     publisher = {Addison-Wesley},
     *     year =      {1991}
     *   }
     * </PRE>
     *
     * @param key
     *            key for KD-tree node
     * @param value
     *            value at that key
     *
     * @throws KeySizeException
     *             if key.length mismatches K
     * @throws KeyDuplicateException
     *             if key already in tree
     */
    public void insert(final int[] key, final Object value) throws KeySizeException, KeyDuplicateException {

        if (key.length != m_K) {
            throw new KeySizeException();
        } else {
            try {
                m_root = KDNode.ins(new HPoint(key), value, m_root, 0, m_K);
            }

            catch (final KeyDuplicateException e) {
                throw e;
            }
        }

        m_count++;
    }

    /**
     * Find KD-tree node whose key is identical to key. Uses algorithm translated from 352.srch.c of Gonnet &
     * Baeza-Yates.
     *
     * @param key
     *            key for KD-tree node
     *
     * @return object at key, or null if not found
     *
     * @throws KeySizeException
     *             if key.length mismatches K
     */
    public Object search(final int[] key) throws KeySizeException {

        if (key.length != m_K) {
            throw new KeySizeException();
        }

        final KDNode kd = KDNode.srch(new HPoint(key), m_root, m_K);

        return kd == null ? null : kd.v;
    }

    /**
     * Delete a node from a KD-tree. Instead of actually deleting node and rebuilding tree, marks node as deleted.
     * Hence, it is up to the caller to rebuild the tree as needed for efficiency.
     *
     * @param key
     *            key for KD-tree node
     *
     * @throws KeySizeException
     *             if key.length mismatches K
     * @throws KeyMissingException
     *             if no node in tree has key
     */
    public void delete(final int[] key) throws KeySizeException, KeyMissingException {

        if (key.length != m_K) {
            throw new KeySizeException();
        }

        else {

            final KDNode t = KDNode.srch(new HPoint(key), m_root, m_K);
            if (t == null) {
                throw new KeyMissingException();
            } else {
                t.deleted = true;
            }

            m_count--;
        }
    }

    public int size() {
        return m_count;
    }

    /**
     * Find KD-tree node whose key is nearest neighbor to key. Implements the Nearest Neighbor algorithm (Table 6.4) of
     *
     * <PRE>
     * &#064;techreport{AndrewMooreNearestNeighbor,
     *   author  = {Andrew Moore},
     *   title   = {An introductory tutorial on kd-trees},
     *   institution = {Robotics Institute, Carnegie Mellon University},
     *   year    = {1991},
     *   number  = {Technical Report No. 209, Computer Laboratory,
     *              University of Cambridge},
     *   address = {Pittsburgh, PA}
     * }
     * </PRE>
     *
     * @param key
     *            key for KD-tree node
     *
     * @return object at node nearest to key, or null on failure
     *
     * @throws KeySizeException
     *             if key.length mismatches K
     */
    public Object nearest(final int[] key) throws KeySizeException {
        return nearest(key, 1)[0];
    }

    /**
     * Find KD-tree nodes whose keys are <I>n</I> nearest neighbors to key. Uses algorithm above. Neighbors are returned
     * in ascending order of distance to key.
     *
     * @param key
     *            key for KD-tree node
     * @param n
     *            how many neighbors to find
     *
     * @return objects at node nearest to key, or null on failure
     *
     * @throws KeySizeException
     *             if key.length mismatches K
     * @throws IllegalArgumentException
     *             if <I>n</I> is negative or exceeds tree size
     */
    public Object[] nearest(final int[] key, final int n) throws KeySizeException, IllegalArgumentException {

        if (n < 0 || n > m_count) {
            throw new IllegalArgumentException("Number of neighbors cannot" + " be negative or greater than number of nodes");
        }

        if (key.length != m_K) {
            throw new KeySizeException();
        }

        final Object[] nbrs = new Object[n];
        final NearestNeighborList nnl = new NearestNeighborList(n);

        // initial call is with infinite hyper-rectangle and max distance
        final HRect hr = HRect.infiniteHRect(key.length);
        final int max_dist_sqd = Integer.MAX_VALUE;
        final HPoint keyp = new HPoint(key);

        KDNode.nnbr(m_root, keyp, hr, max_dist_sqd, 0, m_K, nnl);

        for (int i = 0; i < n; ++i) {
            final KDNode kd = (KDNode) nnl.removeHighest();
            nbrs[n - i - 1] = kd.v;
        }

        return nbrs;
    }

    /**
     * Range search in a KD-tree. Uses algorithm translated from 352.range.c of Gonnet & Baeza-Yates.
     *
     * @param lowk
     *            lower-bounds for key
     * @param uppk
     *            upper-bounds for key
     *
     * @return array of Objects whose keys fall in range [lowk,uppk]
     *
     * @throws KeySizeException
     *             on mismatch among lowk.length, uppk.length, or K
     */
    public Object[] range(final int[] lowk, final int[] uppk) throws KeySizeException {

        if (lowk.length != uppk.length) {
            throw new KeySizeException();
        }

        else if (lowk.length != m_K) {
            throw new KeySizeException();
        }

        else {
            final Vector<KDNode> v = new Vector<KDNode>();
            KDNode.rsearch(new HPoint(lowk), new HPoint(uppk), m_root, 0, m_K, v);
            final Object[] o = new Object[v.size()];
            for (int i = 0; i < v.size(); ++i) {
                final KDNode n = v.elementAt(i);
                o[i] = n.v;
            }
            return o;
        }
    }

    @Override
    public String toString() {
        return m_root.toString(0);
    }

    /**
     * Removes deleted nodes and rebalances the tree based around a point.
     * 
     * @param point
     * @return
     */
    public KDTree pruneAndRebalance(final HPoint point) {
        final KDTree newTree = new KDTree(m_K);

        if (m_root != null) {
            m_root.addTo(newTree, point);
        }

        return newTree;
    }
}

KDNode.java

class KDNode {

    // these are seen by KDTree
    protected HPoint k;

    protected Object v;

    protected KDNode left, right;

    protected boolean deleted;

    // Method ins translated from 352.ins.c of Gonnet & Baeza-Yates
    protected static KDNode ins(final HPoint key, final Object val, KDNode t, final int lev, final int K) throws KeyDuplicateException {

        if (t == null) {
            t = new KDNode(key, val);
        }

        else if (key.equals(t.k)) {

            // "re-insert"
            if (t.deleted) {
                t.deleted = false;
                t.v = val;
            } else {
                throw new KeyDuplicateException();
            }
        }

        else if (key.coord[lev] > t.k.coord[lev]) {
            t.right = ins(key, val, t.right, (lev + 1) % K, K);
        } else {
            t.left = ins(key, val, t.left, (lev + 1) % K, K);
        }

        return t;
    }

    // Method srch translated from 352.srch.c of Gonnet & Baeza-Yates
    protected static KDNode srch(final HPoint key, KDNode t, final int K) {

        for (int lev = 0; t != null; lev = (lev + 1) % K) {

            if (!t.deleted && key.equals(t.k)) {
                return t;
            } else if (key.coord[lev] > t.k.coord[lev]) {
                t = t.right;
            } else {
                t = t.left;
            }
        }

        return null;
    }

    // Method rsearch translated from 352.range.c of Gonnet & Baeza-Yates
    protected static void rsearch(final HPoint lowk, final HPoint uppk, final KDNode t, final int lev, final int K, final Vector<KDNode> v) {

        if (t == null) {
            return;
        }
        if (lowk.coord[lev] <= t.k.coord[lev]) {
            rsearch(lowk, uppk, t.left, (lev + 1) % K, K, v);
        }
        int j;
        for (j = 0; j < K && lowk.coord[j] <= t.k.coord[j] && uppk.coord[j] >= t.k.coord[j]; j++) {
            ;
        }
        if (j == K) {
            v.add(t);
        }
        if (uppk.coord[lev] > t.k.coord[lev]) {
            rsearch(lowk, uppk, t.right, (lev + 1) % K, K, v);
        }
    }

    // Method Nearest Neighbor from Andrew Moore's thesis. Numbered
    // comments are direct quotes from there. Step "SDL" is added to
    // make the algorithm work correctly. NearestNeighborList solution
    // courtesy of Bjoern Heckel.
    protected static void nnbr(final KDNode kd, final HPoint target, final HRect hr, double max_dist_sqd, final int lev, final int K,
            final NearestNeighborList nnl) {

        // 1. if kd is empty then set dist-sqd to infinity and exit.
        if (kd == null) {
            return;
        }

        // 2. s := split field of kd
        final int s = lev % K;

        // 3. pivot := dom-elt field of kd
        final HPoint pivot = kd.k;
        final double pivot_to_target = HPoint.sqrdist(pivot, target);

        // 4. Cut hr into to sub-hyperrectangles left-hr and right-hr.
        // The cut plane is through pivot and perpendicular to the s
        // dimension.
        final HRect left_hr = hr; // optimize by not cloning
        final HRect right_hr = (HRect) hr.clone();
        left_hr.max.coord[s] = pivot.coord[s];
        right_hr.min.coord[s] = pivot.coord[s];

        // 5. target-in-left := target_s <= pivot_s
        final boolean target_in_left = target.coord[s] < pivot.coord[s];

        KDNode nearer_kd;
        HRect nearer_hr;
        KDNode further_kd;
        HRect further_hr;

        // 6. if target-in-left then
        // 6.1. nearer-kd := left field of kd and nearer-hr := left-hr
        // 6.2. further-kd := right field of kd and further-hr := right-hr
        if (target_in_left) {
            nearer_kd = kd.left;
            nearer_hr = left_hr;
            further_kd = kd.right;
            further_hr = right_hr;
        }
        //
        // 7. if not target-in-left then
        // 7.1. nearer-kd := right field of kd and nearer-hr := right-hr
        // 7.2. further-kd := left field of kd and further-hr := left-hr
        else {
            nearer_kd = kd.right;
            nearer_hr = right_hr;
            further_kd = kd.left;
            further_hr = left_hr;
        }

        // 8. Recursively call Nearest Neighbor with paramters
        // (nearer-kd, target, nearer-hr, max-dist-sqd), storing the
        // results in nearest and dist-sqd
        nnbr(nearer_kd, target, nearer_hr, max_dist_sqd, lev + 1, K, nnl);

        double dist_sqd;

        if (!nnl.isCapacityReached()) {
            dist_sqd = Double.MAX_VALUE;
        } else {
            dist_sqd = nnl.getMaxPriority();
        }

        // 9. max-dist-sqd := minimum of max-dist-sqd and dist-sqd
        max_dist_sqd = Math.min(max_dist_sqd, dist_sqd);

        // 10. A nearer point could only lie in further-kd if there were some
        // part of further-hr within distance sqrt(max-dist-sqd) of
        // target. If this is the case then
        final HPoint closest = further_hr.closest(target);
        if (HPoint.sqrdist(closest, target) < max_dist_sqd) {

            // 10.1 if (pivot-target)^2 < dist-sqd then
            if (pivot_to_target < dist_sqd) {

                // 10.1.2 dist-sqd = (pivot-target)^2
                dist_sqd = pivot_to_target;

                // add to nnl
                if (!kd.deleted) {
                    nnl.insert(kd, dist_sqd);
                }

                // 10.1.3 max-dist-sqd = dist-sqd
                // max_dist_sqd = dist_sqd;
                if (nnl.isCapacityReached()) {
                    max_dist_sqd = nnl.getMaxPriority();
                } else {
                    max_dist_sqd = Double.MAX_VALUE;
                }
            }

            // 10.2 Recursively call Nearest Neighbor with parameters
            // (further-kd, target, further-hr, max-dist_sqd),
            // storing results in temp-nearest and temp-dist-sqd
            nnbr(further_kd, target, further_hr, max_dist_sqd, lev + 1, K, nnl);
            final double temp_dist_sqd = nnl.getMaxPriority();

            // 10.3 If tmp-dist-sqd < dist-sqd then
            if (temp_dist_sqd < dist_sqd) {

                // 10.3.1 nearest := temp_nearest and dist_sqd := temp_dist_sqd
                dist_sqd = temp_dist_sqd;
            }
        }

        // SDL: otherwise, current point is nearest
        else if (pivot_to_target < max_dist_sqd) {
            dist_sqd = pivot_to_target;
        }
    }

    // constructor is used only by class; other methods are static
    private KDNode(final HPoint key, final Object val) {
        k = key;
        v = val;
        left = null;
        right = null;
        deleted = false;
    }

    protected String toString(final int depth) {
        String s = k + "  " + v + (deleted ? "*" : "");
        if (left != null) {
            s = s + "\n" + pad(depth) + "L " + left.toString(depth + 1);
        }
        if (right != null) {
            s = s + "\n" + pad(depth) + "R " + right.toString(depth + 1);
        }
        return s;
    }

    private static String pad(final int n) {
        final StringBuilder s = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            s.append(' ');
        }
        return s.toString();
    }

    /**
     * Adds this node and subnodes to a tree. Tries to balance around a point.
     *
     * @param tree
     * @param middle
     */
    public void addTo(final KDTree tree, final HPoint middle) {
        final double distThis = deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, k);
        final double distLeft = left == null || left.deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, left.k);
        final double distRight = right == null || right.deleted ? Double.MAX_VALUE : HPoint.sqrdist(middle, right.k);

        // Add closest nodes first
        if (isMin(distThis, distLeft, distRight)) {
            addThis(tree);
            if (distLeft <= distRight) {
                addLeft(tree, middle);
                addRight(tree, middle);
            } else {
                addRight(tree, middle);
                addLeft(tree, middle);
            }
        } else if (isMin(distLeft, distThis, distRight)) {
            addLeft(tree, middle);
            if (distThis <= distRight) {
                addThis(tree);
                addRight(tree, middle);
            } else {
                addRight(tree, middle);
                addThis(tree);
            }
        } else {
            addRight(tree, middle);
            if (distLeft <= distThis) {
                addLeft(tree, middle);
                addThis(tree);
            } else {
                addThis(tree);
                addLeft(tree, middle);
            }
        }

    }

    private boolean isMin(final double a, final double b, final double c) {
        // returns whether a is the least
        return a <= b && a <= c;
    }

    private void addThis(final KDTree tree) {
        if (!deleted) {
            try {
                tree.insert(k.coord, v);
            } catch (KeySizeException | KeyDuplicateException e) {
                e.printStackTrace();
            }
        }
    }

    private void addLeft(final KDTree tree, final HPoint middle) {
        if (left != null) {
            left.addTo(tree, middle);
        }
    }

    private void addRight(final KDTree tree, final HPoint middle) {
        if (right != null) {
            right.addTo(tree, middle);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Can you clarify the goal of the program? Is it enough that each pixel has a unique color? Or must the leftmost pixels be as close as possible to their original colors? Because you could speed things up a lot if your nearest color search returned an approximately correct answer instead of the exact answer. \$\endgroup\$ – JS1 Sep 12 '15 at 10:09
  • \$\begingroup\$ @JS1 The goal of the program is really just to make a cool picture; I thought the effect of the image being less and less accurate from left to right was pretty cool. Considering I'm now using a kd tree, are you saying there's an even faster method that would return the approximate nearest neighbor? \$\endgroup\$ – Kyranstar Sep 12 '15 at 13:54
  • \$\begingroup\$ Yes, for example in your nnbr() function you could eliminate what you have commented as "step 10". That part searches other parts of the tree for even closer neighbors, but if you can approximate, you can skip that step. \$\endgroup\$ – JS1 Sep 12 '15 at 19:06
3
\$\begingroup\$

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

first run without any changes and almost no monitoring

  1. 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).
  2. 10:22 - 10:23 - initial spike was when all data was loaded. Heap jumped high, CPU jumped high, actual work began.
  3. Overall, not much!
    1. initial spike in CPU 65%, then less than 40%.
    2. GC negligible.
    3. 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)

thread that works

So, I know now what to focus on.

2nd run, sampling

CPU sampling during 2nd run

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

patterns are seen

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

JConsole heap 4th run

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 old Same two methods eat CPU the most.

4th run - heap sampling

heap reinforces it 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 (final InstantiationException e) {
        // handle exception
    } catch (final IllegalAccessException e) {
        // handle exception
    }

in effect can be just a list of exceptions added to throws declaration, or - if you insists on swallowing - just swallow it once, don't set up 4 handlers for 4 exceptions and make Java check each case to do nothing.

Empty for loop

Noticed you had empty for loop to actually iterate through some data and find first case where XYZ. Spent few minutes puzzled by it.

    int j = 0;
    for (j = 0; j < K && lowk.coord[j] <= t.k.coord[j] && uppk.coord[j] >= t.k.coord[j]; j++) {
        ;
    }
    if (j == K) {
        v.add(t);
    }

this can be replaced with streaming:

    IntStream is = IntStream.range(0, K);
    OptionalInt j = is.filter(element -> lowk.coord[element] > t.k.coord[element] || uppk.coord[element] < t.k.coord[element]).findFirst();
    if (j.getAsInt() == K) {

If I understood it correctly of course (but seems for loop was only till first index that met the criteria, and then element so indexed in table t was the one we were after).

Extras

I had to do few things when writing this, so I stopped taking care of it. After an hour and a half, I went back and noticed, that you have some slowly growing activity:

leak perhaps

If your heap behaves like that when your app sits in the background and does nothing, you are likely to have a memory leak.

For first set of remarks I think that will be quite enough. :-) If you want, take a look at these findings (I've also opened pull request against your code) and once you made some changes, open a new question and I'll proceed from there.

https://github.com/kyranstar/UniquePixels/pull/1

Final remark: your code is serial. Splitting the image in n-sections may well allow you to have n-threads working on it at the "same" time (where "same" depends on your machine/OS/CPUs).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.