2017-01-24 29 views
20

Tôi luôn nghĩ rằng so sánh là hoạt động nhanh nhất mà máy tính có thể thực thi. Tôi nhớ đã nghe nó trên một bài thuyết trình của D. Knuth, nơi anh ấy viết các vòng theo thứ tự giảm dần "vì so sánh với 0 là nhanh". Tôi cũng đọc rằng phép nhân nên chậm hơn so với số bổ sung here.Tại sao việc cộng và phép nhân nhanh hơn so sánh?

Tôi ngạc nhiên khi thấy rằng, trong cả Python 2 và 3, thử nghiệm trong cả Linux và Mac, so sánh dường như chậm hơn nhiều so với các phép toán số học.

Có ai giải thích tại sao không?

%timeit 2 > 0 
10000000 loops, best of 3: 41.5 ns per loop 

%timeit 2 * 2 
10000000 loops, best of 3: 27 ns per loop 

%timeit 2 * 0 
10000000 loops, best of 3: 27.7 ns per loop 

%timeit True != False 
10000000 loops, best of 3: 75 ns per loop 

%timeit True and False 
10000000 loops, best of 3: 58.8 ns per loop 

Và dưới python 3:

$ ipython3 
Python 3.5.2 | packaged by conda-forge | (default, Sep 8 2016, 14:36:38) 
Type "copyright", "credits" or "license" for more information. 

IPython 5.1.0 -- An enhanced Interactive Python. 
?   -> Introduction and overview of IPython's features. 
%quickref -> Quick reference. 
help  -> Python's own help system. 
object? -> Details about 'object', use 'object??' for extra details. 

In [1]: %timeit 2 + 2 
10000000 loops, best of 3: 22.9 ns per loop 

In [2]: %timeit 2 * 2 
10000000 loops, best of 3: 23.7 ns per loop 

In [3]: %timeit 2 > 2 
10000000 loops, best of 3: 45.5 ns per loop 

In [4]: %timeit True and False 
10000000 loops, best of 3: 62.8 ns per loop 

In [5]: %timeit True != False 
10000000 loops, best of 3: 92.9 ns per loop 
+3

Tôi mong đợi tất cả những ví dụ đó được lặp lại liên tục trên đường trở thành bytecode. Có lẽ thời gian bị cản trở. –

+5

nói chung, 'bởi vì so sánh với 0 là fast' có liên quan cao nếu lập trình Z80 hoặc tương tự ... nếu không nó có thể không có gì cả, và đó chính là loại điều được nhắc tới bởi một trích dẫn nổi tiếng nhất của Knuth . Tôi có thể đoán rằng Knuth đã nói về ngôn ngữ lắp ráp thô ở đây, và nếu như vậy, cố gắng áp dụng ngôn ngữ đó vào một ngôn ngữ biên dịch/giải thích là một tổng số không gần như không liên tục. –

+2

Khi điểm chuẩn, hãy cảnh giác với [liên tục gấp] (https://en.wikipedia.org/wiki/Constant_folding). – Schwern

Trả lời

18

này xảy ra do Constant Folding trong Peep Holeoptimizer trong trình biên dịch Python .

Sử dụng mô-đun dis, nếu chúng ta phá vỡ từng câu lệnh để xem bên trong cách chúng được dịch ở mức máy, bạn sẽ quan sát thấy tất cả các toán tử như bất bình đẳng, bình đẳng, vv được nạp vào bộ nhớ và sau đó được đánh giá. Tuy nhiên, tất cả các biểu thức như phép nhân, phép cộng vv được tính và được nạp dưới dạng hằng số vào bộ nhớ.

Nhìn chung, điều này dẫn đến một số ít các bước thực hiện, làm cho bước nhanh hơn:

>>> import dis 

>>> def m1(): True != False 
>>> dis.dis(m1) 
    1   0 LOAD_GLOBAL    0 (True) 
       3 LOAD_GLOBAL    1 (False) 
       6 COMPARE_OP    3 (!=) 
       9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   

>>> def m2(): 2 *2 
>>> dis.dis(m2) 
    1   0 LOAD_CONST    2 (4) 
       3 POP_TOP    
       4 LOAD_CONST    0 (None) 
       7 RETURN_VALUE   

>>> def m3(): 2*5 
>>> dis.dis(m3) 
    1   0 LOAD_CONST    3 (10) 
       3 POP_TOP    
       4 LOAD_CONST    0 (None) 
       7 RETURN_VALUE   

>>> def m4(): 2 > 0 
>>> dis.dis(m4) 
    1   0 LOAD_CONST    1 (2) 
       3 LOAD_CONST    2 (0) 
       6 COMPARE_OP    4 (>) 
       9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   

>>> def m5(): True and False 
>>> dis.dis(m5) 
    1   0 LOAD_GLOBAL    0 (True) 
       3 JUMP_IF_FALSE_OR_POP  9 
       6 LOAD_GLOBAL    1 (False) 
     >> 9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   
+0

Tôi ngạc nhiên rằng người tối ưu hóa lổ nhìn trộm không làm giảm các điều kiện đã biết, đặc biệt là xem xét nó sẽ cho phép các nhánh cây chết. Sử dụng tốt dis –

+1

@JonChesterfield _surprised rằng các optimiser lổ nhìn trộm không giảm điều kiện được biết đến: Vâng, vì vậy là I. Nhưng cho rằng sự bất bình đẳng và biểu thức khác có thể được sử dụng trên bất kỳ loại đối tượng trong Python thế giới, có thể, để lại cho họ trong trình biên dịch sẽ hữu ích hơn trong các ví dụ mã thực tế. –

+0

Nó có thể là một câu hỏi riêng biệt. Tôi không thể nghĩ ra lý do tại sao 2 <2 không thể được giải quyết tĩnh. Có lẽ Python cho phép người dùng ghi đè lên '__LT__' cho các kiểu được tạo sẵn hoặc có thể nó chỉ là một trường hợp bị thiếu trong trình tối ưu hóa. –

4

Một nhanh chóng disassambling cho thấy sự so sánh liên quan đến nhiều hoạt động. Theo this answer, có một số precalculation thực hiện bởi các "peephole optimiser" (wiki) cho phép nhân, bổ sung, vv, nhưng không phải cho các nhà khai thác so sánh:

>>> import dis 
>>> def a(): 
... return 2*3 
... 
>>> dis.dis(a) 
    2   0 LOAD_CONST    3 (6) 
       3 RETURN_VALUE 
>>> def b(): 
... return 2 < 3 
... 
>>> dis.dis(b) 
    2   0 LOAD_CONST    1 (2) 
       3 LOAD_CONST    2 (3) 
       6 COMPARE_OP    0 (<) 
       9 RETURN_VALUE 
4

Giống như những người khác đã nhận xét - đó là do tôi ưu hoa lỗ peep mà trước tính kết quả của 2 * 3 (6). Khi dis lãm

0 LOAD_CONST    3 (6) 

Nhưng thử này - nó sẽ vô hiệu hóa ưu từ mầm non tính toán kết quả

>>> def a(a, b): 
...  return a*b 
... 
>>> dis.dis(a) 
    2   0 LOAD_FAST    0 (a) 
       3 LOAD_FAST    1 (b) 
       6 BINARY_MULTIPLY 
       7 RETURN_VALUE 
>>> def c(a,b): 
...  return a<b 
... 
>>> dis.dis(c) 
    2   0 LOAD_FAST    0 (a) 
       3 LOAD_FAST    1 (b) 
       6 COMPARE_OP    0 (<) 
       9 RETURN_VALUE 
>>> 

Nếu bạn có thời gian những chức năng so sánh sẽ nhanh hơn.

2

Đối với trường hợp trăn, các câu trả lời ở trên là chính xác. Đối với mã máy, mọi thứ phức tạp hơn một chút. Tôi giả sử chúng ta đang nói về các hoạt động số nguyên ở đây, với các float và các đối tượng phức tạp, không có phần nào dưới đây sẽ được áp dụng. Ngoài ra, chúng tôi giả định rằng các giá trị bạn đang so sánh đã được tải vào sổ đăng ký. Nếu họ không tìm nạp chúng từ bất cứ nơi nào họ có thể mất 100 lần lâu hơn hoạt động thực tế

CPU hiện đại có một số cách để so sánh hai số. Những người rất phổ biến đang làm XOR a, b nếu bạn chỉ muốn xem hai giá trị bằng hoặc CMP a, b nếu bạn muốn biết mối quan hệ giữa các giá trị (ít hơn, lớn hơn, bằng nhau, v.v.). Hoạt động CMP chỉ là phép trừ với kết quả bị bỏ đi vì chúng ta chỉ quan tâm đến các cờ post-op.

Cả hai thao tác này đều có độ sâu 1, vì vậy chúng có thể được thực hiện trong một chu kỳ CPU. Đây là nhanh như bạn có thể đi. Phép nhân là một dạng bổ sung lặp đi lặp lại nên độ sâu của thao tác thường bằng với kích thước thanh ghi của bạn.Có một số tối ưu hóa có thể được thực hiện để giảm độ sâu, nhưng nói chung nhân là một trong những hoạt động chậm hơn mà CPU có thể thực hiện.

Tuy nhiên, nhân với 0,1 hoặc bất kỳ lũy thừa nào của 2 có thể được giảm xuống để dịch chuyển. Đó cũng là chiều sâu một hoạt động. Vì vậy, phải mất cùng một thời gian khi so sánh hai con số. Hãy suy nghĩ về hệ thập phân, bạn có thể nhân bất kỳ số nào với 10, 100, 1000 bằng cách chắp thêm số không ở cuối số. Bất kỳ trình biên dịch tối ưu hóa nào sẽ nhận ra kiểu phép nhân này và sử dụng thao tác hiệu quả nhất cho nó. CPU hiện đại cũng khá tiên tiến, vì vậy họ có thể thực hiện tối ưu hóa tương tự trong phần cứng bằng cách đếm số lượng bit được đặt trong bất kỳ toán hạng nào. Và nếu nó chỉ là một chút hoạt động sẽ được giảm đến sự thay đổi.

Vì vậy, trong trường hợp của bạn nhân với 2 là nhanh như so sánh hai số. Như những người ở trên chỉ ra bất kỳ trình biên dịch tối ưu hóa sẽ thấy rằng bạn đang nhân hai hằng số, do đó, nó sẽ thay thế chỉ thay thế các chức năng với trả về một hằng số.

8

Như những người khác đã giải thích, điều này là do trình tối ưu hóa lổ nhìn trộm của Python tối ưu hóa các phép tính số học nhưng không so sánh.

Đã viết trình tối ưu hóa lổ nhìn trộm của riêng tôi cho trình biên dịch Cơ bản, tôi có thể đảm bảo với bạn rằng việc tối ưu hóa các so sánh không đổi cũng dễ dàng như tối ưu hóa các phép toán số học liên tục. Vì vậy, không có lý do kỹ thuật tại sao Python nên làm sau này nhưng không phải là trước đây.

Tuy nhiên, mỗi tối ưu hóa như vậy phải được lập trình riêng và đi kèm với hai chi phí: thời gian lập trình và mã tối ưu hóa bổ sung chiếm dung lượng trong Python thực thi. Vì vậy, bạn thấy mình phải làm một số phân loại: mà những tối ưu hóa này là phổ biến, đủ để làm cho nó có giá trị chi phí?

Dường như những người triển khai Python, đủ hợp lý, đã quyết định tối ưu hóa hoạt động số học trước tiên. Có lẽ họ sẽ nhận được vòng để so sánh trong một phiên bản tương lai.

+2

Cần lưu ý rằng trong python 2, các hoạt động 'True! = False' và' True and False' không thể được tối ưu hóa theo cách đó, vì cả 'True' và' False' có thể được định nghĩa lại, vì vậy các globals này cần phải được nhìn lên mỗi khi nó thực hiện. Trong python 3, 'True' và' False' là các từ khóa và không thể được định nghĩa lại. –

+0

Cảm ơn @Amanda, tôi đã không nhận thức được điều đó. Tò mò, sau đó, thời gian Python 3 của OP bỏ qua các trường hợp True và False. – TonyK

+0

Ngoài ra còn có một chi phí thứ ba - thời gian thực hiện để thực sự vượt qua tối ưu hóa mỗi khi nguồn được biên dịch (trong một số trường hợp có thể là mỗi khi chương trình được chạy). :) – psmears

1

Chà, Câu trả lời của @mu 無 làm phiền tâm trí của tôi! Tuy nhiên, điều quan trọng là không khái quát khi đưa ra kết luận của bạn ... Bạn đang kiểm tra thời gian cho CONSTANTS không phải biến số. Đối với các biến, phép nhân dường như chậm hơn so sánh.

Đây là trường hợp thú vị hơn, trong đó các con số để được so sánh được lưu trữ trong các biến thực tế ...

import timeit 
def go(): 
    number=1000000000 
    print 
    print 'a>b, internal:',timeit.timeit(setup="a=1;b=1", stmt="a>b", number=number) 
    print 'a*b, internal:',timeit.timeit(setup="a=1;b=1", stmt="a*b", number=number) 
    print 'a>b, shell :', 
    %%timeit -n 1000000000 "a=1;b=1" "a>b" 
    print 'a*b, shell :', 
    %%timeit -n 1000000000 "a=1;b=1" "a*b" 
go() 

Kết quả cho:

a>b, internal: 51.9467676445 
a*b, internal: 63.870462403 
a>b, shell :1000000000 loops, best of 3: 19.8 ns per loop 
a>b, shell :1000000000 loops, best of 3: 19.9 ns per loop 

Và để được phục hồi trong vũ trụ;)

Để hoàn thành, hãy xem thêm một số trường hợp ... Còn nếu chúng ta có một biến và một hằng số thì sao?

import timeit 
def go(): 
    print 'a>2, shell :', 
    %%timeit -n 10000000 "a=42" "a>2" 
    print 'a*2, shell :', 
    %%timeit -n 10000000 "a=42" "a*2" 
go() 

a>2, shell :10000000 loops, best of 3: 18.3 ns per loop 
a*2, shell :10000000 loops, best of 3: 19.3 ns per loop 

điều gì xảy ra với bools?

import timeit 
def go(): 
    print 
    number=1000000000 
    print 'a==b : ', timeit.timeit(setup="a=True;b=False",stmt="a==b",number=number) 
    print 'a and b : ', timeit.timeit(setup="a=True;b=False",stmt="a and b",number=number) 
    print 'boolean ==, shell :', 
    %%timeit -n 1000000000 "a=True;b=False" "a == b" 
    print 'boolean and, shell :', 
    %%timeit -n 1000000000 "a=False;b=False" "a and b" 
go() 

a==b : 70.8013108982 
a and b : 38.0614485665 
boolean ==, shell :1000000000 loops, best of 3: 17.7 ns per loop 
boolean and, shell :1000000000 loops, best of 3: 16.4 ns per loop 

: D Bây giờ đây là thú vị, có vẻ như boolean và nhanh hơn ==. Tuy nhiên tất cả điều này sẽ được ok như Donald Knuth sẽ không mất ngủ của mình, cách tốt nhất để so sánh sẽ được sử dụng và ...

Trong thực tế, chúng ta nên kiểm tra numpy, mà có thể còn quan trọng hơn ...

import timeit 
def go(): 
    number=1000000 # change if you are in a hurry/ want to be more certain.... 
    print '==== int ====' 
    print 'a>b : ', timeit.timeit(setup="a=1;b=2",stmt="a>b",number=number*100) 
    print 'a*b : ', timeit.timeit(setup="a=1;b=2",stmt="a*b",number=number*100) 
    setup = "import numpy as np;a=np.arange(0,100);b=np.arange(100,0,-1);" 
    print 'np: a>b : ', timeit.timeit(setup=setup,stmt="a>b",number=number) 
    print 'np: a*b : ', timeit.timeit(setup=setup,stmt="a*b",number=number) 
    print '==== float ====' 
    print 'float a>b : ', timeit.timeit(setup="a=1.1;b=2.3",stmt="a>b",number=number*100) 
    print 'float a*b : ', timeit.timeit(setup="a=1.1;b=2.3",stmt="a*b",number=number*100) 
    setup = "import numpy as np;a=np.arange(0,100,dtype=float);b=np.arange(100,0,-1,dtype=float);" 
    print 'np float a>b : ', timeit.timeit(setup=setup,stmt="a>b",number=number) 
    print 'np float a*b : ', timeit.timeit(setup=setup,stmt="a*b",number=number) 
    print '==== bool ====' 
    print 'a==b : ', timeit.timeit(setup="a=True;b=False",stmt="a==b",number=number*1000) 
    print 'a and b : ', timeit.timeit(setup="a=True;b=False",stmt="a and b",number=number*1000) 
    setup = "import numpy as np;a=np.arange(0,100)>50;b=np.arange(100,0,-1)>50;" 
    print 'np a == b : ', timeit.timeit(setup=setup,stmt="a == b",number=number) 
    print 'np a and b : ', timeit.timeit(setup=setup,stmt="np.logical_and(a,b)",number=number) 
    print 'np a == True : ', timeit.timeit(setup=setup,stmt="a == True",number=number) 
    print 'np a and True : ', timeit.timeit(setup=setup,stmt="np.logical_and(a,True)",number=number) 
go() 

==== int ==== 
a>b : 4.5121130192 
a*b : 5.62955748632 
np: a>b : 0.763992986986 
np: a*b : 0.723006032235 
==== float ==== 
float a>b : 6.39567713272 
float a*b : 5.62149055215 
np float a>b : 0.697037433398 
np float a*b : 0.847941712765 
==== bool ==== 
a==b : 6.91458288689 
a and b : 3.6289697892 
np a == b : 0.789666454087 
np a and b : 0.724517620007 
np a == True : 1.55066706189 
np a and True : 1.44293071804 

Một lần nữa, cùng một hành vi ... Vì vậy, tôi đoán, người ta có thể hưởng lợi bằng cách sử dụng thay cho == nói chung,

ít nhất bằng Python 2 (Python 2.7.11 | Anaconda 2.4.1 (64-bit) | (mặc định, ngày 16 tháng 2 năm 2016, 09:58:36) [MSC v.1500 64 bit (AMD64)]), nơi tôi đã thử tất cả những ...

Các vấn đề liên quan