harmony-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Mark Hindess <mark.hind...@googlemail.com>
Subject Re: ArrayList usage (was: [classlib][luni]Collections classes - code reviews and optimisations)
Date Thu, 05 Aug 2010 23:02:04 GMT

There are surprisingly many examples of code which should probably
use better default ArrayList sizes to avoid inevitable copying and
code which could use simpler methods...

In java/io/File.java, there are two examples of default sized arraylists
when we have a suitable upper bound that we could/should use as the initial
size.

java/net/URLConnection.java the code in addRequestProperty:

    valuesList = new ArrayList<String>();
    valuesList.add(0, newValue);

could be:

    valuesList = new ArrayList<String>();
    valuesList.add(newValue);

to avoid the more expensive add at location method when adding to the
just-created empty list.

In java/net/InetAddress.java createHostNameFromIPAddress we know that
in the common cases the

            ArrayList<String> hexStrings = new ArrayList<String>();
            ArrayList<String> decStrings = new ArrayList<String>();

sizes will be 16 and 4 respectively.

Ditto for the (identical?) code in:

  org/apache/harmony/luni/util/Inet6Util.java

In org/apache/harmony/niochar/CharsetProviderImpl.java, ArrayListr
should default to charsets.length() in:

    public Iterator<Charset> charsets() {
        ArrayList<Charset> list = new ArrayList<Charset>();


And that was just a quick scan of luni code.

Regards,
 Mark.

In message <201008052232.o75MWcdA002843@d12av03.megacenter.de.ibm.com>,
Mark Hindess writes:
> 
> The discussion about ArrayList made me wonder about ArrayList usage.
> Perhaps we should review some of our own usage of ArrayList.
> 
> consider drlvm/vm/vmcore/src/kernel_classes/javasrc/java/lang/Class.java:
> 
>     public Class[] getClasses() {
>         checkMemberAccess(Member.PUBLIC);
>         Class<?> clss = this;
> !       ArrayList<Class<?>> classes = null;
>         while (clss != null) {
>             Class<?>[] declared = VMClassRegistry.getDeclaredClasses(clss);
>             if (declared.length != 0) {
> -               if (classes == null) {
> -                   classes = new ArrayList<Class<?>>();
> -               }
>                 for (Class<?> c : declared) {
>                     if (Modifier.isPublic(c.getModifiers())) {
>                         classes.add(c);
>                     }
>                 }
>             }
>             clss = clss.getSuperclass();
>         }
>         if (classes == null) {
>             return new Class[0];
>         } else {
> !           return classes.toArray(new Class[classes.size()]);
>         }
>     }
> 
> I have to wonder whether it might not be better to write:
> 
>     public Class[] getClasses() {
>         checkMemberAccess(Member.PUBLIC);
>         Class<?> clss = this;
> !       ArrayList<Class<?>> classes = new ArrayList<Class<?>>(0);
>         while (clss != null) {
>             Class<?>[] declared = VMClassRegistry.getDeclaredClasses(clss);
>             if (declared.length != 0) {
>                 for (Class<?> c : declared) {
>                     if (Modifier.isPublic(c.getModifiers())) {
>                         classes.add(c);
>                     }
>                 }
>             }
>             clss = clss.getSuperclass();
>         }
>         if (classes == null) {
>             return new Class[0];
>         } else {
> !           return (Class[]) classes.toArray();
>         }
>     }
> 
> That is:
> 
> 1. create an empty 0 size list rather than use null or perhaps create it
>    lazily as it is originally but create it with size declared.length to
>    avoid a possible copy if the number of public classes is > 10.
> 
> 2. avoid the complexity of the toArray with generics method (which might be
>    more beneficial if the contents array was being reused) and just use
>    a cast
> 
> As another more obvious example, consider
> drlvm/vm/vmcore/src/kernel_classes/javasrc/java/lang/ClassLoader.java:
> 
>         private static void initResourceFinder() {
>             synchronized (bootstrapPath) {
>                 if (resourceFinder != null) {
>                     return;
>                 }                
>                 // -Xbootclasspath:"" should be interpreted as nothing define
> d,
>                 // like we do below:
>                 String st[] = fracture(bootstrapPath, File.pathSeparator);
>                 int l = st.length;
> !               ArrayList<URL> urlList = new ArrayList<URL>();
>                 for (int i = 0; i < l; i++) {
>                     try {
>                         urlList.add(new File(st[i]).toURI().toURL());
>                     } catch (MalformedURLException e) {
>                     }
>                 }
>                 ...
>             }
>         }
> 
> We know the maximum length of the bootclasspath is st.length and
> our default bootclasspath is longer than the default ArrayList size
> (~48 compared to 10) so we should create the ArrayList with: new
> ArrayList<URL>(st.length); to avoid the inevitable copy (copies
> actually!) when it gets too big.  Even if a couple of the URLs are
> malformed the cost of a few extra empty ArrayList entries is much
> cheaper than the cost of the grow/copy steps.
> 
> These aren't particularly good examples but are intended to facilitate
> discussion about usage.
> 
> Regards,
>  Mark.
> 



Mime
View raw message