Là std :: deque nhanh hơn std :: vector để chèn vào cuối?

Question

Tôi bắt đầu làm so sánh giữa:

• chèn ở phía trước của danh sách
• chèn ở mặt sau của một vector
• chèn ở phía trước của một deque

Nhưng sau đó tôi nhận thấy thậm chí trên push_back() deque dường như nhanh hơn. Tôi phải làm điều gì đó sai, tôi không thể tin rằng một vùng chứa tổng quát hơn sẽ hoạt động tốt hơn một vùng chứa cụ thể.

Mã của tôi sử dụng google benchmark:

#include "benchmark/benchmark.h" 
#include <deque> 
#include <vector> 

#define NUM_INS 1000 

static void BM_InsertVector(benchmark::State& state) { 
    std::vector<int> v; 
    v.reserve(NUM_INS); 
    while (state.KeepRunning()) { 
     state.PauseTiming(); 
     v.clear(); 
     state.ResumeTiming(); 
     for (size_t i = 0; i < NUM_INS; i++) 
      v.push_back(i); 
    } 
} 
BENCHMARK(BM_InsertVector); 

static void BM_InsertDeque(benchmark::State& state) { 
    std::deque<int> v; 
    while (state.KeepRunning()) { 
     state.PauseTiming(); 
     v.clear(); 
     state.ResumeTiming(); 
     for (size_t i = 0; i < NUM_INS; i++) 
      v.push_back(i); 
    } 
} 
BENCHMARK(BM_InsertDeque); 

BENCHMARK_MAIN(); 

Kết quả:

Run on (1 X 2592 MHz CPU) 
2016-02-18 14:03:47 
Benchmark   Time(ns) CPU(ns) Iterations 
------------------------------------------------ 
BM_InsertVector  2820  2470  312500         
BM_InsertDeque  1872  1563  406977 

tôi nhận thấy một số khác biệt khi chơi với số phần tử, nhưng deque luôn nhanh hơn so với vector.

EDIT: biên dịch: gcc version 5.2.1 biên soạn với: g++ -O3 -std=c++11 push_front.cpp -lbenchmark -lpthread

Tôi nghĩ rằng -O3 thực sự là công cụ; khi tôi tắt nó, tôi nhận được hiệu suất kém hơn kém hiệu suất.

Answer 1

Tôi nghĩ rằng véc tơ chậm hơn vì bạn đang gọi clear(), tùy thuộc vào việc triển khai STL của bạn, có thể giải phóng bộ nhớ mảng cơ bản.

Nếu trường hợp đó xảy ra thì cuộc gọi reserve() của bạn sẽ không giúp ích gì; và vectơ của bạn liên tục thay đổi kích thước, yêu cầu mọi phần tử phải được chuyển sang bộ nhớ mới, lớn hơn, mới hơn.

Answer 2

Về cơ bản có 3 nguồn chi phí liên quan đến việc liên tục phụ thêm yếu tố để một container động:

1. Quản lý bộ nhớ.
2. Sổ kế toán nội bộ của vùng chứa.
3. Bất kỳ hoạt động nào cần phải được thực hiện trên chính các phần tử đó. Đáng chú ý; bất kỳ vùng chứa nào làm mất hiệu lực tham chiếu khi chèn đều có khả năng di chuyển/sao chép các phần tử xung quanh.

Hãy bắt đầu với 1. vector giữ yêu cầu gấp đôi so với bộ nhớ, và deque phân bổ khối có kích thước cố định (deque thường thực hiện như một mảng của mảng, với các mảng tầng thấp hơn là kích thước cố định). Yêu cầu bộ nhớ nhiều hơn có thể mất nhiều thời gian hơn yêu cầu ít hơn, nhưng thông thường trừ khi đống của bạn là rất phân mảnh yêu cầu cho một đoạn lớn cùng một lúc là cách nhanh nhất để có được một số bộ nhớ. Nó có thể nhanh hơn để phân bổ một meg một lần, sau đó yêu cầu một kilobyte 1000 lần. Vì vậy, có vẻ như rõ ràng rằng vector cuối cùng sẽ có lợi thế ở đây (cho đến khi container quá lớn nó bị ảnh hưởng bởi sự phân mảnh). Tuy nhiên, điều này không phải là cuối cùng: bạn chỉ yêu cầu 1000 yếu tố. Tôi đã viết mã sau đây http://coliru.stacked-crooked.com/a/418b18ff8a81c1c0. Nó không phải là rất thú vị nhưng về cơ bản nó sử dụng một phân bổ tầm thường mà tăng một toàn cầu để xem có bao nhiêu phân bổ được thực hiện.

Trong quá trình chuẩn mực, vector yêu cầu bộ nhớ 11 lần và deque chỉ 10. deque tiếp tục yêu cầu số tiền tương tự, vector yêu cầu số tiền gấp đôi. Đồng thời, vector phải gọi số free 10 lần. Và deque 0. Điều này có vẻ giống như một chiến thắng nhỏ cho deque.

Đối với sổ sách kế toán nội bộ, vector có triển khai đơn giản hơn deque. Xét cho cùng, vector chỉ là một mảng động và deque là một mảng các mảng và hoàn toàn phức tạp hơn. Vì vậy, đây rõ ràng là một chiến thắng cho vector.

Cuối cùng, các yếu tố tự vận hành. Trong deque, không có gì được di chuyển. Với vector, mọi phân bổ đống mới cũng liên quan đến việc di chuyển tất cả các phần tử. Nó có thể được tối ưu hóa để sử dụng memcpy cho các loại tầm thường, nhưng thậm chí thấy, đó là 10 cuộc gọi đến memcpy để sao chép 1, 2, 4, 8 ... 512 số nguyên. Đây rõ ràng là một chiến thắng cho deque.

Tôi có thể suy đoán rằng cranking lên đến O3 cho phép nội suy rất tích cực của nhiều mã phức tạp hơn trong deque, giảm trọng số 2. Nhưng rõ ràng, trừ khi bạn làm một chi tiết hơn (rất cẩn thận!) Điểm chuẩn, bạn sẽ không bao giờ biết chắc chắn.

Chủ yếu, bài đăng này là để cho thấy rằng nó phức tạp hơn so với chỉ đơn giản là một container chuyên ngành so với một tổng quát hơn. Tôi sẽ đưa ra một dự đoán mặc dù (đặt cổ của tôi ra để được cắt bỏ, như nó đã được): nếu bạn tăng số lượng các yếu tố bởi thậm chí nói một yếu tố của 2 hoặc 4, bạn sẽ không nhìn thấy deque giành chiến thắng nữa. Đó là bởi vì deque sẽ tạo ra gấp đôi hoặc gấp đôi số lần phân bổ heap, nhưng véc tơ sẽ chỉ tạo thêm 1-2 lần nữa.

Tôi cũng có thể lưu ý ở đây rằng deque thực sự là một cấu trúc dữ liệu lẻ; về mặt lý thuyết là một mảng các mảng nhưng trong nhiều triển khai mảng đó là một kích thước nhất định, hoặc chỉ một phần tử, tùy theo cái nào lớn hơn. Ngoài ra, một số bảo đảm O lớn là vô nghĩa. push_back chỉ cố định thời gian cố định, bởi vì trong C++, chỉ hoạt động trên các phần tử được tính vào O lớn. Nếu không, nó phải rõ ràng, vì nó là mảng mảng, mảng cấp cao nhất sẽ có tỷ lệ thuận với số lượng các phần tử đã được lưu trữ. Và cuối cùng là mảng cấp cao nhất chạy ra khỏi phòng, và bạn phải tái phân bổ nó, di chuyển con trỏ O (N). Vì vậy, nó không thực sự O (1) push_back.