Opened 4 years ago

Closed 3 years ago

Last modified 3 months ago

#10853 closed enhancement (fixed)

improve get_page_hierarchy

Reported by: hailin Owned by:
Priority: normal Milestone: 3.0
Component: Performance Version: 2.8.4
Severity: normal Keywords: needs-unit-tests
Cc: m@…, mike@…

Description

current get_page_hierarchy has O(N*N) complexity.
It is super slow when N is a few thousands.

We should improve this to O(N) using techniques similar to #10852.

Attachments (1)

10853_page_hier.diff​ (1.9 KB) - added by hailin 4 years ago.
patch

Download all attachments as: .zip

Change History (10)

hailin — 4 years ago

patch

comment:1   hailin — 4 years ago

unit tested and verified.
The time improvement is about 500%, even with a small dataset.

comment:2 follow-up: ↓ 5   hailin — 4 years ago

We should not allow O(N*N) complexity in any of WordPress functions :-)
O(N) is what makes Google fast!

comment:3   azaozz — 4 years ago

  • Resolution set to fixed
  • Status changed from new to closed

(In [11976]) Improve get_page_hierarchy, props hailin, fixes #10853

comment:4   azaozz — 4 years ago

  • Component changed from General to Performance
  • Milestone changed from 2.8.5 to 2.9
  • Version set to 2.8.4

comment:5 in reply to: ↑ 2   westi — 4 years ago

  • Keywords needs-unit-tests added
  • Resolution fixed deleted
  • Status changed from closed to reopened

Replying to hailin:

We should not allow O(N*N) complexity in any of WordPress functions :-)
O(N) is what makes Google fast!

Cool. Could we get these test written up as a patch for WordPress tests so we have performance and functionality tests for this code available?

comment:6   ryan — 4 years ago

  • Milestone changed from 2.9 to 3.0

comment:7   mattrude — 3 years ago

  • Cc m@… added

comment:8   hakre — 3 years ago

  • Resolution set to fixed
  • Status changed from reopened to closed

Please create a new ticket instead of re-using this fixed one. New ticket is: #11633

Reference: (In [11976]) Improve get_page_hierarchy, props hailin, fixes #10853

comment:9   mbijon — 3 months ago

  • Cc mike@… added
Note: See TracTickets for help on using tickets.