Tối Ưu Cấu Trúc Dữ Liệu Chuỗi Có Thứ Tự
Trong mô-đun ECS của chúng tôi, có một cấu trúc dữ liệu quan trọng là mảng eid - thành phần của cấu trúc Component, dùng để xác định Component thuộc Entity nào. Hiện tại chúng tôi đang sử dụng mảng có thứ tự để triển khai.
Phân tích yêu cầu
Các thao tác thường gặp với cấu trúc này gồm:
- Duyệt tuần tự
- Truy cập ngẫu nhiên
- Tìm kiếm vị trí của ID
Mảng có thứ tự đáp ứng tốt các yêu cầu này với độ phức tạp:
- Truy cập ngẫu nhiên: O(1)
- Tìm kiếm nhị phân: O(logN)
Tối ưu không gian lưu trữ
Mỗi Entity ID có độ dài 48bit, nhưng lưu trữ full 48/64bit cho mỗi phần tử gây lãng phí. Với giới hạn dưới 2^24 (khoảng 16 triệu) Entity, chúng tôi áp dụng cơ chế chỉ số gián tiếp:
- Dùng 24bit ID nội bộ
- Kết hợp bảng ánh xạ 24bit → 48bit thực tế
Giải pháp phân nhóm thông minh
Để tối ưu hơn nữa, chúng tôi thử nghiệm giải pháp phân nhóm:
- Mỗi nhóm 32-256 phần tử
- Tiêu đề 64bit chứa:
- 40bit cao của phần tử đầu tiên
- 2byte đếm số phần tử ở 2 đoạn đầu
- 16bit offset dữ liệu rời rạc
- Mỗi phần tử chỉ cần 8bit thấp
- Dữ liệu rời rạc lưu riêng với cấu trúc 40bit cao + 24bit index
Giải pháp này đảm bảo:
- Truy cập ngẫu nhiên O(1)
- Tìm kiếm không suy giảm hiệu suất
- Tối ưu không gian (chỉ tốn thêm ~10bit/element)
Bài học thực tiễn
Khi triển khai thực tế, chúng tôi nhận ra:
- Code quá phức tạp, hiệu suất thực tế kém hơn mảng phẳng dù độ phức tạp lý thuyết tương đương
- Số lượng Entity thực tế chỉ khoảng 10,000 (thấp hơn dự kiến 100x) → Quyết định quay về dùng mảng phẳng với 2byte ID nội bộ
Tối ưu thao tác chèn/xóa
Mặc dù ECS không cho phép chèn Component sau khi tạo Entity, nhưng với các “tag” (Component không chứa dữ liệu) cần hỗ trợ thêm/xóa động:
- Xóa: O(logN) (đã tối ưu từ trước)
- Thêm: Tệ nhất O(n), thường tốt hơn
Chúng tôi nghiên cứu các giải pháp kinh điển:
- Cây B: Chia đoạn, chỉ di chuyển dữ liệu trong đoạn khi chèn/xóa
- Skip list: Kết hợp danh sách liên kết với các tầng chỉ số để đạt O(logN) truy vấn
Giải pháp lai hợp lý
Với quy mô dữ liệu 104-105, chúng tôi thiết kế cấu trúc lai:
- Chia mảng thành các nhóm 256 phần tử
- Mỗi nhóm có header nhỏ
- Dùng hàng đợi vòng trong mỗi nhóm
- Hỗ trợ 2 chế độ lưu trữ:
- Dense: Khi min-max trong nhóm ≤64K
- Lưu base 32bit + delta 16bit có dấu
- Sparse: Lưu 256 phần tử 4byte nguyên bản
- Dense: Khi min-max trong nhóm ≤64K
Quản lý bộ nhớ thông minh
- Dùng freelist quản lý các node 1024byte
- Mỗi node chứa được:
- 2 nhóm Dense
- 1 nhóm Sparse
- Khi chuyển đổi chế độ:
- Dense → Sparse: Tách node nếu có nhóm bạn
- Sparse → Dense: Gộp lại nếu có nhóm bạn
Kết quả thực nghiệm
Triển khai bằng C với tối ưu O3:
- Truy cập ngẫu nhiên: Hiệu suất tương đương mảng phẳng
- Tìm kiếm nhị phân: Giảm 5-10% hiệu suất
- Ưu điểm: Sử dụng 16bit/element thay vì 32bit → friendly hơn với bộ nhớ cache
- Header chứa base giúp tối ưu bước tìm kiếm đầu tiên
Giải pháp này cho thấy sự cân bằng tốt giữa hiệu suất lý thuyết và thực tế, đặc biệt phù hợp với quy mô dữ liệu thực tế của hệ thống ECS hiện đại.