Tại sao (a * b! = 0) nhanh hơn (a! = 0 && b! = 0) trong Java?

419
Maljam 2016-02-21 15:51.

Tôi đang viết một số mã bằng Java, tại một số điểm, quy trình của chương trình được xác định bằng cách xem hai biến int, "a" và "b", có khác 0 hay không (lưu ý: a và b không bao giờ âm và không bao giờ trong phạm vi tràn số nguyên).

Tôi có thể đánh giá nó với

if (a != 0 && b != 0) { /* Some code */ }

Hay cách khác

if (a*b != 0) { /* Some code */ }

Bởi vì tôi mong đợi đoạn mã đó chạy hàng triệu lần mỗi lần chạy, tôi đã tự hỏi cái nào sẽ nhanh hơn. Tôi đã thực hiện thử nghiệm bằng cách so sánh chúng trên một mảng lớn được tạo ngẫu nhiên và tôi cũng tò mò muốn xem độ thưa thớt của mảng (phần dữ liệu = 0) sẽ ảnh hưởng như thế nào đến kết quả:

long time;
final int len = 50000000;
int arbitrary = 0;
int[][] nums = new int[2][len];

for (double fraction = 0 ; fraction <= 0.9 ; fraction += 0.0078125) {
    for(int i = 0 ; i < 2 ; i++) {
        for(int j = 0 ; j < len ; j++) {
            double random = Math.random();

            if(random < fraction) nums[i][j] = 0;
            else nums[i][j] = (int) (random*15 + 1);
        }
    }

    time = System.currentTimeMillis();

    for(int i = 0 ; i < len ; i++) {
        if( /*insert nums[0][i]*nums[1][i]!=0 or nums[0][i]!=0 && nums[1][i]!=0*/ ) arbitrary++;
    }
    System.out.println(System.currentTimeMillis() - time);
}

Và kết quả cho thấy rằng nếu bạn mong đợi "a" hoặc "b" bằng 0 hơn ~ 3% thời gian, a*b != 0thì nhanh hơn a!=0 && b!=0:

Tôi tò mò muốn biết tại sao. Bất cứ ai có thể làm sáng tỏ một số điều? Nó là trình biên dịch hay là ở cấp độ phần cứng?

Chỉnh sửa: Vì tò mò ... bây giờ tôi đã học về dự đoán rẽ nhánh, tôi đã tự hỏi so sánh tương tự sẽ hiển thị gì cho OR b là khác 0:

Chúng tôi nhận thấy tác động tương tự của dự đoán nhánh như mong đợi, thú vị là biểu đồ hơi bị lật dọc theo trục X.

Cập nhật

1- Tôi đã thêm vào !(a==0 || b==0)phân tích để xem điều gì sẽ xảy ra.

2- Tôi cũng bao gồm a != 0 || b != 0, (a+b) != 0(a|b) != 0vì tò mò, sau khi học về dự đoán nhánh. Nhưng chúng không tương đương về mặt logic với các biểu thức khác, bởi vì chỉ có một OR b cần khác 0 để trả về true, vì vậy chúng không được dùng để so sánh về hiệu quả xử lý.

3- Tôi cũng đã thêm điểm chuẩn thực tế mà tôi đã sử dụng để phân tích, chỉ là lặp lại một biến int tùy ý.

4- Một số người đã đề nghị bao gồm a != 0 & b != 0trái ngược với a != 0 && b != 0, với dự đoán rằng nó sẽ hoạt động chặt chẽ hơn a*b != 0vì chúng tôi sẽ loại bỏ hiệu ứng dự đoán nhánh. Tôi không biết rằng nó &có thể được sử dụng với các biến boolean, tôi nghĩ rằng nó chỉ được sử dụng cho các phép toán nhị phân với số nguyên.

Lưu ý: Trong bối cảnh mà tôi đang xem xét tất cả những điều này, int tràn không phải là một vấn đề, nhưng đó chắc chắn là một cân nhắc quan trọng trong bối cảnh chung.

CPU: Intel Core i7-3610QM @ 2.3GHz

Phiên bản Java: 1.8.0_45
Java (TM) SE Runtime Environment (build 1.8.0_45-b14)
Java HotSpot (TM) 64-Bit Server VM (build 25.45-b02, hỗn hợp)

5 answers

245
Stephen C 2016-02-21 16:09.

Tôi đang bỏ qua vấn đề rằng điểm chuẩn của bạn có thể bị sai sót và lấy kết quả theo mệnh giá.

Nó là trình biên dịch hay là ở cấp độ phần cứng?

Sau này, tôi nghĩ:

  if (a != 0 && b != 0)

sẽ biên dịch thành 2 tải bộ nhớ và hai nhánh có điều kiện

  if (a * b != 0)

sẽ biên dịch thành 2 tải bộ nhớ, một nhánh nhân và một nhánh có điều kiện.

Phép nhân có thể nhanh hơn nhánh có điều kiện thứ hai nếu dự đoán nhánh cấp phần cứng không hiệu quả. Khi bạn tăng tỷ lệ ... dự đoán nhánh ngày càng kém hiệu quả.

Lý do mà các nhánh có điều kiện chậm hơn là chúng làm cho đường ống thực thi lệnh bị đình trệ. Dự đoán rẽ nhánh là tránh tình trạng đình trệ bằng cách dự đoán nhánh sẽ đi và suy đoán lựa chọn chỉ dẫn tiếp theo dựa trên đó. Nếu dự đoán không thành công, sẽ có độ trễ trong khi tải lệnh cho hướng khác.

(Lưu ý: lời giải thích ở trên được đơn giản hóa quá mức. Để có lời giải thích chính xác hơn, bạn cần xem tài liệu do nhà sản xuất CPU cung cấp cho người viết hợp ngữ và người viết trình biên dịch. Trang Wikipedia trên Branch Predictors là một nền tảng tốt.)


Tuy nhiên, có một điều mà bạn cần phải cẩn thận với việc tối ưu hóa này. Có bất kỳ giá trị nào a * b != 0sẽ cho câu trả lời sai không? Hãy xem xét các trường hợp khi tính toán sản phẩm dẫn đến tràn số nguyên.


CẬP NHẬT

Biểu đồ của bạn có xu hướng xác nhận những gì tôi đã nói.

  • Ngoài ra còn có hiệu ứng "dự đoán nhánh" trong a * b != 0trường hợp nhánh có điều kiện và điều này xuất hiện trong đồ thị.

  • Nếu bạn chiếu các đường cong vượt quá 0,9 trên trục X, có vẻ như 1) chúng sẽ gặp nhau tại khoảng 1,0 và 2) điểm gặp nhau sẽ ở gần cùng giá trị Y như đối với X = 0,0.


CẬP NHẬT 2

Tôi không hiểu tại sao các đường cong lại khác nhau đối với a + b != 0và các a | b != 0trường hợp. Có thể có một cái gì đó thông minh trong logic của các bộ dự đoán nhánh. Hoặc nó có thể chỉ ra một cái gì đó khác.

(Lưu ý rằng loại điều này có thể dành riêng cho một số kiểu chip cụ thể hoặc thậm chí là phiên bản. Kết quả điểm chuẩn của bạn có thể khác trên các hệ thống khác.)

Tuy nhiên, cả hai đều có lợi thế là hoạt động cho tất cả các giá trị không âm của ab.

70
Boann 2016-02-22 05:50.

Tôi nghĩ rằng điểm chuẩn của bạn có một số sai sót và có thể không hữu ích để suy luận về các chương trình thực. Đây là suy nghĩ của tôi:

  • (a|b)!=0(a+b)!=0kiểm tra nếu một trong hai giá trị là khác 0, trong khi a != 0 && b != 0(a*b)!=0kiểm tra nếu cả hai đều khác 0. Vì vậy, bạn không so sánh thời gian của chỉ số học: nếu điều kiện đúng thường xuyên hơn, nó gây ra nhiều lần thực thi hơn if, cũng mất nhiều thời gian hơn.

  • (a+b)!=0 sẽ làm điều sai đối với các giá trị âm và dương có tổng bằng 0, vì vậy bạn không thể sử dụng nó trong trường hợp chung, ngay cả khi nó hoạt động ở đây.

  • Tương tự, (a*b)!=0sẽ làm điều sai đối với các giá trị bị tràn. (Ví dụ ngẫu nhiên: 196608 * 327680 là 0 vì kết quả đúng xảy ra chia hết cho 2 32 , vì vậy 32 bit thấp của nó là 0 và những bit đó là tất cả những gì bạn nhận được nếu đó là một intphép toán.)

  • VM sẽ tối ưu hóa biểu thức trong vài lần chạy đầu tiên của fractionvòng lặp ngoài ( ), khi nào fractionlà 0, khi các nhánh hầu như không bao giờ được lấy. Trình tối ưu hóa có thể làm những việc khác nếu bạn bắt đầu fractionở mức 0,5.

  • Trừ khi máy ảo có thể loại bỏ một số kiểm tra giới hạn mảng ở đây, có bốn nhánh khác trong biểu thức chỉ do kiểm tra giới hạn và đó là một yếu tố phức tạp khi cố gắng tìm ra điều gì đang xảy ra ở mức thấp. Bạn có thể nhận được các kết quả khác nhau nếu bạn chia mảng hai chiều thành hai mảng phẳng, thay đổi nums[0][i]nums[1][i]thành nums0[i]nums1[i].

  • Bộ dự đoán nhánh CPU phát hiện các mẫu ngắn trong dữ liệu, hoặc các lần chạy của tất cả các nhánh được lấy hoặc không được lấy. Dữ liệu điểm chuẩn được tạo ngẫu nhiên của bạn là Tại sao xử lý một mảng đã sắp xếp nhanh hơn xử lý một mảng không được sắp xếp? . Nếu dữ liệu trong thế giới thực có một mô hình có thể dự đoán được hoặc nó có các giá trị bằng 0 và khác 0 trong thời gian dài, thì các nhánh có thể có giá thấp hơn nhiều .

  • Mã cụ thể được thực thi sau khi điều kiện được đáp ứng có thể ảnh hưởng đến hiệu suất đánh giá chính điều kiện đó, vì nó ảnh hưởng đến những thứ như có thể hủy cuộn vòng lặp hay không, thanh ghi CPU nào có sẵn và nếu có bất kỳ numsgiá trị nào được tìm nạp cần được sử dụng lại sau khi đánh giá tình trạng. Chỉ tăng một bộ đếm trong điểm chuẩn không phải là một trình giữ chỗ hoàn hảo cho những gì mã thực sẽ làm.

  • System.currentTimeMillis()trên hầu hết các hệ thống không chính xác hơn +/- 10 ms. System.nanoTime()thường chính xác hơn.

Có rất nhiều điều không chắc chắn và luôn khó để nói bất cứ điều gì chắc chắn với các loại tối ưu hóa vi mô này bởi vì một thủ thuật nhanh hơn trên một máy ảo hoặc CPU có thể chậm hơn trên một máy ảo khác. Nếu đang chạy HotSpot JVM 32-bit thay vì phiên bản 64-bit, hãy lưu ý rằng nó có hai loại: với VM "Máy khách" có các cách tối ưu hóa khác nhau (yếu hơn) so với máy ảo "Máy chủ".

Nếu bạn có thể tháo rời mã máy do VM tạo ra , hãy làm điều đó thay vì cố gắng đoán xem nó làm gì!

24
Pagefault 2016-02-22 16:43.

Các câu trả lời ở đây là tốt, mặc dù tôi đã có một ý tưởng có thể cải thiện mọi thứ.

Vì hai nhánh và dự đoán nhánh liên quan là thủ phạm có khả năng xảy ra, chúng ta có thể giảm nhánh thành một nhánh duy nhất mà không thay đổi logic nào cả.

bool aNotZero = (nums[0][i] != 0);
bool bNotZero = (nums[1][i] != 0);
if (aNotZero && bNotZero) { /* Some code */ }

Nó cũng có thể hoạt động để làm

int a = nums[0][i];
int b = nums[1][i];
if (a != 0 && b != 0) { /* Some code */ }

Lý do là, theo các quy tắc về ngắn mạch, nếu boolean đầu tiên là false thì boolean thứ hai không nên được đánh giá. Nó phải thực hiện thêm một nhánh để tránh đánh giá nums[1][i]nếu nums[0][i]sai. Bây giờ, bạn có thể không quan tâm đến việc nums[1][i]được đánh giá, nhưng trình biên dịch không thể chắc chắn rằng nó sẽ không ném ra ngoài phạm vi hoặc không có ref khi bạn làm vậy. Bằng cách giảm khối if thành các bools đơn giản, trình biên dịch có thể đủ thông minh để nhận ra rằng việc đánh giá boolean thứ hai một cách không cần thiết sẽ không có tác dụng phụ tiêu cực.

11
Sanket Gupte 2016-02-21 16:30.

Khi chúng ta thực hiện phép nhân, ngay cả khi một số là 0, thì tích là 0. Trong khi viết

    (a*b != 0)

Nó đánh giá kết quả của sản phẩm do đó loại bỏ một số lần lặp lại đầu tiên bắt đầu từ 0. Do đó, các so sánh ít hơn khi điều kiện là

   (a != 0 && b != 0)

Nơi mọi phần tử được so sánh với 0 và được đánh giá. Do đó thời gian cần thiết ít hơn. Nhưng tôi tin rằng điều kiện thứ hai có thể cho bạn giải pháp chính xác hơn.

9
StackedCrooked 2016-02-24 15:55.

Bạn đang sử dụng dữ liệu đầu vào ngẫu nhiên khiến các nhánh không thể đoán trước được. Trong thực tế, các nhánh thường có thể dự đoán được (~ 90%) vì vậy trong mã thực, mã nhánh có thể nhanh hơn.

Mà nói. Tôi không thấy làm thế nào a*b != 0có thể nhanh hơn (a|b) != 0. Nói chung phép nhân số nguyên đắt hơn OR một bit. Nhưng những thứ như thế này đôi khi trở nên kỳ lạ. Xem ví dụ về ví dụ "Ví dụ 7: Sự phức tạp của phần cứng" từ Thư viện Hiệu ứng Bộ nhớ cache của Bộ xử lý .

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.

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Một thương hiệu kế thừa khác có được cuộc sống mới khi những người chủ mới của Black Opal có được Hội chợ thời trang

Desiree Rogers, trái, và Cheryl Mayberry McKissack Chuyển sang, Fenty Beauty và Pat McGrath, có một đế chế làm đẹp mới do phụ nữ làm chủ đang trỗi dậy. Sau thương vụ mua lại mỹ phẩm Black Opal vào tháng 9, đội ngũ quyền lực của Giám đốc điều hành công ty Desiree Rogers và Chủ tịch Cheryl Mayberry McKissack đã thông báo mua lại thương hiệu làm đẹp tiên phong Fashion Fair từ người sáng lập Johnson Publishing Company (JPC).

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Ngoài việc trở nên vô nghĩa, các bên bộc lộ giới tính giờ đây đã trở nên chết người

Đối với những người có quá nhiều thời gian, tiệc tiết lộ giới tính là một cách thú vị để không cần áp đặt những định kiến ​​hạn chế lên thai nhi trước một đối tượng bạn bè giả vờ quan tâm một cách lịch sự. Tuy nhiên, việc chỉ dựa vào những chiếc bánh nướng có màu nhân tạo để biểu thị một tiếng hoo-ha hoặc một đứa trẻ đi tè đã trở nên xa xỉ trong các bậc cha mẹ trên Instagram.

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Kirstjen Nielsen đang cố gắng đổi mới bản thân với tư cách là một người phụ nữ 'nói ra sự thật cho sức mạnh'

Hôm thứ Tư, cựu Bộ trưởng An ninh Nội địa Kirstjen Nielsen vì một lý do nào đó đã được đưa ra một diễn đàn để phát biểu tại Hội nghị thượng đỉnh Những người phụ nữ quyền lực nhất của Fortune. Và có thể đoán trước được, người phụ nữ giám sát các nỗ lực (đang diễn ra) của chính quyền Trump nhằm chia cắt các gia đình ở biên giới đã sử dụng thời gian của mình như một cơ hội để tự bảo vệ mình và tự nhận mình là người — và hãy hít thở sâu ở đây — “đã nói sự thật với quyền lực.

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Toyota Racing Development sẽ cho ra mắt Supra 3000GT Concept, Massive Wing vào tháng tới

Vì thế hệ mới nhất của chiếc xe điều chỉnh được yêu thích trên thế giới hiện đã có mặt tại đây, nên chỉ có điều kiện là Toyota Racing Development sẽ đưa phiên bản Supra thế hệ thứ năm sửa đổi của riêng mình đến SEMA vào tháng tới. Toyota đã cho chúng tôi một gợi ý về những gì sẽ xảy ra trong tuần này: một chiếc Concept GR Supra 3000GT hiện đại.

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

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Thanh thiếu niên, Gia đình Florida Hội đồng quản trị trường học về Luật 'Không nói đồng tính': 'Buộc chúng tôi tự kiểm duyệt'

Vụ kiện, nêu tên một số học khu, lập luận rằng dự luật "Không nói đồng tính" được ban hành gần đây của Florida "có hiệu quả im lặng và xóa bỏ học sinh và gia đình LGBTQ +"

Đườ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.

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Khi bạn không thể trở thành người mà Internet muốn bạn trở thành

Tôi ghét từ "tàu đắm". Mọi người cảm thấy thoải mái trong la bàn đạo đức của riêng mình, và khi làm như vậy, họ thấy mình vượt qua sự phán xét.

Language