[WICKET-5983] O(n^2) complexity in MarkupContainer.add

• Type: Bug
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 1.5.13, 6.20.0, 7.0.0
• Fix Version/s: 7.1.0
• Component/s: wicket
• Assignee: Emond Papegaaij
• Reporter: Emond Papegaaij
• Created: 18/Sep/15 12:07
• Updated: 28/Oct/15 07:07
• Resolved: 21/Sep/15 12:29

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