Tại sao chương trình của tôi chậm khi lặp qua chính xác 8192 phần tử?

763
Noname 2012-09-05 03:51.

Đây là phần trích xuất từ ​​chương trình được đề cập. Ma trận img[][]có kích thước SIZE × SIZE và được khởi tạo tại:

img[j][i] = 2 * j + i

Sau đó, bạn tạo một ma trận res[][]và mỗi trường ở đây được tạo thành giá trị trung bình của 9 trường xung quanh nó trong ma trận img. Đường viền được để ở mức 0 cho đơn giản.

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Đó là tất cả những gì có trong chương trình. Vì lợi ích của sự hoàn chỉnh, đây là những gì xảy ra trước đây. Không có mã nào sau đó. Như bạn có thể thấy, nó chỉ là khởi tạo.

#define SIZE 8192
float img[SIZE][SIZE]; // input image
float res[SIZE][SIZE]; //result of mean filter
int i,j,k,l;
for(i=0;i<SIZE;i++) 
    for(j=0;j<SIZE;j++) 
        img[j][i] = (2*j+i)%8196;

Về cơ bản, chương trình này chậm khi SIZE là bội số của 2048, ví dụ: thời gian thực thi:

SIZE = 8191: 3.44 secs
SIZE = 8192: 7.20 secs
SIZE = 8193: 3.18 secs

Trình biên dịch là GCC. Theo những gì tôi biết, điều này là do quản lý bộ nhớ, nhưng tôi không thực sự biết quá nhiều về chủ đề đó, đó là lý do tại sao tôi hỏi ở đây.

Ngoài ra, làm thế nào để khắc phục điều này cũng sẽ tốt, nhưng nếu ai đó có thể giải thích những thời gian thực hiện này, tôi đã đủ vui rồi.

Tôi đã biết về malloc / free, nhưng vấn đề không phải là dung lượng bộ nhớ được sử dụng, mà chỉ là thời gian thực thi, vì vậy tôi không biết điều đó sẽ giúp ích như thế nào.

2 answers

962
Mysticial 2012-09-05 04:43.

Sự khác biệt là do cùng một vấn đề siêu căn chỉnh từ các câu hỏi liên quan sau:

  • Tại sao chuyển vị ma trận 512x512 lại chậm hơn nhiều so với chuyển vị ma trận 513x513?
  • Phép nhân ma trận: Sự khác biệt nhỏ về kích thước ma trận, sự khác biệt lớn về thời gian

Nhưng đó chỉ là vì có một vấn đề khác với mã.

Bắt đầu từ vòng lặp ban đầu:

for(i=1;i<SIZE-1;i++) 
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        for(k=-1;k<2;k++) 
            for(l=-1;l<2;l++) 
                res[j][i] += img[j+l][i+k];
        res[j][i] /= 9;
}

Đầu tiên hãy chú ý rằng hai vòng lặp bên trong là không đáng kể. Chúng có thể được hủy cuộn như sau:

for(i=1;i<SIZE-1;i++) {
    for(j=1;j<SIZE-1;j++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Vì vậy, điều đó để lại hai vòng ngoài mà chúng tôi quan tâm.

Bây giờ chúng ta có thể thấy vấn đề giống nhau trong câu hỏi này: Tại sao thứ tự của các vòng lặp lại ảnh hưởng đến hiệu suất khi lặp qua một mảng 2D?

Bạn đang lặp lại theo cột ma trận thay vì theo hàng.


Để giải quyết vấn đề này, bạn nên hoán đổi hai vòng lặp.

for(j=1;j<SIZE-1;j++) {
    for(i=1;i<SIZE-1;i++) {
        res[j][i]=0;
        res[j][i] += img[j-1][i-1];
        res[j][i] += img[j  ][i-1];
        res[j][i] += img[j+1][i-1];
        res[j][i] += img[j-1][i  ];
        res[j][i] += img[j  ][i  ];
        res[j][i] += img[j+1][i  ];
        res[j][i] += img[j-1][i+1];
        res[j][i] += img[j  ][i+1];
        res[j][i] += img[j+1][i+1];
        res[j][i] /= 9;
    }
}

Điều này loại bỏ hoàn toàn tất cả các truy cập không tuần tự, do đó bạn không còn bị chậm ngẫu nhiên trên lũy thừa lớn-của-hai.


Core i7 920 @ 3,5 GHz

Mã gốc:

8191: 1.499 seconds
8192: 2.122 seconds
8193: 1.582 seconds

Vòng ngoài được thay đổi:

8191: 0.376 seconds
8192: 0.357 seconds
8193: 0.351 seconds
57
bokan 2012-09-05 07:00.

Các bài kiểm tra sau đã được thực hiện với trình biên dịch Visual C ++ vì nó được sử dụng trong cài đặt Qt Creator mặc định (tôi đoán là không có cờ tối ưu hóa). Khi sử dụng GCC, không có sự khác biệt lớn giữa phiên bản của Mystical và mã "được tối ưu hóa" của tôi. Vì vậy, kết luận là tối ưu hóa trình biên dịch chăm sóc tối ưu hóa vi mô tốt hơn con người (cuối cùng là tôi). Tôi để phần còn lại của câu trả lời của tôi để tham khảo.


Xử lý hình ảnh theo cách này không hiệu quả. Tốt hơn là sử dụng mảng một chiều. Xử lý tất cả các pixel được thực hiện trong một vòng lặp. Truy cập ngẫu nhiên vào các điểm có thể được thực hiện bằng cách sử dụng:

pointer + (x + y*width)*(sizeOfOnePixel)

Trong trường hợp cụ thể này, tốt hơn nên tính toán và lưu vào bộ nhớ cache tổng của ba nhóm pixel theo chiều ngang vì chúng được sử dụng ba lần mỗi nhóm.

Tôi đã thực hiện một số bài kiểm tra và tôi nghĩ nó đáng được chia sẻ. Mỗi kết quả là trung bình của năm bài kiểm tra.

Mã gốc của người dùng1615209:

8193: 4392 ms
8192: 9570 ms

Phiên bản của Mystical:

8193: 2393 ms
8192: 2190 ms

Hai lần vượt qua sử dụng mảng 1D: lần đầu tiên vượt qua cho tổng chiều ngang, lần thứ hai cho tổng dọc và trung bình. Hai địa chỉ vượt qua với ba con trỏ và chỉ số gia tăng như thế này:

imgPointer1 = &avg1[0][0];
imgPointer2 = &avg1[0][SIZE];
imgPointer3 = &avg1[0][SIZE+SIZE];

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(*(imgPointer1++)+*(imgPointer2++)+*(imgPointer3++))/9;
}

8193: 938 ms
8192: 974 ms

Hai vượt qua bằng cách sử dụng một mảng 1D và địa chỉ như thế này:

for(i=SIZE;i<totalSize-SIZE;i++){
    resPointer[i]=(hsumPointer[i-SIZE]+hsumPointer[i]+hsumPointer[i+SIZE])/9;
}

8193: 932 ms
8192: 925 ms

Một lần vượt qua bộ nhớ đệm ngang chỉ tính một hàng phía trước để chúng ở trong bộ nhớ cache:

// Horizontal sums for the first two lines
for(i=1;i<SIZE*2;i++){
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
}
// Rest of the computation
for(;i<totalSize;i++){
    // Compute horizontal sum for next line
    hsumPointer[i]=imgPointer[i-1]+imgPointer[i]+imgPointer[i+1];
    // Final result
    resPointer[i-SIZE]=(hsumPointer[i-SIZE-SIZE]+hsumPointer[i-SIZE]+hsumPointer[i])/9;
}

8193: 599 ms
8192: 652 ms

Phần kết luận:

  • Không có lợi ích của việc sử dụng một số con trỏ và chỉ tăng (tôi nghĩ nó sẽ nhanh hơn)
  • Lưu trữ các tổng theo chiều ngang tốt hơn là tính toán chúng vài lần.
  • Hai lần vượt qua không nhanh hơn ba lần, hai lần mà thôi.
  • Có thể đạt được tốc độ nhanh hơn 3,6 lần bằng cách sử dụng cả một lần vượt qua và lưu vào bộ nhớ đệm một kết quả trung gian

Tôi chắc rằng nó có thể làm tốt hơn nhiều.

LƯU Ý Xin lưu ý rằng tôi đã viết câu trả lời này để nhắm mục tiêu các vấn đề hiệu suất chung chứ không phải vấn đề bộ nhớ cache được giải thích trong câu trả lời xuất sắc của Mystical. Lúc đầu nó chỉ là mã giả. Tôi đã được yêu cầu làm các bài kiểm tra trong phần nhận xét ... Đây là một phiên bản được cấu trúc lại hoàn toàn với các bài kiểm tra.

Related questions

MORE COOL STUFF

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett chia tay chồng sau 3 ngày bên nhau và vẫn kết hôn với anh ấy 25 năm sau

Cate Blanchett đã bất chấp những lời khuyên hẹn hò điển hình khi cô gặp chồng mình.

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Tại sao Michael Sheen là một diễn viên phi lợi nhuận

Michael Sheen là một diễn viên phi lợi nhuận nhưng chính xác thì điều đó có nghĩa là gì?

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Hallmark Star Colin Egglesfield Các món ăn gây xúc động mạnh đối với người hâm mộ tại RomaDrama Live! [Loại trừ]

Ngôi sao của Hallmark Colin Egglesfield chia sẻ về những cuộc gặp gỡ với người hâm mộ ly kỳ tại RomaDrama Live! cộng với chương trình INSPIRE của anh ấy tại đại hội.

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Tại sao bạn không thể phát trực tuyến 'chương trình truyền hình phía Bắc'

Bạn sẽ phải phủi sạch đầu đĩa Blu-ray hoặc DVD để xem tại sao Northern Exposure trở thành một trong những chương trình nổi tiếng nhất của thập niên 90.

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

8 công dụng tuyệt vời của Baking Soda và Giấm

8 công dụng tuyệt vời của Baking Soda và Giấm

Bạn biết đấy, hai sản phẩm này là nguồn điện để làm sạch, riêng chúng. Nhưng cùng với nhau, chúng có một loạt công dụng hoàn toàn khác.

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Hạn hán, biến đổi khí hậu đe dọa tương lai của thủy điện Hoa Kỳ

Thủy điện rất cần thiết cho lưới điện của Hoa Kỳ, nhưng nó chỉ tạo ra năng lượng khi có nước di chuyển. Bao nhiêu nhà máy thủy điện có thể gặp nguy hiểm khi các hồ và sông cạn kiệt?

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Quyên góp tóc của bạn để giúp giữ nước sạch của chúng tôi

Tóc tỉa từ các tiệm và các khoản quyên góp cá nhân có thể được tái sử dụng như những tấm thảm thấm dầu và giúp bảo vệ môi trường.

Tận dụng lợi thế của việc bán hàng nhân Ngày của Cha này

Tận dụng lợi thế của việc bán hàng nhân Ngày của Cha này

Màn hình Samsung Galaxy S9 Plus. Chủ nhật này là Ngày của Cha⁠ — trong trường hợp nó khiến bạn suy nghĩ — và thay vì mua cho anh ấy một chiếc cà vạt trong năm nay, có lẽ đã đến lúc bạn mua cho anh ấy thứ mà anh ấy sẽ thực sự sử dụng.

Assassin's Creed Snuck Into Monster Hunter: World Last Night

Assassin's Creed Snuck Into Monster Hunter: World Last Night

Monster Hunter: World yêu thích các sự kiện chéo. Dù có nghĩa là hóa trang thành Dante của Devil May Cry, giả dạng Horizon: Zero Dawn's Aloy, hay chiến đấu với quái vật Final Fantasy, các nhiệm vụ sự kiện khác nhau của Thế giới được nâng cấp tự do so với các trò chơi khác.

Ava DuVernay Có Quà Tặng Ngày Của Mẹ cho Tất Cả Chúng Ta: Nếp Nhăn Thời Gian Sẽ Được Viết Lại Vào Cuối Tuần Ngày Của Mẹ!

Ava DuVernay Có Quà Tặng Ngày Của Mẹ cho Tất Cả Chúng Ta: Nếp Nhăn Thời Gian Sẽ Được Viết Lại Vào Cuối Tuần Ngày Của Mẹ!

Storm Reid, Oprah Winfrey, Mindy Kaling, Reese Witherspoon và Ava DuVernay tại buổi chiếu đặc biệt của A Wrinkle in Time tại Nhà hát Walter Reade ở Thành phố New York vào ngày 7 tháng 3 năm 2018 “Ava rất mong được nói chuyện với bạn,” một trong những người của Array dư luận viên nói qua điện thoại. (Array là tập thể phân phối, nghệ thuật và vận động chính sách của Ava DuVernay tập trung vào các bộ phim của người da màu và phụ nữ.

Nhiệm vụ bất khả thi 5 sẽ khôi phục niềm tin của bạn trong phim hành động Tentpole

Nhiệm vụ bất khả thi 5 sẽ khôi phục niềm tin của bạn trong phim hành động Tentpole

Mission Impossible: Rogue Nation bắt đầu ở một cấp độ khác. Theo nghĩa đen.

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

Edwin McCain ra mắt Grand Ole Opry: Quay cảnh hậu trường với nhạc sĩ 'I'll Be'

McCain, người đang làm việc cho một album mới, lần đầu tiên bước vào vòng kết nối vào tối thứ Sáu ở Nashville

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Forced to Borrow Paris' 'I Love Paris' Sweatshirt After 'Airline Loses All [My] Luggage'

Nicky Hilton Rothschild's luggage got lost, but luckily she has an incredible closet to shop: Sister Paris Hilton's!

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa

Kate Middleton dành một ngày bên bờ nước ở London, cùng với Jennifer Lopez, Julianne Hough và hơn thế nữa. Từ Hollywood đến New York và mọi nơi ở giữa, hãy xem các ngôi sao yêu thích của bạn đang làm gì!

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

17 tuổi bị đâm chết trong khi 4 người khác bị thương trong một cuộc tấn công bằng dao trên sông Wisconsin

Các nhà điều tra đang xem xét liệu nhóm và nghi phạm có biết nhau trước vụ tấn công hay không

Tôi viết như thế nào

Tôi viết như thế nào

Đối với tôi, mọi thứ là về dòng đầu tiên đó và nó sẽ đưa bạn đến đâu. Một số nhà văn bị điều khiển bởi cốt truyện, sự sắp xếp tinh tế của các quân cờ, trong khi những người khác bị lôi cuốn bởi một nhân vật và khả năng thực hiện một cuộc hành trình với một người bạn hư cấu mới.

Đường băng hạ cánh

Đường băng hạ cánh

Cuối hè đầu thu là mùa hoài niệm. Những chiếc đèn đường chiếu ánh sáng của chúng qua những con đường đẫm mưa, và những chiếc lá dưới chân - màu đỏ cam tắt trong bóng chạng vạng - là lời nhắc nhở về những ngày đã qua.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Hãy tưởng tượng tạo ra một chiến lược nội dung thực sự CHUYỂN ĐỔI. Nó có thể.

Vào năm 2021, tôi khuyến khích bạn suy nghĩ lại mọi thứ bạn biết về khách hàng mà bạn phục vụ và những câu chuyện bạn kể cho họ. Lùi lại.

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Sự mất mát của voi ma mút đã mở ra trái tim tôi để yêu

Vào ngày sinh nhật thứ 9 của Felix The Cat, tôi nhớ về một trong những mất mát lớn nhất trong cuộc đời trưởng thành của tôi - Sophie của tôi vào năm 2013. Tôi đã viết bài luận này và chia sẻ nó trên nền tảng này một thời gian ngắn vào năm 2013.

Language