0
\$\begingroup\$

I am writing an app that finds prime numbers within a specified range. Currently i am updating almost every part of the app and i have also changed the way i find prime numbers. The problem is that the new method seems to be much slower. As a test, the old method takes only 8 seconds to find all the primes from 0 - 100,000. The same task takes the new method between 25 - 30 seconds to complete. I'm not sure why the new method is so much slower. Is there anything i can do to make the new method faster, or at least comparable to the old method, while still keeping the functionality (like the ability to pause it).

Since the code is quite long i have posted links to them as well.

Old Method Full class

public class PrimeFinderThread implements Runnable{
    //Flow control booleans
    public boolean threadRunning = false;
    public boolean scanningNumbers = false;
    public boolean stoppedScanning = true;
    public boolean threadStopped = true;

    //Current number being scanned
    public long currentNumber = 2;

    //Scan progress of current number
    public double currentNumberProgress = 0;

    //List of all found prime numbers
    public List<Long> primeNumbers = new ArrayList<>();

    //Buffer for numbers per second
    public List<Double> numbersPerSecondArray = new ArrayList<>();

    //Times for elapsed time calculation
    public long scanStartTime = 0;
    public long threadStartTime = 0;
    public long pausedTime = 0;
    public long elapsedTime = 0;
    public long lastUpdateTime = 0;
    public long loopStartTime = 0;
    public long loopEndTime = 0;
    public long lastOneSecondUpdateTime;

    //Maximum number to check when scanning for primes
    private double sqrtMax = 0;

    //Numbers scanned per second
    public int numbersPerSecond = 0;
    public int numbersSinceLastSecond = 0;

    //Prime numbers found per second
    public int primesPerSecond = 0;
    public int primesSinceLastSecond = 0;

    @Override
    public void run(){
        while (threadRunning){
            threadStopped = false;
            scanningNumbersLoop: while (scanningNumbers){
                stoppedScanning = false;
                loopStartTime = System.nanoTime();
                currentNumberProgress = 0;

                boolean isPrime = true;
                sqrtMax = Math.round(Math.sqrt(currentNumber));
                for (int i = 2; i <= sqrtMax; i++){
                    doUpdates(i);

                    //Check if number is prime
                    double actualNumber =  (double) currentNumber / i;
                    double roundedNumber = Math.round(actualNumber);

                    //Number is not prime, break out of the loop
                    if (actualNumber == roundedNumber){
                        isPrime = false;
                        break;
                    }

                    if (!threadRunning | !scanningNumbers){
                        break scanningNumbersLoop;
                    }
                }

                //Number is prime, add it to the list
                if (isPrime){
                    primeNumbers.add(currentNumber);
                    primesSinceLastSecond++;
                }

                //Stop thread if end value was reached
                if (currentNumber == ScanForPrimesFragment.endValue){
                    scanningNumbers = false;
                    currentNumberProgress = 100;
                    sendUpdateMessage("endValueReached");
                    break;
                }

                //Increase variables
                currentNumber++;
                numbersSinceLastSecond++;
                loopEndTime = System.nanoTime();
            }
            //Thread has stopped scanning for prime numbers
            stoppedScanning = true;
        }
        //Thread has stopped completely
        threadStopped = true;
    }

    /**
     * Called every few milliseconds to update elapsed time and other stats
     * @param i Current iteration of the loop
     */
    private void doUpdates(int i){
        //Update current number progress
        currentNumberProgress = (i / sqrtMax) * 100;

        //Update the time elapsed
        elapsedTime = System.currentTimeMillis() - scanStartTime;

        //Update every second
        if (System.currentTimeMillis() - lastOneSecondUpdateTime >= 1000){
            numbersPerSecond = numbersSinceLastSecond;
            numbersSinceLastSecond = 0;

            primesPerSecond = primesSinceLastSecond;
            primesSinceLastSecond = 0;

            lastOneSecondUpdateTime = System.currentTimeMillis();
        }

        //Update ui
        if (System.currentTimeMillis() - lastUpdateTime >= PrimeNumberFinder.UPDATE_LIMIT_MS){
            lastUpdateTime = System.currentTimeMillis();
            sendUpdateMessage(null);
        }
    }

    /**
     * Send a message to the handler telling the ui to update
     */
    private void sendUpdateMessage(String msgData){
        Message message = ScanForPrimesFragment.handler.obtainMessage();
        Bundle bundle = new Bundle();
        bundle.putString("currentNumber", String.valueOf(currentNumber));
        bundle.putString("msgData", msgData);
        message.setData(bundle);
        ScanForPrimesFragment.handler.sendMessage(message);
    }
}

New Method Full class

public class FindPrimesTask extends Task{

    /**
     * Tag used for logging and debugging.
     */
    private static final String TAG = "FindPrimesTask";

    /**
     * List of all prime numbers found.
     */
    private final List<Long> primeNumbers = new ArrayList<>();

    /**
     * Start and end values. The end value can be modified after the task has started if the user
     * pauses it first. If the end value is set to {@link #LIMIT_NO_LIMIT}, then the task will run
     * forever until stopped by the user or interrupted.
     */
    private final long startValue;
    private long endValue;

    /**
     * If the end value is set to this, then the runnable will run forever until stopped by the
     * user or interrupted.
     */
    public static final int LIMIT_NO_LIMIT = -1;

    /**
     * The current number we are checking.
     */
    private long currentNumber;

    /**
     * The search progress on the current number as a decimal between 0 and 1.
     */
    private float currentProgress = 0;


    private long totalCheckTime;
    private int numbersChecked;

    private final List<EventListener> eventListeners = new ArrayList<>();


    private long[] lastUpdateTimes = new long[2];


    Map<Long, Long> map;
    Map<Long, Long> primesMap;

    /**
     * Create a new {@link FindPrimesTask} to search for prime numbers within a given range.
     *
     * @param startValue The beginning of the search range.
     * @param endValue The end of the search range.
     */
    public FindPrimesTask(final long startValue, final long endValue){
        this.startValue = startValue;
        this.endValue = endValue;

        map = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
        primesMap = ExpiringMap.builder().expiration(1000, TimeUnit.MILLISECONDS).build();
    }

    @Override
    public void run(){

        //The task has started
        dispatchStarted();

        /**
         * Set the current number to the start value. If the start value is less then 2, then set
         * it to 2 because that is the lowest prime number.
         */
        if (startValue < 3){
            if (endValue >= 2){
                sendOnPrimeFound(2);
            }

            currentNumber = 3;
        }else{
            currentNumber = startValue;
        }

        int sqrtMax;
        boolean isPrime;

        boolean running = true;

        //Loop forever
        while (running){

            //Check if the end value has been reached
            if (endValue == LIMIT_NO_LIMIT || currentNumber <= endValue){

                //Check if the number is divisible by 2
                if (currentNumber % 2 != 0){

                    /**
                     * Get the square root of the number. We only need to calculate up to the square
                     * root to determine if the number is prime. The square root of a long will
                     * always fit inside the value range of an int.
                     */
                    sqrtMax = (int) Math.sqrt(currentNumber);

                    //Assume the number is prime
                    isPrime = true;

                    final long checkStartTime = System.nanoTime();

                    /**
                     * Check if the number is divisible by every odd number below it's square root.
                     */
                    for (int i = 3; i <= sqrtMax; i += 2){

                        //Check if the number divides perfectly
                        if (currentNumber % i == 0){
                            isPrime = false;
                            break;
                        }

                        //Calculate current progress
                        currentProgress = (float) i / sqrtMax;
                        sendOnProgressChanged(currentProgress);

                        //Check if we should pause
                        tryPause();
                        if (shouldStop()){
                            running = false;
                            break;
                        }
                    }

                    numbersChecked++;
                    totalCheckTime += (System.nanoTime() - checkStartTime);

                    //Check if the number was prime
                    if (isPrime){
                        synchronized (LOCK){
                            primeNumbers.add(currentNumber);
                            //primesMap.put(currentNumber, currentNumber);
                        }

                        sendOnPrimeFound(currentNumber);
                    }
                }

                //Increase currentNumber
                currentNumber++;
                //map.put(currentNumber, currentNumber);

                //Calculate total progress
                if (endValue != LIMIT_NO_LIMIT){
                    setProgress((float) (currentNumber - startValue) / (endValue - startValue));
                }

            }else{
                currentNumber = endValue;
                currentProgress = 1f;
                setProgress(1);
                //isRunning = false;
                break;
            }
        }

        dispatchStopped();

        //The task has finished
        if (currentNumber == endValue){
            dispatchFinished();
        }

    }

    public long getAverageCheckTime(){
        return (totalCheckTime - getTotalPauseTime()) / numbersChecked;
    }

    public void setEndValue(long endValue){
        this.endValue = endValue;
    }

    public float getCurrentProgress(){
        return currentProgress;
    }

    public long getCurrentNumber(){
        return currentNumber;
    }

    public long getEndValue(){
        return endValue;
    }

    public long getStartValue(){
        return startValue;
    }

    public long getNumbersPerSecond(){
        return map.size();
    }

    public long getPrimesPerSecond(){
        return primesMap.size();
    }

    public void addEventListener(final EventListener eventListener){
        if (!eventListeners.contains(eventListener)) eventListeners.add(eventListener);
    }

    public interface EventListener{
        void onPrimeFound(final long prime);
    }

    private void sendOnPrimeFound(final long prime){
        for (EventListener eventListener : eventListeners){
            eventListener.onPrimeFound(prime);
        }
    }
}

The new method extends from Task, which is just a simple class extending from Thread

Task Full class

public abstract class Task implements Runnable{

    /**
     * Tag used for logging and debugging.
     */
    private static final String TAG = "Task";

    /**
     * Listeners for task events.
     */
    private final List<TaskListener> taskListeners = new ArrayList<>();

    /**
     * Possible task states.
     */
    public enum State{
        NOT_STARTED,
        RUNNING,
        PAUSED,
        STOPPED,
        FINISHED
    }

    /**
     * Current task state.
     */
    private State state = State.NOT_STARTED;

    /**
     * Total task progress. If ongoing task, progress will remain at 0.
     */
    private float progress = 0f;

    /**
     * Keep track of when the task was started and paused. These values are also used to calculate
     * the elapsed time.
     */
    private long startTime;
    private long lastPauseTime;
    private long totalPauseTime;

    /**
     * Lock used to pause the current thread when the task is paused.
     */
    protected final Object LOCK = new Object();

    private boolean requestPause = false;
    private boolean requestStop = false;

    //Override methods

    @Override
    public abstract void run();

    //Utility methods

    protected void tryPause(){
        if (requestPause){
            synchronized (LOCK){
                try{

                    //Pause
                    dispatchPaused();
                    Log.e(TAG, "Time elapsed pause: " + getTimeElapsed());
                    sendOnTaskPaused();

                    //Wait until notified to resume
                    LOCK.wait();

                    //Resume
                    dispatchResumed();

                }catch (InterruptedException e){
                    if (PrimeNumberFinder.DEBUG)
                        Log.e(TAG, "Task was interrupted while paused!");
                }
            }
        }
    }

    protected boolean shouldStop(){
        return requestStop;
    }

    //Lifecycle methods

    public void start(){
        run();
    }

    protected void dispatchStarted(){
        this.startTime = System.currentTimeMillis();
        setState(State.RUNNING);
        sendOnTaskStarted();
    }

    public void pause(){
        requestPause = true;
    }

    private void dispatchPaused(){
        requestPause = false;
        lastPauseTime = System.currentTimeMillis();
        setState(State.PAUSED);
    }

    public void resume(){
        synchronized (LOCK){
            LOCK.notify();
        }
    }

    private void dispatchResumed(){
        totalPauseTime += (System.currentTimeMillis() - lastPauseTime);
        setState(State.RUNNING);
        sendOnTaskResumed();
    }

    protected void dispatchStopped(){
        setState(State.STOPPED);
    }

    protected void dispatchFinished(){
        setState(State.FINISHED);
    }

    public void stop(){
        requestStop = true;
    }

    //Getters and setters

    public void addTaskListener(final TaskListener taskListener){
        if (!taskListeners.contains(taskListener)) taskListeners.add(taskListener);
    }

    public long getTimeElapsed(){
        if (startTime == 0){
            return 0;
        }
        return System.currentTimeMillis() - startTime - totalPauseTime;
    }

    public float getProgress(){
        return progress;
    }

    public void setProgress(float progress){
        this.progress = progress;
    }

    public State getState(){
        return state;
    }

    private void setState(State state){
        this.state = state;
        switch (state){
            case PAUSED:
                sendOnTaskPaused();
                break;

            case STOPPED:
                sendOnTaskStopped();
                break;

            case FINISHED:
                sendOnTaskFinished();
                break;
        }
    }

    protected long getTotalPauseTime(){
        return totalPauseTime;
    }

    //Callbacks

    private void sendOnTaskStopped(){
        for (TaskListener taskListener : taskListeners){
            taskListener.onTaskStopped();
        }
    }

    private void sendOnTaskStarted(){
        for (TaskListener taskListener : taskListeners){
            taskListener.onTaskStarted();
        }
    }

    private void sendOnTaskPaused(){
        for (TaskListener taskListener : taskListeners){
            taskListener.onTaskPaused();
        }
    }

    private void sendOnTaskResumed(){
        for (TaskListener taskListener : taskListeners){
            taskListener.onTaskResumed();
        }
    }

    private void sendOnTaskFinished(){
        for (TaskListener taskListener : taskListeners){
            taskListener.onTaskFinished();
        }
    }

    protected void sendOnProgressChanged(final float percent){
        for (TaskListener taskListener : taskListeners){
            taskListener.onProgressChanged(percent);
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ You have not included sufficent information to compile and run you code. First, show your imports: import java.util.ArrayList;, import java.util.List; etc. Then, make sure all dependencies are included. For example, what is ScanForPrimesFragment? Where is it defined? \$\endgroup\$ – Ryan Mills Mar 12 '17 at 3:50
  • \$\begingroup\$ You do not appear to be using the sieve of Eratosthenes. That will run a lot faster than your current method - dividing by odd number. A sieve will allow you to divide only by prime numbers, omitting 9, 15, 21 25 etc. \$\endgroup\$ – rossum Mar 12 '17 at 12:29
  • \$\begingroup\$ Also not an answer to your question, but a "+1" to rossums comment: just to get a feeling for the time needed, I hacked together a sieve of erastosthenes to calculate the prime numbers from 0 to 100000 and came to a runtime of 3 ms (modern hardware, single threaded). Extending this to a million goes up to 13 ms on my system. Thus, whatever you do, your algorithm seems to be so sub-par, that following through with it is probably not worthwile. \$\endgroup\$ – mtj Mar 14 '17 at 6:45
  • \$\begingroup\$ My tests were all run on an android device in a single thread, so i wasn't expecting great performance. However i was able to bring the time down to about 2 seconds (for 100,000). I have also tested this code on my PC (i7-4990 @ 3.6Ghz) and it took 20ms to get to 100,000 and about 280ms to get to 1 mil (again on a single thread). In the code I posted above, i found that sendOnProgressChanged() was taking a relatively long time, considering it is called every iteration. Removing that helped the performance, but I think i might take your suggestion and implement the sieve. Thanks for the help! \$\endgroup\$ – TychoTheTaco Mar 14 '17 at 23:38
1
\$\begingroup\$

I am taking a step back and writing in general answer to address your concerns.

I think you are doing good stuff but your code looks so much complex because you have combined 3 things together.

1) Finding prime numbers

2) Implement multi threaded application

3) Profile application performance

I would suggest to make implementation of these 3 component separate from each other. Make your design modular so that you can address issues at each level.

As already mentioned in comments, Eratosthenes algorithm is most efficient in terms of solving problem-1

For profiling, there are few good open source tools available which you can use in order to compare performance between different implementation of your application.

Some tools are discussed here: https://stackoverflow.com/questions/948549/open-source-java-profilers

\$\endgroup\$
  • 1
    \$\begingroup\$ I have changed my implementation quite a bit now, to allow these 3 criteria to be met and i am satisfied with it. Thanks for the tips. \$\endgroup\$ – TychoTheTaco Mar 20 '17 at 3:10

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.