I’m aware this may no technically be the right list to discuss this but
this list is impacted by this and fairly active.
During load testing of our application we found a case we spend 10% of
your CPU time in SimpleRole#equals (see attachment). This is because
SimpleRoleGroup uses an ArrayList to maintain a unique set of roles. As
a result it has to call ArrayList#contains a lot, which is itself O(n).
In fact because that’s done when iterating over all the roles it becomes
O(n^2). In our case our principals can have up to 200 roles. I don’t
know if this is exceptionally many or a common case.
We would like to work on a patch but we need your guidance. There are
several possible solutions and it all comes down to whether we can
change the List in the RoleGroup interface to a Collection. All the
users we searched for in WildFly only used the return value for
iterating over, nobody used the index. In fact they all used it an a
for-each loop so the change would even be source compatible but
unfortunately not binary compatible. If we can change the interface then
we can just change the ArrayList in SimpleRoleGroup to a HashSet and be
done with it. If the order is important the we can either use a TreeSet
or a LinkedHashSet.
If changing the RoleGroup interface is not possible then there are two
other possibilities. The first is only internally using a Set but in
getRoles perform a copy. This would produce more garbage. The second
option would be a having a Set and List (to avoid having to do copies)
in SimpleRoleGroup. This would avoid having to do a copy and the Set can
be used for contains checks. Only removeRole would still be O(n) due to
the scan over ArrayList. The only user we found was
All of these would change the serialized form. If it is important to
support reading old instances that could be added as well.