Uploaded image for project: 'Wicket'
  1. Wicket
  2. WICKET-5983

O(n^2) complexity in MarkupContainer.add

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Closed
    • Minor
    • Resolution: Fixed
    • 1.5.13, 6.20.0, 7.0.0
    • 7.1.0
    • wicket
    • None

    Description

      MarkupContainer.add has O(n^2) complexity on the number of childs, because it searches through all other childs for a child with the same id. This may not be much of a problem in most situations, but in large tables, the performance can get very bad.

      Constructing a table with n rows, with 6 cells in each row takes (10k iterations) in Wicket 6.20.0 (Wicket 7 should be comparable, but WICKET-5981 kills perfomance badly):
      10 -> 132ms
      20 -> 245ms
      40 -> 465ms
      80 -> 1000ms
      160 -> 2444ms
      320 -> 6989ms
      640 -> 23201ms
      1280 -> 80784ms

      Attachments

        Activity

          People

            papegaaij Emond Papegaaij
            papegaaij Emond Papegaaij
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: