Depending on the callback function for uasort(), array_multisort() may be faster.

With this patch the running time of element_children() is reduced by about 50% on an element with 10 children with all different #weights, and about 20% on an element with 10 children of which only one has a #weight specified. With 500 children with all different #weights, the running time is reduced with about 65%. If no child has a #weight specified, the running time is unchanged.

The $i++ / 1000 part is moved from form.inc and helps maintain the order of elements with equal weights. For some reason, adding this fraction actually reduces the running time of array_multisort().

This introduces a small BC break in that array_multisort() does not maintain index association for numeric keys, i.e. children added with $element[] = array(...) rather than $element['foo'] = array(...).

The times have been measured using PHP 5.2.6 on a pretty old/slow machine.

CommentFileSizeAuthor
#6 drupal-common.inc-639974-D6.patch951 bytesmikeytown2
#2 ksort-node-add-article.txt1.39 KBcasey
#2 multisort-node-add-article.txt1.39 KBcasey
#2 head-node-add-article.txt1.39 KBcasey
#2 ksort-frontpage.txt1.38 KBcasey
#2 multisort-frontpage.txt1.38 KBcasey
#2 head-frontpage.txt1.38 KBcasey
#2 element_children-ksort.patch2.73 KBcasey
#2 element_children-array-multisort.patch3.4 KBcasey
array-multisort-1.patch2.85 KBc960657

Comments

c960657’s picture

c960657 commented
Status: Active » Needs review
casey’s picture

casey commented
StatusFileSize
new element_children-array-multisort.patch3.4 KB
new element_children-ksort.patch2.73 KB
new head-frontpage.txt1.38 KB
new multisort-frontpage.txt1.38 KB
new ksort-frontpage.txt1.38 KB
new head-node-add-article.txt1.39 KB
new multisort-node-add-article.txt1.39 KB
new ksort-node-add-article.txt1.39 KB

Reroll.

I do however hardly get any difference when benchmarking. I also tried another approach, but not much either.

Benchmarks on frontpage were tested with 10 nodes on it.

dave reid’s picture

dave reid
he/him
Primary language English
Location Nebraska USA
commented

I'm doubtful of this as well...

Status: Needs review » Needs work

The last submitted patch, element_children-ksort.patch, failed testing.

c960657’s picture

c960657 commented

My measurements where made using microtime() (not Xdebug profiling) on the function itself. The idea is to save a few calls to is_array()/isset() — O(n) versus O(n × ln n). I guess sorting generally doesn't take much of the total page generation time, except in extreme conditions (large number of elements, n, in each array).

The idea of moving the $i++ / 1000 to element_children() still applies, though. Currently only forms preserve the original order. The following will output “BA AB” (and some non-visible markup):

function myform() {
  $form['a'] = array('#weight' => 1, '#markup' => 'A');
  $form['b'] = array('#weight' => 1, '#markup' => 'B');
  return $form;
}
print drupal_render(myform()) . ' ' . drupal_render(drupal_get_form('myform'));
mikeytown2’s picture

mikeytown2 commented
StatusFileSize
new drupal-common.inc-639974-D6.patch951 bytes

I see that element_children is a lot different between 6.x & 7.x; but this patch is along the similar goals - speed up element_children(); only its for 6.x. Using this you can knock off about hundred milliseconds from the page render time, if the page has a lot on it.

Let me know if this should go in a new issue or stay here.

catch’s picture

catch
he/him
Primary language English
commented

I profilied the node/add/article page with the original patch and ended up with more calls to is_array() with the patch than without (and no less calls to anything else). No overall difference in performance, 0.1% at most, this is from 120+ calls to element_children() on that page.

array_multisort() compared to uasort() is a lot cheaper looking at the profile data, but that only gets called 9 times on the node form, so no wonder it doesn't make much difference. If there's a better form to test on - maybe modules page or permissions? That might help to compare better.

c960657’s picture

c960657 commented

I profilied the node/add/article page with the original patch and ended up with more calls to is_array() with the patch than without (and no less calls to anything else).

I cannot reproduce that. With the patch I see a reduction in the number of calls to is_array() as well as to element_sort():

                         without    with    
  php::is_array            1583     1322
  php::function_exists      580      580
  php::array_key_exists     551      511
  drupal_static             518      518
  check_plain               491      491
  php::htmlspecialchars     491      491
  php::implode              457      457
  php::preg_replace         284      284
  php::array_keys           277      277
  php::count                237      237
  php::strtr                210      210
  element_children          198      198
  t                         182      182
  php::define               175      175
  element_sort              155        0
  module_load_all           147      147
  php::array_shift          147      147
  theme                     145      155
  drupal_sort_weight        144      144
  ...

The difference between O(n) and O(n × ln n only really gets visible for large values of n, i.e. when the array to be sorted contains a lot of elements, and probably only when the elements are not already almost sorted. I'm not sure where to find a good example in core - most forms are divided into separate fieldsets, and most lists are already sorted.

sun’s picture

sun
Primary language German
Location Karlsruhe
commented 
+++ includes/form.inc	22 Nov 2009 20:14:55 -0000
@@ -1110,22 +1110,19 @@ function form_builder($form_id, $element
     // Assign a decimal placeholder weight to preserve original array order.
-    if (!isset($element[$key]['#weight'])) {
-      $element[$key]['#weight'] = $count/1000;
-    }
-    else {
+    if (isset($element[$key]['#weight'])) {

This needs to stay here, because form elements may be expanded into sub-elements. Therefore, an element may have certain child elements already, but further children are added later in the process. Since the default order of array keys in PHP is derived from their definition order, removing this preemptive #weight will lead to wrongly ordered elements everywhere.

However, aside from that, this array_multisort() approach makes much more sense to me than the other element_sort() performance patch.

Powered by Dreditor.

gielfeldt’s picture

gielfeldt commented

subscribe

bfroehle’s picture

bfroehle commented

Please be aware that array_multisort can cause warnings if some child elements are not arrays -- see #972536-35: Object of class stdClass could not be converted to int in _menu_router_build() - line 3370 for a complete description.

DanPir’s picture

DanPir commented

subscribe

rjbrown99’s picture

rjbrown99 commented

Duplicate of #1345204: Optimize element_children()? There is another patch there for this same general concept.

mikeytown2’s picture

mikeytown2 commented

@rjbrown99
I split the D6 patch (#6) off from this thread as the functions are quite different in D6 vs D7. Similar goals, different code.

Status: Needs work » Closed (outdated)

Automatically closed because Drupal 7 security and bugfix support has ended as of 5 January 2025. If the issue verifiably applies to later versions, please reopen with details and update the version.