{"id":458,"date":"2012-09-30T02:57:08","date_gmt":"2012-09-30T00:57:08","guid":{"rendered":"http:\/\/pit-claudel.fr\/clement\/blog\/?p=458"},"modified":"2013-12-19T01:22:19","modified_gmt":"2013-12-19T00:22:19","slug":"modeling-and-measuring-string-comparison-performance-in-c-cpp-csharp-and-python","status":"publish","type":"post","link":"https:\/\/pit-claudel.fr\/clement\/blog\/modeling-and-measuring-string-comparison-performance-in-c-cpp-csharp-and-python\/","title":{"rendered":"Modeling and measuring string comparison performance in C, C++, C# and Python."},"content":{"rendered":"

\"O(1)\" Comparing strings is often — erroneously — said to be a costly process. In this article I derive the theoretical asymptotic cost of comparing random strings of arbitrary length, and measure it in C, C++, C# and Python.<\/p>\n

<\/p>\n

Theoretical amortized cost<\/h2>\n

Infinite strings<\/h3>\n

Suppose one draws two random strings \\(A = “a_0a_1a_2…”\\) and \\(B = “b_0b_1b_2…”\\) of infinite length, with \\(a_n\\) and \\(b_n\\) respectively denoting the \\(n\\)th<\/sup> character of \\(A\\) and \\(B\\). We will assume that characters are independent, and uniformly drawn over the set \\(\\{a, b, c, …, z\\}\\). For now, we will consider all strings to be of infinite length — we’ll study bounded-length strings in the next section.<\/p>\n

Given that characters making up \\(A\\) and \\(B\\) are independent, the probability of \\(A\\) differing from \\(B\\) at index \\(n\\) is \\(25\/26\\). Conversely, the probability of \\(A\\) matching string \\(B\\) at index \\(n\\) is \\(1\/26\\).<\/p>\n

Consequently, the probability of \\(A\\) matching \\(B\\) up to index \\(n – 1\\), and differing at index \\(n\\), is \\((1\/26)^n ⋅ (25\/26)\\). Therefore, given that comparing strings up to index \\(n\\) included is \\((n+1)\\) the expected number of characters to compare to discriminate \\(A\\) and \\(B\\) is $$ C = \\sum_{n=0}^{\\infty} (n+1) ⋅ (1\/26)^n ⋅ (25\/26) = 26\/25$$<\/p>\n

Indeed, defining \\(C(x) = (1-x) ⋅ \\sum_{n=0}^{\\infty} (n+1) x^n\\), the expected number of comparisons \\(C\\) required to discriminate \\(A\\) and \\(B\\) is \\(C(1\/26)\\). Now \\(C(x) = (1-x) ⋅ \\sum_{n=0}^{\\infty} \\frac{∂ x^n}{∂ x} = (1-x) ⋅ \\frac{∂ \\sum_{n=0}^{\\infty} x^{n+1}}{∂ x} = (1-x) ⋅ (1-x)^{-2} = 1\/(1-x)\\). Plugging \\(x=1\/26\\) yields \\(C = 26\/25 \\approx 1.04\\).<\/p>\n

In other words, it takes an average of \\(1.04\\) character comparisons to discriminate two random strings of infinite length. That’s rather cheap. <\/p>\n

Finite strings<\/h3>\n

In this section we assume that \\(A\\) and \\(B\\) are bounded in length by a constant \\(L\\). This implies that the probability of the comparison routine reaching any index greater than \\((L-1)\\) is \\(0\\); hence the expected number of comparisons \\(C_L\\) is $$C_L = \\sum_{n=0}^{L-1} (n+1) ⋅ (1\/26)^n ⋅ (25\/26) = (26\/25) ⋅ (1 – \\frac{25L + 26}{26^{L+1}})$$
\nFor any \\(L > 3\\), this is virtually indistinguishable from the previously calculated value \\(C = 1.04\\).<\/p>\n

Conclusion<\/h3>\n

The theoretical amortized time required to compare two strings is constant — independent of their length. Of course, there may be a sizeable overhead associated to comparing strings instead of ints: experimental measurements of this overhead are presented below.<\/p>\n

Experimental measurements<\/h2>\n

The following charts present the time it took to perform 100’000 string comparisons on my laptop, compared to a baseline of 100’000 integer comparisons, in 3 different programming languages and for string lengths varying from 1 to 500 characters. Despite large variations for small string lengths, measured times quickly converge to a fixed limit as strings lengthen ((If you want to experiment with the tests, you can download the full python<\/a>, C++<\/a>, or C#<\/a> source code.)).<\/p>\n

\n \"Chart<\/p>\n

Time required to compare 100’000 pairs of random strings, as a function of string length, in Python (3.2.3)<\/p>\n<\/div>\n

\n\t\"Chart<\/p>\n

Time required to compare 100’000 pairs of random strings, as a function of string length, in C# (csc 4.0.30319.17929)<\/p>\n<\/div>\n

\n\t\"Chart<\/p>\n

Time required to compare 100’000 pairs of random strings, as a function of string length, in C++ (gcc 4.3.4).<\/p>\n<\/div>\n

Remarks<\/h3>\n

Though large strings (over ~200 characters) experimentally match our statistical model, small strings exhibit a much more complex behaviour. I can think of a two causes for such variations:<\/p>\n