Cách thay thế bằng cách sử dụng toán tử% và/Toán tử trong C++

Question

Người ta nói rằng toán tử modulo "%" và toán tử phân chia "/" rất không hiệu quả trong nhúng C++.

Làm thế nào tôi có thể cách khác đạt được các biểu thức sau đây:

a = b % c; 

Tôi hiểu rằng đây có thể đạt được bằng cách sử dụng logic sau:

a = b - c; 
while (a >= c) { 
    a = a - c; 
} 

Nhưng câu hỏi của tôi là, là mã này liên quan đến vòng lặp while đủ hiệu quả, so với% nhà điều hành?

Cảm ơn, Kirti

Answer 1

Không có gì sẽ là đáng kể hiệu quả hơn so với các nhà điều hành %. Nếu có một cách tốt hơn để làm điều đó, thì bất kỳ trình biên dịch hợp lý nào cũng sẽ tự động chuyển đổi nó. Khi bạn được thông báo rằng % và / không hiệu quả, đó chỉ là vì đó là những hoạt động khó - nếu bạn cần thực hiện một modulo, thì hãy làm điều đó.

Có thể có trường hợp đặc biệt khi có cách tốt hơn - ví dụ mod mod có thể được viết dưới dạng nhị phân hoặc - nhưng có thể được tối ưu hóa bởi trình biên dịch của bạn.

Answer 2

Phân chia và mô đun thực sự là hoạt động phần cứng tốn kém, bất kể bạn làm gì (điều này liên quan nhiều hơn đến kiến ​​trúc phần cứng so với ngôn ngữ hoặc trình biên dịch), có lẽ chậm hơn 10 lần so với bổ sung.

^{Tuy nhiên, trên máy tính xách tay hoặc máy chủ hiện tại và trên bộ vi điều khiển cao cấp, số lần xóa cache thường chậm hơn nhiều so với các bộ phận!}

Trình biên dịch GCC thường có thể tối ưu hóa chúng, khi ước số là hằng số.

Vòng lặp ngây thơ của bạn thường chậm hơn nhiều so với sử dụng lệnh phân chia phần cứng (hoặc thường xuyên thư viện làm việc đó, nếu không được cung cấp bởi phần cứng). Tôi tin rằng bạn đang sai trong việc tránh sự phân chia & thay thế nó bằng vòng lặp của bạn.

Bạn có thể điều chỉnh thuật toán của mình-ví dụ: bằng cách có sức mạnh của twos- nhưng tôi không khuyên bạn nên sử dụng mã của bạn. Hãy nhớ rằng tối ưu hóa sớm là ác vì vậy trước tiên hãy thử để có được chương trình của bạn chính xác, sau đó hồ sơ nó để tìm các điểm rắc rối.

Answer 3

Đó là mã gần như chắc chắn sẽ chậm hơn so tuy nhiên vi xử lý của bạn/biên dịch quyết định để thực hiện việc phân chia/mod. Nói chung, các phím tắt là khá khó để đi qua cho các toán tử số học cơ bản, kể từ khi các nhà thiết kế mcu/cpu và lập trình biên dịch là khá tốt tại tối ưu hóa này cho hầu như tất cả các ứng dụng.

Một lối tắt chung trong thiết bị nhúng (nơi mỗi chu kỳ/byte có thể tạo sự khác biệt) là giữ mọi thứ theo cơ sở 2 để sử dụng toán tử dịch bit để thực hiện phép nhân và chia, bitwise và (&) để thực hiện modulo.

Ví dụ:

unsigned int x = 100; 
unsigned int y1 = x << 4; // same as x * 2^4 = x*16 
unsigned int y2 = x >> 6; // same as x/2^6 = x/64 
unsigned int y3 = x & 0x07; // same as x % 8 

Answer 4

Nếu số chia được biết đến tại thời gian biên dịch, các hoạt động có thể được chuyển đổi thành một phép nhân bởi một đối ứng, với một số thay đổi, bổ sung, và hoạt động nhanh khác.Điều này sẽ nhanh hơn trên bất kỳ bộ vi xử lý hiện đại nào, ngay cả khi nó thực hiện phân chia phần cứng. Mục tiêu được nhúng thường có các thói quen được tối ưu hóa cao cho phân chia/modulo, vì các hoạt động này được yêu cầu theo tiêu chuẩn.

Answer 5

Phân chia theo hằng số có thể đạt được bằng cách dịch chuyển nếu có công suất 2 hoặc kết hợp thay đổi mul cho người khác.

http: // masm32.com/board/index.php?topic=9937.0 có phiên bản lắp ráp x86 cũng như nguồn C tải xuống từ bài đăng đầu tiên. tạo mã này cho bạn.

Answer 6

Nếu bạn đã lược tả mã của mình một cách cẩn thận và thấy rằng toán tử modulo là chi phí chính trong vòng lặp bên trong thì có một tối ưu hóa có thể hữu ích. Bạn có thể đã quen thuộc với các trick để xác định dấu hiệu của một số nguyên sử dụng số học trái ca (cho các giá trị 32 bit):

sign = (x >> 31) | 1; 

này mở rộng bit dấu trên chữ, vì vậy giá trị tiêu cực mang lại -1 và tích cực giá trị 0. Sau đó bit 0 được thiết lập sao cho giá trị dương đạt được trong 1.

Nếu chúng tôi chỉ tăng giá trị bằng số lượng nhỏ hơn modulo thì có thể sử dụng cùng một kết quả này để kết quả:

val += inc; 
val -= modulo & (static_cast<int32_t>(((modulo - 1) - val)) >> 31); 

Hoặc, nếu bạn đang giảm dần theo giá trị nhỏ hơn modulo thì mã có liên quan là:

int32_t signedVal = static_cast<int32_t>(val - dec); 
val = signedVal + (modulo & (signedVal >> 31)); 

Tôi đã thêm toán tử static_cast vì tôi đã chuyển sang uint32_t, nhưng bạn có thể không thấy chúng cần thiết.

Điều này có giúp ích nhiều như trái ngược với toán tử% đơn giản không? Điều đó phụ thuộc vào trình biên dịch và kiến ​​trúc CPU của bạn. Tôi tìm thấy một vòng lặp đơn giản chạy nhanh hơn 60% trên bộ vi xử lý i3 của tôi khi biên dịch theo VS2012, tuy nhiên trên chip ARM11 trong Raspberry Pi và biên dịch với GCC tôi chỉ có một cải tiến 20%.