Tại sao lấy mod của một số trong python nhanh hơn với số mũ?

Question

Tôi đã cố gắng tối ưu hóa một chương trình tôi đang làm việc với, khi tôi nhận thấy rằng làm value = i % 65536 dường như chạy chậm hơn sau đó thực hiện value = i % (2**16).

Để kiểm tra điều này, tôi chạy chương trình sau đây:

import cProfile 
import pstats 

AMOUNT = 100000000 

def test1(): 
    for i in xrange(AMOUNT): 
     value = i % 65536 
    return 

def test2(): 
    for i in xrange(AMOUNT): 
     value = i % (256**2) 
    return 

def test3(): 
    for i in xrange(AMOUNT): 
     value = i % (16**4) 
    return 

def test4(): 
    for i in xrange(AMOUNT): 
     value = i % (4**8) 
    return 

def test5(): 
    for i in xrange(AMOUNT): 
     value = i % (2**16) 
    return 

def run_tests(): 
    test1() 
    test2() 
    test3() 
    test4() 
    test5() 
    return 

if __name__ == '__main__': 
    cProfile.run('run_tests()', 'results') 
    stats = pstats.Stats('results') 
    stats.sort_stats('calls', 'nfl') 
    stats.print_stats() 

... mà sản xuất đầu ra sau đây:

Fri May 11 15:11:59 2012 results 

     8 function calls in 40.473 seconds 

    Ordered by: call count, name/file/line 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     1 0.000 0.000 40.473 40.473 <string>:1(<module>) 
     1 0.000 0.000 40.473 40.473 test.py:31(run_tests) 
     1 10.466 10.466 10.466 10.466 test.py:6(test1) 
     1 7.475 7.475 7.475 7.475 test.py:11(test2) 
     1 7.485 7.485 7.485 7.485 test.py:16(test3) 
     1 7.539 7.539 7.539 7.539 test.py:21(test4) 
     1 7.508 7.508 7.508 7.508 test.py:26(test5) 

Sử dụng 65536 là chậm nhất tại 10,466 giây, trong khi làm 256**2 là nhanh nhất tại 7.475 giây (với các giá trị số mũ khác có thể rơi vào giữa). Cấp, sự khác biệt về tốc độ này chỉ đáng chú ý với số lượng lặp lại cao, nhưng tôi vẫn tò mò là tại sao điều này xảy ra.

Tại sao lấy mod của một số bằng 65536 chậm hơn sau đó lấy mod bằng số mũ? Họ nên đánh giá cùng một số, và tôi đã nghĩ rằng sẽ mất nhiều thời gian hơn cho trình thông dịch python để đánh giá đầy đủ các số mũ trước khi dùng mod.

Bằng cách gia hạn, nói chung là hiệu quả hơn để sử dụng quyền hạn của hai trong biểu thức python chứ không phải sau đó gõ đầy đủ số ra? Và mô hình này có đúng với các hoạt động ngoài mô đun hoặc cho các số khác ngoài 2 không?

(btw, tôi đang sử dụng Python 2.7.2 (32 bit) và tôi đã chạy ở trên trên máy tính xách tay 64 bit Windows 7).

EDIT:
Vì vậy, tôi đã cố gắng đảo ngược thứ tự của các chức năng tôi gọi, và bây giờ ngược lại là đúng. Có vẻ như chức năng đầu tiên là ở run_tests sẽ luôn chạy chậm hơn một chút khi sử dụng cProfile, là lạ. Vì vậy, bài học kinh nghiệm, tôi đoán - profilers là lạ: D

Answer 1

Không có sự khác biệt trong bytecode được tạo ra, bởi vì trình biên dịch thực hiện tốt công việc của nó và tối ưu hóa biểu thức số học không đổi. Điều đó có nghĩa là kết quả thử nghiệm của bạn chỉ là trùng hợp ngẫu nhiên (hãy thử định thời gian các hàm theo thứ tự khác!).

>>> import dis 
>>> dis.dis(test1) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    1 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> dis.dis(test5) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    3 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   

(cũng thực sự có sự khác biệt: Con số này được lưu trữ tại các độ lệch khác nhau trong bảng liên tục Tôi không thể tưởng tượng này gây ra bất kỳ sự khác biệt, mặc dù.).

Để hoàn chỉnh, đây là một thử nghiệm thích hợp sử dụng các mô-đun timeit:

import timeit 

setup = "i = 1337" 

best1 = best2 = float("inf") 
for _ in range(5000): 
    best1 = min(best1, timeit.timeit("i % 65536", setup=setup, number=10000)) 
for _ in range(5000): 
    best2 = min(best2, timeit.timeit("i % (2**16)", setup=setup, number=10000)) 
print best1 
print best2 

Lưu ý rằng tôi đo thời gian tối thiểu cần thiết, chứ không phải là mức trung bình. Nếu mất nhiều thời gian hơn vì lý do nào đó, điều này có nghĩa là nó bị gián đoạn thường xuyên hơn (vì mã không phụ thuộc vào bất cứ thứ gì ngoài sức mạnh của CPU của bạn).

Answer 2

Hmmm, sử dụng dis để hiển thị mã byte python cho thấy rằng các hàm giống nhau. Python đã tối ưu hóa hằng số (như mong đợi). Vì vậy, tôi nghi ngờ sự khác biệt thời gian là bộ nhớ đệm hiệu ứng. Thời gian trên máy tính xách tay của tôi chịu điều này (sử dụng Python 2.7.3 64 bit trên Linux)

Fri May 11 23:37:49 2012 results 

    8 function calls in 38.825 seconds 

Ordered by: call count, name/file/line 

ncalls tottime percall cumtime percall filename:lineno(function) 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    1 0.000 0.000 38.825 38.825 <string>:1(<module>) 
    1 0.000 0.000 38.825 38.825 z.py:31(run_tests) 
    1 7.880 7.880 7.880 7.880 z.py:6(test1) 
    1 7.658 7.658 7.658 7.658 z.py:11(test2) 
    1 7.806 7.806 7.806 7.806 z.py:16(test3) 
    1 7.784 7.784 7.784 7.784 z.py:21(test4) 
    1 7.697 7.697 7.697 7.697 z.py:26(test5) 

Tất cả khá nhiều giống hệt

>>> from dis import dis 
>>> def test1(): 
...  for i in xrange(AMOUNT): 
...   value = i % 65536 
...  return 
... 
>>> def test5(): 
...  for i in xrange(AMOUNT): 
...   value = i % (2**16) 
...  return 
... 
>>> dis(test1) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    1 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> dis(test5) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    3 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> 

Answer 3

Bạn đã chạy mỗi bài kiểm tra chỉ một lần. Tốc độ của CPU của bạn không phải lúc nào cũng giống nhau, vào lúc bắt đầu thử nghiệm nó có lẽ là ngủ nhiều nhất và đó là lý do tại sao thử nghiệm đầu tiên chậm hơn. Để đánh giá các phần nhỏ của mã (như mod) sử dụng mô-đun thời gian:

>>> timeit.timeit('for i in range(10000): i % 65536', number=1000) 
0.8686108589172363 
>>> timeit.timeit('for i in range(10000): i % 256**2', number=1000) 
0.862062931060791 
>>> timeit.timeit('for i in range(10000): i % 4**8', number=1000) 
0.8644928932189941 
>>> timeit.timeit('for i in range(10000): i % 2**16', number=1000) 
0.8643178939819336 
>>> timeit.timeit('for i in range(10000): i % 65536', number=1000) 
0.8640358448028564 

Bạn có thể thấy rằng mức trung bình luôn là khoảng 0,864.