Câu hỏi Tại sao bổ sung theo nguyên tố nhanh hơn nhiều trong các vòng riêng biệt hơn trong một vòng lặp kết hợp?


Giả sử a1, b1, c1d1 trỏ đến bộ nhớ heap và mã số của tôi có vòng lặp cốt lõi sau đây.

const int n = 100000;

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
    c1[j] += d1[j];
}

Vòng lặp này được thực hiện 10.000 lần thông qua một bên ngoài khác for vòng lặp. Để tăng tốc, tôi đã đổi mã thành:

for (int j = 0; j < n; j++) {
    a1[j] += b1[j];
}

for (int j = 0; j < n; j++) {
    c1[j] += d1[j];
}

Biên soạn trên MS Visual C ++ 10.0 với tối ưu hóa đầy đủ và SSE2 được bật cho 32 bit trên một Intel Core 2 Duo (x64), ví dụ đầu tiên mất 5,5 giây và ví dụ vòng lặp kép chỉ mất 1,9 giây. Câu hỏi của tôi là: (Vui lòng tham khảo câu hỏi được nhắc lại của tôi ở phía dưới)

PS: Tôi không chắc chắn, nếu điều này giúp:

Việc tháo gỡ vòng lặp đầu tiên về cơ bản trông như thế này (khối này được lặp lại khoảng năm lần trong toàn bộ chương trình):

movsd       xmm0,mmword ptr [edx+18h]
addsd       xmm0,mmword ptr [ecx+20h]
movsd       mmword ptr [ecx+20h],xmm0
movsd       xmm0,mmword ptr [esi+10h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [edx+20h]
addsd       xmm0,mmword ptr [ecx+28h]
movsd       mmword ptr [ecx+28h],xmm0
movsd       xmm0,mmword ptr [esi+18h]
addsd       xmm0,mmword ptr [eax+38h]

Mỗi vòng lặp của ví dụ vòng lặp kép tạo ra mã này (khối sau được lặp lại khoảng ba lần):

addsd       xmm0,mmword ptr [eax+28h]
movsd       mmword ptr [eax+28h],xmm0
movsd       xmm0,mmword ptr [ecx+20h]
addsd       xmm0,mmword ptr [eax+30h]
movsd       mmword ptr [eax+30h],xmm0
movsd       xmm0,mmword ptr [ecx+28h]
addsd       xmm0,mmword ptr [eax+38h]
movsd       mmword ptr [eax+38h],xmm0
movsd       xmm0,mmword ptr [ecx+30h]
addsd       xmm0,mmword ptr [eax+40h]
movsd       mmword ptr [eax+40h],xmm0

Câu hỏi hóa ra là không có sự liên quan, vì hành vi này phụ thuộc nhiều vào kích thước của mảng (n) và bộ đệm CPU. Vì vậy, nếu có thêm sự quan tâm, tôi rephrase câu hỏi:

Bạn có thể cung cấp một số thông tin chi tiết vững chắc về các chi tiết dẫn đến các hành vi bộ nhớ cache khác nhau như được minh họa bởi năm khu vực trên biểu đồ sau không?

Nó cũng có thể là thú vị để chỉ ra sự khác biệt giữa CPU / cache kiến ​​trúc, bằng cách cung cấp một đồ thị tương tự cho các CPU.

PPS: Đây là mã đầy đủ. Nó sử dụng TBB  Tick_Count cho thời gian có độ phân giải cao hơn, có thể bị vô hiệu hóa bằng cách không xác định TBB_TIMING Macro:

#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>

//#define TBB_TIMING

#ifdef TBB_TIMING   
#include <tbb/tick_count.h>
using tbb::tick_count;
#else
#include <time.h>
#endif

using namespace std;

//#define preallocate_memory new_cont

enum { new_cont, new_sep };

double *a1, *b1, *c1, *d1;


void allo(int cont, int n)
{
    switch(cont) {
      case new_cont:
        a1 = new double[n*4];
        b1 = a1 + n;
        c1 = b1 + n;
        d1 = c1 + n;
        break;
      case new_sep:
        a1 = new double[n];
        b1 = new double[n];
        c1 = new double[n];
        d1 = new double[n];
        break;
    }

    for (int i = 0; i < n; i++) {
        a1[i] = 1.0;
        d1[i] = 1.0;
        c1[i] = 1.0;
        b1[i] = 1.0;
    }
}

void ff(int cont)
{
    switch(cont){
      case new_sep:
        delete[] b1;
        delete[] c1;
        delete[] d1;
      case new_cont:
        delete[] a1;
    }
}

double plain(int n, int m, int cont, int loops)
{
#ifndef preallocate_memory
    allo(cont,n);
#endif

#ifdef TBB_TIMING   
    tick_count t0 = tick_count::now();
#else
    clock_t start = clock();
#endif

    if (loops == 1) {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++){
                a1[j] += b1[j];
                c1[j] += d1[j];
            }
        }
    } else {
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                a1[j] += b1[j];
            }
            for (int j = 0; j < n; j++) {
                c1[j] += d1[j];
            }
        }
    }
    double ret;

#ifdef TBB_TIMING   
    tick_count t1 = tick_count::now();
    ret = 2.0*double(n)*double(m)/(t1-t0).seconds();
#else
    clock_t end = clock();
    ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC);
#endif

#ifndef preallocate_memory
    ff(cont);
#endif

    return ret;
}


void main()
{   
    freopen("C:\\test.csv", "w", stdout);

    char *s = " ";

    string na[2] ={"new_cont", "new_sep"};

    cout << "n";

    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= 2; i++)
#ifdef preallocate_memory
            cout << s << i << "_loops_" << na[preallocate_memory];
#else
            cout << s << i << "_loops_" << na[j];
#endif

    cout << endl;

    long long nmax = 1000000;

#ifdef preallocate_memory
    allo(preallocate_memory, nmax);
#endif

    for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2)))
    {
        const long long m = 10000000/n;
        cout << n;

        for (int j = 0; j < 2; j++)
            for (int i = 1; i <= 2; i++)
                cout << s << plain(n, m, j, i);
        cout << endl;
    }
}

(Nó cho thấy FLOP / s cho các giá trị khác nhau của n.)

enter image description here


1996
2017-12-17 20:40


gốc


Có thể là hệ điều hành mà làm chậm trong khi tìm kiếm bộ nhớ vật lý mỗi khi bạn truy cập nó và có một cái gì đó giống như bộ nhớ cache trong trường hợp truy cập thứ cấp vào cùng một memblock. - AlexTheo
Bạn đang biên dịch với tối ưu hóa? Điều đó trông giống như rất nhiều mã asm cho O2 ... - Luchian Grigore
Chỉ cần cầu kỳ, hai đoạn mã này không tương đương do các con trỏ có khả năng trùng lặp. C99 có restricttừ khóa cho các tình huống như vậy. Tôi không biết nếu MSVC có một cái gì đó tương tự. Tất nhiên, nếu đây là vấn đề thì mã SSE sẽ không chính xác. - user510306
Điều này có thể có liên quan đến bí danh bộ nhớ. Với một vòng lặp, d1[j] có thể aliase với a1[j], do đó trình biên dịch có thể rút lại từ việc thực hiện một số tối ưu hóa bộ nhớ. Trong khi điều đó không xảy ra nếu bạn tách các bài viết thành bộ nhớ trong hai vòng lặp. - rturrado
@RocketRoy Trước khi bạn đi xung quanh cáo buộc mọi người làm cho công cụ lên, tại sao bạn không thực sự cố gắng chú ý đến một số chi tiết? Bạn nói trong câu trả lời của bạn rằng bạn không thể tái tạo nó. Câu hỏi này là 5 tuổi. Bạn đã xem xét khả năng xử lý đã được cải thiện kể từ đó? Nhìn vào câu trả lời của tôi, nó cho thấy rằng nó tái tạo thời gian lớn trên Core 2, nhưng ít hơn Nehalem và sau đó. - Mysticial


Các câu trả lời:


Khi phân tích sâu hơn về điều này, tôi tin rằng đây là (ít nhất một phần) do sự liên kết dữ liệu của bốn con trỏ. Điều này sẽ gây ra một số mức độ xung đột của ngân hàng / bộ nhớ cache.

Nếu tôi đã đoán chính xác cách bạn phân bổ mảng của mình, họ có thể được căn chỉnh với dòng trang.

Điều này có nghĩa rằng tất cả các truy cập của bạn trong mỗi vòng lặp sẽ rơi trên cùng một cách bộ nhớ cache. Tuy nhiên, bộ xử lý Intel đã có kết nối bộ nhớ cache L1 8 chiều trong một thời gian. Nhưng trong thực tế, hiệu suất không hoàn toàn đồng đều. Truy cập 4-way vẫn chậm hơn so với nói 2 chiều.

EDIT: Nó trong thực tế trông giống như bạn đang phân bổ tất cả các mảng riêng biệt. Thông thường khi yêu cầu phân bổ lớn như vậy, người cấp phát sẽ yêu cầu các trang mới từ hệ điều hành. Do đó, có nhiều khả năng là các phân bổ lớn sẽ xuất hiện ở cùng độ lệch từ một ranh giới trang.

Đây là mã thử nghiệm:

int main(){
    const int n = 100000;

#ifdef ALLOCATE_SEPERATE
    double *a1 = (double*)malloc(n * sizeof(double));
    double *b1 = (double*)malloc(n * sizeof(double));
    double *c1 = (double*)malloc(n * sizeof(double));
    double *d1 = (double*)malloc(n * sizeof(double));
#else
    double *a1 = (double*)malloc(n * sizeof(double) * 4);
    double *b1 = a1 + n;
    double *c1 = b1 + n;
    double *d1 = c1 + n;
#endif

    //  Zero the data to prevent any chance of denormals.
    memset(a1,0,n * sizeof(double));
    memset(b1,0,n * sizeof(double));
    memset(c1,0,n * sizeof(double));
    memset(d1,0,n * sizeof(double));

    //  Print the addresses
    cout << a1 << endl;
    cout << b1 << endl;
    cout << c1 << endl;
    cout << d1 << endl;

    clock_t start = clock();

    int c = 0;
    while (c++ < 10000){

#if ONE_LOOP
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
            c1[j] += d1[j];
        }
#else
        for(int j=0;j<n;j++){
            a1[j] += b1[j];
        }
        for(int j=0;j<n;j++){
            c1[j] += d1[j];
        }
#endif

    }

    clock_t end = clock();
    cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl;

    system("pause");
    return 0;
}

Kết quả điểm chuẩn:

EDIT: Kết quả trên một thực tế Máy kiến ​​trúc lõi 2:

2 x Intel Xeon X5482 Harpertown @ 3,2 GHz:

#define ALLOCATE_SEPERATE
#define ONE_LOOP
00600020
006D0020
007A0020
00870020
seconds = 6.206

#define ALLOCATE_SEPERATE
//#define ONE_LOOP
005E0020
006B0020
00780020
00850020
seconds = 2.116

//#define ALLOCATE_SEPERATE
#define ONE_LOOP
00570020
00633520
006F6A20
007B9F20
seconds = 1.894

//#define ALLOCATE_SEPERATE
//#define ONE_LOOP
008C0020
00983520
00A46A20
00B09F20
seconds = 1.993

Quan sát:

  • 6,206 giây với một vòng lặp và 2.116 giây với hai vòng. Điều này tái tạo chính xác kết quả của OP.

  • Trong hai bài kiểm tra đầu tiên, các mảng được phân bổ riêng biệt.Bạn sẽ nhận thấy rằng tất cả chúng đều có cùng một liên kết tương đối so với trang.

  • Trong hai thử nghiệm thứ hai, các mảng được đóng gói với nhau để phá vỡ sự liên kết đó. Ở đây bạn sẽ thấy cả hai vòng lặp nhanh hơn. Hơn nữa, vòng lặp thứ hai (đôi) bây giờ là chậm hơn như bạn thường mong đợi.

Như @Stephen Cannon chỉ ra trong các bình luận, rất có khả năng là sự liên kết này gây ra giả mạo răng giả trong các đơn vị tải / lưu trữ hoặc bộ nhớ cache. Tôi đã tìm hiểu về điều này và thấy rằng Intel thực sự có một bộ đếm phần cứng cho -sự đánh địa chỉ một phần quầy hàng:

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 Vùng - Giải thích

Vùng 1:

Cái này rất dễ. Tập dữ liệu quá nhỏ đến mức hiệu năng bị chi phối bởi chi phí như vòng lặp và phân nhánh.

Vùng 2:

Ở đây, khi các kích thước dữ liệu tăng, lượng chi phí tương đối giảm xuống và hiệu suất "bão hòa". Ở đây hai vòng chậm hơn vì nó có vòng lặp gấp đôi và phân nhánh trên cao.

Tôi không chắc chắn chính xác những gì đang xảy ra ở đây ... Alignment vẫn có thể chơi một hiệu ứng như Agner Fog đề cập xung đột ngân hàng bộ nhớ cache. (Liên kết đó là về Sandy Bridge, nhưng ý tưởng vẫn nên được áp dụng cho Core 2.)

Vùng 3:

Tại thời điểm này, dữ liệu không còn phù hợp với bộ đệm L1 nữa. Vì vậy, hiệu suất được giới hạn bởi L1 <-> L2 băng thông bộ nhớ cache.

Vùng 4:

Hiệu suất giảm trong vòng lặp đơn là những gì chúng ta đang quan sát. Và như đã đề cập, điều này là do sự liên kết mà (rất có thể) nguyên nhân giả mạo răng giả các quầy hàng trong các đơn vị lưu / tải bộ xử lý.

Tuy nhiên, để giả mạo sai xảy ra, phải có một bước tiến lớn đủ giữa các tập dữ liệu. Đây là lý do tại sao bạn không thấy điều này trong khu vực 3.

Vùng 5:

Tại thời điểm này, không có gì phù hợp trong bộ nhớ cache. Vì vậy, bạn bị ràng buộc bởi băng thông bộ nhớ.


2 x Intel X5482 Harpertown @ 3.2 GHz Intel Core i7 870 @ 2.8 GHz Intel Core i7 2600K @ 4.4 GHz


1546
2017-12-17 21:17



1: Tôi nghĩ đây là câu trả lời. Trái ngược với những gì tất cả các câu trả lời khác nói, nó không phải là về các biến thể vòng lặp duy nhất vốn có nhiều bộ nhớ cache nhớ, đó là về sự liên kết cụ thể của các mảng gây ra bộ nhớ cache nhớ. - Oliver Charlesworth
Điều này; một giả mạo răng giả gian hàng là lời giải thích có khả năng nhất. - Stephen Canon
@VictorT. Tôi đã sử dụng mã OP được liên kết đến. Nó tạo ra một tệp .css mà tôi có thể mở trong Excel và tạo một biểu đồ từ nó. - Mysticial
@Nawaz Một trang thường là 4KB. Nếu bạn nhìn vào các địa chỉ thập lục phân mà tôi in ra, các bài kiểm tra được phân bổ riêng đều có cùng modulo 4096. (đó là 32-byte từ đầu ranh giới 4KB) Có lẽ GCC không có hành vi này. Điều đó có thể giải thích tại sao bạn không thấy sự khác biệt. - Mysticial
Đối với bất kỳ ai quan tâm, đây là đọc tốt về sự liên kết bộ nhớ và đây là vài  liên kết trên đường  dữ liệu được lưu trữ trong bộ nhớ - New Alexandria


OK, câu trả lời đúng chắc chắn phải làm điều gì đó với bộ nhớ cache CPU. Nhưng để sử dụng đối số bộ nhớ cache có thể khá khó khăn, đặc biệt là không có dữ liệu.

Có rất nhiều câu trả lời, dẫn đến nhiều cuộc thảo luận, nhưng hãy đối mặt với nó: Các vấn đề về bộ nhớ cache có thể rất phức tạp và không phải là một chiều. Chúng phụ thuộc nhiều vào kích thước của dữ liệu, vì vậy câu hỏi của tôi là không công bằng: Hóa ra là ở một điểm rất thú vị trong biểu đồ bộ nhớ cache.

Câu trả lời của @ Mysticial đã thuyết phục rất nhiều người (kể cả tôi), có lẽ bởi vì nó là người duy nhất dường như dựa vào sự thật, nhưng đó chỉ là một "điểm dữ liệu" của sự thật.

Đó là lý do tại sao tôi kết hợp thử nghiệm của mình (sử dụng phân bổ liên tục so với phân bổ riêng biệt) và lời khuyên của Người trả lời @James '.

Các đồ thị dưới đây cho thấy rằng hầu hết các câu trả lời và đặc biệt là phần lớn các nhận xét cho câu hỏi và câu trả lời có thể được coi là hoàn toàn sai hoặc đúng tùy thuộc vào kịch bản và thông số chính xác được sử dụng.

Lưu ý rằng câu hỏi ban đầu của tôi là n = 100.000. Điểm này (do tai nạn) thể hiện hành vi đặc biệt:

  1. Nó sở hữu sự khác biệt lớn nhất giữa một và hai phiên bản loop'ed (gần như là một yếu tố của ba)

  2. Đây là điểm duy nhất, trong đó một vòng lặp (cụ thể là với phân bổ liên tục) đánh bại phiên bản hai vòng lặp. (Điều này làm cho câu trả lời của Mysticial có thể, ở tất cả.)

Kết quả sử dụng dữ liệu được khởi tạo:

Enter image description here

Kết quả sử dụng dữ liệu chưa được khởi tạo (đây là những gì mà Mysticial đã kiểm tra):

Enter image description here

Và đây là điều khó giải thích: Dữ liệu khởi tạo, được phân bổ một lần và được sử dụng lại cho mỗi trường hợp thử nghiệm sau đây có kích thước vector khác nhau:

Enter image description here

Đề nghị

Mọi câu hỏi liên quan đến hiệu năng cấp thấp trên Stack Overflow phải được yêu cầu để cung cấp thông tin MFLOPS cho toàn bộ phạm vi kích thước dữ liệu có liên quan đến bộ nhớ cache! Đó là một sự lãng phí thời gian của tất cả mọi người để suy nghĩ về câu trả lời và đặc biệt là thảo luận với những người khác mà không có thông tin này.


195
2017-12-18 01:29



+1 Phân tích tốt. Tôi không có ý định rời dữ liệu chưa được khởi tạo ngay từ đầu. Nó chỉ xảy ra rằng các cấp phát zeroed họ anyway. Vì vậy, các dữ liệu khởi tạo là những gì quan trọng. Tôi vừa chỉnh sửa câu trả lời của mình với kết quả trên thực tế Máy kiến ​​trúc Core 2 và chúng gần gũi hơn với những gì bạn đang quan sát. Một điều nữa là tôi đã thử nghiệm một loạt các kích thước n và nó cho thấy khoảng cách hiệu suất tương tự cho n = 80000, n = 100000, n = 200000, v.v ... - Mysticial
@Micicial Tôi nghĩ rằng hệ điều hành thực hiện trang zeroing bất cứ khi nào đưa ra các trang mới cho một quá trình để tránh gián điệp quá trình liên quan có thể. - v.oddou


Vòng lặp thứ hai liên quan đến hoạt động bộ nhớ cache ít hơn rất nhiều, vì vậy nó dễ dàng hơn cho bộ vi xử lý để theo kịp với các yêu cầu bộ nhớ.


63
2017-12-17 20:47



Bạn đang nói rằng biến thể thứ hai phát sinh ít cache hơn? Tại sao? - Oliver Charlesworth
@Oli: Trong phiên bản đầu tiên, bộ vi xử lý cần truy cập bốn dòng bộ nhớ tại một thời điểm- a[i], b[i], c[i] và d[i] Trong phiên bản thứ hai, nó chỉ cần hai. Điều này làm cho nó nhiều hơn khả thi để nạp tiền cho những dòng trong khi thêm. - Puppy
Nhưng miễn là các mảng không va chạm trong bộ nhớ cache, mỗi biến thể yêu cầu cùng một số lần đọc và ghi chính xác từ / đến bộ nhớ chính. Vì vậy, kết luận là (tôi nghĩ) rằng hai mảng xảy ra được va chạm tất cả các thời gian. - Oliver Charlesworth
Tôi không theo. Mỗi hướng dẫn (ví dụ: mỗi trường hợp x += y), có hai lần đọc và một lần viết. Điều này đúng cho cả hai biến thể. Do đó, yêu cầu băng thông CPU <-> bộ nhớ cache là như nhau. Vì vậy, miễn là không có xung đột, yêu cầu băng thông bộ đệm RAM <-> cũng giống nhau. - Oliver Charlesworth
Như đã nói trong stackoverflow.com/a/1742231/102916, phần cứng tìm nạp trước của Pentium M có thể theo dõi 12 luồng chuyển tiếp khác nhau (và tôi mong đợi phần cứng sau này ít nhất cũng có khả năng). Vòng 2 vẫn chỉ đọc bốn luồng, vì vậy cũng nằm trong giới hạn đó. - Brooks Moses


Hãy tưởng tượng bạn đang làm việc trên một cỗ máy n chỉ là giá trị phù hợp cho nó để có thể giữ hai mảng của bạn trong bộ nhớ cùng một lúc, nhưng tổng bộ nhớ có sẵn, thông qua bộ nhớ đệm đĩa, vẫn đủ để giữ tất cả bốn.

Giả sử một chính sách lưu trữ LIFO đơn giản, mã này:

for(int j=0;j<n;j++){
    a[j] += b[j];
}
for(int j=0;j<n;j++){
    c[j] += d[j];
}

đầu tiên sẽ gây ra a và b được nạp vào RAM và sau đó được làm việc hoàn toàn trong RAM. Khi vòng lặp thứ hai bắt đầu, c và d sau đó sẽ được tải từ đĩa vào RAM và hoạt động trên.

vòng lặp khác

for(int j=0;j<n;j++){
    a[j] += b[j];
    c[j] += d[j];
}

sẽ đưa ra hai mảng và trang trong hai mảng khác mọi lúc quanh vòng lặp. Điều này rõ ràng là nhiều chậm hơn.

Bạn có thể không nhìn thấy bộ nhớ đệm đĩa trong các thử nghiệm của mình nhưng có thể bạn đang thấy các tác dụng phụ của một số hình thức lưu bộ nhớ đệm khác.


Dường như có một chút nhầm lẫn / hiểu lầm ở đây vì vậy tôi sẽ cố gắng xây dựng một chút bằng cách sử dụng một ví dụ.

Nói n = 2 và chúng tôi đang làm việc với byte. Trong kịch bản của tôi, chúng tôi có chỉ 4 byte bộ nhớ cache và phần còn lại của bộ nhớ của chúng tôi chậm hơn đáng kể (truy cập 100 lần lâu hơn).

Giả sử một chính sách bộ nhớ đệm khá câm của nếu byte không có trong bộ nhớ đệm, hãy đặt nó ở đó và nhận byte sau trong khi chúng ta đang ở đó bạn sẽ nhận được một kịch bản một cái gì đó như thế này:

  • Với

    for(int j=0;j<n;j++){
     a[j] += b[j];
    }
    for(int j=0;j<n;j++){
     c[j] += d[j];
    }
    
  • bộ nhớ đệm a[0] và a[1] sau đó b[0] và b[1] và thiết lập a[0] = a[0] + b[0] trong bộ nhớ cache - hiện có bốn byte trong bộ nhớ cache, a[0], a[1] và b[0], b[1]. Chi phí = 100 + 100.

  • bộ a[1] = a[1] + b[1] trong bộ nhớ cache. Chi phí = 1 + 1.
  • Lặp lại cho c và d.
  • Tổng chi phí = (100 + 100 + 1 + 1) * 2 = 404

  • Với

    for(int j=0;j<n;j++){
     a[j] += b[j];
     c[j] += d[j];
    }
    
  • bộ nhớ đệm a[0] và a[1] sau đó b[0] và b[1] và thiết lập a[0] = a[0] + b[0] trong bộ nhớ cache - hiện có bốn byte trong bộ nhớ cache, a[0], a[1] và b[0], b[1]. Chi phí = 100 + 100.

  • đẩy ra a[0], a[1], b[0], b[1] từ bộ nhớ cache và bộ nhớ cache c[0] và c[1] sau đó d[0] và d[1] và thiết lập c[0] = c[0] + d[0] trong bộ nhớ cache. Chi phí = 100 + 100.
  • Tôi nghi ngờ bạn đang bắt đầu nhìn thấy nơi tôi đang đi.
  • Tổng chi phí = (100 + 100 + 100 + 100) * 2 = 800

Đây là một kịch bản bộ nhớ cache cổ điển.


37
2017-12-18 01:36



Điều này là không chính xác. Tham chiếu đến một phần tử cụ thể của một mảng không làm cho toàn bộ mảng được phân trang từ đĩa (hoặc từ bộ nhớ không được lưu trữ); chỉ trang có liên quan hoặc dòng bộ nhớ cache được phân trang. - Brooks Moses
@Brooks Moses - Nếu bạn đi qua toàn bộ mảng, như đang xảy ra ở đây, sau đó nó sẽ. - OldCurmudgeon
Vâng, vâng, nhưng đó là những gì xảy ra trong toàn bộ hoạt động, không phải những gì xảy ra mỗi lần vòng quanh. Bạn đã tuyên bố rằng biểu mẫu thứ hai "sẽ xuất hiện hai mảng và trang ở hai mảng khác mỗi lần xung quanh vòng lặp" và đó là những gì tôi đang phản đối. Bất kể kích thước của mảng tổng thể, ở giữa vòng lặp này, RAM của bạn sẽ giữ một trang từ mỗi mảng trong bốn mảng và không có gì sẽ được phân trang cho đến khi vòng lặp kết thúc với nó. - Brooks Moses
Trong trường hợp cụ thể n chỉ là giá trị phù hợp cho nó để có thể giữ hai mảng của bạn trong bộ nhớ cùng một lúc sau đó truy cập tất cả các phần tử của bốn mảng trong một vòng lặp chắc chắn sẽ kết thúc đập. - OldCurmudgeon
Tại sao bạn ở lại vòng lặp đó 2 trang trong toàn bộ a1 và b1 cho bài tập đầu tiên, thay vì chỉ là trang đầu tiên của mỗi bài? (Bạn có giả định các trang 5-byte, vì vậy một trang là một nửa của bộ nhớ RAM của bạn? Đó không chỉ là mở rộng quy mô, đó là hoàn toàn không giống như một bộ xử lý thực sự.) - Brooks Moses


Nó không phải vì một mã khác, nhưng vì bộ nhớ đệm: RAM chậm hơn so với thanh ghi CPU và bộ nhớ cache nằm bên trong CPU để tránh ghi RAM mỗi lần biến thay đổi. Nhưng bộ nhớ cache không lớn như RAM, do đó, nó chỉ là một phần nhỏ của nó.

Mã đầu tiên sửa đổi các địa chỉ bộ nhớ ở xa xen kẽ chúng tại mỗi vòng lặp, do đó yêu cầu liên tục làm mất hiệu lực bộ đệm ẩn.

Mã thứ hai không thay thế: nó chỉ chạy trên các địa chỉ lân cận hai lần. Điều này làm cho tất cả các công việc được hoàn thành trong bộ nhớ cache, làm mất hiệu lực nó chỉ sau khi vòng lặp thứ hai bắt đầu.


27
2017-12-17 20:49



Tại sao điều này khiến bộ nhớ cache liên tục bị vô hiệu? - Oliver Charlesworth
@OliCharlesworth: Hãy suy nghĩ về bộ nhớ cache dưới dạng bản sao cứng của một dải địa chỉ bộ nhớ tiếp giáp. Nếu bạn giả vờ truy cập một địa chỉ không phải là một phần của chúng, bạn phải tải lại bộ đệm. Và nếu một cái gì đó trong bộ nhớ cache đã được sửa đổi, nó phải được ghi lại trong RAM, hoặc nó sẽ bị mất. Trong mã mẫu, 4 ​​vecto của 100'000 số nguyên (400kBytes) có nhiều khả năng hơn dung lượng bộ đệm L1 (128 hoặc 256K). - Emilio Garavaglia
Kích thước của bộ đệm không có tác động trong kịch bản này. Mỗi phần tử mảng chỉ được sử dụng một lần, và sau đó nó không quan trọng nếu nó bị trục xuất. Kích thước bộ nhớ cache chỉ quan trọng nếu bạn có địa phương thời gian (tức là bạn sẽ sử dụng lại các yếu tố tương tự trong tương lai). - Oliver Charlesworth
@OliCharlesworth: Nếu tôi phải tải một giá trị mới trong bộ đệm, và đã có một giá trị trong đó đã được sửa đổi, trước tiên tôi phải viết nó xuống, và điều này làm cho tôi chờ đợi cho việc ghi xảy ra. - Emilio Garavaglia
Nhưng trong cả hai biến thể của mã OP, mỗi giá trị được sửa đổi chính xác một lần. Bạn làm như vậy cùng số lượng ghi lại trong mỗi biến thể. - Oliver Charlesworth


Tôi không thể nhân rộng các kết quả được thảo luận ở đây.

Tôi không biết liệu mã điểm chuẩn nghèo có bị đổ lỗi hay không, nhưng hai phương thức nằm trong phạm vi 10% trên máy tính của tôi bằng cách sử dụng mã sau đây và một vòng lặp thường chỉ nhanh hơn một chút - như bạn muốn chờ đợi.

Kích thước mảng dao động từ 2 ^ 16 đến 2 ^ 24, sử dụng tám vòng. Tôi đã cẩn thận để khởi tạo các mảng nguồn để += nhiệm vụ không hỏi FPU để thêm bộ nhớ rác được hiểu là đôi.

Tôi chơi xung quanh với các đề án khác nhau, chẳng hạn như đặt nhiệm vụ b[j], d[j] đến InitToZero[j] bên trong các vòng lặp, và cũng với việc sử dụng += b[j] = 1 và += d[j] = 1và tôi nhận được kết quả khá nhất quán.

Như bạn có thể mong đợi, khởi tạo b và d bên trong vòng lặp sử dụng InitToZero[j] đã đưa ra cách tiếp cận kết hợp một lợi thế, khi chúng được thực hiện back-to-back trước khi các bài tập a và c, nhưng vẫn trong vòng 10%. Đi con số.

Phần cứng là Dell XPS 8500 với thế hệ 3 Core i7 @ 3,4 GHz và bộ nhớ 8 GB. Đối với 2 ^ 16 đến 2 ^ 24, sử dụng tám vòng, thời gian tích lũy là 44.987 và 40.965 tương ứng. Visual C ++ 2010, được tối ưu hóa hoàn toàn.

PS: Tôi đã thay đổi các vòng để đếm ngược về 0 và phương pháp kết hợp nhanh hơn một chút. Gãi đầu tôi. Lưu ý số lượng mảng và số vòng lặp mảng mới.

// MemBufferMystery.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <cmath>
#include <string>
#include <time.h>

#define  dbl    double
#define  MAX_ARRAY_SZ    262145    //16777216    // AKA (2^24)
#define  STEP_SZ           1024    //   65536    // AKA (2^16)

int _tmain(int argc, _TCHAR* argv[]) {
    long i, j, ArraySz = 0,  LoopKnt = 1024;
    time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0;
    dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL;

    a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl));
    // Initialize array to 1.0 second.
    for(j = 0; j< MAX_ARRAY_SZ; j++) {
        InitToOnes[j] = 1.0;
    }

    // Increase size of arrays and time
    for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) {
        a = (dbl *)realloc(a, ArraySz * sizeof(dbl));
        b = (dbl *)realloc(b, ArraySz * sizeof(dbl));
        c = (dbl *)realloc(c, ArraySz * sizeof(dbl));
        d = (dbl *)realloc(d, ArraySz * sizeof(dbl));
        // Outside the timing loop, initialize
        // b and d arrays to 1.0 sec for consistent += performance.
        memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl));
        memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl));

        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
                c[j] += d[j];
            }
        }
        Cumulative_Combined += (clock()-start);
        printf("\n %6i miliseconds for combined array sizes %i and %i loops",
                (int)(clock()-start), ArraySz, LoopKnt);
        start = clock();
        for(i = LoopKnt; i; i--) {
            for(j = ArraySz; j; j--) {
                a[j] += b[j];
            }
            for(j = ArraySz; j; j--) {
                c[j] += d[j];
            }
        }
        Cumulative_Separate += (clock()-start);
        printf("\n %6i miliseconds for separate array sizes %i and %i loops \n",
                (int)(clock()-start), ArraySz, LoopKnt);
    }
    printf("\n Cumulative combined array processing took %10.3f seconds",
            (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC));
    printf("\n Cumulative seperate array processing took %10.3f seconds",
        (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC));
    getchar();

    free(a); free(b); free(c); free(d); free(InitToOnes);
    return 0;
}

Tôi không chắc chắn lý do tại sao nó đã được quyết định rằng MFLOPS là một số liệu có liên quan. Mặc dù ý tưởng là tập trung vào các truy cập bộ nhớ, vì vậy tôi đã cố gắng giảm thiểu số lượng thời gian tính toán dấu phẩy động. Tôi còn lại trong +=, nhưng tôi không chắc tại sao.

Một phép gán thẳng không có tính toán sẽ là một thử nghiệm sạch hơn về thời gian truy cập bộ nhớ và sẽ tạo ra một phép thử thống nhất không phụ thuộc vào số vòng lặp. Có lẽ tôi đã bỏ lỡ điều gì đó trong cuộc trò chuyện, nhưng đáng để suy nghĩ hai lần. Nếu dấu cộng bị bỏ ra khỏi nhiệm vụ, thời gian tích lũy gần như giống nhau ở mỗi 31 giây.


16
2017-12-30 01:34



Hình phạt không chính xác mà bạn đề cập ở đây là khi một tải / cửa hàng riêng lẻ được sắp xếp không đúng (bao gồm cả tải / cửa hàng SSE không được ký). Nhưng đó không phải là trường hợp ở đây vì hiệu suất là nhạy cảm với sự sắp xếp tương đối của các mảng khác nhau. Không có sự sai lệch ở cấp độ giảng dạy. Mỗi tải / cửa hàng được căn chỉnh đúng cách. - Mysticial


Đó là bởi vì CPU không có nhiều bộ nhớ cache bị bỏ sót (nơi mà nó phải đợi dữ liệu mảng đến từ các chip RAM). Nó sẽ là thú vị cho bạn để điều chỉnh kích thước của các mảng liên tục để bạn vượt quá kích thước của bộ nhớ cache cấp 1 (L1), và sau đó là bộ nhớ cache cấp 2 (L2), của CPU và vẽ thời gian để mã của bạn thực thi dựa trên kích thước của các mảng. Biểu đồ không phải là một đường thẳng như bạn mong đợi.


14
2017-12-17 20:52



Tôi không tin rằng có bất kỳ tương tác nào giữa kích thước bộ nhớ cache và kích thước mảng. Mỗi phần tử mảng chỉ được sử dụng một lần và sau đó có thể được gỡ bỏ một cách an toàn. Cũng có thể có sự tương tác giữa bộ nhớ cache hàng kích thước và kích thước mảng, mặc dù, nếu nó gây ra bốn mảng xung đột. - Oliver Charlesworth
Bạn nói đúng, đó là ví dụ sai để chứng minh hiệu ứng này - James


Vòng lặp đầu tiên thay thế bằng văn bản trong mỗi biến. Thứ hai và thứ ba chỉ làm cho các bước nhảy nhỏ có kích thước phần tử.

Thử viết hai đường song song gồm 20 cây thánh giá bằng bút và giấy cách nhau 20 cm. Hãy thử một khi hoàn thành một và sau đó các dòng khác và thử một thời gian khác bằng cách viết một chéo trong mỗi dòng luân phiên.


12
2017-08-17 15:23





Câu hỏi gốc

Tại sao một vòng lặp chậm hơn nhiều so với hai vòng?


Đánh giá vấn đề

Mã OP:

const int n=100000;

for(int j=0;j<n;j++){
    a1[j] += b1[j];
    c1[j] += d1[j];
}

for(int j=0;j<n;j++){
    a1[j] += b1[j];
}
for(int j=0;j<n;j++){
    c1[j] += d1[j];
}

Sự xem xét

Xem xét câu hỏi ban đầu của OP về 2 biến thể của vòng lặp và câu hỏi được sửa đổi của anh đối với hành vi của bộ nhớ cache cùng với nhiều câu trả lời xuất sắc khác và nhận xét hữu ích; Tôi muốn thử và làm một cái gì đó khác ở đây bằng cách tham gia một cách tiếp cận khác nhau về tình hình và vấn đề này.


Phương pháp tiếp cận

Xem xét hai vòng và tất cả các cuộc thảo luận về bộ nhớ cache và trang nộp Tôi muốn có cách tiếp cận khác để xem xét điều này từ một quan điểm khác nhau. Một trong đó không liên quan đến bộ nhớ cache và các tập tin trang cũng như thực thi để cấp phát bộ nhớ, trong thực tế, cách tiếp cận này thậm chí không quan tâm đến phần cứng thực tế hoặc phần mềm nào cả.


Quan điểm

Sau khi xem mã trong một thời gian, nó trở nên khá rõ ràng vấn đề là gì và cái gì đang tạo ra nó. Cho phép chia nhỏ điều này thành một vấn đề thuật toán và xem xét nó từ quan điểm của việc sử dụng các ký hiệu toán học sau đó áp dụng một tương tự cho các vấn đề toán học cũng như các thuật toán.


Những gì chúng tôi biết

Chúng tôi biết là vòng lặp của anh ấy sẽ chạy 100.000 lần. Chúng tôi cũng biết rằng a1, b1, c1 & d1 là các con trỏ trên kiến ​​trúc 64 bit. Trong C ++ trên máy 32 bit, tất cả các con trỏ đều là 4 byte và trên máy 64 bit, chúng có kích thước 8 byte vì con trỏ có chiều dài cố định. Chúng tôi biết rằng chúng tôi có 32 byte để phân bổ trong cả hai trường hợp. Sự khác biệt duy nhất là chúng tôi đang phân bổ 32 byte hoặc 2 bộ 2-8byte trên mỗi lần lặp trong đó trong trường hợp thứ 2 chúng tôi phân bổ 16 byte cho mỗi lần lặp cho cả hai vòng độc lập. Vì vậy, cả hai vòng vẫn bằng 32 byte trong tổng số phân bổ. Với thông tin này, chúng ta hãy tiếp tục và hiển thị toán học, thuật toán và tương tự của nó. Chúng tôi biết số lần mà cùng một tập hợp hoặc nhóm hoạt động sẽ phải được thực hiện trong cả hai trường hợp. Chúng tôi biết số lượng bộ nhớ cần được phân bổ trong cả hai trường hợp. Chúng tôi có thể giả định rằng tải công việc tổng thể của phân bổ giữa hai trường hợp sẽ xấp xỉ như nhau.


Những gì chúng ta không biết

Chúng tôi không biết sẽ mất bao lâu cho mỗi trường hợp trừ khi chúng tôi đặt một bộ đếm và chạy thử nghiệm đánh dấu băng ghế dự bị. Tuy nhiên các nhãn hiệu băng ghế dự bị đã được đưa vào từ câu hỏi gốc và từ một số câu trả lời cũng như nhận xét và chúng ta có thể thấy sự khác biệt đáng kể giữa hai và đây là toàn bộ lý do của câu hỏi này và vấn đề trả lời bắt đầu với.


Hãy điều tra 

Nó đã được rõ ràng rằng nhiều người đã làm điều này bằng cách nhìn vào phân bổ heap, kiểm tra đánh dấu băng ghế dự bị, nhìn vào RAM, Cache và Page Files. Nhìn vào các điểm dữ liệu cụ thể và các chỉ mục lặp lại cụ thể cũng được bao gồm và các cuộc hội thoại khác nhau về vấn đề cụ thể này có nhiều người bắt đầu đặt câu hỏi về những thứ liên quan khác về nó. Vậy làm thế nào để chúng ta bắt đầu xem xét vấn đề này bằng cách sử dụng các thuật toán toán học và áp dụng một tương tự cho nó? Chúng tôi bắt đầu bằng cách thực hiện một vài xác nhận! Sau đó, chúng tôi xây dựng thuật toán của chúng tôi từ đó.


Xác nhận của chúng tôi:

  • Chúng ta sẽ để vòng lặp của chúng ta và các lần lặp của nó là một Summation bắt đầu từ 1 và kết thúc ở 100000 thay vì bắt đầu bằng 0 như trong các vòng cho chúng ta không cần phải lo lắng về lược đồ lập chỉ mục 0 của địa chỉ bộ nhớ vì chúng ta chỉ quan tâm đến bản thân thuật toán.
  • Trong cả hai trường hợp, chúng tôi có 4 chức năng để làm việc với và 2 cuộc gọi chức năng với 2 thao tác đang được thực hiện trên mỗi cuộc gọi chức năng. Vì vậy, chúng tôi sẽ thiết lập các chức năng này và các hàm gọi là F1(), F2(), f(a), f(b), f(c) và f(d).

Các thuật toán:

Trường hợp đầu tiên: - Chỉ có một tổng kết nhưng hai cuộc gọi hàm độc lập.

Sum n=1 : [1,100000] = F1(), F2();
                       F1() = { f(a) = f(a) + f(b); }
                       F2() = { f(c) = f(c) + f(d);  }

Trường hợp thứ 2: - Hai lần triệu tập nhưng mỗi lần có chức năng gọi riêng.

Sum1 n=1 : [1,100000] = F1();
                        F1() = { f(a) = f(a) + f(b); }

Sum2 n=1 : [1,100000] = F1();
                        F1() = { f(c) = f(c) + f(d); }

Nếu bạn nhận thấy F2() chỉ tồn tại trong Sum nơi cả hai Sum1 và Sum2 chỉ chứa F1(). Điều này cũng sẽ được hiển nhiên sau này khi chúng tôi bắt đầu kết luận rằng có một loại tối ưu hóa xảy ra từ thuật toán thứ hai.

Lặp lại thông qua trường hợp đầu tiên Sum cuộc gọi f(a) sẽ tự thêm vào f(b) sau đó nó gọi f(c) điều đó sẽ làm tương tự nhưng thêm f(d) cho chính nó cho mỗi 100000 iterations. Trong trường hợp thứ hai chúng ta có Sum1 và Sum2 Và cả hai hành động giống như thể chúng là cùng một hàm được gọi hai lần liên tiếp. Trong trường hợp này chúng ta có thể điều trị Sum1 và Sum2 chỉ đơn giản là cũ Sum Ở đâu Sum trong trường hợp này trông như thế này: Sum n=1 : [1,100000] { f(a) = f(a) + f(b); } và bây giờ điều này trông giống như một tối ưu hóa, nơi chúng ta chỉ có thể xem xét nó là cùng một chức năng.


Tóm tắt với tương tự

Với những gì chúng ta thấy trong trường hợp thứ hai, nó gần như xuất hiện như thể có tối ưu hóa vì cả hai vòng lặp đều có cùng chữ ký chính xác, nhưng đây không phải là vấn đề thực sự. Vấn đề không phải là công việc đang được thực hiện bởi f(a),f(b),f(c)&f(d) trong cả hai trường hợp và so sánh giữa hai trường hợp đó là sự khác biệt trong khoảng cách mà Tổng kết phải di chuyển trong cả hai trường hợp cho bạn sự khác biệt về thời gian thực hiện.

Hãy nghĩ về For Loops như là Summations điều đó lặp lại như là một Boss đó là đưa ra mệnh lệnh cho hai người A & B và công việc của họ là thịt C & D tương ứng và nhận một số gói từ họ và trả lại. Trong tương tự ở đây vòng lặp for hoặc lặp lại tổng kết và điều kiện kiểm tra bản thân không thực sự đại diện cho Boss. Điều gì thực sự đại diện cho Boss ở đây không phải từ các thuật toán toán học thực tế trực tiếp, nhưng từ khái niệm thực tế của Scope và Code Block trong một thường trình hoặc tiểu thường trình, phương pháp, chức năng, đơn vị dịch thuật, vv Thuật toán đầu tiên có 1 phạm vi mà thuật toán thứ 2 có 2 phạm vi liên tiếp.

Trong trường hợp đầu tiên trên mỗi cuộc gọi, trượt Boss đi tới A và đưa ra mệnh lệnh và A đi để lấy B's gói sau đó Boss đi tới C và cung cấp cho các đơn đặt hàng để làm như vậy và nhận được gói từ D trên mỗi lần lặp lại.

Trong trường hợp thứ hai, Boss làm việc trực tiếp với A đi và lấy B's gói cho đến khi tất cả các gói được nhận. Sau đó, Bosslàm việc với C làm tương tự để nhận tất cả D's gói.

Vì chúng ta đang làm việc với một con trỏ 8 byte và xử lý việc phân bổ Heap, hãy xem xét vấn đề này ở đây. Hãy để chúng tôi nói rằng Boss cách 100 feet A và đó A cách 500 feet C. Chúng ta không cần phải lo lắng về việc Boss ban đầu từ C bởi vì trật tự của hành quyết. Trong cả hai trường hợp, Boss ban đầu đi từ A đầu tiên sau đó đến B. Sự tương tự này không phải là để nói rằng khoảng cách này là chính xác; nó chỉ là một trường hợp thử nghiệm sử dụng để hiển thị các hoạt động của các thuật toán. Trong nhiều trường hợp khi thực hiện phân bổ heap và làm việc với các tệp cache và trang, khoảng cách giữa các vị trí địa chỉ có thể không thay đổi nhiều về sự khác biệt hoặc chúng có thể phụ thuộc rất nhiều vào bản chất của các kiểu dữ liệu và kích thước mảng.


Các trường hợp thử nghiệm:

Trường hợp đầu tiên: Trong lần lặp đầu tiên Boss ban đầu phải đi 100 feet để đưa phiếu lệnh đến A và A biến mất và làm việc của mình, nhưng sau đó Boss phải đi 500 feet để C để cho anh ta phiếu lệnh. Sau đó, trên lần lặp tiếp theo và mọi lần lặp lại khác sau Boss phải đi qua lại 500 feet giữa hai người.

Trường hợp thứ hai:  The Boss phải đi 100 feet trên lần lặp đầu tiên A, nhưng sau đó anh ấy đã ở đó và chờ đợi A để lấy lại cho đến khi tất cả phiếu được lấp đầy. Sau đó, Boss phải đi 500 feet trên lần lặp đầu tiên C bởi vì C cách 500 feet A kể từ này Boss( Summation, For Loop ) đang được gọi ngay sau khi làm việc với A và rồi chờ đợi như anh ta đã làm với A cho đến khi tất cả C's phiếu lệnh được thực hiện.


Sự khác biệt trong khoảng cách di chuyển

const n = 100000
distTraveledOfFirst = (100 + 500) + ((n-1)*(500 + 500); 
// Simplify
distTraveledOfFirst = 600 + (99999*100);
distTraveledOfFirst = 600 + 9999900;
distTraveledOfFirst =  10000500;
// Distance Traveled On First Algorithm = 10,000,500ft

distTraveledOfSecond = 100 + 500 = 600;
// Distance Traveled On Second Algorithm = 600ft;    

So sánh các giá trị tùy ý

Chúng ta có thể dễ dàng thấy rằng 600 là ít hơn 10 triệu. Bây giờ điều này không chính xác, bởi vì chúng ta không biết sự khác biệt thực sự về khoảng cách giữa địa chỉ RAM hoặc từ Cache hoặc Page File mỗi cuộc gọi trên mỗi lần lặp lại là do nhiều biến không nhìn thấy khác, nhưng đây chỉ là một đánh giá về tình hình để nhận thức và cố gắng nhìn vào nó từ kịch bản xấu nhất.

Vì vậy, bằng những con số này nó sẽ gần như trông giống như Thuật toán Một nên chậm hơn 99% so với Thuật toán Hai; tuy nhiên, đây chỉ là The Boss's một phần hoặc trách nhiệm của các thuật toán và nó không tính đến các công nhân thực tế A, B, C, & D và những gì họ phải làm trên mỗi lần lặp của Vòng lặp. Vì vậy, công việc của ông chủ chỉ chiếm khoảng 15 - 40% tổng số công việc đang được thực hiện. Vì vậy, phần lớn công việc được thực hiện thông qua công nhân có tác động lớn hơn một chút đến việc giữ tỷ lệ chênh lệch tốc độ xuống khoảng 50-70%


Quan sát: - - Sự khác biệt giữa hai thuật toán

Trong tình huống này, nó là cấu trúc của quá trình công việc đang được thực hiện và nó đi để chỉ ra rằng Trường hợp 2hiệu quả hơn từ cả việc tối ưu hóa một phần của việc có một khai báo và định nghĩa hàm tương tự, nơi nó chỉ là các biến khác nhau theo tên. Và chúng ta cũng thấy rằng tổng quãng đường đi vào Trường hợp 1 xa hơn rất nhiều so với Trường hợp 2 và chúng ta có thể xem xét khoảng cách này Yếu tố thời gian giữa hai thuật toán. Trường hợp 1 có nhiều việc phải làm hơn Trường hợp 2 làm. Điều này cũng được thấy trong bằng chứng của ASM được hiển thị giữa cả hai trường hợp. Ngay cả với những gì đã được nói về những trường hợp này, nó cũng không tính đến thực tế là trong Trường hợp 1 ông chủ sẽ phải đợi cả hai A & C quay lại trước khi anh ấy có thể quay lại A một lần nữa trong lần lặp tiếp theo và nó cũng không tính đến thực tế là nếu A hoặc là B mất một thời gian rất dài rồi cả Boss và (các) nhân viên khác cũng đang chờ ở một nơi nhàn rỗi. Trong Trường hợp 2 người duy nhất nhàn rỗi là Boss cho đến khi công nhân quay trở lại. Vì vậy, ngay cả điều này có ảnh hưởng đến thuật toán.


Phần kết luận:

Trường hợp 1 là một vấn đề nội suy cổ điển xảy ra là một vấn đề không hiệu quả. Tôi cũng nghĩ rằng đây là một trong những lý do hàng đầu tại sao nhiều kiến ​​trúc và nhà phát triển máy đã kết thúc việc xây dựng và thiết kế các hệ thống đa lõi với khả năng thực hiện các ứng dụng đa luồng cũng như lập trình song song.

Vì vậy, thậm chí nhìn vào nó từ cách tiếp cận này mà không cần liên quan đến cách phần cứng, hệ điều hành và trình biên dịch làm việc cùng nhau để thực hiện phân bổ đống có liên quan đến làm việc với RAM, Cache, Page Files, vv; toán học đằng sau nó đã cho chúng ta thấy cái nào trong hai cái này là giải pháp tốt hơn từ việc sử dụng sự tương tự ở trên, nơi Boss hoặc là Summations là những người For Loops phải đi lại giữa các công nhân A & B. Chúng ta có thể dễ dàng thấy rằng Trường hợp 2 ít nhất là 1/2 nhanh nếu không nhiều hơn một chút Trường hợp 1 do sự khác biệt trong khoảng cách đi du lịch và thời gian thực hiện. Và toán học này xếp hàng gần như hầu như và hoàn hảo với cả Bench Mark Times cũng như Số lượng khác biệt về số lượng Hướng dẫn lắp ráp.



Câu hỏi sửa đổi OPs (s)

EDIT: Các câu hỏi hóa ra là không có sự liên quan, như hành vi nghiêm trọng phụ thuộc vào kích thước của mảng (n) và bộ nhớ cache CPU. Vì vậy, nếu có thêm sự quan tâm, tôi rephrase câu hỏi:

Bạn có thể cung cấp một số thông tin chi tiết vững chắc về các chi tiết dẫn đến các hành vi bộ nhớ cache khác nhau như được minh họa bởi năm khu vực trên biểu đồ sau không?

Nó cũng có thể là thú vị để chỉ ra sự khác biệt giữa CPU / cache kiến ​​trúc, bằng cách cung cấp một đồ thị tương tự cho các CPU.


Về những câu hỏi này

Như tôi đã chứng minh mà không nghi ngờ gì, có một vấn đề cơ bản ngay cả trước khi Phần cứng và Phần mềm tham gia. Bây giờ là cho việc quản lý bộ nhớ và bộ nhớ đệm cùng với các tập tin trang, vv mà tất cả các công trình cùng nhau trong một tập hợp các hệ thống giữa: The Architecture {Hardware, Firmware, một số Trình điều khiển nhúng, Kernels và Bộ hướng dẫn ASM}, The OS{Hệ thống quản lý tập tin và bộ nhớ, Trình điều khiển và Registry}, The Compiler {Đơn vị dịch và tối ưu hóa mã nguồn} và thậm chí là Source Code chính nó với (các) thuật toán đặc biệt của nó; chúng ta có thể thấy rằng có một nút cổ chai đang xảy ra trong thuật toán đầu tiên trước khi chúng ta áp dụng nó cho bất kỳ máy nào với bất kỳ tùy ý nào Architecture, OSProgrammable Languageso với thuật toán thứ hai. Vì vậy, đã tồn tại một vấn đề trước khi liên quan đến bản chất của một máy tính hiện đại.


Kết quả cuối cùng

Tuy nhiên; nó không phải là để nói rằng những câu hỏi mới không quan trọng bởi vì bản thân họ là và họ đóng một vai trò sau khi tất cả. Chúng tác động đến các thủ tục và hiệu suất tổng thể và điều đó hiển nhiên với các đồ thị và đánh giá khác nhau từ nhiều người đã đưa ra (các) câu trả lời và (các) nhận xét của họ. Nếu bạn chú ý đến sự tương tự của Boss và hai công nhân A & B những người đã phải đi và lấy các gói từ C & D tương ứng và xem xét các ký hiệu toán học của hai thuật toán được đề cập, bạn có thể thấy rằng thậm chí không có sự tham gia của máy tính Case 2 nhanh hơn khoảng 60% so với Case 1 và khi bạn nhìn vào biểu đồ và biểu đồ sau khi các thuật toán này được áp dụng cho mã nguồn, được biên dịch và tối ưu hóa và thực thi thông qua hệ điều hành để thực hiện các thao tác trên phần cứng đã cho, bạn thậm chí còn thấy sự suy giảm hơn một chút giữa các khác biệt trong các thuật toán này.

Bây giờ nếu tập hợp "Dữ liệu" là khá nhỏ, nó có thể không có vẻ như tất cả những gì xấu của một sự khác biệt lúc đầu tiên nhưng kể từ Case 1 nói về 60 - 70% chậm hơn Case 2 chúng ta có thể xem xét sự tăng trưởng của hàm này như là về sự khác biệt về thời gian thực thi:

DeltaTimeDifference approximately = Loop1(time) - Loop2(time)
//where 
Loop1(time) = Loop2(time) + (Loop2(time)*[0.6,0.7]) // approximately
// So when we substitute this back into the difference equation we end up with 
DeltaTimeDifference approximately = (Loop2(time) + (Loop2(time)*[0.6,0.7])) - Loop2(time)
// And finally we can simplify this to
DeltaTimeDifference approximately = [0.6,0.7]*(Loop2(time)

Và xấp xỉ này là sự khác biệt trung bình giữa hai vòng này cả về mặt thuật toán lẫn hoạt động của máy liên quan đến tối ưu hóa phần mềm và hướng dẫn máy. Vì vậy, khi tập dữ liệu phát triển tuyến tính, thì sự khác biệt về thời gian giữa hai tập dữ liệu là như thế nào. Thuật toán 1 có nhiều lần tìm nạp hơn thuật toán 2 hiển nhiên khi Boss phải di chuyển qua lại khoảng cách tối đa giữa A & C cho mỗi lần lặp sau lần lặp đầu tiên trong khi Thuật toán 2 Boss đã phải đi đến A một lần và sau đó sau khi được thực hiện với A anh ta phải đi một khoảng cách tối đa chỉ một lần khi đi từ A đến C.

Vì vậy, cố gắng để có Boss tập trung vào làm hai việc tương tự cùng một lúc và tung hứng họ qua lại thay vì tập trung vào các nhiệm vụ tương tự tương tự sẽ khiến anh ta khá tức giận vào cuối ngày vì anh phải đi lại và làm việc gấp đôi. Do đó không mất phạm vi của tình huống bằng cách để cho sếp của bạn đi vào một nút cổ chai nội suy vì vợ / chồng và con cái của ông chủ sẽ không đánh giá cao điều đó.


3
2018-01-30 14:00



Đã một thời gian kể từ khi tôi đăng câu trả lời này, nhưng tôi cũng muốn thêm một nhận xét nhanh có thể giúp hiểu điều này: Theo cách tương tự của tôi với Boss như vòng lặp hoặc tổng kết hoặc lặp qua vòng lặp, chúng tôi cũng có thể xem xét ông chủ này là sự kết hợp giữa Stack Frame & Stack Pointer quản lý phạm vi và các biến stack và địa chỉ bộ nhớ của các vòng lặp. - Francis Cugler


Có thể cũ C ++ và tối ưu hóa. Trong máy tính của tôi, tôi đã đạt được tốc độ gần như giống nhau:

một vòng lặp: 1.577ms hai vòng: 1.507ms

Tôi chạy VS2015 trên bộ xử lý E5-1620 3.5Ghz với RAM 16Gb


0
2017-07-11 07:00