URLClassPath does unnecessary linear search through every jar and jar entry to find resource
Peter Levart
peter.levart at gmail.com
Tue Sep 15 15:31:13 UTC 2015
Hi Adrian,
I looked briefly at your code and claims and have some comments inline...
On 09/13/2015 11:08 AM, Adrian wrote:
> Hi,
>
> I posted about this earlier (few weeks ago), and got some responses
> about concerns which I addressed in my last email, though I didn't
> hear back about it.
> My apologies if I shouldn't be sending this; I'm not sure what the
> protocol is about this stuff
>
> Classloading on a standard Java application with jars on the classpath
> currently does a linear search through every jar on the classpath, and
> every entry in a jar, for every class loaded.
> As URLClassPath searches for an entry/resource/class, it's possible to
> cache each entry it encounters -> where to find it, so in the future
> if a resource has already been seen we don't need to repeat the ~2d
> search
>
> Original thread (august list):
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-August/035009.html
> Last message (september list):
> http://mail.openjdk.java.net/pipermail/core-libs-dev/2015-September/035016.html
>
> I got 3 responses: 2 concerning changes to jars at runtime
> (invalidating cache), and 1 saying you're not supposed to modify jars
> at runtime (can confirm via source code, and manual testing - it
> crashes the JVM)
>
> In my last message I addressed
> - jars being modified (which you're not supposed to do; the current
> classloader does not handle this) or the classpath changing (only
> possible if you make public fields/methods via reflection, and this
> could easily be handled gracefully)
> - some details of the finding resource process (e.g. the meta index,
> when the cache for jar entries can't be used because of the semantics
> of other loaders/types of entries on the classpath)
> - a reference implementation of caching that I believe is simple and
> compliant with existing functionality
> - some basic numbers on performance
>
> ---
> So in this email I wanted to explain the problem again, hopefully more
> clearly now
>
> URLClassPath is used by URLClassLoader to find classes, though it
> could be used for finding any resource on a classpath.
> URLClassPath keeps an array of URLs, which are typically folders or
> jars on the local filesystem.
> They can be http or ftp or other files, but that's not
> relevant/doesn't affect this problem
>
> To find a resource/class (URLClassPath#getResource), it:
> 1. Loops through the URLs in order
> 2. Creates Loader objects for each URL lazily (URLClassPath$FileLoader
> or URLClassPath$JarLoader). So if the Loader for the first URL finds
> all the resources, Loaders for the remaining entries on the classpath
> are never created/looked at
> 3. Calls Loader#getResource and returns the resource if found
> (otherwise keep searching)
>
> URLClassPath$JarLoader creates its corresponding JarFile either in the
> constructor or in getResource (depending on the meta index - the
> details I explained in my last email I won't repeat)
> When a JarFile is created, it opens the jar file on the file system,
> reads the central directory of the jar/zip file, and creates an
> internal linked list with all its entries
It's not actually a linked list, but a hash table. See
jdk/src/java.base/share/native/libzip/zip_util.[c,h] ...
the jzfile.table is an array of jint mapping (entry-name-hash-code %
table.length) -> index into jzfile.entries
the jzfile.entries is an array of jzcell which represent heads of hash
buckets that are linked with jzcell.next
So look-ups into individual jar/zip files should be O(1). But each
look-up does cross the Java/JNI boundary, so it has a fixed JNI overhead
too. If there are lots of jar files in class path, you pay for the
unsuccessful hash-table look-ups before finding the resource. This
overhead is not that big, but increases with the number of jar files in
class path. Each look-up into class path is therefore O(N) where N = #
of jar files...
>
> JarFile objects are immutable; you can only open them for read/delete
> (see constructor API
> http://docs.oracle.com/javase/7/docs/api/java/util/jar/JarFile.html#JarFile(java.io.File,%20boolean,%20int)
> ), they do not detect if the file has been modified externally, and
> you only "append" or "delete" entries by creating a new jar
> (JarOutputStream)
>
> When URLClassPath$JarLoader#getResource calls JarFile#getEntry; in the
> C code it searches through the linked list
> (jdk/src/share/native/java/util/zip/zip_util.c, ZIP_GetEntry - jar
> files are just zip files, and the java JarFile object just extends
> ZipFile)
>
> Since the order in which jar files and jar entries are searched is
> invariant, we can create a map of resource -> first jar which contains
> it
>
> However, we don't want to introduce additional overhead.
> When a JarFile is created, it already builds the internal linked list
> - it's O(number of entries)
> I propose that after the JarLoader creates the JarFile, it iterates
> through its entries and adds them to the cache (if the map does not
> already contain the resource, i.e. an earlier jar contains the
> resource)
> This adds a small overhead when instantiating loaders - but creating
> the JarLoader/JarFile is still technically O(number of entries), and
> now getResource is constant time, instead of requiring a linear search
> through every jar and the linked list of entries for each jar
> (O(number of jars * entries/jar))
Have you measured your entry iteration and cache initialization
overhead? When iterating over JarEntries, the code invokes 10 native
methods for each returned JarEntry:
long jzentry = getNextEntry(jzfile, i++)
getEntryFlag(jzentry);
getEntryBytes(jzentry, JZENTRY_NAME)
getEntryTime(jzentry)
getEntryCrc(jzentry)
getEntrySize(jzentry)
getEntryCSize(jzentry)
getEntryMethod(jzentry)
getEntryBytes(jzentry, JZENTRY_EXTRA)
getEntryBytes(jzentry, JZENTRY_COMMENT)
...it uses CharsetDecoder 1 or 2 times to decode the name and optional
comment of each JarEntry, it allocates several java objects...
So I have a feeling that initializing your cache when JarFiles are
constructed, would increase start-up time and not decrease it. It may
pay-of on the long run though. For achieving short start-up time, JDK
tries to be as lazy as possible. Your cache goes against that.
ZipFile native code tries hard to keep the memory usage down for
maintaining the look-up hash table. It only keeps hash codes in the
table, with offsets into memory mapped ZIP central directory for each
entry. Your proposed java-side cache is also a hash table, but it's
memory footprint is much bigger.
I have made a little experiment to see if JNI overhead for negative
answers from ZipFile.getEntry(name) is really that big. I modified
ZipFile.java/ZipFile.c to expose access to a look-up hash table that is
maintained in native code to the java side via two direct ByteBuffers. I
screen each ZipFile.getEntry(name) with a probe that gives a negative
answer for majority of negative lookups without invoking JNI methods.
Here are the changes I made for this experiment:
http://cr.openjdk.java.net/~plevart/jdk9-dev/ZipFile.getEntry/webrev.01/
I have tested the changed JDK with the following JMH benchmark:
http://cr.openjdk.java.net/~plevart/jdk9-dev/ZipFile.getEntry/ZipFileBench.java
This benchmark measures the ZipFile.getEntry(name) method on 2 jar files
(rt.jar ~20K entries, idea.jar ~40K entries) looking up entries in 1st
jar file with names of the entries taken from the 2nd jar file:
Original:
Benchmark (_zipTuple) Mode Samples Score
Error Units
j.t.ZipFileBench.getEntry rt.jar:rt.jar avgt 8 721.536 ±
17.344 ns/op
j.t.ZipFileBench.getEntry rt.jar:idea.jar avgt 8 501.451 ±
10.298 ns/op
j.t.ZipFileBench.getEntry idea.jar:rt.jar avgt 8 423.513 ±
23.268 ns/op
Patched:
Benchmark (_zipTuple) Mode Samples Score
Error Units
j.t.ZipFileBench.getEntry rt.jar:rt.jar avgt 8 743.281 ±
13.467 ns/op
j.t.ZipFileBench.getEntry rt.jar:idea.jar avgt 8 392.569 ±
7.710 ns/op
j.t.ZipFileBench.getEntry idea.jar:rt.jar avgt 8 333.249 ±
14.069 ns/op
The rt.jar:rt.jar therefore gives the score for successful look-ups,
while rt.jar:idea.jar and idea.jar:rt.jar give the score for
unsuccessful look-ups.
The screening of JNI call improves unsuccessful lookup by 20-25% while
not hurting much the successful lookup. The successful look-up could be
improved so that it wouldn't have any overhead by utilizing the result
of the screening probe that must now be re-computed in native code once
more (see TODO).
So is this worth the trouble? I don't know.
Adrian, does this patch improve your situation (don't forget to set the
system property -Dsun.zip.useNativeTableProbe=true to enable the
feature)? This patch should not hurt startup performance, as it does not
maintain or initialize any additional data structures (besides 2
ByteBuffer objects per ZipFile that only expose native memory to Java code).
Regards, Peter
>
> There are several caveats when the cache cannot be used with non-jar
> URLs on the classpath, and the meta index, but I explain them in my
> last email along with comments in the reference implementation
>
> ---
> Regarding modified jars:
> - moved/renamed: the file handle is still valid and it doesn't affect
> the JVM/classloading
> - deleted: the file handle is still valid and it doesn't affect the
> JVM/classloading
> - modified: the JVM crashes
>
> The first two may not be intuitive, but remember that file handles
> point to files; not paths on the filesystem.
> So even though a jar appears renamed in the shell, the java process
> has opened a file, somewhere in the c implementation of file objects
> it has the file handle, and when the JVM does the system call read on
> the file handle say to read the class from the jar file, it all works
> fine
> For what it's worth, here's a stack overflow answer as "source":
> http://stackoverflow.com/questions/2028874/what-happens-to-an-open-file-handler-on-linux-if-the-pointed-file-gets-moved-de
>
> ---
> There is a protected method URLClassLoader#addURL which appends a URL
> to the classpath.
> People could use reflection to make it public.
> Because jars are opened lazily and the cache is also built lazily
> whenever a jar is opened, it doesn't matter if paths are appended
>
> Regarding people making extensive use of reflection to modify the
> order of entries on the classpath, I believe that's irrelevant as
> that's clearly not the semantic of URLClassLoader/URLClassPath.
> People who need custom classloading rules create custom classloaders;
> that's the purpose of classloaders being extensible
>
> ---
> Anyways, I hope this was discussion worthy.
> I've looked much into this and believe I haven't missed anything, but
> if someone knows why it hasn't/can't be done any insight would be
> appreciated!
> Alan from the last email thread said "There was a lot of experiments
> and prototypes in the past along these lines" - are the results
> public?
> He also mentioned improving classloading in Java's upcoming module
> system (originally planned for Java 7, currently delayed to Java 9),
> but I believe the algorithmic complexity and performance of
> URLClassLoader could be improved without complicated changes
>
> Please let me know what you think, and thanks for your time!
>
> Best regards,
> Adrian
More information about the core-libs-dev
mailing list