Tối ưu hóa code copy mảng C++

andynguyen · November 12, 2022, 9:47am

Mình tạo một danh sách liên kết có kiểu dữ liệu A gồm nhiều trường x, y, z.

z là một mảng kiểu char, kích cỡ khác nhau đối với từng object được tạo ra.

Nếu mình kiếm một nốt trên danh sách liên kết theo phương pháp thông thường sẽ rất lâu. Do đó mình chia A thành 2 dữ liệu nhỏ hơn là B và C trong đó B chứa x, C chứa y và z. Để lấy dữ liệu của một nốt cứ tìm key trên B rồi sau đó theo B lấy giá trị trên C. Nói chung là cache đó.

Tốc độ có tăng lên đáng kể. Hiện tại mình dùng memcpy để copy dữ liệu của z từ A sang C. Cho mình hỏi có cách nào tối ưu hơn memcpy không?

Phong_Ky_Vo · September 23, 2018, 3:21am

Hi Anh Nguyen.

Theo mình chưa hiểu lắm A có x, y, z và B có x. Bạn tìm key trên B (So sánh thuộc tính B.x) và tìm key trên A (A.x) thì có gì khác nhau về tốc độ chứ ?.
“Nói chung là cache” mình không rõ lắm có phải cache không ?.khi tìm kiếm đối tượng thường thì có thể so khớp cả đối tượng (Họ tên, ngày tháng năm sinh v.v.v…) hoặc so khớp các giá trị định danh số điện thoại.
Tại sao bạn lại phải copy dữ liệu z từ A sang C ? (Xem lại 1).

P/S Bạm có thể nói rõ hơn phần tìm kiếm trên A không.

anon5203072 · September 23, 2018, 4:30am

memcpy() hầu như là cách chuẩn để copy data, nó cũng được tối ưu hết mức có thể rồi. Nên nếu nó có vẻ chậm đối với bạn thì hoặc là nhu cầu của bạn thực sự đặc biệt, hoặc cách tổ chức dữ liệu của bạn không hiệu quả.

Nếu là #1 thì cách tốt nhất bạn có thể làm là SIMD memcpy() (SSE, AVX), copy data theo parallel, viết tay hoặc dùng library.

andynguyen · September 23, 2018, 7:06am

Câu chuyện chỉ là làm sao cho danh sách liên kết đôi chạy nhanh hơn.

Mình có 1 danh sách gốc gọi là (A) chứa data là mảng kiểu char, key, previous, next.

Thay vì để tất cả thông tin vào trong 1 nốt, mình tạo ra 1 danh sách mới (B) mà trong đó mỗi nốt chỉ chứa key, previous và next và 1 con trỏ (ptr) trỏ tới data nốt đó sẽ chứa.

Data của từng nốt thì mình copy lại từ (A) và cấp phát đâu đó trong vùng nhớ không quan trọng. Các nốt sẽ được nối với nốt tương ứng trong (B) bằng 1 con trỏ. Điều quan trọng là khi mình cần dữ liệu của nốt nào trong cái danh sách gốc (A), mình chỉ cần dùng key truyền vào so sánh với key trong (B). Nếu giống nhau thì mình lấy ra giá trị sử dụng con trỏ (ptr).

(B) là tập hợp những nốt nằm kế sát nhau giống như 1 mảng vậy đó.

Lý thuyết là như vậy. Khi so sánh tìm trên danh sách gốc (A) với cái danh sách mình mới tạo ra thì tốc độ tăng lên khoảng 10 lần (đạt yêu cầu). Nhưng có đứa ra tới 16 lần. Thời gian chuyển từ (A) ra (B) và © của mình là ~140ms, của bạn cùng lớp là dưới 100ms. Cái status thì update tự động thôi và ai cũng là anonymous.

Khi mình hỏi thì nó nói là thay đổi cách copy mảng kiểu char từ (A) qua các nốt dữ liệu. Mình thì làm memcpy. Không biết nó có làm gì đặc biệt khác không.

Phong_Ky_Vo · September 23, 2018, 8:32am

bạn có thể up đề lên không ?. thời gian chạy cỡ ms thì nói xuông rất khó để giải quyết được.

Nguyen_Nam4 · September 23, 2018, 8:38am

Việc bạn mô tả thuật toán mới thì không có gì khác biệt so với thuật toán cũ cả.
Có n phần tử, cách cũ hay cách mới bạn đều so sánh từng phần tử như vậy chi phí tốn O(n), không có sự khác biệt về chi phí thuật toán.
Cách bạn tách dữ liệu mà bảo cách mới nhanh hơn thì mình nghĩ rằng bạn dùng tham số chứ không phải tham chiếu. Không biết có đúng không nhưng mình nghĩ là bạn nên cho bọn mình xem code của bạn xử lý dữ liệu như thế nào?

andynguyen · September 25, 2018, 4:27am

Mình không có đề. Mấy cái này test được viết sẵn rồi. Mình được cho 1 cái API rồi cứ theo mấy cái test mà làm thôi. Nhưng hướng đi giống như hình này nè. Code copy của mình cũng đơn giản thôi.
tempsnip

A* arrayA // có data sẵn rồi

B* arrayB = new B[array_length];

C* arrayC = new C[array_length];

A* temp = arrayA.getFirstNode();

while(temp != NULL)

{

arrayB->x = temp ->x;

arrayC->y = temp ->y;

memcpy(arrayC->z, temp ->z, strlen (arrayA->z) + 1);  

temp = temp->next;
arrayB++;
arrayC++;

}

Phong_Ky_Vo · September 25, 2018, 4:34am

Hi Anh Nguyen.

Theo mình không cần thiết copy ra C. Trong B có một con trỏ trỏ thẳng đến A là được. Hoặc đến A->data. (Mất công copy ra tăng gấp đôi ram rồi chỉ dùng mộ mà có nguy cơ dị bội dữ liệu.).
Tuy nhiên nhìn lại vấn đề thì nếu như thế thì còn dùng danh sách liên kết làm gì nữa khi cả x, y đều được lưu trên mảng ? Chuyển A sang dang vector phần data của A vấn được cấp phát động bình thường riêng phần id, và con trỏ đến data được lưu trong vector (Một dạng mảng của C++ tự nhân dôi kích thước).

Phong_Ky_Vo · September 25, 2018, 4:53am

Hi Anh Nguyen
Mình thấy hơi có vần đề với cách giải quyết này của bạn. Theo mình tối ưu code có 2 loại : tối ưu vi mã (những đoạn mã nhỏ như các phép nhân chia công trừ hay copy mảng) nó không là thay đổi thiết kế của hệ thống, tối ưu thiết kế (áp dụng các loại thuật toán mới dữ liệu mới) là thay đổi kiến trúc của hệ thống hoặc một phần.
Quay lại vấn đề của bạn cần hiểu rõ hai lọa dữ liệu là danh sách liên kêt và mảng. Dều là cấu trúc lưu trữ dữ liệu cũng kiểu.

Danh sách liên kết dùng khi các dữ liệu ít ổn định tối ưu cho việc thêm xóa tại vi trí bất kỳ (VD bài toán quản lý trứng trong một lò ấp)
Mảng dùng cho các loại dữ liệu ổn định chủ yếu là truy cập ít thêm xóa. (VD danh shách học sinh trong lớp thường ít thay đổi trong một học kỳ).
Như hiện tại người thiết kế đang dùng danh sách liên kết và bạn chuyển nó sang mảng. Việc đó có thể tối ưu tìm kiếm nhưng nó là việc thêm, xóa, sửa kém hiệu quả hơn. (Khi thêm một phần tử lại phải mở rộng mảng cạche) nếu đa phần các thao tác là thêm xóa thì thực sự bạn làm cho hệ thống chạy chậm đi.

P/S Việc phân biết dữ liệu ổn định hay không, không thực sự rõ ràng. Cái đó phụ thuộc vào yêu cầu bài toán. Bạn có thể thêm các phần tử vào danh sách liên kết theo quy tắc tăng dần (cái này khá nhanh) và tạo mảng index cho cứ 100 phần tử một.

andynguyen · September 25, 2018, 5:38am

Post thứ nhất:
Xin lỗi mình không nói rõ yêu cầu.

Yêu cầu:

Làm cho danh sách liên kết chạy nhanh hơn.
Nốt cần tìm sẽ nằm đâu đó cuối danh sách liên kết. Không được sắp xếp lại danh sách liên kết theo bất cứ thứ tự nào. Muốn tìm thấy nốt đó thì phải chạy hết danh sách không bỏ cái nào.
Muốn làm gì trên danh sách liên kết thì phải đi từng nốt một bằng cách gọi hàm nextNode(). Mặc dù B được khởi tạo giống mảng nhưng phải coi như nó là 1 danh sách liên kết. Nối từng nốt lại với nhau bằng địa chỉ. Muốn dùng các nốt trong B thì phải dùng nextNode().
Không được sử dụng STL: mấy cái như vector bạn vừa kể không được dùng.
Khai báo trong các lớp A, B, C thế nào thì để y chang vậy. Không thay đổi.

Câu hỏi của mình: làm sao tạo một con trỏ trỏ thẳng đến dữ liệu trong A được? Cái này mình không rành. Dữ liệu trong A và C được khai báo như sau: char textData[size];

Post thứ hai:
Mục tiêu hiện tại chỉ là tìm kiếm và lấy ra dữ liệu thôi.
B vẫn là danh sách liên kết đó chứ. Có điều thay vì tạo nốt rồi để nó nằm tùy ý trong bộ nhớ rồi nối tụi nó lại thì mình tạo các nốt đó nằm sát nhau như 1 cái mảng để tăng cach hit rate. Cách làm thì tạo 1 mảng trước rồi copy key , xong 1 nốt thì cứ array+1 để tới địa chỉ tiếp theo tạo nốt mới, cuối cùng thì nối lại.
Thực sự nếu cho dùng mảng và sắp xếp lại rồi mới tìm thì nó rất đơn giản.

Phong_Ky_Vo · September 25, 2018, 6:09am

Hi Anh Nguyen
Vậy cái này nó giống một bài thi hơn. Và chỉ cho A là một danh sách liên kết. Yêu cầu tìm phần tử trong A nhanh nhất mà không xắp xếp lại A ? Phần B và C là bạn tự nghĩ ra hay là cho luôn cả B và C.

P/S Thực sự việc tạo B là một mảng nhưng sau đó truy cập như một danh sách có nhanh hơn không ?

andynguyen · September 25, 2018, 6:40am

Ah, B và C là cho luôn vì muốn tránh tình trạng sử dụng pointer trỏ vào mấy cái mảng chả trong A. Do đó mình bắt buộc phải copy mảng char từ A qua C bằng memcpy.

Có đứa bảo nếu viết tay lại hàm copy chỉ sử dụng cho 1 mục đích này thì sẽ nhanh hơn memcpy. Một cách nữa là dùng overload operator nhưng mình mới học nên bó tay.

Thật sự là nó nhanh hơn. Nếu kiếm bằng cấu trúc cũ A là 8 giây. Cấu trúc mới có 1 giây hơn. Test có timer luôn nên mình biết kết quả.

Lý do là vì nó để sát nhau, thứ 2 nữa là những trường trong B chỉ phục vụ tìm kiếm nên được giữ trong cache. Đó là lý do mình nói dữ liệu của C nằm đâu không quan trọng. Những cái cần để xác định dữ liệu nằm ở nốt nào thì B đã có. Nếu tìm đúng thì nhảy qua C lấy, không cứ chạy tiếp.

Cái này không phải bài thi. Thực hành cho vui thôi coi như điểm danh.

Phong_Ky_Vo · September 25, 2018, 6:40am

Hi Anh Nguyen

B và C buộc phải là index và data à hay chỉ là 2 danh sách chung chung thôi.
Mình không chắc khi để xát nhau thì bạn có truy cập nhanh hơn không khi thực tế vấn phải lấy địa chỉ rồi truy cập một vòng.
Thay copy mảng thì lấy luôn địa chỉ a nhét vào đó là OK.

andynguyen · September 25, 2018, 6:45am

Mình mới edit lại cái post trước đó. Bạn đọc lại nha chứ mình thấy viết 1 cái 2 lần nhìn kì nên ko viết lại.

Phong_Ky_Vo · September 25, 2018, 6:53am

Hi Anh Nguyen.
Có lẽ do mình hơi chậm hiểu nhưng bạn không muốn sử dụng con trỏ để trỏ vào mảng char trong A bằng cách copy nó ra một chỗ khác rồi dùng một con trỏ (Vâng mảng thì vần là con trỏ) để trỏ vào chỗ mới vừa tạo thế thì có gì khác nhau ?

andynguyen · September 25, 2018, 6:57am

Cái đó mình biết nhưng không hiểu tại sao mình viết:
C->randomData = A->randomData thì visual không cho. Nó nói lvalue must be modifiable thì phải.

Phong_Ky_Vo · September 25, 2018, 7:03am

Hi Anh Nguyen.
Cái đó là hạn chế về ngôn ngữ lập trình của bạn. Thử tìm trên stack xem. Mình thấy nó có vẻ là lỗi kiểu dữ liệu thôi.

rogp10 · September 25, 2018, 7:21am

Vậy C->randomData là mảng chứ không phải con trỏ mà gán ngang như vậy (nếu được) nghĩa là shallow copy dữ liệu vẫn nằm trong A.

andynguyen · September 25, 2018, 7:43am

Bingo. Chắc cách tốt nhất là overload = thôi.