Mã này có thể được tối ưu hóa không?

Question

Tôi có một số mã xử lý hình ảnh lặp qua 2 mảng byte đa chiều (có cùng kích thước). Nó lấy một giá trị từ mảng nguồn, thực hiện một phép tính trên nó và sau đó lưu trữ kết quả trong một mảng khác.

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int x = 0; x < xSize; x++) 
{     
    for (int y = 0; y < ySize; y++) 
    {             
     ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
            (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
} 

Vòng lặp hiện tại mất ~ 11ms, mà tôi cho là chủ yếu do truy cập giá trị mảng byte khi tính toán khá đơn giản (2 phép nhân và 1 lần thêm).

Tôi có thể làm gì để tăng tốc độ này không? Đó là một phần thời gian quan trọng của chương trình của tôi và mã này được gọi là 80-100 lần mỗi giây, vì vậy bất kỳ tăng tốc độ nào, tuy nhiên nhỏ sẽ tạo ra sự khác biệt. Cũng tại thời điểm xSize = 768 và ySize = 576, nhưng điều này sẽ tăng trong tương lai.

Cập nhật: Cảm ơn Guffa (xem câu trả lời bên dưới), mã sau đây giúp tôi tiết kiệm 4-5ms mỗi vòng lặp. Mặc dù mã số không an toàn.

int size = ResultImageData.Length; 
int counter = 0; 
unsafe 
{ 
    fixed (byte* r = ResultImageData, c = CurrentImageData, a = AlphaImageData) 
    { 
     while (size > 0) 
     { 
      *(r + counter) = (byte)(*(c + counter) * AlphaValue + 
            *(a + counter) * OneMinusAlphaValue); 
      counter++; 
      size--; 
     } 
    } 
} 

Answer 1

Để có được bất kỳ speadup thực nào cho mã này, bạn sẽ cần phải sử dụng con trỏ để truy cập các mảng, loại bỏ tất cả các phép tính chỉ mục và kiểm tra giới hạn.

int size = ResultImageData.Length; 
unsafe 
{ 
    fixed(byte* rp = ResultImageData, cp = CurrentImageData, ap = AlphaImageData) 
    { 
     byte* r = rp; 
     byte* c = cp; 
     byte* a = ap; 
     while (size > 0) 
     { 
     *r = (byte)(*c * AlphaValue + *a * OneMinusAlphaValue); 
     r++; 
     c++; 
     a++; 
     size--; 
     } 
    } 
} 

Edit:
biến cố định không thể thay đổi, vì vậy tôi thêm mã để sao chép các con trỏ để trỏ mới có thể thay đổi.

Answer 2

Nếu bạn đang sử dụng LockBits để có được bộ đệm hình ảnh, bạn nên lặp qua y trong vòng ngoài và x trong vòng lặp bên trong như đó là cách nó được lưu trữ trong bộ nhớ (bằng cách liên tiếp, không cột) . Tôi sẽ nói rằng 11ms là khá darn nhanh mặc dù ...

Answer 3

Dữ liệu hình ảnh phải được lưu trữ trong một mảng đa chiều (hình chữ nhật)? Nếu bạn sử dụng các mảng răng cưa thay vào đó, bạn cũng có thể tìm thấy JIT có nhiều tối ưu hóa hơn (bao gồm cả việc loại bỏ việc kiểm tra giới hạn).

Answer 4

Một tùy chọn sẽ là sử dụng mã không an toàn: sửa mảng trong bộ nhớ và sử dụng thao tác con trỏ. Tôi nghi ngờ sự gia tăng tốc độ sẽ được ấn tượng mặc dù.

Một lưu ý: bạn định thời gian như thế nào? Nếu bạn đang sử dụng DateTime thì hãy lưu ý rằng lớp này có độ phân giải kém. Bạn nên thêm một vòng lặp bên ngoài và lặp lại các hoạt động nói mười lần - Tôi đặt cược kết quả là ít hơn 110ms.

for (int outer = 0; outer < 10; ++outer) 
{ 
    for (int x = 0; x < xSize; x++) 
    {     
     for (int y = 0; y < ySize; y++) 
     {             
       ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
              (AlphaImageData[x, y] * OneMinusAlphaValue)); 
     } 
    } 
} 

Answer 5

Kể từ khi nó xuất hiện rằng mỗi tế bào trong ma trận được tính hoàn toàn không phụ thuộc vào người khác. Bạn có thể muốn xem xét việc có nhiều hơn một luồng xử lý điều này. Để tránh chi phí tạo chủ đề, bạn có thể có một nhóm chủ đề.

Nếu ma trận có kích thước đủ, nó có thể là tốc độ tăng rất tốt. Mặt khác, nếu nó quá nhỏ, nó có thể không giúp đỡ (thậm chí tổn thương). Đáng thử mặc dù.

Một ví dụ (pseudo code) có thể là như thế này:

void process(int x, int y) { 
    ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
     (AlphaImageData[x, y] * OneMinusAlphaValue)); 
} 

ThreadPool pool(3); // 3 threads big 

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int x = 0; x < xSize; x++) { 
    for (int y = 0; y < ySize; y++) { 
     pool.schedule(x, y); // this will add all tasks to the pool's work queue 
    } 
} 

pool.waitTilFinished(); // wait until all scheduled tasks are complete 

EDIT:Michael Meadows đề cập trong một chú thích rằng PLINQ có thể là một lựa chọn phù hợp: http://msdn.microsoft.com/en-us/magazine/cc163329.aspx

Answer 6

Đây là tất cả các tính toán độc lập để nếu bạn có một CPU đa lõi, bạn sẽ có thể đạt được một số lợi ích bằng cách song song việc tính toán. Lưu ý rằng bạn cần phải giữ các chủ đề xung quanh và chỉ cần bàn tay họ làm việc để làm kể từ khi chi phí tạo chủ đề có thể sẽ làm cho điều này chậm hơn là nhanh hơn nếu các chủ đề được tái tạo mỗi lần.

Một thứ khác có thể hoạt động là làm việc với bộ xử lý đồ họa.Hãy xem this question để biết một số ý tưởng, ví dụ: sử dụng Accelerator.

Answer 7

Tôi khuyên bạn nên chạy một vài thử nghiệm trống để tìm ra giới hạn lý thuyết của bạn là gì. Ví dụ, đưa ra các tính toán từ bên trong vòng lặp và xem có bao nhiêu thời gian được lưu. Hãy thử thay thế vòng lặp đôi bằng một vòng lặp duy nhất chạy cùng một số lần và xem lượng thời gian lưu. Sau đó, bạn có thể chắc chắn rằng bạn đang đi xuống con đường bên phải để tối ưu hóa (hai đường dẫn tôi thấy là làm phẳng vòng lặp đôi thành một vòng lặp duy nhất và làm việc với phép nhân [có thể sử dụng một bảng tra cứu sẽ nhanh hơn]).

Answer 8

Chỉ cần thực nhanh chóng, bạn có thể nhận được một tối ưu hóa bằng cách lặp ngược lại và so sánh với 0. Hầu hết các CPU đã một op nhanh để so sánh với 0.

Ví dụ:

int xSize = ResultImageData.GetLength(0) -1; 
int ySize = ResultImageData.GetLength(1) -1; //minor optimization suggested by commenter 

for (int x = xSize; x >= 0; --x) 
{     
    for (int y = ySize; y >=0; --y) 
    {             
      ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
             (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
} 

Xem http://dotnetperls.com/Content/Decrement-Optimization.aspx

Answer 9

Nếu CurrentImageData và/hoặc AlphaImageData không thay đổi mỗi khi bạn chạy đoạn mã của bạn, bạn có thể lưu trữ các sản phẩm trước khi chạy đoạn mã bạn hiển thị và tránh nhân rằng trong bạn vòng lặp.

Chỉnh sửa: Một điều tôi vừa nghĩ đến: Đôi khi hoạt động int nhanh hơn hoạt động byte. Bù đắp điều này với việc sử dụng bộ nhớ cache của bộ xử lý (bạn sẽ tăng kích thước dữ liệu đáng kể và có nguy cơ bị thiếu bộ nhớ cache cao hơn).

Answer 10

Có thể bạn đang bị Bindingchecking. Giống như bang Jon Skeet, một mảng răng cưa thay vì một đa chiều (tức là data[][] thay vì data[,]) sẽ nhanh hơn, kỳ lạ như có vẻ như vậy.

Trình biên dịch sẽ tối ưu hóa

for (int i = 0; i < data.Length; i++) 

bằng cách loại bỏ việc kiểm tra phạm vi mỗi phần tử. Nhưng đó là một loại trường hợp đặc biệt, nó sẽ không làm tương tự cho Getlength().

Đối với cùng một lý do, bộ nhớ đệm hoặc cẩu tài sản Chiều dài (đặt nó trong một biến như xSize) cũng từng là một điều xấu mặc dù tôi đã không thể xác minh rằng với Framework 3.5

Answer 11

442,368 bổ sung và 884,736 phép nhân cho phép tính tôi nghĩ rằng 11ms thực sự cực kỳ chậm trên CPU hiện đại.

trong khi tôi không biết nhiều về chi tiết cụ thể của .net tôi biết tính toán tốc độ cao không phải là bộ đồ mạnh mẽ của nó. Trong quá khứ tôi đã xây dựng các ứng dụng java với các vấn đề tương tự, tôi đã luôn luôn sử dụng thư viện C để thực hiện xử lý hình ảnh/âm thanh.

đến từ góc độ phần cứng bạn muốn đảm bảo truy cập bộ nhớ là tuần tự, đó là bước qua bộ đệm theo thứ tự nó tồn tại trong bộ nhớ. bạn cũng có thể cần sắp xếp lại thứ tự này để trình biên dịch tận dụng các hướng dẫn có sẵn như SIMD. Làm thế nào để tiếp cận này sẽ kết thúc được phụ thuộc vào trình biên dịch của bạn và tôi không thể giúp trên vs.net.

trên một DSP nhúng tôi sẽ thoát ra khỏi

(AlphaImageData [x, y] * OneMinusAlphaValue) và (CurrentImageData [x, y] * AlphaValue) và sử dụng các chỉ lệnh SIMD để tính toán bộ đệm, có thể song song trước khi thực hiện phép cộng. có lẽ làm khối nhỏ đủ để giữ cho bộ nhớ đệm trong bộ nhớ cache trên cpu.

tôi tin rằng bất cứ điều gì bạn làm sẽ yêu cầu truy cập trực tiếp vào bộ nhớ/CPU nhiều hơn .net cho phép.

Answer 12

Bạn cũng có thể muốn xem qua thời gian chạy Mono và tiện ích mở rộng Simd của nó. Có lẽ một số tính toán của bạn có thể sử dụng tăng tốc SSE khi tôi thu thập rằng bạn về cơ bản tính toán vector (tôi không biết kích thước vector nào có gia tốc cho phép nhân nhưng có một số kích thước)

(Blog đăng thông báo Mono.Simd: http://tirania.org/blog/archive/2008/Nov-03.html)

Tất nhiên, điều đó sẽ không hoạt động trên Microsoft .NET nhưng có thể bạn quan tâm đến một số thử nghiệm.

Answer 13

Điều thú vị là dữ liệu hình ảnh thường khá giống nhau, có nghĩa là các phép tính có thể rất lặp đi lặp lại. Bạn đã khám phá làm một bảng tra cứu cho các tính toán? Vì vậy, bất cứ lúc nào 0.8 được nhân với 128 - giá trị [80,128] mà bạn đã tính toán trước đến 102,4, bạn chỉ cần nhìn lên đó? Về cơ bản, bạn đang kinh doanh không gian bộ nhớ cho tốc độ CPU, nhưng nó có thể làm việc cho bạn.

Tất nhiên, nếu dữ liệu hình ảnh của bạn có độ phân giải quá cao (và chuyển thành chữ số quá đáng kể), điều này có thể không thực tế.

Answer 14

Hãy thử đổi x và y cho các vòng lặp để có mẫu truy cập bộ nhớ tuyến tính hơn và (do đó) ít nhớ cache hơn, như vậy.

int xSize = ResultImageData.GetLength(0); 
int ySize = ResultImageData.GetLength(1); 

for (int y = 0; y < ySize; y++) 
{ 
    for (int x = 0; x < xSize; x++) 
    { 
     ResultImageData[x, y] = (byte)((CurrentImageData[x, y] * AlphaValue) + 
      (AlphaImageData[x, y] * OneMinusAlphaValue)); 
    } 
}