Re-evaluate "slowness" linter rule
Closed, ResolvedPublic
Actions

Assigned To

Authored By

	joshuaspence
	Aug 5 2015, 3:42 AM

Description

Currently we have a linter rule (ArcanistSlownessXHPASTLinterRule) which recommends that strncmp() is used instead of strpos() for checking whether a string starts with some substring. It seems that this was added in D3296.

I am having trouble understanding the reasoning behind this linter rule. From some initial benchmarking, strpos seems to be more performant than strncmp. From a comment on http://php.net/manual/en/function.strncmp.php:

<?php

$haystack = "abcdefghijklmnopqrstuvwxyz";
$needles = array('abc', 'xyz', '123');
foreach ($needles as $needle) {
  $times['strncmp'][$needle] = -microtime(true);
  for ($i = 0; $i < 1000000; $i++) {
    $result = strncmp($haystack, $needle, 3) === 0;
  }
  $times['strncmp'][$needle] += microtime(true);
}
foreach ($needles as $needle) {
  $times['strpos'][$needle] = -microtime(true);
  for ($i = 0; $i < 1000000; $i++) {
    $result = strpos($haystack, $needle) === 0;
  }
  $times['strpos'][$needle] += microtime(true);
}
var_export($times);

On my machine (running PHP 5.6.4), running this script produces the following output:

array (
  'strncmp' => 
  array (
    'abc' => 0.76744794845581055,
    'xyz' => 0.73814797401428223,
    123 => 0.74603605270385742,
  ),
  'strpos' => 
  array (
    'abc' => 0.6839301586151123,
    'xyz' => 0.68808603286743164,
    123 => 0.67514586448669434,
  ),
)

Related Objects

Mentioned Here: T2312: Modifying PHP

Event Timeline

joshuaspence created this task.Aug 5 2015, 3:42 AM

joshuaspence raised the priority of this task from to Needs Triage.

joshuaspence updated the task description. (Show Details)

joshuaspence added a project: Lint.

joshuaspence added a subscriber: joshuaspence.

Try with a 10MB haystack.

Interesting... okay, thanks for clarifying.

array (
  'strncmp' => 
  array (
    'abc' => 0.0013141632080078125,
    'xyz' => 0.0013310909271240234,
    123 => 0.0013611316680908203,
  ),
  'strpos' => 
  array (
    'abc' => 0.58029699325561523,
    'xyz' => 48.226685047149658,
    123 => 0.54850196838378906,
  ),
)

Yeah, basically strncmp has worst-case runtime O(length(needle)) while strpos has worst-case runtime O(length(haystack) * length(needle)).

(The Boyer-Moore algorithm or some variant of it can improve this, but I don't think PHP ever uses it.)

In the common case, both lengths are small and runtime is dominated by overhead, so both calls have similar performance. Specifically, I'd guess the difference in the short string case is measuring the cost of passing a third parameter to strncmp(), which is minuscule but measurable.

In the worst case, where the haystack is aaa...aaa and huge (say, 128MB), and the needle is aaa...aaab and very large but not quite as large (say, 4MB), strpos() has much worse runtime.

This bad case is technically reachable -- at least partly -- in most checks, because the haystack is usually user-controlled (a URL, or chat message, or comment, or whatever). The needle is more rarely user-controlled, but even with a short needle the runtime can be much worse against a large haystack.

The lint message recommends strncmp() because it has similar average-case behavior to strpos() but much better worst-case behavior, and the worst case is often reachable, either by accident with large inputs or by malicious users crafting large inputs.

There are some cases where the minuscule difference in call overhead could show up on a profile, and strpos() might appear faster for real data than strncmp(), but I've never encountered a case like this where it isn't better to be more aggressive about removing the call overhead. Testing with isset() and comparing individual indexes has lower overhead than calling either function. For example, we do this in phutil_tag():

if (isset($href[0])) {
  $is_anchor_href = ($href[0] == '#');

  $is_domain_href = ($href[0] == '/') &&
                    (!isset($href[1]) || $href[1] != '/');

This is testing for # and / prefixes, and was faster than calling strpos() or strncmp() when profiled. I think this is the only place in the codebase where I've optimized away calls to these functions. Another approach in cases like this could be to port the whole method implementation to an extension; see T2312.

Re-evaluate "slowness" linter ruleClosed, ResolvedPublicActions

Description

Related Objects

Event Timeline

Re-evaluate "slowness" linter rule
Closed, ResolvedPublic
Actions