Bài viết nằm trong series Multithread từ hardware tới software với Java.
Câu hỏi 1: từ các bài trước, khi chia các bài toán ra thành nhiều phần có thể xử lý đồng thời và implement với multi-thread sẽ nhanh hơn single-thread. Vậy nhanh hơn bao nhiêu lần, làm thế nào để tính được con số cụ thể hoặc gần đúng nhất?
Câu hỏi 2: lập trình multi-thread có thật sự nhanh hơn single-thread không?
Bài viết này sẽ giải đáp 2 mối bận tâm trên. Let's begin!
1) Computational graph
Điều quan trọng khi lập trình multi-thread là xác định các bước có thể thực thi đồng thời, sau đó kết nối chúng để ra kết quả cuối cùng với mục đích tận dụng tối đa parallel execution.
Các bước đó cần được mô hình hóa để dễ dàng hình dung/implement và computational graph sẽ giúp ích trong tình huống này.
Mình sẽ sử dụng lại bài toán salad để lấy ví dụ cho phần này. Các step có thể làm đồng thời là cắt kiwi, cà rốt, rau củ. Sau đó trộn tất cả nguyên liệu lên và thêm sốt. Mỗi step là một task cần phải thực thi, ta gọi chúng là unit of work hoặc unit of execution.
Với computational graph, chúng được biểu diễn như sau:
- Mỗi task là một node.
- Mũi tên chỉ thứ tự thực hiện của các task.
- Task chỉ được thực hiện khi toàn bộ các task phía trước đã hoàn thành.
Graph dưới cho biết tất cả các task được thực hiện tuần tự, là single path execution, có thể implement với single thread.
Tất nhiên để tối ưu lợi thế của parallel execution, các task cắt kiwi, rau củ có thể thực hiện asynchronous với nhau, thực hiện theo bất kì thứ tự nào, thời gian bao lâu cũng không ảnh hưởng đến kết quả cuối ?.
Với graph trên, ta chia các task có thể thực thi concurrent và chạy với các thread khác nhau. Tuy nhiên, tất cả đều phải hoàn thành thì task tiếp theo mới được thực thi. Sẽ có 2 cặp từ khóa cần chú ý:
- Spawn & Sync
- Fork & Join
Cả 2 cặp từ khóa trên đều diễn tả việc tách các công việc có thể thực hiện concurrent ra và thực thi trên các thread khác nhau. Sau khi xong sẽ tổng hợp lại kết quả, làm các bước tiếp theo nếu có. Nếu dùng Java 8 trở lên ắt hẳn bạn đã quen thuộc với tream và parallelStream, parallelStream bên dưới sử dụng ForkJoinFramework của Java.
Có rất nhiều cách khác nhau để vẽ computational graph, tuy nhiên mục đích chung của nó là cung cấp cái nhìn tổng quan khi chương trình được thực thi:
- Mối quan hệ của các task.
- Task nào có thể thực thi đồng thời.
2) Parallel ratio
Ngoài 2 mục đích trên, computational graph cũng được dùng để diễn tả các phần của chương trình được thực thi song song như thế nào.
Với mỗi một task phía trên, mình sẽ chuyển nó thành thời gian để các task hoàn thành. Ví dụ như sau.
Với single-processor, tổng thời gian hoàn thành các task chính là tổng thời gian thực thi của mỗi task, bằng 90 (đơn vị thời gian). Bạn có đặt ra vì sao multi-thread nhưng vẫn cộng tổng như vậy không? Nếu không thì chúc mừng, bạn đã nắm rõ bài học. Lý do: mặc dù multi-thread nhưng do single-processor, bản chất vẫn chỉ thực thi duy nhất một thread tại một thời điểm.
Với graph trên, ta có thể tìm được đường đi dài nhất là 3, 20, 5, 19, 14. Nó được gọi là critical path, diễn tả đường đi dài nhất, một chuỗi của các task nối liền nhau trong chương trình. Tổng thời gian thực thi của critical path là 61. Mặc dù là đường đi dài nhất nhưng nó diễn tả tổng thời gian ngắn nhất để hoàn thành công việc nếu chương trình được thực thi song song ở mức tối đa (cần multiple-processors).
Từ đó, chúng ta có công thức để tính toán được tỉ lệ tối đa mà một chương trình được xử lý song song (parallel ratio) khi được thực thi với multi-processor và single-processor.
Con số 1.48 nói lên điều gì? Trong trường hợp lý tưởng, chương trình trên chạy trên multi-processor sẽ nhanh hơn single-processor tối đa 1.48 lần.
Trong software programming, khá khó để giảm tổng thời gian xử lý các task, do đó ta cần thiết kế chương trình sao cho giảm tối đa thời gian xử lý critical path.
Như vậy, đã trả lời được câu hỏi thứ nhất ở đầu bài.
3) Trả lời câu hỏi thứ hai
Thứ nhất, như các bạn thấy ở trên, mặc dù multi-thread nhưng nếu thực thi trên single processor thì còn chậm hơn single-thread với single processor. Ngoài ra, ta cần fork và join các task lại với nhau, điều đó cũng sẽ tốn thời gian.
Thứ hai, nếu độ phức tạp của các task rất nhỏ, thời gian thực thi rất nhanh thì việc tách ra multi-thread sẽ chậm hơn so với single-thread, công sức cho context switch lớn hơn cả công sức cho việc thực thi tính toán. Code ví dụ cho thật, nói mồm ai tin.
Mình sẽ thực hiện tăng biến COUNTER từ 0 lên 100 * 10^6.
public class SingleThread { static long COUNTER = 0; public static void main(String... args) { long start = System.currentTimeMillis(); for (int i = 0; i < 100_000_000; i++) { ++COUNTER; } long end = System.currentTimeMillis(); System.out.println("Executed in: " + (end - start)); System.out.println(COUNTER); }
}
Với single-thread, mất khoảng 10 ms để có kết quả.
public class MultiThread { static long COUNTER = 0; public static void main(String... args) throws InterruptedException { var threads = IntStream .range(0, 100) .mapToObj(ignore -> new Thread(() -> { synchronized (MultiThread.class) { for (int i = 0; i < 1_000_000; i++) { ++COUNTER; } } })).collect(Collectors.toList()); long start = System.currentTimeMillis(); threads.forEach(Thread::start); for (var thread : threads) { thread.join(); } long end = System.currentTimeMillis(); System.out.println("Executed in: " + (end - start)); System.out.println(COUNTER); }
}
Với multi-thread cụ thể là 100 thread,mất khoảng 30 ms để xử lý. Lý do như mình đã trình bày phía trên.
Trong thực tế các task đều phức tạp nên khi lập trình multi-thread sẽ tận dụng được sức mạnh của multi-processor. Với các bài toán đơn giản thì single-thread đôi khi lại là giải pháp tốt hơn.
Ngoài ra, cách đặt vị trí variable (class/instance/local variable) cũng ảnh hưởng đến hiệu suất của bài toán. Nó liên quan đến cách quản lý bộ nhớ trong Java (sẽ có series riêng về phần này).
No silver bullet, ta cần linh hoạt áp dụng các cách triển khai và xử lý để đạt hiệu quả tối ưu. Bài tiếp theo sẽ bàn luận về performance khi lập trình multi-thread.
Reference
- https://en.wikipedia.org/wiki/Flynn's_taxonomy
- https://www.javatpoint.com/memory-management-in-java
- https://www.tutorialspoint.com/difference-between-process-and-thread
- http://tutorials.jenkov.com/java-concurrency/concurrency-vs-parallelism.html
© Dat Bui