Tại sao GCC lại sử dụng phép nhân với một số lạ trong việc thực hiện phép chia số nguyên?

233
qiubit 2016-12-17 01:59.

Tôi đã đọc về divmulcác phép toán lắp ráp, và tôi quyết định xem chúng hoạt động bằng cách viết một chương trình đơn giản trong C:

Tệp phân chia.c

#include <stdlib.h>
#include <stdio.h>

int main()
{
    size_t i = 9;
    size_t j = i / 5;
    printf("%zu\n",j);
    return 0;
}

Và sau đó tạo mã hợp ngữ với:

gcc -S division.c -O0 -masm=intel

Nhưng nhìn vào division.stệp được tạo , nó không chứa bất kỳ phép toán div nào! Thay vào đó, nó thực hiện một số loại ma thuật đen với dịch chuyển bit và số ma thuật. Đây là một đoạn mã tính toán i/5:

mov     rax, QWORD PTR [rbp-16]   ; Move i (=9) to RAX
movabs  rdx, -3689348814741910323 ; Move some magic number to RDX (?)
mul     rdx                       ; Multiply 9 by magic number
mov     rax, rdx                  ; Take only the upper 64 bits of the result
shr     rax, 2                    ; Shift these bits 2 places to the right (?)
mov     QWORD PTR [rbp-8], rax    ; Magically, RAX contains 9/5=1 now, 
                                  ; so we can assign it to j

Những gì đang xảy ra ở đây? Tại sao GCC không sử dụng div? Làm thế nào nó tạo ra con số kỳ diệu này và tại sao mọi thứ hoạt động?

5 answers

172
Sneftel 2016-12-17 02:09.

Phép chia số nguyên là một trong những phép toán số học chậm nhất mà bạn có thể thực hiện trên bộ xử lý hiện đại, với độ trễ lên đến hàng chục chu kỳ và thông lượng kém. (Đối với x86, hãy xem bảng hướng dẫn của Agner Fog và hướng dẫn về vi tinh bột ).

Nếu bạn biết trước số chia, bạn có thể tránh phép chia bằng cách thay thế nó bằng một tập hợp các phép toán khác (nhân, cộng và dịch) có hiệu quả tương đương. Ngay cả khi cần một số phép toán, nó thường vẫn nhanh hơn rất nhiều so với phép chia số nguyên.

Thực hiện /toán tử C theo cách này thay vì với một chuỗi nhiều lệnh liên quan đến divchỉ là cách mặc định của GCC để thực hiện phép chia cho các hằng số. Nó không yêu cầu tối ưu hóa giữa các hoạt động và không thay đổi bất kỳ điều gì ngay cả khi gỡ lỗi. (Tuy nhiên, việc sử dụng -Oscho kích thước mã nhỏ sẽ khiến GCC sử dụng div.) Sử dụng phép nghịch đảo nhân thay vì phép chia giống như sử dụng leathay vì muladd

Kết quả là, bạn chỉ có xu hướng nhìn thấy divhoặc idivtrong đầu ra nếu số chia không được biết tại thời điểm biên dịch.

Để biết thông tin về cách trình biên dịch tạo ra các trình tự này, cũng như mã để cho phép bạn tạo chúng cho chính mình (hầu như chắc chắn là không cần thiết trừ khi bạn đang làm việc với trình biên dịch braindead), hãy xem libdivide .

124
abligh 2016-12-17 03:44.

Chia cho 5 giống như nhân 1/5, một lần nữa giống như nhân với 4/5 và dịch sang phải 2 bit. Giá trị liên quan CCCCCCCCCCCCCCCDở dạng hex, là biểu diễn nhị phân của 4/5 nếu được đặt sau dấu thập lục phân (tức là hệ nhị phân cho bốn phần năm được 0.110011001100lặp lại - xem bên dưới để biết lý do). Tôi nghĩ bạn có thể lấy nó từ đây! Bạn có thể muốn kiểm tra số học điểm cố định (mặc dù lưu ý rằng nó được làm tròn thành số nguyên ở cuối.

Vì sao, phép nhân nhanh hơn phép chia, và khi số chia được cố định, đây là một con đường nhanh hơn.

Xem Phép nhân đối ứng, một hướng dẫn để biết chi tiết về cách hoạt động của nó, giải thích về điểm cố định. Nó chỉ ra cách thức hoạt động của thuật toán tìm đối ứng và cách xử lý phép chia và mô đun có dấu.

Hãy xem xét trong một phút tại sao 0.CCCCCCCC...(hex) hoặc 0.110011001100...nhị phân là 4/5. Chia biểu diễn nhị phân cho 4 (dịch chuyển sang phải 2 vị trí) và chúng ta sẽ nhận được 0.001100110011...bằng cách kiểm tra nhỏ có thể được thêm vào bản gốc để lấy 0.111111111111..., rõ ràng là bằng 1, theo cùng một cách 0.9999999...trong thập phân bằng một. Do đó, chúng ta biết rằng x + x/4 = 1, vì vậy 5x/4 = 1, x=4/5. Sau đó, giá trị này được biểu diễn dưới dạng CCCCCCCCCCCCDhex để làm tròn (vì chữ số nhị phân nằm ngoài chữ số cuối cùng hiện tại sẽ là a 1).

59
plugwash 2016-12-17 11:04.

Nói chung, phép nhân nhanh hơn nhiều so với phép chia. Vì vậy, nếu chúng ta có thể loại bỏ việc nhân với nghịch đảo thay vào đó chúng ta có thể tăng tốc đáng kể phép chia cho một hằng số

Một điểm khó khăn là chúng ta không thể biểu diễn nghịch đảo chính xác (trừ khi phép chia là lũy thừa của hai nhưng trong trường hợp đó, chúng ta thường có thể chuyển phép chia thành một bit shift). Vì vậy, để đảm bảo câu trả lời chính xác, chúng tôi phải cẩn thận để lỗi trong đối ứng của chúng tôi không gây ra sai sót trong kết quả cuối cùng của chúng tôi.

-3689348814741910323 là 0xCCCCCCCCCCCCCCCD, là giá trị chỉ hơn 4/5 được biểu thị bằng 0,64 điểm cố định.

Khi chúng ta nhân một số nguyên 64 bit với một số điểm cố định 0,64, chúng ta nhận được kết quả 64,64. Chúng tôi cắt bớt giá trị thành số nguyên 64 bit (làm tròn giá trị về 0 một cách hiệu quả) và sau đó thực hiện một phép dịch chuyển nữa chia cho bốn và một lần nữa cắt bớt.

Điều này rõ ràng cung cấp cho chúng ta ít nhất một phép chia gần đúng cho 5 nhưng nó có cung cấp cho chúng ta một câu trả lời chính xác được làm tròn chính xác đến 0 không?

Để có được câu trả lời chính xác, lỗi cần phải đủ nhỏ để không đẩy câu trả lời qua một ranh giới làm tròn.

Câu trả lời chính xác cho phép chia cho 5 sẽ luôn có phần phân số là 0, 1/5, 2/5, 3/5 hoặc 4/5. Do đó, sai số dương nhỏ hơn 1/5 trong kết quả được nhân và dịch chuyển sẽ không bao giờ đẩy kết quả vượt qua ranh giới làm tròn.

Sai số trong hằng số của chúng tôi là (1/5) * 2 -64 . Giá trị của i nhỏ hơn 2 64 nên sai số sau khi nhân nhỏ hơn 1/5. Sau khi chia cho 4, sai số nhỏ hơn (1/5) * 2 −2 .

(1/5) * 2 −2 <1/5 nên câu trả lời sẽ luôn bằng khi thực hiện một phép chia chính xác và làm tròn về 0.


Thật không may, điều này không hoạt động cho tất cả các ước số.

Nếu chúng ta cố gắng biểu diễn 4/7 dưới dạng một số điểm cố định 0,64 với việc làm tròn đi từ 0, chúng ta sẽ có sai số là (6/7) * 2 -64 . Sau khi nhân với giá trị i của chỉ dưới 2 64, chúng ta kết thúc với sai số chỉ dưới 6/7 và sau khi chia cho bốn, chúng ta kết thúc với sai số chỉ dưới 1.5 / 7 lớn hơn 1/7.

Vì vậy, để thực hiện đúng số chia cho 7, chúng ta cần nhân với một số điểm cố định 0,65. Chúng tôi có thể thực hiện điều đó bằng cách nhân với 64 bit thấp hơn của số điểm cố định của chúng tôi, sau đó thêm số gốc (điều này có thể tràn vào bit mang) sau đó thực hiện xoay vòng qua mang.

12
rcgldr 2016-12-20 03:52.

Đây là liên kết đến tài liệu của một thuật toán tạo ra các giá trị và mã mà tôi thấy với Visual Studio (trong hầu hết các trường hợp) và tôi giả sử vẫn được sử dụng trong GCC để chia một số nguyên biến cho một số nguyên không đổi.

http://gmplib.org/~tege/divcnst-pldi94.pdf

Trong bài viết, một uword có N bit, một udword có 2N bit, n = tử số = cổ tức, d = mẫu số = số chia, ℓ ban đầu được đặt thành ceil (log2 (d)), shpre là chuyển dịch trước (được sử dụng trước khi nhân ) = e = số bit không theo sau trong d, shpost là dịch chuyển sau (được sử dụng sau khi nhân), prep là độ chính xác = N - e = N - shpre. Mục đích là để tối ưu hóa việc tính toán n / d bằng cách sử dụng dịch chuyển trước, nhân và sau.

Cuộn xuống hình 6.2, xác định cách tạo ra một hệ số udword (kích thước tối đa là N + 1 bit), nhưng không giải thích rõ ràng quá trình này. Tôi sẽ giải thích điều này dưới đây.

Hình 4.2 và hình 6.2 cho thấy cách hệ số nhân có thể được giảm xuống một N bit hoặc hệ số nhân nhỏ hơn đối với hầu hết các ước số. Phương trình 4.5 giải thích cách công thức được sử dụng để xử lý số nhân N + 1 bit trong hình 4.1 và 4.2.

Trong trường hợp của X86 hiện đại và các bộ xử lý khác, thời gian nhân là cố định, vì vậy dịch chuyển trước không giúp ích gì cho các bộ xử lý này, nhưng nó vẫn giúp giảm hệ số nhân từ N + 1 bit xuống N bit. Tôi không biết liệu GCC hoặc Visual Studio có loại bỏ tính năng chuyển trước cho các mục tiêu X86 hay không.

Quay lại Hình 6.2. Tử số (số bị chia) cho mlow và mhigh chỉ có thể lớn hơn một ô chữ khi mẫu số (số chia)> 2 ^ (N-1) (khi ℓ == N => mlow = 2 ^ (2N)), trong trường hợp này thay thế tối ưu cho n / d là một phép so sánh (nếu n> = d, q = 1, khác q = 0), do đó không có hệ số nhân nào được tạo ra. Các giá trị ban đầu của mlow và mhigh sẽ là N + 1 bit và hai phép chia udword / uword có thể được sử dụng để tạo ra mỗi giá trị N + 1 bit (mlow hoặc mhigh). Sử dụng X86 ở chế độ 64 bit làm ví dụ:

; upper 8 bytes of dividend = 2^(ℓ) = (upper part of 2^(N+ℓ))
; lower 8 bytes of dividend for mlow  = 0
; lower 8 bytes of dividend for mhigh = 2^(N+ℓ-prec) = 2^(ℓ+shpre) = 2^(ℓ+e)
dividend  dq    2 dup(?)        ;16 byte dividend
divisor   dq    1 dup(?)        ; 8 byte divisor

; ...
        mov     rcx,divisor
        mov     rdx,0
        mov     rax,dividend+8     ;upper 8 bytes of dividend
        div     rcx                ;after div, rax == 1
        mov     rax,dividend       ;lower 8 bytes of dividend
        div     rcx
        mov     rdx,1              ;rdx:rax = N+1 bit value = 65 bit value

Bạn có thể kiểm tra điều này với GCC. Bạn đã thấy cách j = i / 5 được xử lý. Hãy xem cách xử lý j = i / 7 (phải là trường hợp nhân N + 1 bit).

Trên hầu hết các bộ vi xử lý hiện tại, nhân có thời gian cố định, do đó không cần chuyển trước. Đối với X86, kết quả cuối cùng là một chuỗi hai lệnh cho hầu hết các ước số và một chuỗi năm lệnh cho các ước số như 7 (để mô phỏng hệ số nhân N + 1 bit như thể hiện trong phương trình 4.5 và hình 4.2 của tệp pdf). Ví dụ mã X86-64:

;       rax = dividend, rbx = 64 bit (or less) multiplier, rcx = post shift count
;       two instruction sequence for most divisors:

        mul     rbx                     ;rdx = upper 64 bits of product
        shr     rdx,cl                  ;rdx = quotient
;
;       five instruction sequence for divisors like 7
;       to emulate 65 bit multiplier (rbx = lower 64 bits of multiplier)

        mul     rbx                     ;rdx = upper 64 bits of product
        sub     rbx,rdx                 ;rbx -= rdx
        shr     rbx,1                   ;rbx >>= 1
        add     rdx,rbx                 ;rdx = upper 64 bits of corrected product
        shr     rdx,cl                  ;rdx = quotient
;       ...
1
dmeister 2020-06-11 08:22.

Tôi sẽ trả lời ở một góc độ hơi khác: Vì nó được phép làm điều đó.

C và C ++ được định nghĩa dựa trên một máy trừu tượng. Trình biên dịch chuyển đổi chương trình này dưới dạng máy trừu tượng thành máy cụ thể theo quy tắc as-if .

  • Trình biên dịch được phép thực hiện BẤT KỲ thay đổi nào miễn là nó không thay đổi hành vi có thể quan sát được như được chỉ định bởi máy trừu tượng. Không có kỳ vọng hợp lý nào rằng trình biên dịch sẽ chuyển đổi mã của bạn theo cách đơn giản nhất có thể (ngay cả khi nhiều lập trình viên C giả định như vậy). Thông thường, nó thực hiện điều này vì trình biên dịch muốn tối ưu hóa hiệu suất so với cách tiếp cận đơn giản (như đã thảo luận trong các câu trả lời khác ở độ dài).
  • Nếu trong bất kỳ trường hợp nào mà trình biên dịch "tối ưu hóa" một chương trình đúng thành một chương trình nào đó có hành vi quan sát khác, thì đó là lỗi trình biên dịch.
  • Bất kỳ hành vi không xác định nào trong mã của chúng tôi (tràn số nguyên đã ký là một ví dụ cổ điển) và hợp đồng này vô hiệu.

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