Uploaded image for project: 'Jenkins'
  1. Jenkins
  2. JENKINS-75200

Quadratic algorithm in SecureGroovyScript.cleanUpGlobalClassValue - repeated remove from array

      The following code seems to have O(n²) complexity:

      SecureGroovyScript.java#L237

              List<Class<?>> toRemove = new ArrayList<>(); // not sure if it is safe against ConcurrentModificationException or not
      ...
              Iterator<Class<?>> it = toRemove.iterator();
              while (it.hasNext()) {
                  Class<?> klazz = it.next();
                  ClassLoader encounteredLoader = klazz.getClassLoader();
                  if (encounteredLoader != loader) {
                      it.remove();
                      if (LOGGER.isLoggable(Level.FINEST)) {
                        LOGGER.log(Level.FINEST, "ignoring {0} with loader {1}", new Object[] {klazz, /* do not hold from LogRecord */String.valueOf(encounteredLoader)});
                      }
                  }
              }

      As toRemove is an array each it.remove() has to rewrite the whole array. It means that if there are many elements to remove the array will have to be rewritten many times, making it O(n²), with n - number of elements.

      We noticed that when our Jenkins with many scripted fields in many jobs was having performance problems and monitoring?part=threadsDump is reporting many threads running:

      org.jenkinsci.plugins.scriptsecurity.sandbox.groovy.SecureGroovyScript.cleanUpGlobalClassValue(SecureGroovyScript.java:241) 

      This is on script-security-1.71 but the code is unchanged in the latest version.


      I'd expect that the code to create a separate array with filtered-out values instead.

          [JENKINS-75200] Quadratic algorithm in SecureGroovyScript.cleanUpGlobalClassValue - repeated remove from array

          There are no comments yet on this issue.

            Unassigned Unassigned
            tometzky Tomasz
            Votes:
            3 Vote for this issue
            Watchers:
            4 Start watching this issue

              Created:
              Updated: