Dùng & thay cho && trong biểu thức so sánh

#1

Cho mình hỏi về performance khi sử dụng bitwise operator vs arithmetic. Thông thường theo mình hiểu nếu như cần nhân hay chia, thay vì sử dụng * hay /, mình shift bit left hoặc right thì sẽ tối ưu hơn cho performance. Gần như các post mình tìm được trên mạng đều đồng ý với cái đó và cái này thầy mình cũng từng nói. Hôm qua khi ngồi tán dóc với một ông kì cựu trong ngành phát triển game thì ổng nói cái đó không đúng. Mình dẫn chứng bằng tấm hình dưới đây (note từ lớp học) thì ổng nói nó sai.

Mình về google lại thì thấy cái này. https://www.quora.com/Why-are-bitwise-operations-slow-and-CPU-inefficient

Đại khái thì nếu dùng bitwise operator trong trường hợp so sánh Logical, chương trình chạy chậm hơn.

Thấy nó cũng đúng nhưng nếu xét nhân/chia thì bitwise vẫn nhanh hơn. Mình nhớ không lầm thì lúc học Hệ thống, nếu optimize 1 hay 2 gì đó trong C thì compiler sẽ chuyển/nhân chia ra bitwise thay vì vẫn để nhân chia khi không được optimize. Mình có xem hợp ngữ trước và sau optimize thì hợp ngữ viết như vậy.

Kiến thức của mình có bị hổng chổ nào không? Mình có nghe nói về cycle count nhưng không rành lắm. Có trường hợp nào mà arithmetic outperforms bitwise không?

Capture
Capture.JPG1004×279 25.4 KB

#2

Hi Anh Nguyen.

  1. Mình có tìm qua và có vẻ như các trình biên dịch khi chạy các tùy chọn tối ưu sẽ thực hiện một số thay đổi để tối ưu code (Cái này không phải là quá khó để tích hợp).
  2. Tuy nhiên vấn đề là khi áp dụng máy móc một công nghệ không bao giờ đem lại hiệu quả tốt. Bạn có thể thấy biểu thức logic trong link là một ví dụ.
  3. Vệc dùng hay không dùng nó phụ thuộc vào thực tế sử dụng nếu cần tối ưu từng chút một thì có thể thử nghiệm. Tuy nhiên, trong lập trình bình thường thì cũng không thực sự quan trọng lắm.
#3

Chậm hơn thì do nó làm việc thêm việc.
Như nếu ban so sánh

if (a == b && c == d) {
}

Thì compiler sẽ

  1. So sánh a với b
  2. Nếu a ko bằng b thoát khỏi if
  3. Nếu a = b thì tiếp tục so sánh c và d
  4. Nếu c không bằng đi thì thoát khỏi if
  5. Nếu c = d thì thực thi code trong if

Tuy nhiên nếu dùng phép & để so sánh như thế này

if ((a == b) & (c == d)) {
}

Khi đó compiler hiểu là

  1. So sánh a và b
  2. Nếu a = b thì gán giá trị 1 vào biến tạm 1
  3. Nếu a != b thì gán giá trị 0 vào biến tạm 1
  4. So sánh c và d
  5. Nếu c = d thì gán giá trị 1 vào biến tạm 2
  6. Nếu c != d thì gán giá trị 0 vào biến tạm 2
  7. Thực hiện phép AND giữa 2 biến tạm 1 và 2
  8. So sánh giá trị vừa được tính ra
  9. Nếu bằng 0 thì thoát khỏi vòng if
  10. Nếu bằng 1 thì thực thi code trong if

Dễ thấy việc làm của phép & phải nhiều hơn. Và chưa kể nếu dùng && thì a != b chương trình sẽ ko so sánh tới c và d nữa thế là tiết kiệm cũng kha khá tgian xử lý. Còn ở trường hợp dùng toán tử &, dù a != b thì vẫn tính tiếp c và d. Sau đó lại so sánh lần nữa. Mất công hơn rất nhiều.

Còn về CPU Cycle.
Các lệnh đơn giản như MOV, ADD, OR, XOR, SHL, SHR … chỉ tốn 1 cycle thôi. Nên phép cộng (ở các CPU đời mới) có tốc độ xử lý nhanh bằng một phép dịch trái, dịch phải hoặc phép OR, …

Có các lệnh phức tạp như MUL, IMUL, … thì tốn nhiều hơn nên ưu tiên dùng dịch bit để đẩy nhanh quá trình nhân chia kia các toán hạng ở dạng 2^n.

9 Likes
#4

Cảm ơn các bạn. Mình hỏi là để kiểm tra lại kiến thức của mình thôi chứ mấy cái nhỏ như thế này thì mình để compiler làm. Thêm nữa nếu viết như vậy người khác đọc sẽ khó hiểu hơn so với * hay /.

#5

Bạn có thể dùng godbolt.org :slight_smile: mình dùng thì thấy dịch cho x64 ngoài shl còn có lea. Thừa số nhỏ có thể kết hợp với add, còn lại là imul 3 toán hạng.

and hay or tính riêng thì nhanh hơn thật vì không có carry :slight_smile: nhưng giờ có carry-lookahead rồi nên nhìn tổng thể thì vẫn là 1 cycle.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?