Xdebug's code coverage functionality has had dead code analysis for years. It is used to be able to mark lines of as having executable code on it, as well as lines which can not be reached. In order to provide this functionality it runs an algorithm code after each file has been compiled. For each class and function it checks whether the algorithm to analyse executable lines and dead code has already been run, as it makes no sense to check it for the same class, method, or function twice.

Until PHP 7.4, Xdebug stored this information on whether it has seen a class with a special flag on the class entry of a class, PHP's internal structure that contains all the information the engine needs to be able to instantiate objects and run methods.

PHP 7.4 changes the values of these flags, which prompted me to ask Nikita whether it was actually safe to use a flag like this as a marker of whether Xdebug has already analysed that class (and its methods). He said no and suggested that instead I should use a hash table to store this information instead. I implemented that for Xdebug 2.8, that was released just before PHP 7.4 came out.

Soon after PHP 7.4 came out, I received a bug report that code coverage was now now significantly slower. A specific run went from 8 minutes to more than 3.5 hours. I tried this out for myself with the test suite of the Document package of Zeta Components, and indeed, with PHP 7.3 and Xdebug 2.7.2 it took about 2.83 minutes, and with PHP 7.3 and Xdebug 2.8.0 46 minutes — a slow down of about 16 times.

I quickly discovered that I had forgotten a ! in the code, which meant that the analyses would run for every class after a new file was loaded/compiled. I fixed that in Xdebug 2.8.1. This did improve the code coverage timings, but it still took 22.26 minutes, instead of the original 8 minutes.

I started talking to twitter user Anthony to try out a few more speed improvements, and although we were making improvements, I was not getting anywhere near the original timings of Xdebug 2.7. At this point I referred back to Nikita to ask whether he had a good idea to improve on this. He mentioned that classes and functions are always added to the end of the class/function tables, and that they are never removed either. He also hinted at a method to only loop over the newly added classes and functions after each PHP file was compiled: loop over the table backwards up to the point where the size of the list was the previous time that we looped. This resulted in a patch that did exactly that. Xdebug now longer needs the hash table mechanism to check whether we have analysed classes with their methods, and functions already, and also no longer loops over the whole list of classes after each file. As most people use one class per file, the algorithm went from O(n²) to O(n) approximately.

This cut down the time to run the test suite with code coverage for the Document package to 1.21 minutes. About 2½ times faster as Xdebug 2.7 and earlier. Anthony was also pleased and surprised:

Although I tend to make an Xdebug release only once a month, in this case I thought it warranted to expedite this. So here is your end-of-year present: Xdebug 2.9.

🔔 📣 ⛄ ❄️ 📣 🎄 🎇 🎆 🎃 🎄 ✨ 🎉 🎊