Heap dump trong Java

Đối với các bạn làm backend thì rất có thể sẽ gặp tình huống là khi ứng dụng Java của chúng ta chạy một thời gian, nó sẽ ngốn rất nhiều RAM và càng chạy lâu  thì ngốn càng nhiều hay thậm chí là bị lỗi OutOfMemory. Đến lúc này, việc chúng ta cần làm đó là điều tra nguyên nhân. Để làm được điều này chúng ta cần xem được tại các thời điểm trên, các object nào là nhiều nhất và tốn nhiều bộ nhớ nhất. Java có hỗ trợ chúng ta việc này bằng cách tạo file heap dump. Do đó:

Heap dump là file ghi lại toàn bộ các object của chương trình được tạo ra khi chương trình đang chạy tại một thời điểm.

Có 2 cách để tạo file heap dump:

1. Tự động tạo file heap dump khi chương trình bị OutOfMemory

Chúng ta chỉ cần truyền vào tham số cho JVM:

-XX:+HeapDumpOnOutOfMemoryError -XX:HeapDumpPath=<path to this heap dump file>

Nếu chương trình của bạn bị lỗi OutOfMemory, bạn có thể sử dụng cách này để tạo file heap dump. Tuy nhiên, cách này không được khuyến khích, vì chúng ta cần phải chủ động phân tích bộ nhớ trước khi để xảy ra lỗi bằng cách:

2. Tạo file heap dump manual

Đầu tiên các bạn cần xác định pid của ứng dụng bằng cách sử dụng cmd:

ps -ef | grep “app_name”

Sau khi có được pid của ứng dụng thì bạn chỉ việc chạy lện dump của jmap

jmap -dump:live,file=path/name. pid

Ở lệnh trên mình đã lấy được pid của chương trình pkg999c3443

Đến lúc này, chúng ta chỉ việc sử dụng VisualVM để load file dump vừa được tạo và xem thống kê các object được tạo của chương trình tạo thời điểm tạo file dump.

Hình ảnh về các object của ứng dụng pkg999

Tham khảo thêm:

https://dzone.com/articles/memory-analysis-how-to-obtain-java-heat-dump
https://www.ibm.com/support/knowledgecenter/SS3KLZ/com.ibm.java.diagnostics.memory.analyzer.doc/heapdump.html
https://www.javaworld.com/article/2072864/heap-dump-and-analysis-with-visualvm.html

 

Đánh giá độ phức tạp thuật toán – Algorithmic complexity

Ở bài trước, mình đã giới thiệu hai giải thuật khá căn bản đó là tìm kiếm nhị phân và đệ quy. Trong bài viết, mình hay dùng cụm từ độ phức tạp của giải thuật này, độ phức tạp của giải thuật kia…, vậy O(n), O(logn) là gì và dựa vào đâu mà mình có thể khẳng định độ phức tạp của giải thuật này là O(n), độ phức tạp của giải thuật kia là O(logn)… Thì bài viết hôm nay mình sẽ giới thiệu về Big O và một vài nguyên tắc của Big O để đánh giá mức độ hiệu quả hay kém hiệu quả của một giải thuật.

Giới thiệu

Giải thuật đơn giản chỉ là cách để giải quyết vấn đề nào đó trong lập trình, việc đánh giá giải thuật chính là lựa chọn cách viết code (implement) sao cho hiệu quả nhất. Trong thực tế khi giải quyết vấn đề nào đó chúng ta cũng thường phân tích ưu nhược điểm các cách giải quyết để lựa chọn cách giải quyết có lợi hơn.

Ví dụ, khi mình cần di chuyển từ TP HCM về Bình Định, thông thường mình sẽ có 2 sự lựa chọn. Thứ nhất là đi bằng máy bay và thứ hai là đi bằng xe khách. Đi bằng máy bay có ưu điểm là sẽ nhanh nhưng nhược điểm là chi phí cao, và ngược lại đi bằng xe khách tuy chậm nhưng chi phí lại rẻ. Vậy thì mình đã dựa vào chi phí và thời gian để đánh giá là cách di chuyển nào là hiệu quả hơn. Do đó tùy vào trường hợp mình cần tiết kiệm khoản nào thì mà sử dụng phương tiện di chuyển cho hợp lý.

Tương tự trong lập trình, để giải quyết vấn đề nào đó thì chúng ta cũng cần sử dụng các phép tính toán hay còn gọi là độ phức tạp thời gian bởi và vùng nhớ để lưu trữ hay còn gọi là độ phức tạp không gian. Để đánh giá giải thuật này là hiệu quả hơn giải thuật khác ta cần phải đánh giá dựa trên cùng một tập dữ liệu và với kích thước dữ liệu là lớn (vì với tập dữ liệu nhỏ thì sẽ rất khó để đánh giá, vì tốc độ xử lý của máy tính là rất lớn). Tất nhiên cũng giống như trong ví dụ trên của mình, chúng ta cần tùy vào trường hợp để lựa chọn giải thuật phù hợp.

Phạm vi của bài viết này mình chỉ tổng hợp lại một vài thuật ngữ và quy tắc để đánh giá độ phức tạp về thời gian.

BigO

BigO là chỉ số để đánh giá độ phức tạp của một giải thuật được sử dụng phổ biến nhất trong lập trình (ngoài ra còn có Big Ô-mê-ga và Big Thê-ta).

BigO đánh giá dựa vào thời gian chạy lớn nhất của một giải thuật trên các dữ liệu cùng cỡ.

Ví dụ: Giải thuật tìm kiếm tuyến tính trong trường hợp tốt nhất chỉ cần thực hiện 1 phép tính, trường hợp xấu nhất là n phép tính và trường hợp trung bình là n/2 phép tính (với n là số lượng phần tử). Thì với BigO, độ phức tạp của giải thuật tìm kiếm tuyến tính là O(n).

Một số chỉ số độ phức tạp phổ biến theo mức độ tăng dần.
– Constant time: O(1) số phép tính là hằng số, không phụ thuộc vào dữ liệu đầu vào. vd: a + b
– Logarithmic time: O(logn) số phép tính (thời gian thực hiện) tăng theo kích thước dữ liệu theo hàm logarit. vd: tìm kiếm nhị phân
– Linear time: O(n) số phép tính phụ thuộc vào dữ liệu đầu vào theo 1 biến. vd: tìm kiếm tuyến tính
– Log-linear time: O(nlogn) tổng hợp của n và logn (lồng nhau). vd: Heap sort, Merge sort
– Polynimial time: O(n^c) các vòng lặp lồng nhau
– Exponential time: O(c^n)  bài toán tìm số fibonacci thứ n
– Factorial time: O(n!)  bài toán TSP

Biểu đồ thời gian với số lượng phần tử với các độ phức tạp

Đánh giá độ phức tạp

– Quy tắc hằng: O(k*f(n) = O(f(n)) đơn giản là ta bỏ hằng số đi. vd: O(100n) = O(n)
– Quy tắc cộng: O(f(n) + O(g(n)) = max(f(n),g(n), ta lấy độ phức tạp lớn hơn. vd: O(n^2 + n) = O(n^2)
– Quy tắc nhân: O(f(n) * O(g(n)) = O(f(n)) * O(g(n)) ta lấy tích. vd: O(n) * O(logn) = O(nlogn)

Bài tập:

int count = 0;
        for (int i = N; i > 0; i /= 2) {
            for (int j = 0; j < i; j++) {
                count += 1;
            }
        }

Các bạn hãy dựa vào nguyên tắc trên để đánh giá độ phức tạp của đoạn code trên nhé. Have fun!