Hôm nay tôi đã quyết định điểm chuẩn và so sánh một số khác biệt về khả năng tối ưu hóa gcc của std::vector và std::array. Nói chung, tôi đã tìm thấy những gì tôi mong đợi: thực hiện tác vụ trên mỗi bộ sưu tập các mảng ngắn nhanh hơn nhiều so với thực hiện các tác vụ trên một vectơ tương đương thu thập.Tại sao mảng <T, N> lại chậm hơn vector <T>?
Tuy nhiên, tôi tìm thấy một cái gì đó bất ngờ : sử dụng std::vector để lưu trữ các bộ sưu tập của mảng là nhanh hơn so với sử dụngstd::array. Chỉ trong trường hợp nó là kết quả của một số tạo phẩm của một lượng lớn dữ liệu trên stack, tôi cũng đã cố gắng phân bổ nó như một mảng trên heap và trong một mảng kiểu C trên heap (nhưng kết quả vẫn giống như một mảng mảng trên ngăn xếp và một vectơ của mảng).
Bất cứ ý tưởng tại sao std::vector sẽ bao giờ tốt hơn std::array (mà trên đó các trình biên dịch có nhiều thời gian biên dịch thông tin)?
Tôi đã biên soạn bằng cách sử dụng gcc-4.7 -std=c++11 -O3 (gcc-4.6 -std=c++0x -O3 cũng nên dẫn đến câu hỏi hóc búa này). Thời gian chạy được tính bằng cách sử dụng lệnh bash -native time (thời gian người dùng).
Code:
#include <array>
#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>
template <typename VEC>
double fast_sq_dist(const VEC & lhs, const VEC & rhs) {
assert(lhs.size() == rhs.size());
double result = 0.0;
for (int k=0; k<lhs.size(); ++k) {
double tmp = lhs[k] - rhs[k];
result += tmp * tmp;
}
return result;
}
int main() {
const std::size_t K = 20000;
const std::size_t N = 4;
// declare the data structure for the collection
// (uncomment exactly one of these to time it)
// array of arrays
// runtime: 1.32s
std::array<std::array<double, N>, K > mat;
// array of arrays (allocated on the heap)
// runtime: 1.33s
// std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >;
// C-style heap array of arrays
// runtime: 0.93s
// std::array<double, N> * mat = new std::array<double, N>[K];
// vector of arrays
// runtime: 0.93
// std::vector<std::array<double, N> > mat(K);
// vector of vectors
// runtime: 2.16s
// std::vector<std::vector<double> > mat(K, std::vector<double>(N));
// fill the collection with some arbitrary values
for (std::size_t k=0; k<K; ++k) {
for (std::size_t j=0; j<N; ++j)
mat[k][j] = k*N+j;
}
std::cerr << "constructed" << std::endl;
// compute the sum of all pairwise distances in the collection
double tot = 0.0;
for (std::size_t j=0; j<K; ++j) {
for (std::size_t k=0; k<K; ++k)
tot += fast_sq_dist(mat[j], mat[k]);
}
std::cout << tot << std::endl;
return 0;
}
NB 1: Tất cả các phiên bản in cùng một kết quả.
NB 2: Và chỉ để chứng minh rằng sự khác biệt giữa thời gian chạy std::array<std::array<double, N>, K>, std::vector<std::array<double, N> >, và std::vector<std::vector<double> > không chỉ đơn giản là từ hoạt động chuyển/khởi khi phân bổ, các runtimes chỉ đơn giản là phân bổ các bộ sưu tập (ví dụ cho ý kiến ra việc tính toán và in ấn của tot) là 0,000, 0,000 và 0,004 giây, tương ứng.
NB 3: Mỗi phương pháp được biên dịch và chạy riêng biệt (không được định thời gian quay lại trong cùng một tệp thực thi), để ngăn chặn sự khác biệt không công bằng trong bộ nhớ đệm.
NB 4:
hội cho mảng của các mảng: http://ideone.com/SM8dB
hội vector của các mảng: http://ideone.com/vhpJv
hội vector của vector: http://ideone.com/RZTNE
NB 5: Chỉ cần để được hoàn toàn rõ ràng , Tôi không có ý định chỉ trích STL. Một STL hoàn toàn yêu thích và, không chỉ tôi sử dụng nó thường xuyên, chi tiết về việc sử dụng hiệu quả đã dạy tôi rất nhiều tính năng tinh tế và tuyệt vời của C++. Thay vào đó, đây là một sự theo đuổi trí tuệ: Tôi chỉ đơn giản là thời gian để tìm hiểu các nguyên tắc của thiết kế C++ hiệu quả.
Hơn nữa, sẽ không thể đổ lỗi cho STL, vì khó phân tích nguyên nhân của sự khác biệt thời gian chạy: Với tối ưu hóa được bật, nó có thể từ tối ưu hóa trình biên dịch làm chậm mã thay vì làm nhanh nó.Với tối ưu hóa tắt, nó có thể là từ các hoạt động sao chép không cần thiết (sẽ được tối ưu hóa và không bao giờ được thực thi trong mã sản xuất), có thể thiên vị đối với một số loại dữ liệu nhất định.
Nếu bạn tò mò như tôi, tôi rất muốn bạn giúp tìm hiểu điều này.
Hãy thử chạy với số lần lặp như 1000 để xem các giá trị chính xác hơn. Những cái nhìn như họ chỉ có thể là giá trị độ trễ. –
@ColeJohnson Bạn có nghĩa là 'N = 1000' hoặc' K = 1000'? Nếu bạn có nghĩa là 'N = 1000', một vec tơ của mảng gần giống với vectơ của vec-tơ (vì chi phí của việc không bỏ vòng lặp là rất cao). Sử dụng 'N = 1' dẫn đến sự khác biệt cao hơn nhiều giữa vector của mảng và vector của vectơ, bởi vì vector của mảng nên về cơ bản được chuyển đổi thành vectơ gấp đôi. Vì vậy, trường hợp thú vị nhất để so sánh mảng mảng và vectơ của mảng là 'K << N' (' << 'trong nghĩa của toán học, chứ không phải ý nghĩa thay đổi bit). – user
Điều gì sẽ xảy ra nếu bạn trao đổi hai bài kiểm tra? – Mehrdad