Mã định danh theo chỉ số có thể thay con trỏ trong quản lý bộ nhớ C và C++

Một bài viết năm 2018 đề xuất dùng mã định danh theo chỉ số thay cho con trỏ thô và con trỏ thông minh trong các chương trình C, C++, nhằm tập trung quản lý bộ nhớ và giảm phân mảnh, lỗi truy cập cũng như bỏ lỡ dữ liệu trong bộ nhớ đệm. Tác giả cũng trình bày cách dùng bộ đếm thế hệ để phát hiện mã định danh cũ bị trùng với mã của một đối tượng mới.

Vì sao nên hạn chế con trỏ?

Sau hơn 15 năm làm việc với các cơ sở mã C++ lớn, từ 500.000 đến khoảng một triệu dòng, tác giả nhận thấy những chương trình có hàng chục nghìn đến hàng trăm nghìn đối tượng nhỏ, mỗi đối tượng được cấp phát riêng trên vùng nhớ động và liên kết với nhau bằng con trỏ thông minh, thường khó tối ưu.

Kiểu tổ chức này có thể hạn chế một số lỗi hỏng bộ nhớ nhờ các kiểm tra khi giải tham chiếu con trỏ. Tuy nhiên, việc các đối tượng nằm rải rác trong bộ nhớ khiến chương trình thường xuyên phải truy cập các vùng nhớ không liền kề, làm giảm hiệu quả của bộ nhớ đệm của bộ xử lý. Phân mảnh bộ nhớ và tình trạng một con trỏ thông minh bị bỏ quên khiến vùng nhớ không được giải phóng cũng là những vấn đề thường gặp.

Thay vì để mã ứng dụng tự do cấp phát và giải phóng từng đối tượng, tác giả đề xuất giao quyền quản lý bộ nhớ cho các hệ thống tập trung, chẳng hạn hệ thống dựng hình, vật lý hoặc hoạt ảnh. Các hệ thống này giữ dữ liệu trong những mảng liên tục và chỉ trả ra mã định danh theo chỉ số, thay vì địa chỉ bộ nhớ của đối tượng.

Quản lý đối tượng trong các hệ thống tập trung

Một hệ thống là phần tương đối lớn của chương trình, đảm nhiệm một nhóm công việc liên quan và cung cấp giao diện hàm rõ ràng cho phần còn lại. Hệ thống dựng hình có thể quản lý bộ đệm đỉnh, kết cấu và bộ tô bóng; hệ thống vật lý quản lý vật thể cứng, khớp nối và hình dạng va chạm.

Việc cấp phát và giải phóng bộ nhớ khác với việc tạo hoặc hủy một đối tượng theo yêu cầu của mã ứng dụng. Khi hệ thống nắm quyền quản lý vùng nhớ, nó có thể tận dụng hiểu biết về cách dữ liệu được sử dụng để bố trí chúng hợp lý, kiểm tra thao tác tạo và hủy, cũng như điều chỉnh cách cấp phát.

Chẳng hạn, tài nguyên dựng hình có thể vẫn đang được bộ xử lý đồ họa sử dụng trong một danh sách lệnh đang chờ thực thi. Vì vậy, hệ thống dựng hình có thể đánh dấu tài nguyên để hủy khi nhận yêu cầu, nhưng chỉ giải phóng thực sự sau khi bộ xử lý đồ họa không còn dùng đến.

Lưu các đối tượng cùng loại trong mảng

Thay vì cấp phát một vùng nhớ riêng mỗi khi tạo đối tượng, hệ thống có thể dành sẵn các mảng cho từng loại dữ liệu và quản lý những vị trí còn trống. Khi một đối tượng được tạo, hệ thống chọn một vị trí trống; khi đối tượng bị hủy, vị trí đó được đánh dấu là có thể dùng lại.

Cách làm này tương tự bộ cấp phát vùng nhớ theo nhóm. Lợi ích không chỉ nằm ở tốc độ cấp phát, bởi các bộ cấp phát thông thường hiện đại cũng xử lý tốt những vùng nhớ nhỏ. Mảng còn giúp:

• Đặt dữ liệu sát nhau, hạn chế phần bộ nhớ phụ trợ mà bộ cấp phát có thể lưu cạnh dữ liệu.
• Giữ các dữ liệu thường được dùng cùng nhau trong vùng nhớ liên tục để tận dụng bộ nhớ đệm của bộ xử lý.
• Chia dữ liệu của một đối tượng thành nhiều mảng khác nhau để bố trí gọn hơn. Những thay đổi về cách sắp xếp vẫn được giữ bên trong hệ thống, không làm ảnh hưởng mã bên ngoài.
• Tránh phân mảnh khi các mảng không cần cấp phát lại.
• Phát hiện sớm số lượng đối tượng vượt dự kiến. Ví dụ, một trò chơi có thể đặt giới hạn không quá 1.024 kết cấu đang tồn tại và đưa ra cảnh báo hữu ích khi vượt ngưỡng.

Dùng mã định danh thay cho địa chỉ bộ nhớ

Khi các đối tượng nằm trong mảng, có thể xác định chúng bằng chỉ số. Hệ thống giữ kín địa chỉ đầu mảng và chỉ cung cấp chỉ số cho mã bên ngoài. Không có địa chỉ đầu mảng, phần mã đó không thể tự tính vị trí đối tượng trong bộ nhớ để truy cập trực tiếp.

Trong nhiều trường hợp, mã bên ngoài không cần đọc hay sửa dữ liệu trực tiếp; chỉ hệ thống cần thao tác với dữ liệu. Khi đó, việc không đưa con trỏ ra ngoài giúp hạn chế nguy cơ làm hỏng bộ nhớ. Hệ thống cũng có thể di chuyển hoặc cấp phát lại mảng mà không làm thay đổi các mã định danh đang được sử dụng.

Nếu cần truy cập trực tiếp, hệ thống cung cấp hàm tra cứu để đổi mã định danh thành con trỏ. Con trỏ chỉ nên được dùng trong một đoạn mã ngắn, không lưu lại và không giữ qua các lần gọi hàm. Vùng nhớ có thể bị cấp phát lại hoặc đối tượng có thể bị hủy, khiến con trỏ cũ không còn hợp lệ.

Kiểm tra tính hợp lệ và phát hiện mã cũ

Mỗi loại mã định danh nên có kiểu riêng trong C hoặc C++, chẳng hạn kiểu cấu trúc hoặc lớp riêng. Cách này giúp trình biên dịch phát hiện trường hợp truyền nhầm loại mã; chỉ dùng bí danh kiểu đơn giản có thể không đủ để tạo ra cảnh báo.

Khi đổi mã định danh thành con trỏ, hệ thống có thể kiểm tra chỉ số có nằm trong giới hạn mảng hay không, vị trí đó có đang chứa một đối tượng còn hoạt động hay không, rồi mới tính địa chỉ. Các kiểm tra này giúp phát hiện truy cập ngoài phạm vi và một số trường hợp sử dụng đối tượng sau khi đã hủy.

Tuy vậy, chỉ kiểm tra vị trí còn hoạt động là chưa đủ: một đối tượng có thể bị hủy, rồi vị trí cũ được dùng cho đối tượng mới. Mã định danh cũ khi ấy vẫn trỏ đến một vị trí hợp lệ nhưng không còn là đối tượng ban đầu.

Để xử lý tình huống này, có thể dành một phần bit trong mã định danh làm nhãn thế hệ. Ví dụ, nếu mã có 16 bit và mảng chỉ cần hỗ trợ tối đa 1.024 đối tượng, 10 bit dùng để biểu diễn chỉ số, còn 6 bit còn lại dùng làm nhãn. Khi tra cứu, hệ thống so sánh toàn bộ mã nhận được với mã đang lưu tại vị trí đó. Nếu hai mã khác nhau, đối tượng đã bị hủy hoặc vị trí đã được dùng lại.

Cách kiểm tra này giảm nguy cơ truy cập bằng mã cũ, nhưng nếu nhãn bị lặp lại thì va chạm vẫn có thể xảy ra. Số bit dành cho nhãn, cách tái sử dụng vị trí trống và tần suất tạo, hủy đối tượng đều ảnh hưởng đến khả năng xảy ra va chạm.

Cập nhật ngày 28/11/2018: dùng bộ đếm thế hệ

Bài viết bổ sung cách tránh va chạm bằng cách gắn một bộ đếm thế hệ riêng cho mỗi vị trí trong mảng. Bộ đếm tăng khi mã định danh được giải phóng. Khi kiểm tra mã, hệ thống so sánh nhãn trong mã với bộ đếm hiện tại của vị trí.

Nếu bộ đếm sắp tràn, vị trí đó sẽ bị vô hiệu hóa để không phát sinh mã mới từ vị trí này. Cách làm giúp tránh va chạm, nhưng về lâu dài, các vị trí có thể lần lượt bị vô hiệu hóa khi hết giá trị bộ đếm.

Theo bài viết, với mã 32 bit, hệ thống có thể tạo tổng cộng 4 tỷ đối tượng trong suốt vòng đời; số đối tượng tồn tại đồng thời tối đa là 2 mũ (32 trừ số bit dành cho bộ đếm). Tác giả cũng nêu khả năng kích hoạt lại vị trí đã vô hiệu hóa nếu có thể bảo đảm không còn mã định danh nào của vị trí đó được sử dụng, chẳng hạn khi chuyển vào hoặc ra khỏi một màn chơi.

Các ứng dụng khác và ví dụ

Mã định danh có thể dùng làm dấu hiệu nhận biết đối tượng được chia sẻ giữa nhiều tiến trình, chẳng hạn giữa máy chủ và các máy khách trong một trò chơi trực tuyến, hoặc để lưu tham chiếu giữa các đối tượng trong dữ liệu lưu trò chơi. Một mã dạng phạm vi cũng có thể đại diện cho một nhóm đối tượng liên quan, gồm chỉ số phần tử đầu tiên và số lượng phần tử.

Bài viết nêu sokol-gfx, một giao diện lập trình bằng C dùng mã định danh để quản lý tài nguyên dựng hình, cùng với mô-đun Oryol Gfx viết bằng C++ và mô-đun hoạt ảnh Oryol Anim, vốn lưu dữ liệu trong các mảng.

Góc nhìn

Với các chương trình thường xuyên tạo và hủy nhiều đối tượng, cách tiếp cận này giúp nhóm phát triển tập trung quyền sở hữu bộ nhớ vào những hệ thống hiểu rõ cách dữ liệu được dùng. Đổi lại, mã ứng dụng cần tuân thủ ranh giới truy cập: chỉ dùng con trỏ tạm thời khi thật sự cần và không giữ con trỏ sau khi thao tác kết thúc.

Đây không phải giải pháp phù hợp cho mọi kiến trúc. Cách làm phát huy hiệu quả nhất khi dữ liệu được xử lý theo từng nhóm trong các vòng lặp tập trung; việc đưa nó vào một cơ sở mã hướng đối tượng lớn, nơi đối tượng được tạo và hủy ở nhiều nơi, có thể đòi hỏi thay đổi đáng kể.