C++ đã ký và unsigned int so với tốc độ dài dài

Question

Hôm nay, tôi nhận thấy rằng tốc độ của một số thao tác bit và số học đơn giản khác nhau đáng kể giữa int, unsigned, long long và unsigned long long trên máy tính 64 bit của tôi.

Cụ thể, vòng lặp sau nhanh gấp hai lần cho unsigned như đối với long long, điều mà tôi không mong đợi.

int k = 15; 
int N = 30; 
int mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    int lo = mask & ~(mask - 1); 
    int lz = (mask + lo) & ~mask; 
    mask |= lz; 
    mask &= ~(lz - 1); 
    mask |= (lz/lo/2) - 1; 
} 

(đầy đủ đang here)

Sau đây là các timings (tính bằng giây) (đối với g++ -O, -O2 và -O3):

1.834207723 (int) 
3.054731598 (long long) 
1.584846237 (unsigned) 
2.201142018 (unsigned long long) 

Những thời gian được tính rất phù hợp (ví dụ: 1% lề). Nếu không có cờ -O, mỗi cờ sẽ chậm hơn một giây, nhưng tốc độ tương đối giống nhau.

Có lý do rõ ràng cho việc này không? Vector hóa có thể là đối với các loại 32 bit, nhưng tôi không thể thấy sự khác biệt lớn giữa giữa long long và unsigned long long là gì. Một số hoạt động có chậm hơn nhiều so với các loại khác, hay chỉ là một điều chung mà các loại 64 bit chậm hơn (thậm chí trên các kiến ​​trúc 64 bit)?

Đối với những người quan tâm, vòng lặp này lặp trên tất cả các tập con của {1,2,...,30} với chính xác 15 phần tử. Điều này được thực hiện bằng cách lặp (theo thứ tự) trên tất cả các số nguyên nhỏ hơn 1<<30 với chính xác 15 bit được đặt. Đối với trường hợp hiện tại, đó là 155117520 lần lặp. Tôi không biết nguồn của đoạn mã này nữa, nhưng this bài giải thích một số thông tin khác.

Chỉnh sửa

Có vẻ như mã lắp ráp có thể được thực hiện nhanh hơn khi loại không được ký. Tôi nghĩ điều đó có ý nghĩa, bởi vì chúng tôi không phải tính đến bit dấu.

Bên cạnh đó, các hoạt động 32-bit sử dụng movl và xxxl khác hướng dẫn, trong khi hoạt động 64-bit sử dụng movq và xxxq.

Sửa 2

Sau khi đọc bài tôi liên kết, tôi quyết định sử dụng công thức cho đằng kia:

T k = 15; 
T N = 30; 
T mask = (1 << k) - 1; 
while (!(mask & 1 << N)) { 
    T t = mask | (mask - 1); 
    mask = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(mask) + 1)); 
} 

này chạy trong khoảng một phần ba thời gian của mã được đăng trên đây, và sử dụng cùng một thời điểm cho cả bốn loại.

Answer 1

Các hoạt động chậm nhất trong mã của bạn là

phận

mask |= (lz/lo/2) - 1 

32-bit là nhanh hơn so với bộ phận 64-bit đáng kể. Ví dụ, trên Ivy Bridge, IDIV 32 bit mất 19-26 đồng hồ trong khi IDIV 64 bit mất 28-103 độ trễ đồng hồ.

Phiên bản chưa ký cũng nhanh hơn chữ ký vì chia cho 2 là chuyển bit đơn giản trong trường hợp chưa được ký và không có cuộc gọi mở rộng kích thước (CDQ, CQO).

trong trường hợp unsigned là sự thay đổi chút đơn giản trong khi ở ký

[1] http://www.agner.org/optimize/instruction_tables.pdf