Finding element using multithreading takes double the time of a single thread

Question

I am trying something similar to Search for an element in array with threads. Instead of using an actual array, the target value will be between 0 and Integer.MAX_VALUE * 10L and the goal is to find that target through the usage of a simple for loop.

The Searcher class will be the thread itself. Note the condition of the for loop which is i <= endIndex && Starter.running.get().
The Starter will create the threads and take care of initializing everything else.

There is AtomicBoolean variable type named running used to ensure threads stop execution when one of them find the element. The issue is that the the multithreaded approach takes twice the time compared to the single-threaded one. Without running, the multithreaded code will take even longer.

My goal is to stop all the threads when the target is found and know whether or not the target is found. Of course, if the target isn't in range, then the threads will have to check the entire segment and not find anything.

Sample output:

Target is: 15794437641
Multithreaded option has now started...
Found target using multithreading: 15794437641
Found!
Multithreaded time: 00h:00m:08s.714
Multithreaded option has now completed.

Single thread option has now started...
Found target using single thread: 15794437641
Single thread time: 00h:00m:04s.226
Single thread option has now completed...

The entire code:

import java.util.concurrent.atomic.AtomicBoolean;

class Searcher implements Runnable {
    private long target;
    private long startIndex;
    private long endIndex;
    private long range;

    public Searcher(long target, long startIndex, long endIndex, long range) {
        this.target = target;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
        this.range = range;
    }

    public void run() {
        for (long i = startIndex; i <= endIndex && Starter.running.get(); i++) {
            if (i == target) {
                Starter.running.set(false);
                Starter.isFound.set(true);
                System.out.println("Found target using multithreading: " + i);
                Thread.currentThread().interrupt();
            }
        }
    }
}

public class Starter {
    public static final AtomicBoolean running = new AtomicBoolean(true);
    public static final AtomicBoolean isFound = new AtomicBoolean(false);

    private static void findElementMultithreaded(
            int threadNumber, long target, long range
    ) {
        Thread[] threads = new Thread[threadNumber];//store threads created
        long segment = range / threadNumber;
        //create the threads but don't start them yet
        for (int i = 0; i <= threadNumber - 1; i++) {
            Searcher s;
            Thread t;
            long start = i * range;
            long end = range - 1;
            if (i == threadNumber - 1) {
                s = new Searcher(target, start, end, segment);
            } else {
                s = new Searcher(target, start, start + end, segment);
            }
            t = new Thread(s);
            threads[i] = t;
        }
        //start all threads
        for (Thread t : threads) {
            t.start();
        }
        //join all threads
        for (Thread t : threads) {
            try {
                t.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private static void findElementSingleThread(long target, long size) {
        for (long i = 0; i < size; i++) {
            if (i == target) {
                System.out.println("Found target using single thread: " + i);
                break;
            }
        }
    }

    public static String getLapsedTime(long start, long end) {
        long t = end - start;
        long millis = t % 1000;
        long x = t / 1000;
        long seconds = x % 60;
        x /= 60;
        long minutes = x % 60;
        x /= 60;
        long hours = x % 24;
        return String.format(
                "%02dh:%02dm:%02ds.%03d", hours, minutes, seconds, millis
        );
    }


    public static void main(String[] args) {
        int numberOfThreads = 8;
        long size = Integer.MAX_VALUE * 10L;
        long target = (long) (Math.random() * size);
        System.out.println("Target is: " + target);
        long start;
        long end;

        System.out.println("Multithreaded option has now started...");
        start = System.currentTimeMillis();
        findElementMultithreaded(numberOfThreads, target, size);
        if (isFound.get()) {
            System.out.println("Found!");
        }
        end = System.currentTimeMillis();
        System.out.println("Multithreaded time: " + getLapsedTime(start, end));
        System.out.println("Multithreaded option has now completed.\n");
        //
        System.out.println("Single thread option has now started...");
        start = System.currentTimeMillis();
        findElementSingleThread(target, size);
        end = System.currentTimeMillis();
        System.out.println("Single thread time: " + getLapsedTime(start, end));
        System.out.println("Single thread option has now completed...");
    }
}

You're including time for thread creation and termination; that may be significant. — iggy, Jul 31 '21 at 02:08
is the running variable that is being shared volatile ? https://stackoverflow.com/questions/13582395/sharing-a-variable-between-multiple-different-threads — Mauricio Gracia Gutierrez, Jul 31 '21 at 02:21
@iggy, even if I only time the code after starting the threads, it still gives the same time. — M. Al Jumaily, Jul 31 '21 at 02:26
@MauricioGraciaGutierrez It doesn't seem to change anything. — M. Al Jumaily, Jul 31 '21 at 02:45
@M.AlJumaily I have provided an answer that works as expected (IMHO) — Mauricio Gracia Gutierrez, Jul 31 '21 at 05:06

score 1 · Answer 1 · answered Jul 31 '21 at 05:08

As Ella pointed out, the start and end range calculation for the threads is incorrect. However, the multi-threaded solution still works because at least on of the threads covers the resulting segment.

The most likely cause of the slowness comes from the difference in the loop comparison. Adding the following on every iteration is a huge increase in cost over the simple comparison of the single-threaded solution, especially since it is atomic, which means locking and contention:

Starter.running.get()

score 0 · Answer 2 · answered Jul 31 '21 at 04:45

0

You are dividing the range of numbers among threads, and each thread gets the segment amount of work. Then the start and end indexes for thread i should be:

long start = i * segment;
long end = start + segment - 1;

answered Jul 31 '21 at 04:45

Ella Blackledge

329
1
7

Mauricio Gracia Gutierrez · Answer 3 · 2021-07-31T05:09:12.553

Here are my results after the fixes I describe below

Here is what I did to make it work

Divide the segment to search in the correct way
Since range was not being used inside Searcher I have remove it
Simplify the Searcher class to only keep what it needs to keep
avoid using running and found since the represent the same concept (an element was found)
Instead of having an array of threads to create, run and join, I just run them while I create them
Measure the time correctly, inside the methods

Here is the code

public class Searcher implements Runnable {
    private long threadNumber ;
    private long startIndex;
    private long endIndex;

    public Searcher(long threadNumber, long startIndex, long endIndex) {
        this.threadNumber = threadNumber ;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public void run() {
        long i = startIndex; 
        
        while(i <= endIndex && !Starter.isFound.get()) {
            if (i == Starter.target) {
                Starter.isFound.set(true) ;
                Starter.threadThatFoundIt = this.threadNumber ;
            }
            else {
                i++ ;
            }
        }

        if(Starter.isFound.get()) {
            Thread.currentThread().interrupt();
        }
    }
}

import java.util.concurrent.atomic.AtomicBoolean;

public class Starter {
    public static final AtomicBoolean isFound = new AtomicBoolean(false);
    public static long target;
    public static long threadThatFoundIt ;

    private static void findElementMultithreaded(
            int numberOfThreads, long range
    ) {
        long segment = range / numberOfThreads;

        System.out.println("Multithreaded option has now started...");
        long start = System.currentTimeMillis();

        //create the threads and start them 
        for (int i = 0; i < numberOfThreads ; i++) {
            Searcher s;
            Thread t;

            s = new Searcher(i, i*segment, (i+1)*segment) ;
            t = new Thread(s);
            t.start(); 
        }

        while(!isFound.get()) ; //this could be improved from pooling to firing event or using the join correclty 
        if (isFound.get()) {
            System.out.println(String.format("Thread %d found target %d using multithreading", Starter.threadThatFoundIt, Starter.target)); 
        }
        long end = System.currentTimeMillis();
        System.out.println("Multithreaded time: " + getLapsedTime(start, end));
        System.out.println("Multithreaded option has now completed.\n");
    }

    private static void findElementSingleThread(long size) {
        System.out.println("Single thread option has now started...");
        long start = System.currentTimeMillis();

        for (long i = 0; i < size; i++) {
            if (i == target) {
                System.out.println("Found target using single thread: " + i);
                Starter.isFound.set(true) ;
                break;
            }
        }

        long end = System.currentTimeMillis();
        System.out.println("Single thread time: " + getLapsedTime(start, end));
        System.out.println("Single thread option has now completed...");
    }

    public static String getLapsedTime(long start, long end) {
        long t = end - start;
        long millis = t % 1000;
        long x = t / 1000;
        long seconds = x % 60;
        x /= 60;
        long minutes = x % 60;
        x /= 60;
        long hours = x % 24;
        return String.format(
                "%02dh:%02dm:%02ds.%03d", hours, minutes, seconds, millis
        );
    }


    public static void main(String[] args) {
        int numberOfThreads = 4;
        long size = Integer.MAX_VALUE * 10L;
        Starter.target = (long) (Math.random() * size);
        System.out.println(String.format("Target is: %d using %d threads", target, numberOfThreads));
        
        findElementSingleThread(size);

        findElementMultithreaded(numberOfThreads, size);
    }
}

Finding element using multithreading takes double the time of a single thread

3 Answers3