Viblo Learning
+23

013: Lập trình multi-thread có thật sự nhanh hơn single-thead?

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ó tốt hơn single-thread không và tốt hơn trong trường hợp nào?

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 treamparallelStream, 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 path61. 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-processorsingle-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 forkjoin 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.

Cụ thể, dựa trên các đặc điểm tương tác của task mà phân chia ra làm 2 loại là:

  • I/O bound task.
  • CPU bound task.

CPU bound task

CPU bound nói về task được thực hiện đa phần với processor ví dụ:

  • Thao tác phép tính với các con số: +, -, *, /.
  • Sắp xếp các phần tử trong array.
  • Đảo ngược một ma trận...

Tốc độ xử lý các bài toán này chủ yếu dựa trên sức mạnh của processor. Processor càng mạnh tốc độ xử lý càng nhanh, càng nhiều processor thì các CPU bound task được thực thi càng nhanh.

Do đó, multi-threading với các task này sẽ tận dụng được khả năng parallel execution giúp chương trình được thực thi nhanh hơn. Và nó chỉ thực sự phát huy tác dụng khi các task là concurrent task, không phải là sequence task giống như ví dụ ở trên nhé.

I/O bound task

I/O bound nói về task mang tính chất tương tác với các hệ thống bên ngoài. Ví dụ:

  • Gọi ra các service bên ngoài thông qua internet ví dụ như TCP, UDP, HTTP...
  • Tương tác với database: đọc/ghi dữ liệu.
  • Tương các với hệ thống file.

Với bài trước, ta biết rằng tốc độ xử lý của processor là cực nhanh, hơn gấp nhiều lần tốc độ internet, HDD, SSD hay RAM. Do đó, tốc độ xử lý của chương trình không phụ thuộc và processor mà lúc này phụ thuộc vào tốc độ đường truyền internet, tốc độ đọc/ghi của ổ đĩa (I/O computation).

Do đó, nếu áp dụng multi-threading với các task này, việc gia tăng tốc độ gần như không đáng kể, thậm chí còn làm chương trình chậm đi.

Tuy nhiên nó vẫn có lợi ích nhất định, multi-threading trong trường hợp này giúp chúng ta thực hiện asynchronize task, thay vì chờ response từ client (service/database), ta sẽ thực hiện task đó trên thread khác tránh gây block cho main thread từ đó giúp chương trình chạy mượt mà 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).

Không phải bài toán nào áp dụng multi-thread programming cũng thành công mà cần dựa trên tính chất và cách phân chia bài toán, mình sẽ nói cụ thể ở bài sau. 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

Reference in series: https://viblo.asia/s/multithread-programming-tu-hardware-toi-software-voi-java-QqKLvp2rl7z

© Dat Bui


All Rights Reserved

Viblo
Let's register a Viblo Account to get more interesting posts.