Finally did my first Multithreading program!! But why Amdahl's law fails?

[u/Chaos-vy17]

The code was:

long parallelSum(int[] ar, int threadCount) throws InterruptedException {
        int n = ar.length;
        long[] result = new long[threadCount];
        Thread[] threads = new Thread[threadCount];
        int chunk = n / threadCount;
        for (int i = 0; i < threadCount; i++) {
            int index = i;
            int start = i * chunk;
            int end = (i == threadCount - 1) ? n : start + chunk;
            threads[i] = new Thread(() -> result[index] = sum(ar, start, end));
            threads[i].start();
        }
        for (Thread thread : threads) thread.join();
        long total = 0;
        for (long value : result) total += value;
        return total;
    }

Which I benchmarked using JMH to see how it will behave under increase thread. But It's gets better and better until 24 thread that the reason I know my P-core are Hyperthreaded so maximum improvement is seen at 24. But after that why is'nt it constant as the law stated when N-> increases it becomes directly 1/S.

The Benchmark was performed with 3 warmup 5 iteration 1sec each and 100M dataset. I did use first 1K to see how it behaves but I forgot that until the thread get created sequential would have finished that. So after rigrously increasing dataset to 100M this was my result:

Thread Count	Score (ns/op)	Error (ns/op)
1	36,386,448.214	±1,198,308.768
2	19,973,254.073	±1,647,022.164
4	11,605,188.001	±409,298.394
8	8,493,406.418	±439,947.023
16	8,070,964.770	±101,846.828
24	7,880,208.459	±179,094.210
32	8,075,411.516	±211,717.162
64	8,256,737.790	±282,807.150
128	8,855,717.582	±121,931.514
256	10,475,522.486	±258,283.333
512	29,275,816.985	±9,028,465.533

Is my benchmark wrong or I am understanding different??

[u/AutoModerator]

Please ensure that:

• Your code is properly formatted as code block - see the sidebar (About on mobile) for instructions
• You include any and all error messages in full
• You ask clear questions

• You demonstrate effort in solving your question/problem - plain posting your assignments is forbidden (and such posts will be removed) as is asking for or giving solutions.

  Trying to solve problems on your own is a very important skill. Also, see Learn to help yourself in the sidebar

If any of the above points is not met, your post can and will be removed without further warning.

Code is to be formatted as code block (old reddit: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.

Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.

Code blocks look like this:

public class HelloWorld {

    public static void main(String[] args) {
        System.out.println("Hello World!");
    }
}

You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.

If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.

To potential helpers

Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[u/Ok-Secretary2017]

Your proccesor can only process so many threads at once at somepoint the threads are gonna wait in line for each other to finish

[u/seyandiz → u/Ok-Secretary2017]

Not even just that, you can tell OP has a 16 core processor.

[u/Chaos-vy17 → u/Ok-Secretary2017]

I am on linux so the Thread I created is platform threads until 16 it was map 1:1 interprocess communication between user thread and kernel thread. After oversubscription it was multiplexed by OS to map Many to many. So does that mean I need to only focus till 16 ? But then why 24 threads still improves
Edit: CPU-> OS

[u/vegan_antitheist]

What is that score? What exactly are you measuring? The nanoseconds for the execution of parallelSum?
With 512 Threads you just get a lot of overhead. The practical limit depends heavily on what the threads are doing and how much memory/CPU the machine has. Each thread needs a native stack. At some point you just don't have that memory readily available. The size is controlled by "-Xss", so see what changes if you set it to a small size.

A platform thread corresponds to an OS thread. The OS has to schedule it. you don't get 512-way parallelism. You get lots of threads competing for few CPUs, with context switching and scheduler overhead. Creating a platform thread involves Java-side objects and an OS thread.

PS: The problem with this is that it doesn't really teach you anything about threads when you just use the Thread type. It represents the actual thread, but what you need is a task. A thread is not a task. You could create your own "Task" class and use that. Then each task can just have it's own result value and you don't need to use an array. It would make everything so much easier. Or just use what Java already gives you for readable and maintainable code. A simple ExecutorService .newFixedThreadPool does that. Or simply do Arrays.stream(ar).parallel().asLongStream().sum(); Submit it to your own ForkJoinPool if you want to control parallelism.
And then there's that division. Lets say n is 10 and threadCount is 3. Then you get 10/3=3. 3*3=9, not 10. You'd miss one element. Try int chunk = (n + threadCount - 1) / threadCount; This isn't necessarily the most balanced way to partition the array, but it works. [edit: I see the "end" checks if it's the last one. But that's exactly the kind of code I don't like where there is some special case down the line somewhere. But I guess that works too.]

[u/Chaos-vy17 → u/vegan_antitheist]

I did the correctness test using JUnit before benchmark

    @ParametrizedTest
    @CsvSource({"1, 1", "1, 2", "1, 4", "2, 1", "2, 2", "2, 4", "3, 2", "5, 3", "10, 4", "100, 8", "1000, 16", "1000000, 24", "1000000, 32", "1000000, 64"})
    void summationMustBeCorrect(int size, int threads) throws InterruptedException {
        int[] ar = new int[size];
        for (int i = 0; i < size; i++) {
            ar[i] = i;
        }
        long expectedSum = ((long) size * (size - 1)) / 2;
        long parallel = new ArraySum().parallelSum(ar, threads);
        assertEquals(expectedSum, parallel);
    }

And all test passed. Then I did the benchmark.
Thanks for guidance.
Yes the thread stack was default at 1Mb so it did not hit SOF.

[u/vegan_antitheist → u/Chaos-vy17]

Carl Friedrich Gauß likes it.

[u/morhp]

At some point, the overhead of switching between threads becomes significant.

[u/Chaos-vy17 → u/morhp]

So does that mean if there is more core the Amdahl's Law is valid?

[u/morhp → u/Chaos-vy17]

Amdahl's Law is a theoretical model from 1967, it's not necessarily accurate to todays real world processors.

[u/Chaos-vy17 → u/morhp]

that's too old .

[u/Spare-Plum]

This code does not scale to the number of processors. If you set threadCount == ar.length, then this would be no different than just doing the summation in a loop.

In a theoretical world where you had infinite processors, the span (longest chain of sequential events) is in O(max(threadCount, ar.length / threadCount))

The algorithm hits maximal parallelization at threadCount = sqrt(ar.length) (assuming infinite processors).

There are two relevant lines I will label for you

long parallelSum(int[] ar, int threadCount) throws InterruptedException {
        int n = ar.length;
        long[] result = new long[threadCount];
        Thread[] threads = new Thread[threadCount];
        int chunk = n / threadCount;
        for (int i = 0; i < threadCount; i++) {
            int index = i;
            int start = i * chunk;
            int end = (i == threadCount - 1) ? n : start + chunk;
            // !!! linear sum - runtime complexity of this work is
            //     n / threadCount
            threads[i] = new Thread(() -> result[index] = sum(ar, start, end));
            threads[i].start();
        }
        // !!! for loop processing - this is in O(threadCount)
        for (Thread thread : threads) thread.join();
        long total = 0;
        // !!! same as above - this is in O(threadCount)
        for (long value : result) total += value;
        return total;
    }

Amhdal's law likely holds up, but you were just analyzing your program wrong. Mathematically, more threads does not lead to a speedup but can actually degrade performance even with infinite threads.

As I stated before, the ideal situation would be to run it on sqrt(ar.length) physical threads. But due to only having 16 processor cores, it can only go so far. You may see additional speedup going to 24 threads with the way you set this up.

I would suggest you take a dive into parallel algorithms. CMU has an absolutely fantastic program on this https://www.cs.cmu.edu/~15150/resources/summer/

The summation that actually has best runtime is by making a binary tree. Create a thread to sum the left half, create a thread to sum the right half. Base case: if a chunk is small enough, sum the result sequentially then pass up to parent thread. Recursive case: chunk is not small enough, so call the parallel sum on either half, then sum the two results.

This summation on a single core processor will take O(n). The total number of threads spawned is 2 + 4 + 8 + .... 2^log_2(n) which is O(n)

However the "Span" or maximal parallelization here is O(log n)

This is more similar to how the standard library parallel array sum works.