Fermat Points Proof

Tim B. had been tasked with updating an older internal application implemented in Java. Its primary purpose was to read in and display files containing a series of XY points—around 100,000 points per file on average—which would then be rendered as a line chart. It was notoriously slow, taking 1-2 minutes to process each file, but otherwise remained fairly stable.

Except that lately, some newer files were failing during the loading process. Tim quickly identified the problem—date formats had changed—and fixed the necessary code. Since the code that read in the XY points happened to reside in the same class, Tim asked his boss whether he could take a crack at killing two birds with one stone. With her approval, he dug in to figure out why the loading process was so slow.

//Initial code, pulled from memory so forgive any errors.
try {
            //The 3rd party library we are passing the values to requires
            //an array of doubles
            double[][] points = null;
            BufferedReader input =  new BufferedReader(new FileReader(aFile));
            try {
                String line = null;
               
                while (( line = input.readLine()) != null)
                {
                    //First, get the XY points from line using a convenience class
                    //to parse out the values.
                    XYPoint p = new XYPoint(line);
                    //Now, to store the points in the array.
                    if ( points == null )
                    {
                        //Okay, we've got one point so far.
                        points = new double[1][2];
                        points[0][0] = p.X;
                        points[0][1] = p.Y;
                    }
                    else
                    {
                        //Uh oh, we need more room. Let's create an array that's one larger
                        //and copy all of our points so far into it.
                        double[][] newPointArray = new double[points.length + 1][2];
                        for ( int i = 0; i < points.length; i++ )
                        {
                            newPointArray[i][0] = points[i][0];
                            newPointArray[i][1] = points[i][1];
                        }
                        //Now we can add the new point!
                        newPointArray[points.length][0] = p.X;
                        newPointArray[points.length][1] = p.Y;
                        points = newPointArray;
                    }
                }
               
                //Now, we can pass this to our next function
                drawChart( points );
            }
            finally
            {
                input.close();
            }
        } catch (IOException ex)
        {
            ex.printStackTrace();
        }
//End original code

After scouring the code twice, Tim called over a few coworkers to have a look for themselves. Unfortunately, no, he wasn't reading it wrong. Apparently the original developer, who no longer worked there, had run into the problem of not knowing ahead of time how many points would be in each file. However, he'd needed an array of doubles to pass to the next library so he could use a list, which only accepted objects. Thus had he engineered a truly brillant workaround.

Tim determined that for the average file of 100,000 points, each import required a jaw-dropping 2 billion copy operations (1 billion for the Xs, 1 billion for the Ys). After a quick refactoring to use an ArrayList, followed by a copy to a double array, the file load time went from minutes to nearly instantaneous.

//Re-factored code below.
try {
            //The 3rd party library we are passing the values to requires
            //an array of doubles
            double[][] points = null;
            ArrayList xyPoints = new ArrayList();
            BufferedReader input =  new BufferedReader(new FileReader(aFile));
            try {
                String line = null;
               
                while (( line = input.readLine()) != null)
                {
                    xyPoints.add( new XYPoint(line) );
                }
               
                //Now, convert the list to an array
                points = new double[xyPoints.size()][2];
                for ( int i = 0; i < xyPoints.size(); i++ )
                {
                    points[i][0] = xyPoints.get(i).X;
                    points[i][1] = xyPoints.get(i).Y;
                }
                //Now, we can pass this to our next function
                drawChart( points );
            }
            finally
            {
                input.close();
            }
        } catch (IOException ex)
        {
            ex.printStackTrace();
        }
//End re-factored code.
[Advertisement] BuildMaster allows you to create a self-service release management platform that allows different teams to manage their applications. Explore how!