Giter VIP home page Giter VIP logo

psychic-thread-adventure's Introduction

psychic-thread-adventure

What's the difference between sorting different counts of numbers using multiple threads and sorting them single threaded, in terms of time needed to sort the numbers?

This project discovers how threading influences performance of simple algorithms like Mergesort algorithm. Besides that the effort will be documented what needs to be done to make a program run with multiple threads w/o using frameworks. Maybe some tests will be done using Java 8 later on.

Inspired by Robert C. Martin's (et al.) Clean Code, 2009, Pearson Education, Inc, chapter on concurrency.

Additional Information

Micro Benchmarking libraries

Concurrency and Distribution Framework

Adventure Experience

To run the measuring on your machine, please runAdventure.java as JUnit test.

gradle clean test --tests *Adventure

Run the akka version like this:

clean compile exec:java -Dexec.mainClass=de.bschandera.tryouts.MergesortThreadedWithAkka

Adventure Planning

Threading constellations

  • without threading, i.e., one execution path, no branching

    • consider different n and different machines

  • few threads (fix number of threads)

    • consider different #Threads, different n and different machines

  • dynamically created threads according to high/low n

    • consider different n and different machines

  • (probably) M. written in functional style, oriented towards this article

  • different number of threads

    • #Threads 2
    • #Threads 3
    • #Threads 4
    • #Threads 8

  • different ns

    • 4.000,
    • 16.000,
    • 32.000 and

  • on different machines

Results

NOTE: Merge sort's average case performance is O(n log n)

NOTE: Limits of concurrency gains: The runtime is limited by parts of the task which can be performed in parallel. The theoretical possible performance gain can be calculated by the following rule which is referred to as Amdahl's Law (thank you vogella).

If F is the percentage of the program which can not run in parallel and N is the number of processes, then the maximum performance gain is 1 / (F + ((1-F)/n)). So making at most code parallel as possible leads to highest performance gain!

2015-04-22 - My MacBook Pro (2 cores, Intel Core i7, 16GB RAM)

Adventure.sort4000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.01 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 0.16, time.warmup: 0.05, time.bench: 0.11
Adventure.sort4000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.00 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 0.07, time.warmup: 0.02, time.bench: 0.04
Adventure.sort16000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.14 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 1, GC.time: 0.00, time.total: 2.02, time.warmup: 0.67, time.bench: 1.35
Adventure.sort16000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.04 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 0, GC.time: 0.00, time.total: 0.57, time.warmup: 0.20, time.bench: 0.37
Adventure.sort32000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.53 [+- 0.03], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 2, GC.time: 0.01, time.total: 7.93, time.warmup: 2.64, time.bench: 5.29
Adventure.sort32000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.14 [+- 0.00], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 2, GC.time: 0.00, time.total: 2.11, time.warmup: 0.71, time.bench: 1.40
Adventure.sort64000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 2.31 [+- 0.39], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 3, GC.time: 0.01, time.total: 33.61, time.warmup: 10.52, time.bench: 23.09
Adventure.sort64000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.55 [+- 0.02], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 3, GC.time: 0.02, time.total: 8.47, time.warmup: 2.94, time.bench: 5.52
Adventure.sort128000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 8.72 [+- 1.40], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 56, GC.time: 0.18, time.total: 129.65, time.warmup: 42.42, time.bench: 87.24
Adventure.sort128000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 2.29 [+- 0.36], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 27, GC.time: 0.14, time.total: 34.22, time.warmup: 11.32, time.bench: 22.90
Adventure.sort256000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 32.85 [+- 2.82], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 35, GC.time: 0.34, time.total: 479.17, time.warmup: 150.64, time.bench: 328.53
Adventure.sort256000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 7.97 [+- 0.58], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 11, GC.time: 0.12, time.total: 123.88, time.warmup: 44.23, time.bench: 79.65

2014-12-12/13 #2 - My HP machine (2 cores AMD Sempron, 3GB RAM)

Adventure.sort4000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.04 [+- 0.01], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 11, GC.time: 0.02, time.total: 0.67, time.warmup: 0.24, time.bench: 0.44

Adventure.sort4000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.02 [+- 0.01], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 10, GC.time: 0.02, time.total: 0.28, time.warmup: 0.10, time.bench: 0.19

Adventure.sort16000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.79 [+- 0.21], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 46, GC.time: 0.09, time.total: 11.83, time.warmup: 3.86, time.bench: 7.96

Adventure.sort16000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.24 [+- 0.02], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 49, GC.time: 0.13, time.total: 3.63, time.warmup: 1.21, time.bench: 2.43

Adventure.sort32000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 7.11 [+- 1.96], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 103, GC.time: 0.21, time.total: 106.37, time.warmup: 35.30, time.bench: 71.07

Adventure.sort32000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 1.78 [+- 0.48], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 99, GC.time: 0.29, time.total: 24.51, time.warmup: 6.72, time.bench: 17.79

Adventure.sort64000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 32.24 [+- 9.77], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 220, GC.time: 0.60, time.total: 481.48, time.warmup: 159.11, time.bench: 322.37

Adventure.sort64000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 14.94 [+- 2.25], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 222, GC.time: 0.75, time.total: 223.85, time.warmup: 74.43, time.bench: 149.42

2014-12-12/13 #1 - My HP machine (2 cores AMD Sempron, 3GB RAM)

AdventureTest.sort4000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.04 [+- 0.01], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 11, GC.time: 0.02, time.total: 0.63, time.warmup: 0.20, time.bench: 0.42

AdventureTest.sort4000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.02 [+- 0.01], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 11, GC.time: 0.02, time.total: 0.38, time.warmup: 0.17, time.bench: 0.20

AdventureTest.sort16000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.75 [+- 0.02], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 48, GC.time: 0.08, time.total: 11.26, time.warmup: 3.77, time.bench: 7.49

AdventureTest.sort16000Numbers2Threads: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.26 [+- 0.05], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 51, GC.time: 0.20, time.total: 3.88, time.warmup: 1.36, time.bench: 2.52

2014-12-10 - My HP machine (2 cores AMD Sempron, 3GB RAM)

AdventureTest.sort4000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.04 [+- 0.01], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 12, GC.time: 0.01, time.total: 0.62, time.warmup: 0.20, time.bench: 0.42

AdventureTest.sort16000Numbers1Thread: [measured 10 out of 15 rounds, threads: 1 (sequential)]
 round: 0.77 [+- 0.09], round.block: 0.00 [+- 0.00], round.gc: 0.00 [+- 0.00], GC.calls: 51, GC.time: 0.07, time.total: 11.78, time.warmup: 4.05, time.bench: 7.73

Effort Notes

  • Find out what part of the program ist really cost expensive
  • change your mind. Even the program flow has to be in a parallel manner. Dont wait for one thread to finish before calling another one.
  • Cope with the slightly different way of handling results that are calculated by different threads.
  • separate application logic from thread logic

psychic-thread-adventure's People

Contributors

husterknupp avatar

Watchers

avatar avatar avatar

psychic-thread-adventure's Issues

How to display results?

I want to show the results of the sorting. For details see #4. These information should be displayed in an easy to understand manner. It will be sufficient to have the results in text form for now. The code will provide required data in a log file.

Implement Simple Multithreaded Version (duplicate)

I want to have a way to run the algorithm in multiple threads. In a second step I want to be able to set the number of threads. The algorithm should use exactly this set numbers of threads for the calculation.

Provide performance statistics

As discussed in #3 for now, it will be sufficient to simply log the required information.

Problem
No information on any statistic can be consulted, yet.

Solution
Find reasonable positions in the program where to log statistics and do the logging. Use a logging library like log4j.

Acceptance Criterium

  • automated descriptions can be found on System.out that reflect the sorting scenario.
  • one of the libraries suggested below should be used to measure performance (use JUnitBenchmarks)

Implement Simple Multithreaded Version

Problem
No multithreaded sorting can be benchmarked, yet.
Solution
Based on the single threaded Version of Mergesort I would like to have a way to run the algorithm in multiple threads. In a second step I want to be able to set the number of threads. The algorithm should use exactly this set numbers of threads for the calculation.
Acceptance Criteria
Results of sorting different counts of numbers using two threads can be found in the log.

Implement Mergesort (no multithreading)

Problem
No algorithm can be used to measure anything, yet.

Solution
Implement Mergesort algorithm using Java. Do not split execution paths in threads at this point. Develop test driven.

Acceptance Criteria

  • Algorithm/method is tested with a numerical sequence of at least 10 numbers
  • All tests run

It will be sufficient for the algorithm to be runnable from within an IDE.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.