Triển khai sequence trong C

Anonymous trong Xử Lý Ngôn Ngữ Tự Nhiên và Phát Triển Nhanh

2009-11-01 Khoảng 1100 từ 6 phút

Dạo này tôi dành hầu hết thời gian viết code, mỗi tuần khoảng 3-4 nghìn dòng. Vì thế không còn thời gian dư dả để viết blog. Có lẽ một thời gian nữa tôi mới có dịp tổng hợp các ý tưởng của mình.

Vài năm gần đây tôi chủ yếu sử dụng C để thiết kế và lập trình hệ thống (dĩ nhiên cũng viết khá nhiều đoạn mã Lua). Điều khiến tôi băn khoăn nhất chính là xác định các yêu cầu tối thiểu trong lập trình hệ thống. C++ cung cấp quá nhiều thứ, nhưng C lại quá ít. Khi làm việc lâu dài với C, chúng ta chắc chắn cần nhiều hơn thế.

Ví dụ như các kiểu dữ liệu cơ bản, trong cuốn “C Interfaces and Implementations” gọi là ADT (Kiểu dữ liệu trừu tượng). Tác giả đã liệt kê rất nhiều, nhưng theo tôi vẫn còn dư thừa. Thực tế tôi không cần đến nhiều như vậy.

Trong đó chỉ có atom là thiết yếu. Trong hệ thống của tôi, mặc dù tên gọi chưa chuẩn xác lắm nhưng bản chất vẫn vậy. Tôi đã từng viết một bài blog phân tích chi tiết về vấn đề này.

Do sử dụng Lua rất thường xuyên, tôi thấy rằng cấu trúc dữ liệu kiểu từ điển (dictionary) cực kỳ hữu ích. Vì vậy tôi đã tự xây dựng một bản triển khai cơ bản của hash map.

Biến thể phổ biến tôi hay dùng là mảng động và hàng đợi dùng để gửi/nhận thông điệp. Hai cấu trúc này tương đối đơn giản nên tôi thường viết inline mỗi khi cần, không tách thành module độc lập. Dù dễ viết ít sai sót, nhưng sau nhiều năm tôi vẫn muốn trừu tượng hóa chúng. Khi thảo luận với đồng nghiệp, bạn Đồng học (Soloist) gợi ý rằng thực ra tôi đang tìm kiếm một kiểu sequence chuẩn.

Đây là kiểu dữ liệu có thể chèn/xóa ở cả hai đầu, có độ dài thay đổi linh hoạt, cho phép truy cập ngẫu nhiên hiệu quả. Trong cuốn “C Interfaces and Implementations” gọi tắt là seq, và Haskell cũng có khái niệm tương tự.

Tuy nhiên vì thói quen theo đuổi hiệu năng tối đa, tôi luôn do dự khi tách seq thành module độc lập. Tôi nghĩ rằng tại sao không dùng trực tiếp mảng nguyên sinh với con trỏ để lặp, vừa đơn giản lại tiết kiệm các cuộc gọi hàm và gián tiếp truy cập dữ liệu?

Dĩ nhiên STL trong C++ đưa ra giải pháp trung hòa bằng cách triển khai phần lớn mã nguồn trong file .h (thông qua template) để trình biên dịch tối ưu inline. Tuy nhiên điều này làm lộ chi tiết triển khai cấu trúc dữ liệu. Theo tôi hiện nay, việc này còn tệ hơn nữa. (Xin phép được giữ quan điểm bảo thủ này, bạn đọc có thể không đồng tình)

Một lần nữa tôi dành thời gian nghiêm túc suy nghĩ về vấn đề này, và hôm nay đã hoàn thành bản triển khai seq tương đối hài lòng.

Ẩn giấu chi tiết bên trong tất yếu gây một số tổn thất hiệu năng. Vậy yếu tố nào cần tối ưu và yếu tố nào có thể chấp nhận?

Theo tôi, việc duyệt qua các phần tử seq phải đạt tốc độ tối đa - hiệu quả ngang việc dùng vòng lặp for thông thường với biến đếm i kiểu int. Các thao tác đọc/ghi dữ liệu trong seq cũng cần nhanh. Còn thao tác chèn/xóa ở hai đầu có thể cho phép hiệu năng kém hơn một chút.

Cấu trúc dữ liệu bên trong seq phải được ẩn giấu. Hầu hết thao tác chỉ được cung cấp qua API C. Seq cần hỗ trợ thay đổi kích thước, đồng thời dữ liệu phải liên tục trong bộ nhớ (đảm bảo hiệu năng đọc/ghi tốt nhất).

Thiết kế cuối cùng của tôi sử dụng mảng mô phỏng hàng đợi vòng, đồng thời công khai cấu trúc iterator. Hầu hết các iterator này chỉ được phép khai báo trên stack. Tôi áp dụng mẹo nhỏ trong C học hỏi từ cách định nghĩa jmp_buf: cấu trúc seqi được thiết kế như mảng một phần tử, cho phép khai báo trực tiếp trên stack và truyền con trỏ.

1
2
3
4
5
6
7
8


struct seq;
struct _seq_iterator {
  struct seq *seq;
  void **begin;
  int offset;
  int length;
};
typedef struct _seq_iterator seqi[1];

Vì seq có thể thay đổi kích thước trong khi duyệt, tôi chọn cách thông báo cho iterator khi seq thay đổi, thay vì kiểm tra liên tục trong quá trình duyệt. Do đó các iterator cần đăng ký với seq.

Iterator ghi nhận một đoạn bộ nhớ liên tục, trong phạm vi này có thể tự do duyệt qua lại và đọc/ghi dữ liệu thông qua hàm inline hoặc macro. Chỉ khi vượt ra ngoài mới cần gọi các API phức tạp hơn. Do seq dùng cấu trúc hai đoạn bộ nhớ liên tiếp (hàng đợi vòng), việc quản lý này hơi phức tạp, nhưng may mắn là trường hợp này không thường xuyên.

Một số hàm quan trọng được định nghĩa như sau:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


void seq_head(struct seq *s , seqi iter);
void seq_tail(struct seq *s , seqi iter);
void seq_close(seqi iter);
void seq_update(seqi iter);

static inline void
seq_inc(seqi iter)
{
  ++iter->offset;
  if (iter->offset >= iter->length) {
    seq_update(iter);
  }
}

static inline void
seq_dec(seqi iter)
{
  --iter->offset;
  if (iter->offset < 0) {
    seq_update(iter);
  }
}

static inline bool
seq_isvalid(seqi iter)
{
  return iter->begin != 0;
}

static inline void*
seq_read(seqi iter)
{
  return *(iter->begin + iter->offset);
}

static inline void*
seq_write(seqi iter, void *v)
{
  *(iter->begin + iter->offset) = v;
  return v;
}

Cách sử dụng rất trực quan, gần giống vòng lặp for thông thường với hiệu năng ngang mảng nguyên sinh:

1
2
3
4


seqi iter;
for (seq_head(s,iter); seq_isvalid(iter); seq_inc(iter)) {
  printf("%p\n", seq_read(iter));
}

Quy ước đơn giản là khi iterator đến cuối seq hoặc dữ liệu bị pop ra, nó sẽ không thể phục hồi. Tôi chỉ cần ghi dấu này bằng cách đặt

Triển Khai Sequence Trong C