You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@wicket.apache.org by "Emond Papegaaij (JIRA)" <ji...@apache.org> on 2015/09/18 14:08:04 UTC
[jira] [Updated] (WICKET-5983) O(n^2) complexity in
MarkupContainer.add
[ https://issues.apache.org/jira/browse/WICKET-5983?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Emond Papegaaij updated WICKET-5983:
------------------------------------
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
was:
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 WIKCET-5981 kills perfomance badly):
10 -> 132ms
20 -> 245ms
40 -> 465ms
80 -> 1000ms
160 -> 2444ms
320 -> 6989ms
640 -> 23201ms
1280 -> 80784ms
> O(n^2) complexity in MarkupContainer.add
> ----------------------------------------
>
> Key: WICKET-5983
> URL: https://issues.apache.org/jira/browse/WICKET-5983
> Project: Wicket
> Issue Type: Bug
> Components: wicket
> Affects Versions: 1.5.13, 6.20.0, 7.0.0
> Reporter: Emond Papegaaij
> Assignee: Emond Papegaaij
> Priority: Minor
>
> 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
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)