Multi-thread performance in Java when working with a list

Question

I'm new to the multi-threading concept and I'm creating a simple Java program to experience with multiple threads and stuff.
In my program, I simply have a linked list, and I create a thread to just remove list items from the beginning. I implement the Runnable interface and this is what the run method of my thread looks like: (I set list in the constructor)

public void run() {
    System.out.println("Starting...");

    while (!list.isEmpty()) {
        synchronized (list) {
            list.removeFirst();             
        }
    }

    System.out.println("Finished!");
}

In the main method, I add a huge number of items to the linked list (10,000,000) and simply create instances of this class to run concurrently and I measure the time:

    Thread my1 = new Thread(new MyThread("my1", list));
    Thread my2 = new Thread(new MyThread("my2", list));
    Thread my3 = new Thread(new MyThread("my3", list));

    startTime = System.currentTimeMillis();
    my1.start();
    my2.start();
    my3.start();
    my1.join();
    my2.join();
    my3.join();
    endTime = System.currentTimeMillis();
    elapsedTime = endTime - startTime;

    System.out.println("Main finished in " + elapsedTime + " milliseconds.");

Interestingly enough, when I run my program using these 3 threads, I receive the message:

Main finished in 444 milliseconds

But, when I use only a single thread, I receive the message:

Main finished in 223 milliseconds

Is there anyway I can tweak the code to run actually faster when using multiple threads???

Thank you in advance

just loose all the reference by list = null; why do you want to remove elements one by one if your purpose is to remove all faster — Jigar Joshi
– Jigar Joshi, Commented Jul 11, 2014 at 23:02
as soon as you're using synchronized - you're gaining nothing from different threads, only making it worse because of synchronization, basically you usually gain nothing in case of shared resources as in this example — Iłya Bursov
– Iłya Bursov, Commented Jul 11, 2014 at 23:04
also, the list.empty() test outside of the synch block is not thread-safe. — jtahlborn
– jtahlborn, Commented Jul 11, 2014 at 23:14
In my main problem, the list holds objects that determine an action to be made (add or find elements in a tree)... I have to read these objects and perform the required actions until the list is empty... I cannot figure out how I can use multiple threads to improve performance... — Farzad
– Farzad, Commented Jul 11, 2014 at 23:27
Are those operations demonstrably expensive? Are they independent, or do they depend on previous outputs. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Jul 12, 2014 at 4:08

Justin Kaeser · Accepted Answer · 2014-07-11 23:12:34Z

2

This example cannot benefit from multiple threads, on the contrary: You are adding overhead by synchronizing access to the list, so that only one thread can access it at a time. While this is necessary for correctness, the actual operation is so low-overhead that the synchronization dominates.

This scenario could make sense if your worker threads did some expensive computation or I/O with the data from the list. If that is the actual goal, you should include this in your benchmark.

answered Jul 11, 2014 at 23:12

Justin Kaeser

5,97830 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Farzad Over a year ago

Actually, this was a practice for a bigger problem for my programming assignment in which list items are objects that we should read and do something based on their properties (more precisely, find or add elements in a tree)... There has to be a way to improve performance, but nothing comes to my mind

Justin Kaeser Over a year ago

The "doing something" part might be what actually benefits from multiple threads. Would they all work on the same tree?

Farzad Over a year ago

I'll try to be concise: I have a search tree initially containing items. I'm supposed to create a list of "Tasks" that can do two things: search for an item or add an item. I need to use multiple threads to read these "Tasks" from the list and do their jobs until the list is empty, and finally output the resulting tree to show that the "add"s have been applied

chrylis -cautiouslyoptimistic- · Accepted Answer · 2014-07-11 23:45:36Z

0

You've run into what's called the critical path, the portion of the code that has to be be properly ordered and thus can't be parallelized. In this example, the critical path is most of your program, so you won't gain anything by trying to use multiple threads. Multiple threads provide a benefit only when they do a substantial amount of work (I/O, localized computation) that's independent.

answered Jul 11, 2014 at 23:45

chrylis -cautiouslyoptimistic-

77.5k21 gold badges127 silver badges167 bronze badges

1 Comment

Farzad Over a year ago

I briefly described the thing I need to do in the comment above... I was thinking about the problem and I started with manipulating this simple list to get the idea, but I still don't know how I can improve the speed

Collectives™ on Stack Overflow

Multi-thread performance in Java when working with a list

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related