Khởi Tạo Có Chọn Lọc Cho Bộ Nhớ

Vài ngày trước, trong lúc thảo luận với đồng nghiệp về một vấn đề kỹ thuật, tôi đã thử nghiệm một giải pháp nhỏ.

Câu chuyện bắt đầu từ việc studio tại Thượng Hải của công ty tiến hành kiểm tra áp lực máy chủ cho dự án MMO. Khi nói đến việc tối ưu hiệu suất, chúng tôi tập trung vào các module C được sử dụng trong server. Điều đặc biệt là họ biên dịch cùng một bộ mã C++ (phân biệt bằng namespace) nhiều lần để phục vụ các service khác nhau. Tôi cảm thấy tò mò vì thông thường các module C trong Lua có thể dùng chung cho nhiều máy ảo mà không cần liên kết vật lý nhiều bản. Qua phân tích kỹ hơn, hóa ra mã nguồn này sử dụng một số đối tượng toàn cục (theo mô hình singleton).

Ngay lập tức tôi nhận thấy thiết kế dùng nhiều đối tượng toàn cục thường tiềm ẩn rủi ro. Khi kiểm tra từng đối tượng, một cái tên thú vị xuất hiện: module tìm đường (pathfinding).

Module này về bản chất không lưu giữ trạng thái. Dữ liệu tĩnh về chướng ngại vật trên bản đồ được tách riêng và chia sẻ toàn cục - đây là thiết kế hợp lý. Tuy nhiên, một đối tượng pathfinding không trạng thái lại được khởi tạo hàng chục lần để phục vụ các service độc lập.

Ban đầu tôi không hiểu tại sao một hàm tìm đường không trạng thái lại cần tồn tại dưới dạng đối tượng toàn cục. Khi đọc mã nguồn, tôi phát hiện quá trình khởi tạo thuật toán đòi hỏi một khối bộ nhớ lớn: một mảng 3 chiều kích thước 200x200x16, mỗi ô khoảng 16 byte. Thuật toán sử dụng A* cơ bản để tìm đường trong lưới 3D, và yêu cầu toàn bộ khối nhớ này phải được khởi tạo bằng 0 - chiếm khoảng 10MB. Với tần suất gọi cao, việc memset 10MB này gây ra chi phí không nhỏ.

Để giải quyết vấn đề này, người viết mã đã áp dụng một kỹ thuật thông minh: mỗi ô trong mảng được ghi lại một số nguyên 64-bit làm “phiên bản”. Mỗi lần tìm đường, phiên bản sẽ tăng lên. Khi truy cập ô nào, hệ thống sẽ kiểm tra phiên bản của ô đó có khớp với phiên bản hiện tại không để xác định liệu ô đó đã được khởi tạo trong vòng tìm đường này chưa.

Vì quá trình tìm đường thực tế chỉ sử dụng một phần rất nhỏ trong 10MB bộ nhớ này, nên giải pháp này tiết kiệm đáng kể thời gian khởi tạo. Tuy nhiên, nó đòi hỏi phải giữ nguyên khối bộ nhớ toàn cục, không thể tạo mới đối tượng này mỗi lần tìm đường.

Tôi suy nghĩ về vấn đề này và nhận ra đây thực chất là bài toán quản lý ma trận thưa 3D. Về lý thuyết, chúng ta có thể dùng bảng băm với khóa là bộ ba chỉ số (x,y,z). Tuy nhiên, người viết mã lo ngại về hiệu năng không xác định nên chọn phương án đánh đổi không gian lấy thời gian bằng cách sử dụng cấu trúc bộ nhớ phẳng khổng lồ để đạt tốc độ truy cập O(1). Điều này lại dẫn đến vấn đề khởi tạo khối bộ nhớ lớn mỗi lần sử dụng.

Ngoài bảng băm, còn nhiều cách biểu diễn ma trận thưa như cây KD, cây bát phân (octree)… nhưng đều phức tạp về triển khai và hiệu quả truy cập. Tôi chợt nghĩ: nếu server không gặp vấn đề về không gian bộ nhớ, tại sao không thiết kế một cấu trúc bộ nhớ khởi tạo có chọn lọc?

Tôi thử nghiệm một đoạn mã nhỏ như sau: Giả sử dòng cache của CPU là 64 byte và từ máy 64 bit, tôi quyết định khởi tạo bộ nhớ theo từng khối 64 byte (vì xóa 1 byte hay 64 byte đều tốn thời gian như nhau). Với 10MB bộ nhớ, ta chia thành khoảng 156.000 khối. Dùng 1 bit để đánh dấu mỗi khối đã được khởi tạo hay chưa, và kiểm tra bit này trước khi truy cập.

156.000 bit tương đương khoảng 2400 từ 64 bit (gần 20KB bộ nhớ). Nếu muốn tối ưu hơn nữa, ta có thể áp dụng cơ chế đánh dấu hai cấp: chia 20KB này thành 64 đoạn, mỗi đoạn khoảng 300 byte, và dùng một từ 64 bit để quản lý từng đoạn.

Khi kiểm tra mã hợp ngữ sau khi biên dịch với gcc -O2, tôi thấy trình biên dịch đã tối ưu rất tốt.

Dự án này sử dụng bản đồ có kích thước lên đến 4000x4000x16 ô, chứa thông tin chướng ngại vật dạng lưới. Module tìm đường này chủ yếu giải quyết bài toán NPC tấn công người chơi gần đó và cần tránh chướng ngại vật.

Đáng chú ý, module không cần xử lý tìm đường dài mà chỉ tập trung vào việc né tránh chướng ngại vật lân cận. Các chướng ngại vật này là tĩnh và không thay đổi. Những khu vực này thường không phải mê cung phức tạp, cấu trúc chướng ngại vật có độ phân bố thấp. Điều này khiến mật độ thông tin trong mảng chướng ngại vật khổng lồ kia cực kỳ thưa thớt.

Tôi cho rằng việc đầu tư không gian lớn như vậy chỉ để đơn giản hóa thuật toán tìm đường. Thực tế, dung lượng này đủ để lưu trữ toàn bộ các đường đi từ mỗi điểm trên bản đồ đến các mục tiêu gần đó. Nếu thực hiện tiền xử lý và lưu trữ bằng cấu trúc dữ liệu phù hợp, chúng ta hoàn toàn có thể truy vấn đường đi trong thời gian O(1). Tôi sẽ chia sẻ chi tiết cách thực hiện trong bài viết tiếp theo.