Tối ưu hóa mô đun lặp lại trong vòng lặp

Question

Tôi có tuyên bố này trong chương trình c của mình và tôi muốn tối ưu hóa. Bằng cách tối ưu hóa, tôi đặc biệt muốn tham khảo các toán tử bitwise (nhưng bất kỳ gợi ý nào khác cũng tốt).

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
for (int i=0; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (h_one + i * h_two) % size; //suggest some optimization for this line. 
} 

Bất kỳ đề xuất nào cũng sẽ hữu ích.

Edit: Tính đến nay size thể được bất kỳ int nhưng nó không phải là một vấn đề và chúng ta có thể làm tròn thành thủ tiếp theo (nhưng có thể không phải là một sức mạnh của hai như đối với các giá trị càng lớn thì sức mạnh của 2 tăng nhanh và nó sẽ dẫn đến lãng phí nhiều bộ nhớ)

h_two là một bit int 64 (về cơ bản là một chuck 64 byte).

Answer 1

nên về cơ bản bạn đang làm

k_0 = h_1 mod s 
k_1 = h_1 + h_2 mod s = k_0 + h_2 mod s 
k_2 = h_1 + h_2 + h_2 mod s = k_1 + h_2 mod s 
.. 
k_n = k_(n-1) + h_2 mod s 

Tùy thuộc vào tràn vấn đề (không nên khác với bản gốc nếu kích thước nhỏ hơn một nửa của 2**64), điều này có thể nhanh hơn (ít dễ dàng hơn để song song):

uint64_t h_one = hash[0]; 
uint64_t h_two = hash[1]; 
k_hash[0] = h_one % size; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two) % size; 
} 

Lưu ý rằng có khả năng trình biên dịch của bạn đã đến biểu mẫu này, tùy thuộc vào cờ tối ưu hóa bạn sử dụng.

Tất nhiên điều này chỉ loại bỏ một phép nhân. Nếu bạn muốn loại bỏ hoặc giảm modulo, tôi đoán rằng dựa trên h_two%size và h_1%size bạn có thể định trước các bước mà bạn phải gọi một cách rõ ràng %size, một cái gì đó như thế này:

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
step = (size-(h_one))/(h_two)-1; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(i==step) 
    { 
     k_hash[i] %= size; 
    } 
} 

Note Tôi không chắc chắn của công thức (không thử nghiệm nó), nó là một ý tưởng chung hơn. Điều này sẽ phụ thuộc rất nhiều vào dự đoán chi nhánh của bạn tốt như thế nào (và mức độ hiệu quả của việc đánh giá sai là bao nhiêu). Ngoài ra, nó chỉ có khả năng giúp đỡ nếu bước là lớn.

chỉnh sửa: hoặc đơn giản hơn (và có lẽ với hiệu suất tương tự) -Cảm ơn đến Mystical:

uint64_t h_one = hash[0]%size; 
uint64_t h_two = hash[1]%size; 
k_hash[0] = h_one; 
for (int i=1; i<k; ++i) 
{ 
    (uint64_t *) k_hash[i] = (k_hash[i-1] + h_two); 
    if(k_hash[i] > size) 
    { 
     k_hash[i] -= size; 
    } 
} 

Answer 2

Nếu kích thước là một sức mạnh của hai, sau đó áp dụng toán tử AND để kích thước - 1 tối ưu hóa "% kích thước":

(uint64_t *)k_hash[i] = (h_one + i * h_two) & (size - 1)