Why do two different equality tests between two strings of same length take different amounts of time

Question

According to the Python reference manual:

Strings are compared lexicographically using the numeric equivalents (the result of the built-in function ord()) of their characters. Unicode and 8-bit strings are fully interoperable in this behavior.

Meaning hashing is not used for this purpose.

Now, lets assume that internally during an equality test Python first checks the length of the two strings and proceeds with the lexicographical comparison, if both are of same length (I suppose it does the same with all the other comparisons too).

Well, if that is so then why does the following two, different, comparisons consume different amounts of time?

>>> str1 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge1"
>>> 
>>> str2 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge2"
>>> 
>>> def compare():
     t1 = time.time()
     for x in xrange(100000000):
         str1 == str2
     print time.time() - t1
 
>>> 
>>> compare()
13.001019001
>>> 
>>> str2 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge1"
>>> 
>>> compare()
7.41645097733

In both the comparisons str1 and str2 are of the same length. In the first one both differ only by the last character and in the second by none.

PS: Used a long strings and large iterations to make the difference appreciable.

No, caching does not occur, I verified the results of hus787. — Gregor, Sep 16 '12 at 14:41

actual · Accepted Answer · 2012-09-16T14:49:00.497

1

There is some pool of string literals in Python, as in many languages, in the second case both strings are, in fact, the same object, so they are compared by references, not by actual values.

Typical string comparison function in reference-based languages:

if (ref(a) == ref(b)) return true;
if (len(a) != len(b)) return false;
return compare_actual_data(a, b);

edited Sep 16 '12 at 14:49

answered Sep 16 '12 at 14:42

actual

2,370
1
21
32

1

In fact, this can be proven by id(str1) == id(str2). – Gregor Sep 16 '12 at 14:43

score 1 · Answer 2 · answered Sep 16 '12 at 14:47

1

As the other answers surmise, the comparison is indeed short-circuited if the strings are identical, which is the case for string literals with the same content.

answered Sep 16 '12 at 14:47

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

score 1 · Answer 3 · answered Sep 16 '12 at 14:49

In the second case, the two strings are in fact the same object, having the same id.

str1 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge1"
str2 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge2"

def compare():
    t1 = time.time()
    for x in xrange(100000000):
        str1 == str2
    print time.time() - t1


print "%d, %d" % (id(str1), id(str2))
compare()

str2 = "foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge_foo_bar_cruft_kludge1"

print "%d, %d" % (id(str1), id(str2))
compare()

In the second case, the ids are identical, therefore the python interpreter will not have to compare the whole string byte-by-byte.

score 0 · Answer 4 · edited May 23 '17 at 12:27

If two strings are 'interned' then they can be compared by a pointer comparison. Maybe in this case the byte-code generator is noticing the strings are constants and interning them?

You could demonstrate (or disprove) this by showing that the smaller timing is largely independent (or not) of the length of the string.

And indeed, I get these results:

$ ./test.py 
17.4877259731
8.61179995537
$ ./test_halflengthstrings.py 
12.6504788399
8.58732700348

Why do two different equality tests between two strings of same length take different amounts of time

4 Answers4