[wildfly-dev] SimpleRoleGroup#roles

[Philippe Marschall]

Hi

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 
OptionsRoleMappingProvider.
All of these would change the serialized form. If it is important to 
support reading old instances that could be added as well.

Cheers
Philippe
-------------- next part --------------
A non-text attachment was scrubbed...
Name: SimpleRole-equals.png
Type: image/png
Size: 61538 bytes
Desc: not available
Url : http://lists.jboss.org/pipermail/wildfly-dev/attachments/20150608/eeea02d8/attachment-0001.png