Series Phản Phác Quy Chân – Tại sao cộng string lại chậm

Lý giải chút về tên series

返璞归真 – Phản phác quy chân: Nghĩa là điểm cao nhất cũng chính là điểm xuất phát, được ứng dụng trong rất nhiều lĩnh vực. Trong võ học, nó có nghĩa là đạt tới cảnh giới “Tối thượng” trong truyền thuyết, quên đi tất cả võ học trong thiên hạ, bản thân đã không còn chiêu thức cụ thể, chỉ dựa vào ý cảnh mà đơn giản xử lý.

Võ học được thành lập từ các chiêu thức cơ bản, tuyệt thế võ công cũng từ các chiêu thức cơ bản mà ra. Code học cũng tạo thành từ bit/byte cơ bản, chương trình phức tạp đến mấy cũng dịch được ra bytecode. Đôi khi, ta đã quá quen với việc dùng thư viện, dùng framework mà quên thì những thứ nằm sâu bên dưới, không nắm được bản chất. Có những vấn đề mà phải nắm rõ bản chất của nó ta mới có thể giải quyết được.

Như cái tên “Phản Phác Quy Chân”, series này không giới thiệu công nghệ hay ngôn ngữ mới, mà sẽ tập trung quay lại những cái bản chất, đơn giản, tinh túy nhất mà ít người quan tâm để ý (Bên tiếng Anh có một từ tương tự : Back to Basic, bỏ qua những cái phức tạp, quay lại những cái cơ bản để hiểu tận gốc vấn đề).

01_s_by_darkdamage-d5yo32c

Ở bài viết đầu, mình sẽ nhắc sơ lại về string, cũng như giải thích lý do vì sao việc cộng string sẽ ảnh hưởng tới bộ nhớ và performance của hệ thống (Hình minh họa và bài viết méo liên quan với nhau đâu, vì tác giả thích thế :v).

Chuyện về String

Ngày xửa ngày xưa, thời còn học Java, ta thường được nghe dạy rằng khi cộng chuỗi, phải dùng StringBuilder và append, thay vì cộng String. Lý do là vì String là kiểu immutable, giá trị của nó không thay đổi, khi cộng string ta tạo một string mới trong bộ nhớ. Còn StringBuilder là kiểu mutable, do đó khi ta dùng append, giá trị của nó thay đổi chứ không tạo ra string mới. Do đó dùng StringBuilder sẽ tiết kiệm bộ nhớ và chạy nhanh hơn.

Không tin à, hãy xem 2 đoạn code dưới đây, đoạn code dùng StringBuilder chỉ mất 4ms để chạy, còn đoạn code sử dụng String mất tới 4828ms (Nguồn).

Ta tạm gật gù đồng ý “Ồ, ra thế”. Tuy nhiên, có bao giờ ta tự hỏi, tại sao cộng string lại chậm hay không? Hãy cùng đọc bài viết và tìm hiểu nhé.

Cộng string thì có vấn đề gì

Để giải thích vấn đề này, ta hãy thử trải nghiệm cảm giác “Phản phác qui chân“: Bỏ qua một bên những công nghệ mới mẻ hoành tráng, những framework đồ sộ, những ngôn ngữ ảo diệu, quay lại từ cái thời ngày xửa ngày xưa còn dùng DevC, còn làm việc với byte và bộ nhớ. Đúng vậy, những kiến thức về byte, về bộ nhớ là nền tảng cho hệ thống kiến thức của bạn.

Hãy nhớ lại cách C lưu trữ string: String là một mảng các byte, có kí tự cuối cùng là kí tự null. Với cách lưu trữ này, để biết được độ dài của string, ta phải chạy một vòng lặp bắt đầu từ con trỏ chứa byte đầu tiên cho tới khi gặp kí tự null. Dưới đây là một phiên bản của hàm strcat, hàm cộng chuỗi trong C.

Đọc code và suy ngẫm nhé. Dòng đầu tiên, code sẽ chạy từ đầu cho tới khi gặp phải null character cuối string dest, sau đó nó sẽ copy từng byte của string src và string dest. Hai vòng lặp, độ phức tạp chỉ là O(n), đâu có gì ghê gớm nhỉ?? Tuy nhiên, khi ta thực hiện việc cộng chuỗi nhiều lần, với chuỗi dài thì sao?

Mỗi lần gọi strcat, vòng lặp sẽ chạy từ đầu cho tới cuối chuỗi, chuỗi càng dài thì vòng lặp chạy càng lâu. Tới khi chuỗi string vô cùng lớn thì việc cộng chuỗi diễn ra rất nặng nề và chậm chạp. Bác Joel có một câu chuyện cười (mình đọc chả thấy vui) để mô tả vấn đề này.

Một cô tóc vàng mới vào nghề sơn vạch phân tuyến trên đường cao tốc. Ngày đầu, cô sơn được 10 dặm, ngày hôm sau cô chỉ sơn được 7 dặm. Ông chủ nghĩ rằng cô mệt, nên cho nghỉ một ngày. Sau hôm đó, cô ta làm cũng chỉ được 5 dặm. Cứ thế mỗi ngày cô lại làm ít hơn. Ông chủ gọi cô tới hỏi:

– Có chuyện gì xảy ra thế? Tại sao năng suất của cô giảm từng ngày?

– Tôi tưởng là ông phải biết chứ! Đơn giản là càng ngày, tôi càng đi xa cái thùng sơn hơn.

Tương tự như trong truyện, string gốc càng dài thì vòng lặp phải chạy càng lâu. Do đó, để giải quyết vấn đề này, một số phiên bản khác của hàm strcat đã được tạo ra:

Với cách viết này, sau khi cộng chuỗi, ta trả ra vị trí con trỏ cuối cùng. Mỗi lần cộng thêm, vòng lặp chỉ cần chạy từ con trỏ được trả cho tới cuối chuỗi src thôi, không còn lặp nhiều như thuật toán ban đầu nữa.

facebook-edgerank

Kết luận

Lâu lâu tìm hiểu về những khái niệm/ngôn ngữ bậc thấp cũng khá hay phải không nào. May mắn là chúng ta được sử dụng C#, Java tự giải phóng bộ nhớ, lại có khá nhiều thư viện hỗ trợ. Nhiều bác vẫn còn viết C, C++, truy cấp bộ nhớ bằng tay rất cực (Cực nhưng lương cao chót vót đấy nhé). Tuy nhiên, nếu mình là người viết code, trong 90% các trường hợp, mình vẫn sẽ dùng String hoặc String.Format thay vì StringBuilder!! Vì sao?? Chịu khó chờ nhé, mình sẽ dành một bài viết khác để giải thích chuyện này.

Bài viết tham khảo nhiều từ blog Joel on Software của bác Joel, một người vừa cứng technical vừa giỏi điều hành và quản lý: http://www.joelonsoftware.com/articles/fog0000000319.html. Bài viết gốc mổ xẻ khá nhiều vấn đề về performance, bộ nhớ liên quan tới string, cơ mà mình thấy không có ích mấy nên không đưa vào bài viết nhé.

 

Advertisements

6 thoughts on “Series Phản Phác Quy Chân – Tại sao cộng string lại chậm”

  1. “Tuy nhiên, nếu mình là người viết code, trong 90% các trường hợp, mình vẫn sẽ dùng String hoặc String.Format thay vì StringBuilder!! Vì sao?? Chịu khó chờ nhé, mình sẽ dành một bài viết khác để giải thích chuyện này.”
    đã có bài viết này chưa vậy a?

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s