Why does switch(true) have a smaller NPath complexity than if() elseif()?

Question

I have this function that is responsible for converting a file's name and mime-type into something more "human" (e.g. file.png, image/png to [Image, PNG]). What I found interesting was that groups of if() elseif() statements had a higher NPath complexity than a switch(true) statement.

With the following code, PHP Mess Detector outputs an NPath of 4410:

public function humanKind()
{
    $typeRA = explode("/", strtolower($this->type));
    $fileRA = explode(".", $this->name);
    $fileType = strtoupper($fileRA[count($fileRA) - 1]);

    switch($typeRA[0]) {
        case "image":
            $humanType = "Image";
            break;
        case "video":
            $humanType = "Video";
            break;
        case "audio":
            $humanType = "Sound";
            break;
        case "font":
            $humanType = "Font";
            break;
        default:
            $humanType = "File";
    }

    switch ($this->type) {
        case "application/msword":
        case "application/pdf":
        case "applicaiton/wordperfect":
        case "text/plain":
        case "text/rtf":
        case "image/vnd.photoshop":
        case "image/psd":
        case "image/vnd.adobe.photoshop":
        case "image/x-photoshop":
        case "application/xml":
        case "application/x-mspublisher":
        case "text/html":
        case "application/xhtml+xml":
        case "text/richtext":
        case "application/rtf":
        case "application/x-iwork-pages-sffpages":
        case "application/vnd.apple.pages":
            $humanType = "Document";
            break;
        case "application/vnd.ms-excel":
        case "application/vnd.openxmlformats-officedocument.spreadsheetml.sheet":
        case "application/x-iwork-numbers-sffnumbers":
        case "application/vnd.apple.numbers":
            $humanType = "Spreadsheet";
            break;
        case "application/vnd.ms-powerpoint":
        case "application/vnd.openxmlformats-officedocument.presentationml.presentation":
        case "application/vnd.openxmlformats-officedocument.presentationml.slideshow":
        case "application/x-iwork-keynote-sffkey":
        case "application/vnd.apple.keynote":
            $humanType = "Slideshow";
            break;
        case "application/zip":
        case "application/x-zip-compressed":
        case "application/x-compressed":
        case "application/x-compress":
        case "application/x-rar-compressed":
        case "applicaiton/x-7z-compressed":
        case "application/x-ace-compressed":
            $humanType = "Archive";
            break;
        case "text/x-vcard":
        case "text/x-ms-contact":
            $humanType = "Contact";
            break;
        case "text/x-php":
        case "application/x-dosexec":
        case "application/x-xpinstall":
        case "application/x-opera-extension":
        case "application/x-chrome-extension":
        case "application/x-perl":
        case "application/x-shockwave-flash":
        case "application/java-archive":
            $humanType = "Program";
            break;
        case "application/vnd.ms-fontobject":
        case "application/font-woff":
        case "application/x-font-truetype":
        case "application/x-font-opentype":
        case "application/x-font-ttf":
        case "application/font-sfnt":
            $humanType = "Font";
            break;
    }

    // Special Cases
    if ($humanType == "Archive" && $fileType == "APK") { // Android App
        $humanType = "App";
    } elseif ($humanType == "Archive" && $fileType == "XPS") {
        $humanType = "Document";
    } elseif ($this->type == "application/xml" && $fileType == "CONTACT") {
        $humanType = "Contact";
    } elseif ($this->type == "application/octet-stream" && $fileType == "JNT") {
        $humanType = "Document";
    }

    if (strlen($fileType) > 4) {
        $fileType = "";
    }

    return array($humanType, $fileType);

If we then replace the special cases if elseif with the below:

    // Special Cases
    switch(true) {
        case ($humanType == "Archive" && $fileType == "APK"): // Android App
            $humanType = "App";
            break;
        case ($humanType == "Archive" && $fileType == "XPS"):
            $humanType = "Document";
            break;
        case ($this->type == "application/xml" && $fileType == "CONTACT"):
            $humanType = "Contact";
            break;
        case ($this->type == "application/octet-stream" && $fileType == "JNT"):
            $humanType = "Document";
            break;
    }

PHP Mess Detector reports an NPath Complexity of 1960.

Why is this? What makes switch(true) less complex than what appears to me to be just about the same control structure?

Devoice

Neat question. You might find a quick answer by hopping on the IRC channel for PHPMD. – Hydroxy

@Hydroxy Actually, the IRC channel for PHP Depend will be a more-likely candidate; PHPMD is an interface wrapped on-top of PHP Depend, the latter actually containing the NPathComplexity metric calculations (which can be found here) – Justle

Please post the answer to this if you get one. – Kendrakendrah

@Kendrakendrah I plan on it. I'm really interested in the science behind it (provided it's not a bug). – Devoice

Just a quick question, can you try with if ($x = (/*first_cond*/)) {xxx;} if ($x = ($x || /* second_cond */)) {...} as I would assume it is more likely to be desugared like this instead of an if/else (if it is desugared) ($x || being there if there is no break; in the previous case statement) – Kendrakendrah

You should not rely on so called optinisation tools . You should read what the tool's results are, but for better results you should make your own judgement . Read about the PHP core files and about the compiler if you really need a very fine grained optimisation . Generraly it all falls on the compilers . In my opinion @Kovo gave you the right answere. PHP is a high level programming language and you should think twice if you really want to use it for fine grained optimisation or for it's ease of maintaining your code . PHPMD is weak/irelevant tool in my opinion . – Polynices

Answer 1

Since NPath complexity measures the number of unit tests required to get complete coverage of your code there should be no difference between your 2 "Special Cases" implementations.

But there is some difference in the calculation. Let's step through the 2 "Special Cases" implementations and calculate the NPath Complexity manually:

NPath Complexity with if .. elseif ..

if ($humanType == "Archive" && $fileType == "APK") { // Android App
    $humanType = "App";
} 
elseif ($humanType == "Archive" && $fileType == "XPS") {
    $humanType = "Document";
} 
elseif ($this->type == "application/xml" && $fileType == "CONTACT") {
    $humanType = "Contact";
} 
elseif ($this->type == "application/octet-stream" && $fileType == "JNT") {
    $humanType = "Document";
}

This statement results in NPath Complexity of 9: 1 point for if .. else, 1 point for every if(expr) and 1 point for every && operator. (1 + 4 + 4 = 9)

NPath Complexity with switch(true)

switch(true) {
    case ($humanType == "Archive" && $fileType == "APK"): // Android App
        $humanType = "App";
        break;
    case ($humanType == "Archive" && $fileType == "XPS"):
        $humanType = "Document";
        break;
    case ($this->type == "application/xml" && $fileType == "CONTACT"):
        $humanType = "Contact";
        break;
    case ($this->type == "application/octet-stream" && $fileType == "JNT"):
        $humanType = "Document";
        break;
}

And this statement results in NPath Complexity of only 4: 0 points for switch(true) because it contains no && or || operators and 1 point for every case label. (0 + 4 = 4)

NPath Complexity of your humanKind function

NPath values are calculated for each statement and than the values are multiplied. The NPath Complexity of your function without the "Special Cases" statement is 490. Multiplied with the NPath value for the if .. else if .. statement of 9 you get a NPath Complexity of 4410. And multiplied with the NPath value for the switch(true) statement of 4 you get a complexity of only 1960. That's all!

And now we know: NPath Complexity does not measure expression complexity of case labels in switch statements!

Olin

Thank you sir! I honestly didn't know if it was a bug in calculation (which it appears to be) or if it made it less complex (since I wasn't 100% on what NPath Complexity is) but you've enlightened me. – Devoice

Answer 2

In general, switch can be faster than if/elseif due to the fact that switch statements evaluate the condition once, and then compare to each case.

It is my understanding that cases in a switch statement are internally indexed, and thus you may be getting better performance because of it (though I cannot find the original article talking about this, thus I cannot prove it).

I would also imagine the AST for a switch statement to be far simpler than the equivalent if/elseif one.

Edit:

In C based languages (and most likely others), switch statements get implemented as lists/hash tables when they become longer than 4-5 cases. This means access times for each item become the same. Whereas in an if/elseif block, there is no such optimization.

The compiler has an easier time dealing with these kinds of switch statements since it can make more assumptions about the different conditions. Thus, less complexity. Look-ups of an arbitrary case are O(1). Which again links into my previous statement of how the AST of a switch is most likely far simpler.

Edit #2:

In more CS lingo, compilers can use branch tables (or jumping) to reduce cpu time for switch statements: http://en.wikipedia.org/wiki/Branch_table

Wilding

All sounds like conjecture – Masturbate

I'm with @Masturbate -- it sounds like conjecture and I'd really like a well rooted reason as to why (computer sciency). Is this the wrong Exchange for that? – Devoice

@Devoice Edited the response a bit. Hope that helps. – Wilding

The hash table optimisation does not apply to switch(true). Remember that usually a switch statement has logic in the switch, and constants in the cases (therefore a hash table or list can be built at compile-time, speeding up runtime). For switch true, this is not the case, and it devolves into if/else if anyway. You don't even get the advantage of computing something only once (since what you compute once is "true". For what it's worth, I think the OP has found a bug. But I don't know enough about NPath complexity to say for sure. – Eigenvalue