Improve speed of sorting

... because sometimes the arguments are objects.

Hm. That should definitely not be. In what case have you bumped into this?

Nice catch.

Curious. Does it make sense to explicitly specify the datatype of these function arguments now that we're not checking if they're arrays?

e.g. change:

 function element_sort($a, $b) {

to:

 function element_sort(array $a, array $b) {

?

According to my testing it doens't make a difference - here are my results (test script is attached):

Test 1: 33.6663048267
Test 2: 17.7335600853
Test 3: 17.4855830669

Also attached is a patch which adds the array parameters

woah i have no idea what happened here:

@@ -5941,7 +5941,7 @@ function drupal_write_record($table, &$o
   }
 
   // Convert to an object if needed.
-  if (is_array($object)) {
+  if ($arrayName = array('' => , );array($object)) {
     $object = (object) $object;
     $array = TRUE;
   }

New patch should work.

#12: 872680.patch queued for re-testing.

Removing those array checks is a good idea if they aren't needed. Internally they result in multiple function calls > 4, none expensive by themselves but they add up quickly.

Subscribing, unlikely to be able to look at this until next week though due to travelling.

Related: #639974: Speed up element_children() using array_multisort()

#22: 872680.diff queued for re-testing.

#22: 872680.diff queued for re-testing.

WTF does this patch have to do with simpletest getting enabled. bot is on some extended bender i think.

#22: 872680.diff queued for re-testing.

Well, bender or not, we can't put this in if it breaks testbot. Maybe ping boombatower, DamZ, or rfay and see if they can take a look.

This patch does fail (at least on PHP 5.3). At the end of the installation, I get:

Recoverable fatal error: Argument 1 passed to element_sort() must be an array, string given in element_sort() (line 5743 of /var/lib/drupaltestbot/sites/default/files/checkout/includes/common.inc).

On mostly every page, including on the modules page. That prevents the test bot from enabling the testing module.

Frankly, I would rather fix those "properties used without #", which is basically a bug.

Last patch has lots of taxo changes. They are needed here?

Makes sense.

I just committed #839556: Fix isset regression in tablesort, add tests, and cleanup theme_process_registry() which might conflict with this patch. Asking for a re-test.

#43: 872680.diff queued for re-testing.

What's up with the testbot?

+++ includes/common.inc	25 Oct 2010 09:29:57 -0000
@@ -5741,8 +5741,9 @@ function drupal_render_cid_create($eleme
-  $a_weight = (is_array($a) && isset($a['#weight'])) ? $a['#weight'] : 0;
...
+  $a_weight = isset($a['#weight']) ? $a['#weight'] : 0;

What happened to the regression that

isset($a['#weight'])

is TRUE, if $a is a string?

Powered by Dreditor.

I skimmed the issue, but I don't see benchmarks, which prove that casting everything to an array is faster than is_array() - which would be a surprise to me. Sorry if I missed it.

Actually, I found some inconsistencies in common.inc.

First, element_sort() and drupal_sort_weight() are duplicate functions.
The same form element_sort_title() and drupal_sort_title().

I did a really faster implementation of element_sort(), and merged all the duplicates functions.

I also did a lot of benchmarking (using xdebug, the best tool I think for) and it tells that element_children() is really a bottleneck for performances.

I did all this on my side, I did not known this issue exits.

See my patch for faster element_sort() implementation and functions merge (working on rc2 version actually).

EDIT: Sorry I did not do a patch using CVS because I had not a CVS on my box while doing this, I may redo it later if you really need to, thus this is not hard to read and merge there are really a few lines.

Now that I read the full thread, I have some notes:

• #8 no you shouldn't specify datatypes, because the function signature is already given by the PHP function uasort() and must accept anything. You should respect the given API.
• #9 These tests may be irrevelant, because CLI and HTTPd execution context are really not the same. I think that only a profiler comparaison using percentage of execution time between executions could tell you if it's a benefit or not. This remains a good idea to do this test because it will show you true if there is a really big difference.
• #61 On my environment it was actually something almost 10% performance gain on some pages, using my patch.
• @all You should look at the uasort() callback signature, nowhere it's said that you have to return 0, -1, or 1, using two int cast and a substraction should be more efficient than doing five or six if() comparisons.

Here is an even faster implementation for weight sorting:

function drupal_sort_weight($a, $b) {
  $a_weight = isset($a['#weight']) ? (int) $a['#weight'] : 0;
  $b_weight = isset($b['#weight']) ? (int) $b['#weight'] : 0;
  return $a_weight - $b_weight;
}

This method does less tests than the previous. whatever is the type of $a, whatever the isset() returns true or not, the int cast will filter inconsistent types and return 0.
Then, this function, in best case, will do 2 if(isset()) and a int sub, in worst case will do 2 if(isset()), 2 int cast, and one int sub, without errors (untested on php 5.3, please tell me), which is quite fast.

I did some CLI tests, see attached file, it gave absolutely no errors on PHP 5.2.14 with default error handling set (so all notice should normally appear on the ouptut).

EDIT: This may not be revelant, but on let's say about 10 hits on my dev box on the same page (just displayying 10 nodes, no blocks), with RC2 implementation it gaves me PHP generation time scores between 550 and 700ms, with my patch it gaves me scores between 470 and 630ms approximatively, removing the lowest and the hightest scores which can be considered as statistic accidents and should not be taken into account. This leads to approximatively between 15% to 10% performance gain for a really simple and small page.

#6 I would be pleased to know what tools did you use for benchmarking, I actually uses CLI scripts as a start, but then I already use xdebug profiles and kcachegrind time display to ensure my results, throught multiple hits, sometimes doing some statistics manually using dozens of hits on the same page. This is a method, but it's fastidious, any helper would be great to know.

Your test includes floats as weights, as I can remember weights are int, right? If not, my own patch can easily be fixed, either by casting as float (which then may be longer) either by not casting at all hoping the current form or elements array was not written by an idiot :) This should do the trick the revert to the original behavior. I think the second solution is better, developers will have notices or errors caused by their own code, which is kinda right here?

I didn't notice the slight difference between drupal_sort_weight and element_sort, this is my error here. If the difference is only a '#' char, then the same algorithm should be applied on both, and a strong comment should be added to both documentation functions to highlight that.

Whatever are the differences between all algorithmes, the fastest solution should be kept, even if the behavior changes slightly, it won't in most cases (usage of pure ints). Remember when you do your tests that elements array are all differents, and the results will vary among pages, so any kind of test should may be done over a random computed element array, I did that, see the code attached.

EDIT: Oh and I forgot, a test on only one page is not sufficient, it should be done on at least two very different profiles of page (a big form, a "normal" frontend page), with at least douzens of hit, using some average numbers as proof.

@dalin: Ok for comment edition.

I must admin, I'm playing with D7 since beta3, and on all my testing environments, it's a lot slower than D6, and doing a lot of profiling, it this seems to be architectural because there is major bottleneck I could spot. I really think that 500ms to build a page, where the exact same site took 100ms using D6 is not acceptable.

IMHO this kind of performance improvement can easily gain up to 50ms on my environment, this is I think really *huge* and it worth the shot.

If you don't want to apply on core, I would understand, this is a reasonable choice, but I admit that I'll really apply this patch on any D7 install I will made because I can't neglect 50ms per page hit.

If a proposed change is causing a performance increase so small that it requires benchmarking to that level of detail to prove, then your efforts are likely better spent elsewhere. Your proposed patch is clearly faster with just a few back-and-forths using a profiler on a few different URLs.

Not sure about that, what I meant is the real web environment has so much factors that can alter its behavior and speed, among all the layers a single page hit goes through that real benchmarking cannot be done in one hit, you'll always have many surprises if you stick to that, whatever the patch is.

Unfortunately it's not that simple. If you read back in this issue you'll see that we tried that approach very early on. But many places (even in core) do not properly use element arrays and so $a or $b may be a string instead of an array. See #951734 for more details.

So, you are telling me the real issue is that the core itself is buggy. If some code parts in core don't respect its own API, then it should be fixed, frozen or not. I'm an external developer, I tell you I can't rely on something I cannot trust.

Ok maybe my last comment was a little harsh, but that's the feeling it gaves me when I read something like this. I sincerely apologize for the reaction though.

This is not only a bug, but a good performance improvement, however I understand your opinion and know this is the core way to deal with these kind of issues at RC phase. I respect that. I will still maintain some patches of my own an use them because I really can't neglect those 50ms.

#62: 872680.diff queued for re-testing.

• API simplification (remove two functions): 4 files changed, 7 insertions(+), 49 deletions(-)
• Faster sorting for drupal_sort_weight()
• Removed element_sort() and replaced all occurrences by drupal_sort_weight()
• Removed element_sort_by_title() and replaced all occurrences by drupal_sort_title()

We still need some additional benchmarking and testing.

NR to see who thinks testbot.

+++ b/core/includes/common.inc
@@ -6188,45 +6188,6 @@ function drupal_render_cid_create($elements) {
-function element_sort($a, $b) {
-  $a_weight = (is_array($a) && isset($a['#weight'])) ? $a['#weight'] : 0;
...
-function element_sort_by_title($a, $b) {

@@ -6284,12 +6245,9 @@ function element_info_property($type, $property_name, $default = NULL) {
 function drupal_sort_weight($a, $b) {
-  $a_weight = (is_array($a) && isset($a['weight'])) ? $a['weight'] : 0;

The difference between element_ and drupal_ ua_sort() helper functions is that the former checks a '#property' and the latter checks 'property'.

The drupal_ helpers need to be retained separately, as they're used in many places (not only in core).

So, I understand that we can only apply performance improvements.

element_sort has moved to ArraySort::sortByWeightProperty(), and the code doesn't appear to have been much refactored in there, so this could still be an issue.

Created a new patch for D8.

This should fix a lot of the failed tests.

This is the right patch.

Re-uploading prior patch for the bots.

I really like this, but it still needs those benchmarks.

> only to discover that yes it is necessary because sometimes the arguments are objects.

Is this still true?

If so, it looks like the patch will change the sort order of objects -- previously they would have been sorted as it the value was '' and now the value of the $key property is used.