Thuật Toán Tìm Kiếm Nhị Phân Có Dự Đoán
Trong quá trình xây dựng framework ECS tối ưu bộ nhớ bằng ngôn ngữ C, tôi hướng đến việc thiết kế cấu trúc dữ liệu đơn giản nhưng hiệu quả để quản lý lượng lớn đối tượng. Giải pháp tôi chọn là mỗi component được biểu diễn dưới dạng struct thuần không chứa tham chiếu, đi kèm với một định danh 32-bit. Tập hợp các component này được lưu trữ trong một vùng nhớ liên tục.
Định danh 32-bit này không được expose qua API (không phải entity ID), cho phép tái sắp xếp trong quá trình chạy. Khi hai component thuộc loại khác nhau có cùng ID, chúng được coi là thuộc về một entity chung. Vai trò chính của ID là quản lý vòng đời component và hỗ trợ tìm kiếm các component liên kết trong cùng entity khi duyệt qua dữ liệu.
Trong ứng dụng của tôi, thao tác phổ biến nhất là duyệt qua tập hợp component cùng loại. Với cấu trúc dữ liệu hiện tại, việc này được thực hiện đơn giản bằng vòng lặp for duyệt mảng cơ bản. Tuy nhiên, một số hệ thống yêu cầu tìm kiếm các component “anh em” trong cùng entity khi xử lý một component cụ thể. Do không sử dụng bộ nhớ phụ để thiết lập mối liên kết giữa các component, chi phí cho thao tác này ban đầu lên đến O(n) (với n là số lượng component), điều này hoàn toàn không thể chấp nhận được.
Giai đoạn tối ưu đầu tiên: Tôi sắp xếp các component trong mảng theo thứ tự tăng dần của ID. Nhờ cơ chế cấp phát ID tăng dần tự nhiên, mảng luôn giữ được trạng thái sắp xếp cho đến khi ID quay vòng (wrap-around) xảy ra. Lúc đó, chỉ cần sắp xếp lại toàn bộ. Với mảng đã sắp xếp, thuật toán tìm kiếm nhị phân truyền thống giúp giảm độ phức tạp xuống O(logN).
Giai đoạn tối ưu thứ hai: Khi N đạt mức lớn (trên 100,000 phần tử), thời gian tìm kiếm vẫn còn cao. Dựa trên đặc điểm hệ thống của tôi - các component cùng loại thường được xử lý theo thứ tự tăng dần của ID (do bản chất sắp xếp tự nhiên), tôi nhận thấy mối tương quan mạnh giữa các lần tìm kiếm liên tiếp. Ví dụ: Khi xử lý tuần tự các ID [1,3,5,7,9] trong component A, việc tìm kiếm trong component B chứa [1,4,5,9,10] sẽ có xu hướng dịch chuyển vị trí tìm kiếm về phía sau mỗi lần.
Từ nhận định này, tôi phát triển thuật toán “tìm kiếm nhị phân có dự đoán” (Predictive Binary Search). Cơ chế hoạt động như sau:
- Trước khi bắt đầu tìm kiếm nhị phân thông thường, hệ thống sẽ dự đoán khoảng chứa mục tiêu dựa trên kết quả tìm kiếm trước đó
- Khoảng dự đoán được thiết lập từ vị trí tìm thấy lần trước đến 64 ô nhớ (slot) tiếp theo
- Nếu mục tiêu nằm trong khoảng dự đoán, độ phức tạp vẫn giữ nguyên O(logN) nhưng giá trị N thực tế bị thu nhỏ đáng kể
Kết quả benchmark:
- Với N = 1,000,000 phần tử: Tốc độ tăng 2-3 lần
- Với N = 100,000 phần tử: Hiệu suất cải thiện ~70%
- Với N = 10,000 phần tử: Vẫn đạt mức tăng 10%
Lưu ý thiết kế:
- Kích thước khoảng dự đoán 64 slot được chọn dựa trên kích thước dòng cache CPU tiêu chuẩn (64 bytes), giúp tối ưu hiệu suất truy cập bộ nhớ
- Cơ chế này hoàn toàn tự động, không yêu cầu can thiệp thủ công từ người dùng hệ thống
- Khi phát hiện wrap-around ID, hệ thống sẽ tự động kích hoạt cơ chế sắp xếp lại toàn bộ component
Giải pháp này đã giúp tôi cân bằng tốt giữa hiệu suất tính toán và tiêu hao tài nguyên bộ nhớ, phù hợp với các hệ thống yêu cầu xử lý realtime với lượng dữ liệu lớn.