Bạn vẫn chưa tính tới thời gian chạy dòng dưới. Thời gian chạy dòng dưới bao gồm thơi gian chạy hàm clock() và thơi gian thực hiện phép div và còn nhiều yếu tố khác. Nên là bạn không thể so sánh kiểu đấy được.

Khi muốn đo tốc độ chạy chương trình, thì đầu tiên cần phải loại bỏ hết những yếu tố có thể ảnh hưởng đến tốc độ chương trình:

• Đầu tiên là mảng arr không làm gì --> compiler có thể optimize bỏ luôn đoạn code này.
• Đoạn code này chạy quá nhanh --> không thể đo chính xác thời gian chạy. Ít nhất phải chạy vòng for lớn gấp 100 lần như vậy
• Độ lớn của mảng arr là lũy thừa của 2 --> có thể ảnh hưởng đến cache của bộ nhớ, do hàm hash của cache dùng dịch bit. Cái này thường sẽ ảnh hưởng đến mảng >= 2 chiều, nhưng tốt nhất là thông thường ko nên để mảng có độ lớn là lũy thừa 2.

Sau khi sửa 3 cái này thì mình thu được code ở dưới, tốc độ chạy 2 vòng for lệch nhau khoảng 6 lần. Vẫn không được 16, nhưng có thể là do còn những cái mà mình chưa biết :)

#include <iostream>
#include <ctime>

#define size (64 * 1024 * 1024 + 11LL)

using namespace std;

int arr[size];

int main(){
        for(int i = 0; i < size; ++i)
            arr[i] = rand() % 10;

	const clock_t begin_time = clock();
        long long size_100 = size * 100LL;
	for (long long i = 0; i < size_100; i++) arr[i % size] *= 3;
	for (long long i = 0; i < size_100; i += 16) arr[i % size] *= 3;
	std::cout << float( clock () - begin_time ) /  CLOCKS_PER_SEC << endl;

        long long sum = 0;
        for(int i = 0; i < size; ++i) sum += arr[i];
        cout << sum << endl;
}

Đúng là trong đoạn code này, cache là yếu tố ảnh hưởng lớn nhất đến tốc độ.

Theo mình biết thì việc truy xuất memory có 2 kiểu cache là spatial locality và temporal locality:

• Với spatial locality thì khi truy xuất 1 ô nhớ, máy sẽ tự động load 1 block tiếp theo sau đó lên cache -> optimize truy xuất những phần tử liên tiếp.
• Với temporal locality thì khi truy xuất 1 ô nhớ máy sẽ đưa ô đó lên cache (nếu cache đầy thì sẽ xóa 1 ô khác ra) -> optimize truy xuất những phần tử với có số lần truy xuất cao.

Tùy theo hệ thống sẽ ưu tiên loại cache nào hơn.

-> Sửa lại một chút từ code của anh RR thì mình thu được tốc độ chênh lệch nhau khoảng 16 lần như mong muốn :D.

#include <iostream>
#include <ctime>

#define size (64 * 1024 * 1024 + 11LL)
#define prime 1009

using namespace std;

int arr[size], pos[size];

int main(){
    for(int i = 0; i < size; ++i) {
        arr[i] = rand() % 10;
        if (i) pos[i] = (pos[i - 1] + prime) % size;
        else pos[i] = 0;
    }

    const clock_t begin_time = clock();
    for (long long i = 0; i < size; i++) arr[pos[i]] *= 3;
    // for (long long i = 0; i < size; i += 16) arr[pos[i]] *= 3;
    std::cout << float( clock () - begin_time ) /  CLOCKS_PER_SEC << endl;

    long long sum = 0;
    for(int i = 0; i < size; ++i) sum += arr[i];
    cout << sum << endl;

    return 0;
}