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ó thật sự nhanh hơn single-thread không?

Câu hỏi 3: số lượng thread nên bao nhiêu là đủ?

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) Multi-threading có nhanh hơn Single-threading không?

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.

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 đó, việc áp dụng multi-threading với I/O bound task không cải thiện tăng tốc độ thực thi, thậm chí còn làm chương trình xử lí tác vụ chậm hơn.

Nhưng chắc chắn nó vẫn đem lại 2 lợi ích vô cùng thiết thực:

• Multi-threading với I/O bound task giúp 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.
• Multi-threading giúp handle được nhiều request hơn trong một thời điểm. Ví dụ nếu có 3 request mà chỉ có một thread thì 2 request đến sau phải chờ, nhưng nếu có 3 thread thì tất cả các request đều được xử lý đồng thời.

4) Bao nhiêu thread là đủ?

Làm một ví dụ đơn giản, cho folder chứa một danh sách các file. Nhiệm vụ là đếm số lượng kí là chữ cái latin (a-z, A-Z) xuất hiện tổng cộng bao nhiêu lần?

Xử lí với single-threading và multi-threading để thấy sự khác biệt, đồng thời tuning số lượng thread để trả lời câu hỏi đầu bài.

4.1) Single thread

Xử lí với single thread thì chẳng có gì để bàn, cứ tuần tự mà làm thôi.

4.2) Multi thread

Tất nhiên là phải code luôn multi thread thì mới compare được. Phân tích nhanh thì concurrent task sẽ là kiểm tra một string xem số lần xuất hiện của các kí tự là bao nhiêu. Các string có thể là một kí tự, một từ, một dòng, một file.

Bây giờ là đến việc tính toán số lượng thread như thế nào, phân chia task ra sao, hàng loạt các câu hỏi hiện lên trong đầu…

• Đọc file, mỗi dòng đẩy cho 1 thread xử lý có ổn không? Hay 1 thread xử lí cả đoạn văn, hay là 1 file luôn?
• Nếu tạo ít thread quá, có 2 3 cái mà có tận 16 files thì có chậm không?
• Hay mỗi file sinh ra một thread xử lí thì sao nhỉ? Nhưng lỡ có vài trăm vài nghìn files thì cũng không ổn?

Đi vào phân tích kĩ hơn, có 2 task chính cần thực hiện:

• I/O bound task: đọc file, lấy data để xử lý. Vì là I/O bound task nên cố gắng tối đa số lượng thread để read được càng nhiều data càng tốt.
• CPU bound task: kiểm tra kí tự có là chữ cái latin hay không. Theo như mớ lý thuyết ở trên, chỉ cần tạo ra một thread là đủ.

Tiếp theo, phân tích về architecture, có thể tiếp cận với 2 cách sau:

• Mô hình Actor: tạo thread pool để read data, sau đó đẩy data sang một thread chuyên để xử lí kí tự, giao tiếp với nhau qua blocking queue.
• Mô hình fork join: vẫn là tạo thread pool, nhưng các thread sẽ làm từ đầu đến cuối cho một file, bao gồm read data và xử lí kí tự. Sau khi tất cả hoàn tất sẽ tổng hợp data.

Quẩy luôn cả 2 cách và tiến hành run code so sánh.

3) Run

Source code các bạn có thể tham khảo kĩ hơn tại đây nhé. Mình sẽ tạo ra tổng cộng 9 scenario để có thể dễ dàng so sánh và kiểm chứng mớ lí thuyết của series này.

• Single thread
• Fork Join với lần lượt 2, 4, 8 và 16 threads.
• Actor cũng với lần lượt 2, 4, 8 và 16 threads.

Cấu hình máy chạy test là CPU Intel i7-1165G7 4 cores - 8 threads.

public class Application {

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            System.out.println("New round ------------------------------------ ");
            execute(new SingleThreadCountingService(), args[0], "Single thread: \t\t\t");
            execute(new ForkJoinCountingService(2), args[0], "ForkJoin 02 thread: \t");
            execute(new ForkJoinCountingService(4), args[0], "ForkJoin 04 thread: \t");
            execute(new ForkJoinCountingService(8), args[0], "ForkJoin 08 thread: \t");
            execute(new ForkJoinCountingService(16), args[0], "ForkJoin 16 thread: \t");
            execute(new ActorCountingService(2), args[0], "Actor 02 thread: \t\t");
            execute(new ActorCountingService(4), args[0], "Actor 04 thread: \t\t");
            execute(new ActorCountingService(8), args[0], "Actor 08 thread: \t\t");
            execute(new ActorCountingService(16), args[0], "Actor 16 thread: \t\t");
        }
    }

    private static void execute(CharacterCountingService service, String dir, String message) {
        service.count(dir);
        System.out.printf("%s %15d %n", message, service.getExecutedTimeInNanos());
    }

}

Mình chạy tổng cộng 5 lượt để đưa ra đánh giá khách quan nhất. Lưu ý rằng kết quả của round đầu tiên sẽ bỏ qua vì cần warm-up code.

Đầu tiên, với folder data-1, kết quả như sau (bỏ round đầu tiên):

New round ------------------------------------ 
Single thread:          3455551600 
ForkJoin 02 thread:     1948649200 
ForkJoin 04 thread:     1314783500 
ForkJoin 08 thread:     1203243500 
ForkJoin 16 thread:     1242951800 
Actor 02 thread:        3092987600 
Actor 04 thread:        3130461000 
Actor 08 thread:        3139415900 
Actor 16 thread:        3135735200 
New round ------------------------------------ 
Single thread:          3448729400 
ForkJoin 02 thread:     1887355700 
ForkJoin 04 thread:     1330755100 
ForkJoin 08 thread:     1192182800 
ForkJoin 16 thread:     1233279900 
Actor 02 thread:        3113192000 
Actor 04 thread:        3131072800 
Actor 08 thread:        3130556300 
Actor 16 thread:        3196362400 
New round ------------------------------------ 
Single thread:          3531286300 
ForkJoin 02 thread:     1956214700 
ForkJoin 04 thread:     1298034700 
ForkJoin 08 thread:     1213541000 
ForkJoin 16 thread:     1254718100 
Actor 02 thread:        3112010700 
Actor 04 thread:        3199576800 
Actor 08 thread:        3114821800 
Actor 16 thread:        3150662900 
New round ------------------------------------ 
Single thread:          3497896900 
ForkJoin 02 thread:     1985285900 
ForkJoin 04 thread:     1314125300 
ForkJoin 08 thread:     1216979700 
ForkJoin 16 thread:     1211707400 
Actor 02 thread:        3148100900 
Actor 04 thread:        3304655300 
Actor 08 thread:        3183578200 
Actor 16 thread:        3382464400

Tổng quan về kết quả thì Fork Join 8 thread là chạy tốt nhất.

Từ đây, lí thuyết đầu tiên đã được kiểm chứng. Quá ít hoặc quá nhiều thread đều không đem lại kết quả tối ưu. Tốt nhất số thread nên bằng số lượng cores. Vì thứ thực sự thực thi task chính là core/processor chứ không phải thread.

Tiếp theo, về lí thuyết thì Actor nên có tốc độ xử lí tốt hơn ForkJoin, nhưng vì sao thực tế không phải vậy? Mặc dù việc check character là CPU bound task nhưng chúng ta có đến hàng chục kí tự trong tất cả các files. Mà việc tính toán này lại chỉ thực hiện trên single thread thì chậm là đúng. Đáng lí phải xử lý giống như ForkJoin, nhiều thread thực hiện check character và chỉ cần 1 thread để read data từ file là đủ.

Tuy nhiên, kết quả của nó vẫn tốt hơn SingleThread vì việc read file được thực thi trên multi thread.

Bây giờ thay đổi dữ liệu một chút, chúng ta sẽ xử lý với folder này (8 files, trung bình 500 kí tự một file). Thử đoán kết quả trước khi xem tiếp nhé…

New round ------------------------------------ 
Single thread:          1779600 
ForkJoin 02 thread:     1777900 
ForkJoin 04 thread:     1158000 
ForkJoin 08 thread:     1573700 
ForkJoin 16 thread:     1579400 
Actor 02 thread:         162900 
Actor 04 thread:         220200 
Actor 08 thread:         268000 
Actor 16 thread:         514400 
New round ------------------------------------ 
Single thread:          1774100 
ForkJoin 02 thread:     1501900 
ForkJoin 04 thread:     1219700 
ForkJoin 08 thread:     1748500 
ForkJoin 16 thread:     2140700 
Actor 02 thread:         275400 
Actor 04 thread:         169300 
Actor 08 thread:         352100 
Actor 16 thread:         258000 
New round ------------------------------------ 
Single thread:          1853600 
ForkJoin 02 thread:     1710100 
ForkJoin 04 thread:     1190200 
ForkJoin 08 thread:     1319800 
ForkJoin 16 thread:     1631500 
Actor 02 thread:         121000 
Actor 04 thread:         520700 
Actor 08 thread:         131900 
Actor 16 thread:         112200 
New round ------------------------------------ 
Single thread:          1253200 
ForkJoin 02 thread:     1301600 
ForkJoin 04 thread:     1866300 
ForkJoin 08 thread:     1717900 
ForkJoin 16 thread:     1826500 
Actor 02 thread:         141500 
Actor 04 thread:          98100 
Actor 08 thread:         200100 
Actor 16 thread:          84900 

Và.. một sự bất ngờ không hề nhẹ.

• SingleThread thỉnh thoảng có kết quả tốt hơn ForkJoin (multi thread).
• Actor lúc này cho kết quả tốt nhất.

Giải thích vô cùng đơn giản như sau:

• Số lượng kí tự ít, đồng nghĩ với việc các CPU bound task nhỏ. Việc thực thi trên single thread đem lại kết quả tốt vì cost cho switch context nhỏ hơn rất nhiều so với multi thread.
• CPU bound task thấp, nên single thread là đủ để thực hiện nhiệm vụ. Tuy nhiên lúc này còn I/O bound task đọc data từ file, lúc này sử dụng multi thread là một lựa chọn cực kì hợp lí. Vì vậy mà lúc này Actor phát huy tối đa tác dụng!

5) Kết luận

Chắc cũng không cần thêm gì nhiều vì toàn bộ ví dụ trên đã giải thích tất cả.

• Không phải cứ nhiều thread đã là nhanh.
• Không phải single thread đều chậm hơn multi thread.
• Điều quan trọng là biết vận dụng đúng cách, phân chia task hợp lí để đạt hiệu quả tốt nhất.

Reference

• https://hackmd.io/@datbv/r1uoC54Kd#Reference

After credit

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.

© Dat Bui