Tại sao mã C ++ để kiểm tra phỏng đoán Collatz chạy nhanh hơn so với lắp ráp viết tay?

851
rosghub 2016-11-01 20:12.

Tôi đã viết hai giải pháp này cho Project Euler Q14 , trong assembly và C ++. Họ thực hiện cách tiếp cận bạo lực giống hệt nhau để kiểm tra phỏng đoán Collatz . Giải pháp lắp ráp được lắp ráp với:

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++ được biên dịch với:

g++ p14.cpp -o p14

Lắp ráp, p14.asm:

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp:

#include <iostream>

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = 3*n + 1;
        ++count;
    }
    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }
    std::cout << maxi << std::endl;
}

Tôi biết về tối ưu hóa trình biên dịch để cải thiện tốc độ và mọi thứ, nhưng tôi không thấy có nhiều cách để tối ưu hóa hơn nữa giải pháp lắp ráp của mình (nói theo chương trình, không phải toán học).

Mã C ++ sử dụng môđun cho mọi thuật ngữ và phân chia mọi thuật ngữ khác, trong khi mã hợp ngữ chỉ sử dụng một phép chia duy nhất cho mọi thuật ngữ khác.

Nhưng quá trình lắp ráp mất trung bình lâu hơn 1 giây so với giải pháp C ++. Tại sao thế này? Tôi hỏi chủ yếu vì tò mò.

Thời gian thực hiện

Hệ thống của tôi: Linux 64 bit trên 1,4 GHz Intel Celeron 2955U (vi kiến ​​trúc Haswell).

10 answers

1931
Peter Cordes 2016-11-01 21:04.

Nếu bạn nghĩ rằng một lệnh DIV 64 bit là một cách tốt để chia cho hai, thì không có gì ngạc nhiên khi đầu ra asm của trình biên dịch đánh bại mã viết tay của bạn, ngay cả với -O0(biên dịch nhanh, không cần tối ưu hóa thêm và lưu trữ / tải lại vào bộ nhớ sau / trước mỗi câu lệnh C để trình gỡ lỗi có thể sửa đổi các biến).

Xem hướng dẫn lắp ráp tối ưu hóa của Agner Fog để tìm hiểu cách viết asm hiệu quả. Anh ấy cũng có các bảng hướng dẫn và hướng dẫn về vi tinh để biết chi tiết cụ thể cho các CPU cụ thể. Xem thêm wiki thẻ x86 để biết thêm liên kết hoàn hảo.

Xem thêm câu hỏi tổng quát hơn này về việc đánh bại trình biên dịch bằng asm viết tay: Ngôn ngữ hợp ngữ nội tuyến có chậm hơn mã C ++ gốc không? . TL: DR: vâng nếu bạn làm sai (như câu hỏi này).

Thông thường, bạn vẫn ổn để trình biên dịch làm công việc của nó, đặc biệt nếu bạn cố gắng viết C ++ có thể biên dịch hiệu quả . Cũng xem lắp ráp có nhanh hơn các ngôn ngữ biên dịch không? . Một trong những câu trả lời liên kết đến các trang trình bày gọn gàng này cho thấy cách các trình biên dịch C khác nhau tối ưu hóa một số chức năng thực sự đơn giản với các thủ thuật thú vị. Cuộc nói chuyện CppCon2017 của Matt Godbolt “ Gần đây, trình biên dịch của tôi đã làm gì cho tôi? Mở nắp của Trình biên dịch ”cũng tương tự như vậy.


even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Trên Intel Haswell, div r64là 36 uops, với độ trễ là 32-96 chu kỳ và thông lượng là một trên mỗi 21-74 chu kỳ. (Cộng với 2 uops để thiết lập RBX và không RDX, nhưng việc thực thi không theo thứ tự có thể chạy sớm những điều đó). Căn chỉnh nhánh cho các vòng liên quan đến các lệnh được mã hóa vi mô trên các CPU Intel SnB-familyTrong trường hợp này, độ trễ là yếu tố có liên quan nhất vì nó là một phần của chuỗi phụ thuộc được thực hiện theo vòng lặp.

shr rax, 1thực hiện cùng một phép chia không dấu: Đó là 1 uop, với độ trễ 1c và có thể chạy 2 lần mỗi chu kỳ đồng hồ.

Để so sánh, phân chia 32-bit nhanh hơn, nhưng vẫn còn kinh khủng so với sự thay đổi. idiv r32là 9 uops, độ trễ 22-29c và một uops trên 8-11c thông lượng trên Haswell.


Như bạn có thể thấy khi xem -O0đầu ra asm của gcc ( trình khám phá trình biên dịch Godbolt ), nó chỉ sử dụng các lệnh thay đổi . clang -O0không biên dịch một cách ngây thơ như bạn nghĩ, thậm chí sử dụng IDIV 64-bit hai lần. (Khi tối ưu hóa, trình biên dịch sử dụng cả hai đầu ra của IDIV khi nguồn thực hiện phép chia và mô đun với cùng các toán hạng, nếu chúng sử dụng IDIV)

GCC không có một chế độ hoàn toàn ngây thơ; nó luôn chuyển đổi thông qua GIMPLE, có nghĩa là không thể tắt một số "tối ưu hóa" . Điều này bao gồm việc nhận biết phép chia theo hằng số và sử dụng dịch chuyển ( lũy thừa của 2) hoặc 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? (không phải lũy thừa của 2) để tránh IDIV (xem div_by_13trong liên kết chốt chặn ở trên).

gcc -Os(tối ưu hóa cho kích thước) không sử dụng IDIV cho không quyền lực-of-2 bộ phận, không may, ngay cả trong trường hợp mã nghịch đảo là chỉ hơi lớn hơn nhưng nhanh hơn nhiều.


Giúp trình biên dịch

(tóm tắt cho trường hợp này: sử dụng uint64_t n)

Trước hết, thật thú vị khi xem đầu ra của trình biên dịch được tối ưu hóa. ( -O3). -O0tốc độ về cơ bản là vô nghĩa.

Xem đầu ra asm của bạn (trên Godbolt, hoặc xem Làm cách nào để loại bỏ “tiếng ồn” khỏi đầu ra của cụm GCC / tiếng kêu? ). Khi trình biên dịch không tạo mã tối ưu ngay từ đầu: Viết mã nguồn C / C ++ của bạn theo cách hướng dẫn trình biên dịch tạo mã tốt hơn thường là cách tiếp cận tốt nhất . Bạn phải biết asm, và biết những gì hiệu quả, nhưng bạn áp dụng kiến ​​thức này một cách gián tiếp. Các trình biên dịch cũng là một nguồn ý tưởng tốt: đôi khi tiếng kêu sẽ làm điều gì đó thú vị và bạn có thể bắt gcc làm điều tương tự: xem câu trả lời này và những gì tôi đã làm với vòng lặp không được cuộn trong mã của @ Veedrac bên dưới.)

Cách tiếp cận này có tính di động và trong 20 năm nữa, một số trình biên dịch trong tương lai có thể biên dịch nó thành bất kỳ thứ gì hiệu quả trên phần cứng trong tương lai (x86 hoặc không), có thể sử dụng phần mở rộng ISA mới hoặc tự động vectơ hóa. X86-64 asm viết tay từ 15 năm trước thường không được điều chỉnh tối ưu cho Skylake. ví dụ: so sánh & hợp nhất macro chi nhánh không tồn tại trước đó. Những gì tối ưu hiện tại cho asm được chế tạo thủ công cho một vi kiến ​​trúc có thể không tối ưu cho các CPU hiện tại và tương lai. Tại sao mã C ++ để kiểm tra phỏng đoán Collatz chạy nhanh hơn so với lắp ráp viết tay? thảo luận về sự khác biệt chính giữa AMD Bulldozer và Intel Haswell, có ảnh hưởng lớn đến mã này. Nhưng trên lý thuyết, g++ -O3 -march=bdver3g++ -O3 -march=skylakesẽ làm điều đúng đắn. (Hoặc -march=native.) Hoặc -mtune=...chỉ điều chỉnh mà không cần sử dụng hướng dẫn mà các CPU khác có thể không hỗ trợ.

Cảm giác của tôi là việc hướng dẫn trình biên dịch asm tốt cho CPU hiện tại mà bạn quan tâm sẽ không phải là vấn đề đối với các trình biên dịch trong tương lai. Hy vọng rằng họ sẽ tốt hơn các trình biên dịch hiện tại trong việc tìm cách chuyển đổi mã và có thể tìm ra cách hoạt động cho các CPU trong tương lai. Bất chấp điều đó, x86 trong tương lai có thể sẽ không tệ với bất kỳ thứ gì tốt trên x86 hiện tại và trình biên dịch trong tương lai sẽ tránh bất kỳ cạm bẫy nào dành riêng cho asm trong khi triển khai một cái gì đó như di chuyển dữ liệu từ nguồn C của bạn, nếu nó không thấy điều gì đó tốt hơn.

Asm viết tay là một hộp đen cho trình tối ưu hóa, do đó, truyền liên tục không hoạt động khi nội tuyến làm cho đầu vào trở thành hằng số thời gian biên dịch. Các tối ưu hóa khác cũng bị ảnh hưởng. Đọc https://gcc.gnu.org/wiki/DontUseInlineAsm trước khi sử dụng asm. (Và tránh asm nội tuyến kiểu MSVC: đầu vào / đầu ra phải đi qua bộ nhớ làm tăng thêm chi phí .)

Trong trường hợp này : của bạn ncó kiểu đã ký và gcc sử dụng chuỗi SAR / SHR / ADD để làm tròn số chính xác. (IDIV và số học-shift "vòng" khác nhau đối với đầu vào âm, xem mục nhập thủ công SAR insn set ref ). (IDK nếu gcc đã thử và không chứng minh được điều đó nkhông thể phủ định được hay sao. Tràn đã ký là hành vi không xác định, vì vậy lẽ ra nó có thể xảy ra.)

Bạn nên sử dụng uint64_t n, vì vậy nó có thể chỉ SHR. Và do đó, nó có thể di động đến các hệ thống longchỉ có 32-bit (ví dụ: Windows x86-64).


BTW, đầu ra asm được tối ưu hóa của gcc trông khá tốt (bằng cách sử dụng )unsigned long n : vòng lặp bên trong nó nội tuyến main()thực hiện điều này:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

Vòng lặp bên trong không có nhánh và đường dẫn tới hạn của chuỗi phụ thuộc được thực hiện theo vòng lặp là:

  • LEA 3 thành phần (3 chu kỳ)
  • cmov (2 chu kỳ trên Haswell, 1c trên Broadwell trở lên).

Tổng: 5 chu kỳ mỗi lần lặp, nút cổ chai độ trễ . Việc thực thi không theo thứ tự sẽ xử lý mọi thứ khác song song với điều này (về lý thuyết: tôi chưa thử nghiệm với bộ đếm hiệu suất để xem liệu nó có thực sự chạy ở 5c / iter hay không).

Đầu vào FLAGS của cmov(do TEST tạo ra) được tạo ra nhanh hơn so với đầu vào RAX (từ LEA-> MOV), vì vậy nó không nằm trên đường quan trọng.

Tương tự, MOV-> SHR tạo ra đầu vào RDI của CMOV nằm ngoài đường dẫn quan trọng, vì nó cũng nhanh hơn LEA. MOV trên IvyBridge trở lên không có độ trễ (được xử lý tại thời điểm đăng ký đổi tên). (Nó vẫn mất một khoảng thời gian và một vị trí trong đường dẫn, vì vậy nó không miễn phí, chỉ có độ trễ bằng không). MOV bổ sung trong chuỗi dep LEA là một phần của nút cổ chai trên các CPU khác.

Cmp / jne cũng không phải là một phần của đường dẫn quan trọng: nó không mang tính vòng lặp, bởi vì các phụ thuộc điều khiển được xử lý với dự đoán nhánh + thực thi suy đoán, không giống như các phụ thuộc dữ liệu trên đường dẫn quan trọng.


Đánh bại trình biên dịch

GCC đã làm một công việc khá tốt ở đây. Nó có thể lưu một byte mã bằng cách sử dụng inc edxthay vìadd edx, 1 , bởi vì không ai quan tâm đến P4 và các phụ thuộc sai của nó đối với các hướng dẫn sửa đổi một phần cờ.

Nó cũng có thể lưu tất cả các lệnh MOV và TEST: SHR đặt CF = bit được dịch chuyển ra ngoài, vì vậy chúng ta có thể sử dụng cmovcthay cho test/ cmovz.

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

Xem câu trả lời của @ johnfound để biết một thủ thuật thông minh khác: loại bỏ CMP bằng cách phân nhánh trên kết quả cờ của SHR cũng như sử dụng nó cho CMOV: zero chỉ khi bắt đầu bằng n là 1 (hoặc 0). (Thực tế thú vị: SHR với số đếm! = 1 trên Nehalem hoặc phiên bản cũ hơn gây ra lỗi nếu bạn đọc kết quả cờ . Đó là cách họ tạo ra nó một lần. Tuy nhiên, mã hóa đặc biệt shift-by-1 vẫn ổn.)

Tránh MOV hoàn toàn không giúp được gì cho độ trễ trên Haswell ( MOV của x86 có thực sự "miễn phí" không? Tại sao tôi không thể tái tạo điều này? ). Nó giúp ích đáng kể trên các CPU như Intel pre-IvB và AMD Bulldozer-family, nơi MOV không có độ trễ bằng 0. Các lệnh MOV lãng phí của trình biên dịch ảnh hưởng đến đường dẫn quan trọng. Phức hợp của BD-LEA và CMOV đều có độ trễ thấp hơn (tương ứng là 2c và 1c), do đó, đó là một phần nhỏ hơn của độ trễ. Ngoài ra, tắc nghẽn thông lượng cũng trở thành một vấn đề, vì nó chỉ có hai đường ống ALU số nguyên. Tại sao mã C ++ để kiểm tra phỏng đoán Collatz chạy nhanh hơn so với lắp ráp viết tay? , nơi anh ấy có kết quả tính thời gian từ CPU AMD.

Ngay cả trên Haswell, phiên bản này có thể giúp ích một chút bằng cách tránh một số sự chậm trễ không thường xuyên trong đó một uop không quan trọng đánh cắp một cổng thực thi từ một cổng trên đường dẫn quan trọng, làm chậm quá trình thực thi 1 chu kỳ. (Đây được gọi là xung đột tài nguyên). Nó cũng lưu một thanh ghi, có thể hữu ích khi thực hiện nsong song nhiều giá trị trong một vòng lặp xen kẽ (xem bên dưới).

Độ trễ của LEA phụ thuộc vào chế độ định địa chỉ , trên các CPU Intel SnB-family. 3c cho 3 thành phần ( [base+idx+const]mất hai thành phần bổ sung riêng biệt), nhưng chỉ 1c với 2 thành phần trở xuống (một thành phần thêm). Một số CPU (như Core2) thậm chí còn thực hiện LEA 3 thành phần trong một chu kỳ duy nhất, nhưng SnB-family thì không. Tệ hơn, Intel SnB-family tiêu chuẩn hóa độ trễ để không có 2c uops , nếu không LEA 3 thành phần sẽ chỉ là 2c như Bulldozer. (LEA 3 thành phần cũng chậm hơn trên AMD, chỉ là không nhiều).

Vì vậy, lea rcx, [rax + rax*2]/ inc rcxchỉ có độ trễ 2c, nhanh hơn so với các lea rcx, [rax + rax*2 + 1]CPU Intel SnB-family như Haswell. Hòa vốn trên BD và tệ hơn trên Core2. Nó làm tốn thêm một khoản tiền, điều này thường không đáng để tiết kiệm 1c độ trễ, nhưng độ trễ là điểm nghẽn chính ở đây và Haswell có một đường ống đủ rộng để xử lý thông lượng tăng thêm.

Cả gcc, icc và clang (trên chốt chặn) đều không sử dụng đầu ra CF của SHR, luôn sử dụng AND hoặc TEST . Trình biên dịch ngớ ngẩn. : P Chúng là những bộ máy móc phức tạp tuyệt vời, nhưng một con người thông minh thường có thể đánh bại chúng trong những vấn đề quy mô nhỏ. (Tất nhiên, với hàng ngàn đến hàng triệu lần để suy nghĩ về nó, tất nhiên! Trình biên dịch không sử dụng các thuật toán toàn diện để tìm kiếm mọi cách có thể để thực hiện công việc, bởi vì điều đó sẽ mất quá nhiều thời gian khi tối ưu hóa nhiều mã nội tuyến, đó là điều chúng làm tốt nhất. Chúng cũng không mô hình hóa đường ống trong vi kiến ​​trúc mục tiêu, ít nhất là không chi tiết như IACA là gì và tôi sử dụng nó như thế nào? hoặc các công cụ phân tích tĩnh khác; chúng chỉ sử dụng một số phương pháp heuristics.)


Việc mở vòng lặp đơn giản sẽ không hữu ích ; vòng lặp này gây tắc nghẽn về độ trễ của chuỗi phụ thuộc được thực hiện theo vòng lặp, không phải về chi phí / thông lượng của vòng lặp. Điều này có nghĩa là nó sẽ hoạt động tốt với siêu phân luồng (hoặc bất kỳ loại SMT nào khác), vì CPU có nhiều thời gian để xen kẽ các lệnh từ hai luồng. Điều này có nghĩa là song song hóa vòng lặp trong main, nhưng điều đó tốt vì mỗi luồng chỉ có thể kiểm tra một dải ngiá trị và kết quả là tạo ra một cặp số nguyên.

Việc xen kẽ bằng tay trong một sợi đơn cũng có thể khả thi . Có thể tính toán trình tự cho một cặp số song song, vì mỗi số chỉ lấy một vài thanh ghi và tất cả chúng đều có thể cập nhật giống nhau max/ maxi. Điều này tạo ra sự song song cấp độ hướng dẫn hơn .

Bí quyết là quyết định xem có nên đợi cho đến khi tất cả các ngiá trị đã đạt đến 1trước khi nhận được một cặp ngiá trị bắt đầu khác hay không hoặc có nên thoát ra và lấy điểm bắt đầu mới cho chỉ một giá trị đã đạt đến điều kiện kết thúc mà không cần chạm vào các thanh ghi cho chuỗi khác. Có lẽ tốt nhất là giữ cho mỗi chuỗi hoạt động trên dữ liệu hữu ích, nếu không bạn phải tăng bộ đếm của nó một cách có điều kiện.


Bạn thậm chí có thể làm điều này với công cụ so sánh đóng gói SSE để tăng có điều kiện bộ đếm cho các phần tử vectơ nchưa đạt đến 1. Và sau đó để ẩn độ trễ thậm chí còn lâu hơn của việc triển khai tăng dần có điều kiện SIMD, bạn cần lưu giữ nhiều vectơ ngiá trị hơn. Có lẽ chỉ có giá trị với vector 256b (4x uint64_t).

Tôi nghĩ rằng chiến lược tốt nhất để thực hiện phát hiện 1"dính" là che vectơ của tất cả những cái mà bạn thêm vào để tăng bộ đếm. Vì vậy, sau khi bạn nhìn thấy một 1trong một phần tử, vectơ gia tăng sẽ có số 0 và + = 0 là không chọn.

Ý tưởng chưa được thử nghiệm cho vectơ hóa thủ công

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

Bạn có thể và nên thực hiện điều này bằng bản chất thay vì viết tay asm.


Cải tiến thuật toán / triển khai:

Bên cạnh việc chỉ thực hiện cùng một logic với asm hiệu quả hơn, hãy tìm cách để đơn giản hóa logic hoặc tránh công việc thừa. ví dụ: ghi nhớ để phát hiện các kết thúc chung cho các chuỗi. Hoặc thậm chí tốt hơn, hãy xem 8 bit sau cùng một lúc (câu trả lời của gnasher)

@EOF chỉ ra rằng tzcnt(hoặc bsf) có thể được sử dụng để thực hiện nhiều n/=2lần lặp lại trong một bước. Điều đó có lẽ tốt hơn so với việc vector hóa SIMD; không có lệnh SSE hoặc AVX nào có thể làm điều đó. Tuy nhiên, nó vẫn tương thích với việc thực hiện nsong song nhiều đại lượng vô hướng trong các thanh ghi số nguyên khác nhau.

Vì vậy, vòng lặp có thể trông như thế này:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

Điều này có thể thực hiện ít lần lặp hơn đáng kể, nhưng sự thay đổi về số lượng biến là chậm trên các CPU Intel SnB-family không có BMI2. 3 lần, độ trễ 2c. (Chúng có phụ thuộc đầu vào vào FLAGS vì count = 0 có nghĩa là các cờ không bị sửa đổi. Chúng xử lý điều này như một phụ thuộc dữ liệu và lấy nhiều uop vì một uop chỉ có thể có 2 đầu vào (dù sao trước HSW / BDW)). Đây là kiểu mà những người phàn nàn về thiết kế CISC điên rồ của x86 đang đề cập đến. Nó làm cho các CPU x86 chậm hơn so với chúng nếu ISA được thiết kế từ đầu ngày nay, ngay cả theo cách gần như tương tự. (tức là đây là một phần của "thuế x86" chi phí tốc độ / điện năng.) SHRX / SHLX / SARX (BMI2) là một chiến thắng lớn (độ trễ 1 uop / 1c).

Nó cũng đặt tzcnt (3c trên Haswell trở lên) trên con đường quan trọng, do đó, nó kéo dài đáng kể tổng độ trễ của chuỗi phụ thuộc được thực hiện theo vòng lặp. Tuy nhiên, nó loại bỏ bất kỳ nhu cầu nào đối với CMOV hoặc để chuẩn bị lưu giữ đăng ký n>>1. Câu trả lời của @ Veedrac khắc phục tất cả điều này bằng cách trì hoãn tzcnt / shift cho nhiều lần lặp, điều này có hiệu quả cao (xem bên dưới).

Chúng ta có thể sử dụng BSF hoặc TZCNT thay thế cho nhau một cách an toàn , vì nkhông bao giờ có thể bằng 0 tại thời điểm đó. Mã máy của TZCNT giải mã dưới dạng BSF trên các CPU không hỗ trợ BMI1. (Các tiền tố vô nghĩa bị bỏ qua, vì vậy REP BSF chạy như BSF).

TZCNT hoạt động tốt hơn nhiều so với BSF trên các CPU AMD hỗ trợ nó, vì vậy bạn có thể sử dụng nó REP BSF, ngay cả khi bạn không quan tâm đến việc thiết lập ZF nếu đầu vào bằng 0 thay vì đầu ra. Một số trình biên dịch thực hiện điều này khi bạn sử dụng __builtin_ctzllngay cả với -mno-bmi.

Chúng hoạt động tương tự trên CPU Intel, vì vậy chỉ cần lưu byte nếu đó là tất cả những gì quan trọng. TZCNT trên Intel (trước Skylake) vẫn có sự phụ thuộc sai vào toán hạng đầu ra được cho là chỉ ghi, giống như BSF, để hỗ trợ hành vi không có giấy tờ mà BSF với đầu vào = 0 không thay đổi đích của nó. Vì vậy, bạn cần phải giải quyết vấn đề đó trừ khi chỉ tối ưu hóa cho Skylake, vì vậy sẽ không thu được gì từ byte REP bổ sung. (Intel thường vượt quá những gì mà hướng dẫn sử dụng x86 ISA yêu cầu, để tránh phá vỡ mã được sử dụng rộng rãi phụ thuộc vào thứ mà nó không nên hoặc điều đó không được phép trở về trước. Ví dụ: Windows 9x giả định không tìm nạp trước các mục TLB , điều này an toàn khi mã được viết, Quan sát hướng dẫn cũ tìm nạp trên x86 với mã tự sửa đổi .)

Dù sao, LZCNT / TZCNT trên Haswell có cùng một cảnh báo sai với POPCNT: hãy xem Việc thay thế bộ đếm vòng lặp 32 bit bằng 64 bit tạo ra độ lệch hiệu suất điên rồ với _mm_popcnt_u64 trên CPU Intel . Đây là lý do tại sao trong đầu ra asm của gcc cho mã của @ Veedrac, bạn thấy nó phá vỡ chuỗi dep với xor-zeroing trên thanh ghi mà nó sắp sử dụng làm đích của TZCNT khi nó không sử dụng dst = src. Vì TZCNT / LZCNT / POPCNT không bao giờ để đích của chúng là không xác định hoặc không sửa đổi, sự phụ thuộc sai này vào đầu ra trên CPU Intel là một lỗi / hạn chế về hiệu suất. Có lẽ điều đáng giá là một số bóng bán dẫn / công suất để chúng hoạt động giống như các uops khác đi cùng một đơn vị thực thi. Ưu điểm hoàn hảo duy nhất là tương tác với một hạn chế khác của uarch: Chế độ hợp nhất và địa chỉ vi mô trên Haswell, nhưng trên Skylake, nơi Intel đã loại bỏ mô hình giả cho LZCNT / TZCNT, chúng "hủy kết hợp" các chế độ địa chỉ được lập chỉ mục trong khi POPCNT vẫn có thể kết hợp vi mô bất kỳ chế độ bổ trợ nào.


Cải tiến ý tưởng / mã từ các câu trả lời khác:

Câu trả lời của @ hidefromkgb có một nhận xét tuyệt vời rằng bạn được đảm bảo có thể thực hiện đúng một ca sau 3n + 1. Bạn có thể tính toán điều này thậm chí còn hiệu quả hơn là chỉ bỏ qua các kiểm tra giữa các bước. Tuy nhiên, việc triển khai asm trong câu trả lời đó bị hỏng (nó phụ thuộc vào OF, không được xác định sau SHRD với số lượng> 1) và chậm: ROR rdi,2nhanh hơn SHRD rdi,rdi,2và sử dụng hai lệnh CMOV trên đường dẫn quan trọng sẽ chậm hơn so với một KIỂM TRA bổ sung có thể chạy song song.

Tôi đã đặt C gọn gàng / cải tiến (hướng dẫn trình biên dịch tạo ra asm tốt hơn) và đã thử nghiệm + làm việc nhanh hơn asm (trong phần nhận xét bên dưới C) trên Godbolt: xem liên kết trong Tại sao mã C ++ để kiểm tra phỏng đoán Collatz chạy nhanh hơn so với lắp ráp viết tay? . (Câu trả lời này đạt đến giới hạn 30 nghìn ký tự từ các URL Godbolt lớn, nhưng liên kết ngắn có thể bị hỏng và quá dài đối với goo.gl.)

Cũng cải thiện tính năng in đầu ra để chuyển đổi thành chuỗi và tạo một chuỗi write()thay vì viết một ký tự tại một thời điểm. Điều này giảm thiểu tác động đến thời gian của toàn bộ chương trình với perf stat ./collatz(để ghi lại bộ đếm hiệu suất) và tôi đã giải mã một số asm không quan trọng.


Mã của @ Veedrac

Tôi đã nhận được một sự tăng tốc nhỏ từ việc chuyển sang phải nhiều như chúng tôi biết cần phải làm và kiểm tra để tiếp tục vòng lặp. Từ 7,5 giây cho giới hạn = 1e8 xuống 7,275 giây, trên Core2Duo (Merom), với hệ số hủy đăng ký là 16.

mã + bình luận trên Godbolt . Không sử dụng phiên bản này với tiếng kêu; nó làm điều gì đó ngớ ngẩn với vòng lặp trì hoãn. Sử dụng bộ đếm tmp kvà sau đó thêm nó vào để countthay đổi những gì sau này tiếng kêu, nhưng điều đó hơi đau gcc.

Xem thảo luận trong phần bình luận: Mã của Veedrac rất tuyệt vời trên các CPU có BMI1 (tức là không phải Celeron / Pentium)

106
johnfound 2016-11-01 22:29.

Tuyên bố rằng trình biên dịch C ++ có thể tạo ra mã tối ưu hơn một lập trình viên hợp ngữ thành thạo là một sai lầm rất nặng. Và đặc biệt là trong trường hợp này. Con người luôn có thể làm cho mã tốt hơn mà trình biên dịch có thể, và tình huống cụ thể này là minh họa tốt cho tuyên bố này.

Sự khác biệt về thời gian mà bạn đang thấy là do mã lắp ráp trong câu hỏi rất xa so với tối ưu trong các vòng lặp bên trong.

(Đoạn mã dưới đây là 32-bit, nhưng có thể dễ dàng chuyển đổi thành 64-bit)

Ví dụ, hàm tuần tự có thể được tối ưu hóa chỉ với 5 lệnh:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

Toàn bộ mã trông giống như:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

Để biên dịch mã này, cần có FreshLib .

Trong các thử nghiệm của tôi, (bộ xử lý AMD A4-1200 1 GHz), mã trên nhanh hơn khoảng bốn lần so với mã C ++ từ câu hỏi (khi được biên dịch với -O0: 430 ms so với 1900 ms) và nhanh hơn hai lần (430 ms so với 830 ms) khi mã C ++ được biên dịch với -O3.

Đầu ra của cả hai chương trình đều giống nhau: chuỗi max = 525 trên i = 837799.

26
gnasher729 2016-11-03 00:04.

Để có hiệu suất cao hơn: Một thay đổi đơn giản là quan sát rằng sau n = 3n + 1, n sẽ là số chẵn, vì vậy bạn có thể chia cho 2 ngay lập tức. Và n sẽ không phải là 1, vì vậy bạn không cần phải kiểm tra nó. Vì vậy, bạn có thể tiết kiệm một vài câu lệnh if và viết:

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

Đây là một chiến thắng lớn : Nếu bạn nhìn vào 8 bit thấp nhất của n, tất cả các bước cho đến khi bạn chia 2 tám lần hoàn toàn được xác định bởi tám bit đó. Ví dụ: nếu tám bit cuối cùng là 0x01, đó là trong hệ nhị phân, số của bạn là ???? 0000 0001 thì các bước tiếp theo là:

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

Vì vậy, tất cả các bước này có thể được dự đoán và 256k + 1 được thay thế bằng 81k + 1. Điều gì đó tương tự sẽ xảy ra cho tất cả các kết hợp. Vì vậy, bạn có thể tạo vòng lặp với câu lệnh chuyển đổi lớn:

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

Chạy vòng lặp cho đến khi n ≤ 128, bởi vì tại thời điểm đó n có thể trở thành 1 với ít hơn tám phép chia cho 2, và thực hiện tám bước trở lên cùng một lúc sẽ khiến bạn bỏ lỡ điểm mà bạn đạt đến 1 lần đầu tiên. Sau đó, tiếp tục vòng lặp "bình thường" - hoặc chuẩn bị sẵn một bảng cho bạn biết cần thêm bao nhiêu bước để đạt được 1.

Tái bút. Tôi thực sự nghi ngờ gợi ý của Peter Cordes sẽ làm cho nó nhanh hơn. Sẽ không có nhánh điều kiện nào ngoại trừ một nhánh và nhánh đó sẽ được dự đoán chính xác ngoại trừ khi vòng lặp thực sự kết thúc. Vì vậy, mã sẽ giống như

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

Trong thực tế, bạn sẽ đo lường xem việc xử lý 9, 10, 11, 12 bit cuối cùng của n tại một thời điểm có nhanh hơn hay không. Đối với mỗi bit, số lượng mục nhập trong bảng sẽ tăng gấp đôi và tôi gặp phải sự chậm lại khi các bảng không vừa với bộ đệm L1 nữa.

PPS. Nếu bạn cần số lượng phép toán: Trong mỗi lần lặp, chúng tôi thực hiện chính xác tám phép chia cho hai và một số biến của (3n + 1) phép toán, vì vậy một phương pháp hiển nhiên để đếm các phép toán sẽ là một mảng khác. Nhưng chúng ta thực sự có thể tính toán số bước (dựa trên số lần lặp lại của vòng lặp).

Chúng ta có thể xác định lại vấn đề một chút: Thay n bằng (3n + 1) / 2 nếu lẻ và thay n bằng n / 2 nếu chẵn. Sau đó, mỗi lần lặp sẽ thực hiện đúng 8 bước, nhưng bạn có thể coi đó là gian lận :-) Vì vậy, giả sử có r hoạt động n <- 3n + 1 và s hoạt động n <- n / 2. Kết quả sẽ khá chính xác là n '= n * 3 ^ r / 2 ^ s, vì n <- 3n + 1 có nghĩa là n <- 3n * (1 + 1 / 3n). Lấy logarit ta tìm được r = (s + log2 (n '/ n)) / log2 (3).

Nếu chúng ta thực hiện vòng lặp cho đến khi n ≤ 1.000.000 và có một bảng tính trước cần bao nhiêu lần lặp từ bất kỳ điểm bắt đầu nào n ≤ 1.000.000 thì việc tính r như trên, làm tròn đến số nguyên gần nhất, sẽ cho kết quả đúng trừ khi s thực sự lớn.

20
hidefromkgb 2016-11-02 09:35.

Một lưu ý khá không liên quan: nhiều hack hiệu suất hơn!

  • [«phỏng đoán» đầu tiên cuối cùng đã được @ShreevatsaR lật tẩy; loại bỏ]

  • Khi duyệt qua chuỗi, chúng ta chỉ có thể nhận được 3 trường hợp có thể xảy ra trong vùng lân cận 2 của phần tử hiện tại N(được hiển thị đầu tiên):

    1. [chẵn lẻ]
    2. [lẻ thậm chí]
    3. [thậm chí] [thậm chí]

    Nhảy qua những yếu tố 2 phương tiện để tính toán (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1N >> 2, tương ứng.

    Hãy chứng minh rằng đối với cả hai trường hợp (1) và (2), có thể sử dụng công thức đầu tiên (N >> 1) + N + 1,.

    Trường hợp (1) là hiển nhiên. Trường hợp (2) ngụ ý (N & 1) == 1, vì vậy nếu chúng ta giả sử (không mất đi tính tổng quát) rằng N dài 2 bit và các bit của nó có giá trị batừ quan trọng nhất đến nhỏ nhất, thì a = 1và những điều sau đây là đúng:

    (N << 1) + N + 1:     (N >> 1) + N + 1:
    
            b10                    b1
             b1                     b
           +  1                   + 1
           ----                   ---
           bBb0                   bBb
    

    ở đâu B = !b. Dịch chuyển sang phải kết quả đầu tiên cho chúng ta chính xác những gì chúng ta muốn.

    QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

    Như đã được chứng minh, chúng ta có thể duyệt qua chuỗi 2 phần tử cùng một lúc, sử dụng một phép toán bậc ba duy nhất. Giảm 2 lần thời gian.

Thuật toán kết quả trông như thế này:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Ở đây chúng tôi so sánh n > 2vì quá trình có thể dừng lại ở 2 thay vì 1 nếu tổng độ dài của dãy là lẻ.

[BIÊN TẬP:]

Hãy dịch nó thành assembly!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Sử dụng các lệnh sau để biên dịch:

nasm -f elf64 file.asm
ld -o file file.o

Xem C và phiên bản cải tiến / sửa lỗi của asm bởi Peter Cordes trên Godbolt . (ghi chú của biên tập viên: Xin lỗi vì đã đưa nội dung của tôi vào câu trả lời của bạn, nhưng câu trả lời của tôi đã đạt đến giới hạn 30 nghìn ký tự từ liên kết Godbolt + văn bản!)

6
Mangu Singh Rajpurohit 2016-11-01 20:26.

Các chương trình C ++ được dịch sang các chương trình hợp ngữ trong quá trình tạo mã máy từ mã nguồn. Sẽ là sai lầm nếu nói lắp ráp chậm hơn C ++. Hơn nữa, mã nhị phân được tạo ra khác với trình biên dịch. Vì vậy, một trình biên dịch C ++ thông minh có thể tạo ra mã nhị phân tối ưu và hiệu quả hơn mã của một trình biên dịch ngu ngốc.

Tuy nhiên, tôi tin rằng phương pháp lập hồ sơ của bạn có những sai sót nhất định. Sau đây là các hướng dẫn chung cho việc lập hồ sơ:

  1. Đảm bảo hệ thống của bạn ở trạng thái bình thường / không hoạt động. Dừng tất cả các quy trình (ứng dụng) đang chạy mà bạn đã khởi động hoặc sử dụng CPU nhiều (hoặc thăm dò ý kiến ​​trên mạng).
  2. Kích thước dữ liệu của bạn phải lớn hơn.
  3. Bài kiểm tra của bạn phải chạy trong hơn 5-10 giây.
  4. Đừng chỉ dựa vào một mẫu. Thực hiện thử nghiệm của bạn N lần. Thu thập kết quả và tính giá trị trung bình hoặc trung vị của kết quả.
6
Emanuel Landeholm 2016-11-06 08:49.

Đối với vấn đề Collatz, bạn có thể tăng hiệu suất đáng kể bằng cách lưu vào bộ nhớ đệm các "đuôi". Đây là sự đánh đổi thời gian / bộ nhớ. Xem: ghi nhớ ( https://en.wikipedia.org/wiki/Memoization ). Bạn cũng có thể xem xét các giải pháp lập trình động để đánh đổi thời gian / bộ nhớ khác.

Triển khai python mẫu:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))
5
Ped7g 2016-11-02 07:18.

Từ nhận xét:

Nhưng, mã này không bao giờ dừng lại (vì tràn số nguyên)!?! Yves Daoust

Đối với nhiều số nó sẽ không bị tràn.

Nếu nó sẽ tràn - đối với một trong những hạt giống ban đầu không may mắn đó, số tràn xuống rất có thể sẽ hội tụ về 1 mà không có lần tràn khác.

Điều này vẫn đặt ra một câu hỏi thú vị, liệu có một số hạt giống chu kỳ tràn không?

Bất kỳ chuỗi hội tụ cuối cùng đơn giản nào đều bắt đầu với lũy thừa của hai giá trị (đủ rõ ràng?).

2 ^ 64 sẽ tràn về 0, là vòng lặp vô hạn không xác định theo thuật toán (chỉ kết thúc bằng 1), nhưng giải pháp tối ưu nhất trong câu trả lời sẽ kết thúc do shr raxtạo ra ZF = 1.

Chúng ta có thể sản xuất 2 ^ 64 không? Nếu số bắt đầu là số 0x5555555555555555lẻ, số tiếp theo là 3n + 1, là 0xFFFFFFFFFFFFFFFF + 1= 0. Về mặt lý thuyết ở trạng thái không xác định của thuật toán, nhưng câu trả lời được tối ưu hóa của johnfound sẽ phục hồi bằng cách thoát trên ZF = 1. Của cmp rax,1Peter Cordes sẽ kết thúc trong vòng lặp vô hạn (biến thể QED 1, "rẻo" thông qua 0số không xác định ).

Làm thế nào về một số phức tạp hơn, mà sẽ tạo ra chu kỳ mà không có 0? Thành thật mà nói, tôi không chắc, lý thuyết Toán học của tôi quá mù mờ để có được bất kỳ ý tưởng nghiêm túc nào, làm thế nào để giải quyết nó một cách nghiêm túc. Nhưng theo trực giác, tôi sẽ nói rằng chuỗi sẽ hội tụ thành 1 với mọi số: 0 <number, vì công thức 3n + 1 sẽ từ từ biến mọi thừa số nguyên tố không phải 2 của số ban đầu (hoặc trung gian) thành lũy thừa của 2, sớm hay muộn. . Vì vậy, chúng ta không cần phải lo lắng về vòng lặp vô hạn cho chuỗi gốc, chỉ có tràn mới có thể cản trở chúng ta.

Vì vậy, tôi chỉ đặt một vài số vào trang tính và xem xét các số bị cắt bớt 8 bit.

Có ba giá trị tràn tới 0: 227, 17085( 85đi thẳng tới 0, hai khác tiến về phía 85).

Nhưng không có giá trị nào tạo ra hạt giống tràn theo chu kỳ.

Thật thú vị là tôi đã kiểm tra, đây là số đầu tiên bị cắt bớt 8 bit và đã 27bị ảnh hưởng! Nó đạt đến giá trị 9232trong chuỗi không bị cắt ngắn thích hợp (giá trị bị cắt ngắn đầu tiên là 322ở bước thứ 12) và giá trị tối đa đạt được cho bất kỳ số nào trong số 2-255 số đầu vào theo cách không bị cắt ngắn là 13120(đối với 255chính nó), số bước tối đa để hội tụ đến 1là khoảng 128(+ -2, không chắc liệu "1" có được tính không, v.v.).

Thật thú vị (đối với tôi) con số 9232là tối đa cho nhiều số nguồn khác, có gì đặc biệt về nó? : -O 9232= 0x2410... hmmm .. không biết.

Thật không may, tôi không thể hiểu sâu hơn về chuỗi này, tại sao nó lại hội tụ và ý nghĩa của việc cắt ngắn chúng thành k bit, nhưng với cmp number,1điều kiện kết thúc, chắc chắn có thể đặt thuật toán vào vòng lặp vô hạn với giá trị đầu vào cụ thể kết thúc như 0sau sự cắt bớt.

Nhưng giá trị 27tràn cho trường hợp 8 bit là một loại cảnh báo, điều này có vẻ như nếu bạn đếm số bước để đạt đến giá trị 1, bạn sẽ nhận được kết quả sai cho phần lớn các số từ tổng số k-bit tập hợp các số nguyên. Đối với các số nguyên 8 bit, 146 số trong số 256 đã bị ảnh hưởng bởi chuỗi bị cắt bớt (một số trong số chúng có thể vẫn đạt đúng số bước do tình cờ, tôi quá lười để kiểm tra).

5
Damon 2016-11-02 09:50.

Bạn đã không đăng mã được tạo bởi trình biên dịch, vì vậy có một số phỏng đoán ở đây, nhưng ngay cả khi chưa nhìn thấy nó, người ta có thể nói rằng điều này:

test rax, 1
jpe even

... có 50% khả năng xác định sai chi nhánh, và điều đó sẽ phải trả giá đắt.

Trình biên dịch gần như chắc chắn thực hiện cả hai phép tính (chi phí cao hơn đáng kể vì div / mod có độ trễ khá dài, vì vậy phép nhân-cộng là "miễn phí") và theo sau bằng CMOV. Tất nhiên, không có phần trăm khả năng bị đoán sai.

5
Dmitry Rubanovich 2016-11-02 11:16.

Ngay cả khi không nhìn vào quá trình lắp ráp, lý do rõ ràng nhất là nó /= 2có lẽ được tối ưu hóa vì >>=1và nhiều bộ xử lý có hoạt động chuyển dịch rất nhanh. Nhưng ngay cả khi bộ xử lý không có hoạt động shift, phép chia số nguyên sẽ nhanh hơn phép chia dấu phẩy động.

Chỉnh sửa: số tiền của bạn có thể thay đổi theo câu lệnh "phép chia số nguyên nhanh hơn phép chia dấu phẩy động" ở trên. Các nhận xét bên dưới tiết lộ rằng các bộ xử lý hiện đại đã ưu tiên tối ưu hóa phép chia fp hơn phép chia số nguyên. Vì vậy, nếu ai đó đang tìm kiếm nguyên nhân phần nhiều cho tăng tốc mà câu hỏi của chủ đề này yêu cầu tối ưu hóa về, sau đó trình biên dịch /=2như >>=1sẽ là nơi tốt nhất để 1 cái nhìn.


Trên một lưu ý không liên quan , nếu nlà số lẻ, biểu thức n*3+1sẽ luôn là số chẵn. Vì vậy không cần thiết phải kiểm tra. Bạn có thể thay đổi nhánh đó thành

{
   n = (n*3+1) >> 1;
   count += 2;
}

Vì vậy, toàn bộ tuyên bố sau đó sẽ là

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}
4
gnasher729 2016-11-05 07:15.

Như một câu trả lời chung chung, không hướng cụ thể vào nhiệm vụ này: Trong nhiều trường hợp, bạn có thể tăng tốc đáng kể bất kỳ chương trình nào bằng cách thực hiện các cải tiến ở mức cao. Như tính toán dữ liệu một lần thay vì nhiều lần, tránh hoàn toàn các công việc không cần thiết, sử dụng bộ nhớ đệm theo cách tốt nhất, v.v. Những điều này dễ thực hiện hơn nhiều bằng ngôn ngữ cấp cao.

Viết mã trình hợp dịch, có thể cải thiện những gì một trình biên dịch tối ưu hóa làm, nhưng nó là công việc khó khăn. Và sau khi hoàn thành, mã của bạn khó sửa đổi hơn nhiều, vì vậy việc thêm các cải tiến thuật toán cũng khó hơn nhiều. Đôi khi bộ xử lý có chức năng mà bạn không thể sử dụng từ ngôn ngữ cấp cao, hợp ngữ nội tuyến thường hữu ích trong những trường hợp này và vẫn cho phép bạn sử dụng ngôn ngữ cấp cao.

Trong các vấn đề của Euler, hầu hết thời gian bạn thành công bằng cách xây dựng một thứ gì đó, tìm ra lý do tại sao nó chậm, xây dựng thứ gì đó tốt hơn, tìm ra lý do tại sao nó chậm, v.v. Điều đó rất, rất khó sử dụng trình lắp ráp. Một thuật toán tốt hơn với một nửa tốc độ có thể thường sẽ đánh bại một thuật toán kém hơn ở tốc độ tối đa và việc đạt được tốc độ tối đa trong trình hợp dịch không phải là chuyện nhỏ.

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