Did some more testing since the test was already in place. It appears that rendering a simple repeating view is O(n) in complexity:
Rendering 10000 components took 37ms Rendering 20000 components took 104ms Rendering 40000 components took 111ms Rendering 80000 components took 163ms Rendering 160000 components took 310ms This is measured after the components were added. Martijn On Sat, Sep 19, 2015 at 2:20 AM, Francois Meillet <[email protected]> wrote: > Suberb !!! > > Thanks a lot > François > > > > > > Le 18 sept. 2015 à 21:48, Martijn Dashorst <[email protected]> a > écrit : > >> 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 > -- Become a Wicket expert, learn from the best: http://wicketinaction.com
