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/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.