I'm working on a test case that can check for this, but it requires considerable memory due to the massive number of components added to make the test cases significant:
Adding 40000 components took 202ms Adding 10000 components took 10ms Adding 20000 components took 19ms Adding 40000 components took 34ms Adding 80000 components took 60ms Adding 160000 components took 119ms Adding 320000 components took 254ms Adding 640000 components took 602ms These numbers were generated running JUnit with -Xmx4g and -Xms4g. Running with default settings (iirc -Xmx256m) will make the results unreliable due to the garbage collector kicking in (1g is also not safe). Now we don't have too much control over our systems where the tests run, so the value might not be there. The algorithm's O(1) complexity after our changes is 'proven', so we can leave it at that. What do you think? Martijn On Fri, Sep 18, 2015 at 8:21 PM, Martijn Dashorst <[email protected]> wrote: > You can find the commit(s) here: > > https://github.com/apache/wicket/compare/WICKET-5981 > > Martijn > > > On Fri, Sep 18, 2015 at 3:04 PM, Emond Papegaaij > <[email protected]> wrote: >> Hi all, >> >> Martijn and I spent some more time measuring Wicket's performance, mostly in >> component tree construction. It turned out that code written bij Johan, back >> in the Wicket 1.2 time, causes O(n^2) complexity on the number children of a >> MarkupContainer. We've rewritten the entire children storage, using a >> LinkedHashMap when the number of children exceeds 24 (this number was found >> after some test trials). For smaller sizes, a simple ArrayList is used, which >> is more memory efficient. >> >> The new code now has almost O(1) on adding/removing/get-by-id but O(n) on get >> by index. MarkupContainer.swap also is O(n). >> >> Can someone take a look at the new code? MarkupContainer is a rather >> important >> class and if we want to put this in 7.1, it'd better be bug-free :) >> >> Best regards, >> Martijn and Emond > > > > -- > Become a Wicket expert, learn from the best: http://wicketinaction.com -- Become a Wicket expert, learn from the best: http://wicketinaction.com
