Performance: optimize building theme registry by using get_defined_functions() instead of function_exists()

adding tag "Performance"

Btw, in the 80.000 calls to function_exists() there were around 40.000 different function names. Most of them occur only once, some around 16 times, and a few occur 150 times or so... just so you get an idea.

I think the function_exists is not a problem for itself (it is mostly just an array lookup), it's just the big number of loop iterations, each with some string operations + the call to function_exists.

Hm.. sorry, but aren't we just rebuilding the registry in this function? Looking into the DB seems like the wrong thing..

I duplicated myself, see #584024: speed up _theme_process_registry(): get_defined_functions() instead of function_exists().

Attached is a reworked version of some code I already posted in the above issue.
All it does is analyze a list of function names, either be obtained via get_defined_functions() or specified as an argument, for the hooks these functions could possibly implement.

The mechanism does not care if a hook 'exists'. Instead, it preemptively collects everything that could be a hook implementation, waiting for the day when some module decides to use it as such.

The attached functions do not care where the array of hooks is cached (DB and/or static variable) - this needs additional code.

The returned array is keyed like this:

$hook_implementations[$hook][$suffix][$module] = $function;

where $suffix can be an empty string.

The idea of the $suffix is that you can find things like '_preprocess_' or '_alter_', or themename_views_view_field__suffix.

The site I tested this with has a lot of modules installed, including views and ubercart. On my localhost, the full scan was around 50ms, the scan for '_preprocess_' was around 20ms (measured with PHP microtime, not xdebug).

This can result in a huge improvement for things like '_theme_process_registry'.
For normal page requests it has to be evaluated if it's any faster to cache the stuff in the database between requests.

Some interesting issues to look into:
#497118: Remove the registry (for functions)
#221964: Registry (don't post there, the registry idea has been canceled!!)
#557542: Cache module_implements()

And another one, that would play nicely with the above ideas.
#569646: New hook that is called whenever a hook implementation is added, removed or modified.

I don't want the discussion to split up in different places, so I add some thoughts from
http://drupal.org/node/221964#comment-2082326

One problem to think about:
- module 'x' has a hook implementation 'x_y()' in 'x.inc'
- the module decides at runtime if 'x.inc' should be included or not, to dynamically include or exclude it from calls to hook_y().

This is hard to do with a cached list of hook implementations. I don't know if such modules exist in D6, but theoretically they can.

Yes, there are modules that do this. Web Links, for example checks for the presence of at least 3 other modules to decide whether or not to include those hook files.

What we would need from a module is a list of possible function names from include files that should be considered as hook implementations, and/or a list of files to include before doing the get_defined_functions. The most robust would be doing it in the module's *.info file.

; files other than *.module that contain hook implementations,
; and that are not included by default in *.module
hook_includes[] = includefile.inc
hook_includes[] = includefile2.inc

; hook implementations that are neither in *.module,
; nor in any of the files listed in hook_includes,
; nor in any of the files included by default in *.module
hook_functions[] = modulename_hook1
hook_functions[] = modulename_hook2

This would only be necessary for those rare modules where hook includes depend on a dynamic condition. But it is still an API change, which could kill this idea :(

I think for Web Links it would not even be necessary, because the condition (other modules exists or not) is rather static. The hook cache is rebuilt every time you enable/disable a module.

Let's keep this separate
- Lazy loading is about file inclusion. This went in, Crell says.
- Registry is a memory of hook implementations. This idea was rejected, afaik.

So, what does that mean for hook implementation scanning? Do we scan for individual hooks, or do we scan for everything at once? Do we scan with every request, or do we scan only occasionally, when a registry has to be rebuilt?

In any case, there will be some scanning going on, at some point!
If we scan for more than just one hook, or if we have some fancy prefix / suffix combinations, then a get_defined_functions() based algorithm can be the superior solution. If we only scan individual hooks, it will be better to use good old function_exists().
For any scanning, be it by function_exists or get_defined_functions, we have to include all relevant files before doing so, be that by lazy loading rules or just assuming that all files containing hook implementations are loaded by default.

Incidentally, there is already a function that uses get_defined_functions(): drupal_find_theme_functions(). However, this function does not iterate on the list of functions, but rather on the list of hooks, and then does a preg_grep on the list of functions in each iteration. This kind of kills the purpose of my proposal, but maybe it's still fast enough thanks to the hard-wired preg_grep - I dunno.

My proposal:
- Find out if we really ever want to scan all module hook implementations at once, or if there are special module hook or callbacks prefix / suffix patterns where iterating on get_defined_functions() would be faster than iterating on the theoretically possible prefix combinations.
- If _theme_process_registry() is really all that remains, we could instead reopen #584024: speed up _theme_process_registry(): get_defined_functions() instead of function_exists(), or rename this issue to something related to theme_get_registry().

I think it does make a lot of sense to keep at least one of the issues open at least for theme registry rebuilding.

Saying it another way:
- If we have a global DB registry for all functions (which, as I understood, we do not), then we can or should use get_defined_functions() to build that global registry, and possibly use that global registry to rebuild the theme registry (but not sure if we need to).
- If we don't have a global registry, we can / should use get_defined_functions() approach for rebuilding the theme registry, instead of guessing for all possible implementation names.

Having a look at drupal_find_theme_functions(), I had a new idea.

<?php
$functions = get_defined_functions();
$matches = preg_grep('/_preprocess_/', $functions['user']));
?>

Result: 3884 functions, 46 hits, around 4 milliseconds for the entire scan.
Why even bother with theme registry?

EDIT:
As a comparison, module_implements('some_random_string') needs around 0.4 ms on my localhost. So it's still 10x faster than me for scanning an individual hook.

@Crell,
I would love to do that, but, as things tend to be, my time is limited.
Or otherwise, you need to wait.
Writing a patch would mean I have to get more familiar with D7, and really dig into the code and all possible side effects. And not only that, I also need to keep up to date with ongoing work on D7.

Usually when I encounter a bug or performance problem, I want to find out why, and let the community know about it. I always hope that my explanations are good enough for someone to pick up the matter and turn it into a patch. I wrote a few patches myself (such as one for imagecache rounded corners), but, doing that for all my proposals is not realistic at the moment.

Still, I think that the explanations I wrote are better than just saying "Page X in Drupal loads far too slow. Make it faster." If you need further info, ask. Or otherwise, as said, you need to wait.

Well, actually, I did already start writing a patch (D6), after your post, but I am too busy to finish that soon.
If that is any helpful for you, my approach was to cache the function candidates returned by preg_grep in a static array in _theme_process_registry, indexed by hook name, and containing only candidates for existing modules. With this information, in case $type == 'module', we no longer need to iterate on foreach ($prefixes), but can instead look directly into the cached matches for each possible suffix.
The trick is, that after the preg_grep(), we have a really small and nice array to work with, and the sub-arrays (for one hook) are even smaller.

Does this help?

DISCLAIMER:
The only situation where I would see a problem with this is if some implementations of hook_theme include further files. Functions in these files will not be found in the initial get_defined_functions(). I think for D7 this should not be a problem, if module developers are aware of this. And even with the current implementation in D6, I would not recommend any module developer to rely on file inclusions in hook_theme, as very much would depend on the sequence of modules being processed in _theme_build_registry. Would be a very fragile thing to do.

EDIT:
And for the expected performance benefit, you can profile _theme_build_registry with xdebug. Theoretically, the patch would divide that result by the number of modules (well, almost).

True, it's not relevant for everyday surfing performance.

But, bottlenecks like this can slow down development (if you have "rebuild theme registry on every page" enabled), and they can make administration tasks impossible on some shared hosting providers with restrictions on memory limit, or page execution time (maybe not this one in particular, but some other things that are not directly relevant to visitors).

Similar issues are the slow menu rebuilding (slowing down CCK content type management and other things), directory scanning (every time you open the modules page, drupal will scan the modules folder for *.info files), and maybe other things. Remember how many people complained about the slow modules page!

None of these three things needs to be that slow because of task complexity - they simply use poor algorithms. And in case of theme_build_registry it wouldn't be so difficult to improve, for someone who is familiar enough with D7.

Here's a D7 patch for _theme_process_registry().
My D7 install is currently not working, which means I can't test. I'm not surprised if it breaks.
I might upload a tested patch later, but at least you can now see what I imagine.

What it does:
- On first call of the _theme_process_registry, an array of phase function candidates is built using get_defined_functions(), preg_grep() and explode().
- The $prefixes array construction is moved out of the foreach loops, to avoid it from being called more often than needed.
- The innermost foreach($prefixes) loop is replaced by a loop on the candidates from get_defined_functions. This is where I expect a major performance improvement in the average case.

Tell that to the guys who made Tortoise CVS.
Doing it manually now, I hope it works.
Next time I'll do it with git.

..

Could be line endings.

Resolved PHP syntax errors.
Still don't have D7 working.

A quick update:

• Made a new version that produces almost the same theme registry as the original one, except for the order of process and preprocess functions. I don't post it yet, because I'm not finished with testing.
• One tricky thing and possible show stopper is files being included in the hook_theme calls. Functions in these files are not found in the initial get_defined_functions(). In those examples that I found the functions all started with "template_", which can be easily checked for with function_exists() without losing performance (theoretically). Of course, this is not a universal solution.
• Performance for a normal D7 install is disappointing. It's around 2x slower than the old mechanism. With more modules installed, it is around the same speed. I tried installing more modules to see if that makes a difference, but now my D7 is broken again - no surprise, with most of the D7 contrib modules being only development snapshots. Very annoying: The poor error reporting. Some try{} and catch{} on module install would be very appreciated.

The following custom module code can show a performance advantage for the new old algorithm:

<?php
function themetest_theme() {
  $hooks = array();
  for ($i=0; $i<10000; ++$i) {
    $hooks["themetest_$i"] = array(
      'render element' => 'elements',
      'template' => 'themetest-x',
    );
  }
  return $hooks;
}
?>

My benchmarks showed
3.308296918869 seconds for the old algorithm
0.7493200302124 seconds for the new algorithm

Modules installed: Basic modules shipped with D7, plus the custom themetest module.

The above example is very theoretical, and the result is still not as impressive as I hoped for.
I will continue and see where I can get.

@Fabianx, @joelpittet

The biggest problem is that newly added functions need to be processed, so a static won't work, see Approach B of the 85% faster issue, where I explored that same scheme ...

The problem could be avoided if we split up the "parent" function, _theme_build_registry(): First invoke all hook_theme() implementations, and only then discover the preprocess and friends.

I think we can assume that contrib does not call _theme_process_registry(), since it is "private". Or not?
Otherwise, we could simply keep _theme_process_registry() for BC, but never call it from _theme_build_registry().

Btw, it seems that get_defined_functions() always prepends new functions to the end of the list. I wonder if this is reliable?

he problem could be avoided if we split up the "parent" function, _theme_build_registry(): First invoke all hook_theme() implementations, and only then discover the preprocess and friends.

Or maybe just do this for the part that deals with modules.

Here are some functions that might prove useful (D7):
https://gist.github.com/donquixote/bbd7003a3b31689a536d

They group the known functions (from get_defined_functions()) by suffix and prefix. E.g.

$grouped['preprocess_page']['template'] === 'template_preprocess_page';

There are basically two variants:
1. Analyze based on positions of '_'.
2. Analyze based on a known list of prefixes (module names, theme names, etc).

The first variant obviously results in more false positives.
E.g.

$grouped['clear_opcode_cache']['drupal'] = 'drupal_clear_opcode_cache';
$grouped['opcode_cache']['drupal_clear'] = 'drupal_clear_opcode_cache';
$grouped['cache']['drupal_clear_opcode'] = 'drupal_clear_opcode_cache';

With the known list of prefixes, this function would be totally skipped.

Both variations can handle newly defined functions appearing later in the request, when new files were included.

Benchmarks so far:
Based on known prefixes: ~19ms on first hit.
Based on arbitrary '_' position: ~67ms on first hit.

In theory, any subsequent call should be:
- not much more than get_defined_functions() (~1.3ms), if no new functions were added.
- a bit more, if new functions were added by file inclusion.

However, I currently get unexpected random durations between 3ms and 12ms for such subsequent hits, no matter if new functions were added or not. I currently have no explanation for this.

But I think it is ok if we avoid calling it too often.

-------

Maybe this could become a 3rd party library.
We could get rid of the static variables, and use objects instead.
This first attempt was mostly aimed at D7.

This patch really reduces the time for the process / preprocess discovery for implemented by modules.
The rest of _theme_build_registry() is being refactored quite a lot too.. not sure if we want this.
Of course, there are still other bottlenecks in _theme_build_registry() which this patch does not fix.

The patch intends to preserve original behavior of D7 core. Even if this behavior could be seen as undesirable.
Exceptions below.

I used a drush command to detect changes in the registry. I am attaching the drush command file.
E.g.:
- Install the drush command globally.
- Assume the web root is in ./htdocs.
- Create a folder ./themereg as a sibling of ./htdocs
- In ./htdocs, run drush cc all; drush theme-get-registry > ../themereg/theme_get_registry.php
- In ./themereg, run git init; git add .; git commit -m"Initial commit."
- Apply the patch.
- Run drush cc all; drush theme-get-registry > ../themereg/theme_get_registry.php; cd ../themereg; git diff HEAD; cd ../htdocs
- Do local modifications in ./htdocs, then repeat the previous command.

On quite a complex site, the only changes to the registry I found were "good ones". Stuff that looked wrong before.

E.g.

     'preprocess functions' => 
     array (
-      0 => 'template_preprocess_bootstrap_grid_view',
-      1 => 'template_preprocess',
-      3 => 'global_filter_preprocess',
-      4 => 'contextual_preprocess',
+      0 => 'template_preprocess',
+      1 => 'template_preprocess_bootstrap_grid_view',
+      2 => 'global_filter_preprocess',
+      3 => 'contextual_preprocess',
     ),

or

     'preprocess functions' => 
     array (
       0 => 'template_preprocess',
-      1 => 'global_filter_preprocess',
-      2 => 'contextual_preprocess',
-      4 => 'template_preprocess_date_views_filter_form',
+      1 => 'template_preprocess_date_views_filter_form',
+      2 => 'global_filter_preprocess',
+      3 => 'contextual_preprocess',
     ),

I would argue that the old order in these cases was wrong, and the new order is better.