File.lastModified *extremely* slow ?

[Robert Mischke]

The much delayed JSR203 (http://www.jcp.org/en/jsr/detail?id=203) might
provide a solution when it is eventually completed. Until then using
NTFS instead of FAT32 might help (the directory is sorted by name, so
locating an entry in a large directory is faster). You could also try
using JNI.

Thanks, that is very interesting. Looks like I'm not alone:

"The Java platform has long needed a filesystem interface better than
the java.io.File class. [...], it does not support efficient
file-attribute access, [...]"

If they are really adding this to the 1.5 release (instead of 6, as
originally planned), well, that's one more reason to look forward to
1.5


Robert

 

[Robert Mischke]

It does sound reasonable when you look at it from a Windows programmer's
perspective. Unfortunately it looks like pointless complication from a UNIX
programmer's perspective, since there is no underlying API that it maps onto,
and it would seem that Sun's Java programmers think like UNIXers ;-)

But it could still provide an efficient underlying implementation on
Unix, even if there's no API support from the OS. The class I was
thinking of should in no way be forced on the developer, but instead
left as an option when it makes sense. And *if* you need the
functionality, it would save you some coding even on Unix.

From what Mark wrote, the guys at Sun are actually planning to improve
on this in Java 1.5, so at least there is hope

The problem is that this kind of performance is kind of a show-stopper
for my application.

Is it really a show stopper ? [...]

Well, it is... because there is an existing Delphi application which
does the job, and I was planning to port it to Java for platform
independence, easier maintenance, and later on, extended features.

But if these points come at the price of increasing the scan times to
the sixfold (sp?), I think many users will continue to use the old,
working Delphi app - and this makes it not worthwhile to rebuild this
application from scratch in Java, as much as I'd like to. Given the
usual prejudices against Java, chances are the new app would be
dismissed as "yet another slow java thing", although in every other
aspect, it competes very well so far...

Scanning times make up a significant part of the user interaction
already, and there is only little that can be reduced by caching etc.,
because the whole point of the scan is to keep in sync with the disk
state.

Robert

 

[Robert Mischke]

I can't explain your observations, but I ran my own test just now (Java
1.4.2 / Win2000 SP4 / Athlon (classic) 1.4 GHz / 25 GB FAT32 filesystem
/ 7200 RPM disk), and my results don't match up very well with yours. I
created a simple FS scanner that recursively traverses a directory tree.
In phase 1 of the test the scanner invokes getName() on each regular
file; in phase 2 (separate test runs) it invokes both getName() and
lastModified(). I observed a big speedup (ca. 2.5x) from the first run
to all subsequent ones, presumably because of the OS caches being
loaded, so that run was excluded from the statistics.

I found that for 101208 files in 4882 directories, the scan took an
average of 12.9 seconds without lastModified(), and 15.6 seconds with
lastModified(), for a difference of roughly 21%.

This is really strange... only three seconds difference on 100.000
files is indeed much less that what I've got. (I eliminated the first
run from my tests as well.)

[Note that JVM startup
time is _not_ factored out of those numbers.]

This might explain the low gain in percentage, as I ran my app from
Eclipse (which keeps a JV running) - but the absolute difference is
still much less than mine. And my system specs are almost identical to
yours, so this is not likely to be the cause: Athlon 1.8, Fat32,
Win2000 SP4, Java 1.4.2_03.

Confusing... but thanks for the test. Maybe I'll try to run some tests
on several machines as well.


Robert

 

[Robert Mischke]

The first thing to come to my mind after read this post it's that your
windows partition maybe need a "defrag".

Good idea, but the disk I was reading from is defragmented regularily.


Thanks anyway,

Robert

 

[Robert Mischke]

If they are really adding this to the 1.5 release (instead of 6, as
originally planned), well, that's one more reason to look forward to
1.5

....which, as I just read, is planned for release on September, 30th,
according to Graham Hamilton.

 

[Chris Uppal]

But it could still provide an efficient underlying implementation on
Unix, even if there's no API support from the OS.

My point is that, from the POV of a UNIXer, it would be a bizarrely complex API
that provided no advantage in either expressiveness or performance. Hence
they'd not add it. The /only/ reason to introduce an API like this is to
support systems where there is an actual performance advantage; otherwise it's
just adding complexity with no return.

From what Mark wrote, the guys at Sun are actually planning to improve
on this in Java 1.5, so at least there is hope

Yes, but I suspect it'll be 1.6 rather than 1.5. I hope I'm wrong...

The problem is that this kind of performance is kind of a show-stopper
for my application.

Is it really a show stopper ? [...]

Well, it is... because [...]

Fair enough.

BTW, the hope that an improvement will "soon" be available for Windows makes
the case against JNI even weaker. You will not only not have to support that
solution on multiple platforms, but you'll also not be committing yourself to
maintaining the Windows JNI code for ever.

-- chris

 

[Chris Uppal]

That's an interesting article; thanks for pointing it out. The
article's premise is slightly flawed, but the code (the first example,
at least) works.

I will therefore have to retrench, and say that when
you intern() a String you *may* ensure that a copy is retained for the
remainder of the VM's lifetime. Whether or not that is is in fact
ensured depends on the String implementation [not on the VM
implementation, as the JW article's author mistakenly implied].

It certainly doesn't /depend/ on the JVMs implementation. I think the author's
reasoning was (or rather, should have been ;-) that in the specific JVM he was
testing, String interning /is/ done by the JVM -- in the discussion afterwards
he talks of the interned String data being kept outside the heap.
Incidentally, I can't see the sense of that implementation decision: either the
implementation is simple-minded and does not reclaim interned Strings, in which
case it makes sense to keep the data in a special non-GCable area outside the
heap; or it does reclaim them, in which case the sensible approach is to use a
weak collection (or perhaps just the JVM's underpinnings for weak collection)
and it would be pointless to store them anywhere except the heap -- which is,
after all, designed for that kind of thing.

Changing the subject slightly. It's not completely clear to me that it is
legal for the JVM to recycle interned Strings in this way -- at least not it if
has observable consequences (other than not-running-out-of-memory ;-) and
System.identityHash() is certainly observable. The contract of intern() is
perhaps not strong enough to rule this optimisation out for "normal" strings
(and in any case, I'm not sure that the JavaDocs are normative). However the
contract in the JLS2 for the String literals does not (IMO) leave any scope for
/any/ observable recycling of the corresponding objects -- the language is
unambiguous and repeated. What's more the interning of Sting literals is
discussed (briefly) in the context of class loading, so it would not be easy to
argue that the JLS writers had just "forgotten" this issue.

The obvious (and preferable, IMO) fix would be to weaken the language of the
JLS in its next edition. Alternatively, the implementation could "pin"
interned Strings when their identityHash() is evaluated, and make them
non-recyclable at that time (say by adding a strong ref to the String to some
internal list).

As it stands (and despite the article's assertion) I don't see any reason to be
confident that:

class Oddity
{
static final int aHash = System.identityHash("Hello");
static bool check() { return aHash == System.identityHash("Hello"); }
}

cannot false from Oddity.check().

-- chris

 

[John C. Bollinger]

That's an interesting article; thanks for pointing it out. The
article's premise is slightly flawed, but the code (the first example,
at least) works. I will therefore have to retrench, and say that when
you intern() a String you *may* ensure that a copy is retained for the
remainder of the VM's lifetime. Whether or not that is is in fact
ensured depends on the String implementation [not on the VM
implementation, as the JW article's author mistakenly implied].

JVMs do not have to follow the java source code when implementing
standard classes and methods. For example the java.Math class appears to
delegate to StrictMath, but many JVMs will replace that implementation
with (much faster) intrinsic methods.

If you mean that the Java source distributed with Sun's Java SDKs may
not correspond on all points to the actual class files in the platform
library, then I'm fine with that. String.intern() is a native method
anyway (in the Sun source) so I wasn't drawing anything from their
implementation. In addition, VMs certainly have leeway to manipulate
the bytecodes provided to them, at least in so much as compiling some of
them to native code or perhaps reorganizing them. If you are
suggesting, however, that VMs treat specific classes specially by
completely replacing some of their methods with alternative
implementations, then I have to object. It sounds unlikely -- kludgey
even -- and I'm not prepared to accept it on your word alone.

Since I don't believe that a VM will provide its own canned
implementation of any method of any class, I still maintain that
String.intern(), however implemented, is exclusively the domain of the
String class, and not the responsibility of the VM. Some
implementations of that method may indeed manage the pool of interned
Strings separately from the JVM's heap, and apparently some String
implementations have a way to release Strings from the pool, but that
need not depend on VM magic.


John Bollinger
(e-mail address removed)

 

[John C. Bollinger]

I will therefore have to retrench, and say that when
you intern() a String you *may* ensure that a copy is retained for the
remainder of the VM's lifetime. Whether or not that is is in fact
ensured depends on the String implementation [not on the VM
implementation, as the JW article's author mistakenly implied].

It certainly doesn't /depend/ on the JVMs implementation. I think the author's
reasoning was (or rather, should have been ;-) that in the specific JVM he was
testing, String interning /is/ done by the JVM -- in the discussion afterwards
he talks of the interned String data being kept outside the heap.

He certainly seemed to imply that the VM was the responsible agent, and
I continue to disagree. There was a question in the discussion that
appeared to get at this point, but which was not interpreted in that light.

He did claim in the discussion that interned String data is kept outside
the heap. Inasmuch as that behavior is neither required nor forbidden
by Java, I have to take issue with his blanket statement to that effect.
It may be true of many -- or even all -- existing JVM / platform
library implementations, but one cannot assume that it will be so.

Incidentally, I can't see the sense of that implementation decision: either the
implementation is simple-minded and does not reclaim interned Strings, in which
case it makes sense to keep the data in a special non-GCable area outside the
heap; or it does reclaim them, in which case the sensible approach is to use a
weak collection (or perhaps just the JVM's underpinnings for weak collection)
and it would be pointless to store them anywhere except the heap -- which is,
after all, designed for that kind of thing.

I agree, and I suspect that Sun's current implementation is an artifact.
It appears that their earlier VMs really didn't ever reclaim interned
Strings, and thus it would have made sense to keep the pool outside of
the heap. When they changed that, they may have done a less thorough
redesign than they ought to have done.

Changing the subject slightly. It's not completely clear to me that it is
legal for the JVM to recycle interned Strings in this way -- at least not it if
has observable consequences (other than not-running-out-of-memory ;-) and
System.identityHash() is certainly observable. The contract of intern() is
perhaps not strong enough to rule this optimisation out for "normal" strings
(and in any case, I'm not sure that the JavaDocs are normative). However the
contract in the JLS2 for the String literals does not (IMO) leave any scope for
/any/ observable recycling of the corresponding objects -- the language is
unambiguous and repeated. What's more the interning of Sting literals is
discussed (briefly) in the context of class loading, so it would not be easy to
argue that the JLS writers had just "forgotten" this issue.

I agree again. I wonder whether the part that was forgotten was
System.identityHashCode(); I can't think of any other way to observe the
effect. I'm not string on JNI, though; could there be a way to figure
it out from the native side?

The obvious (and preferable, IMO) fix would be to weaken the language of the
JLS in its next edition. Alternatively, the implementation could "pin"
interned Strings when their identityHash() is evaluated, and make them
non-recyclable at that time (say by adding a strong ref to the String to some
internal list).

When you're right, Chris, you're right. Once again I agree.

As it stands (and despite the article's assertion) I don't see any reason to be
confident that:

class Oddity
{
static final int aHash = System.identityHash("Hello");
static bool check() { return aHash == System.identityHash("Hello"); }
}

cannot false from Oddity.check().

I'm not sure I follow. I know you're aware of the requirements of the
JLS, in particular: "Literal strings within the same class (§8) in the
same package (§7) represent references to the same String object
(§4.3.1)." Are you suggesting that common VMs may be non-compliant on
this point, or that "same object" should be interpreted differently in
the context of that statement (JLS 2ed, 3.10.5) than elsewhere in the JLS?


John Bollinger
(e-mail address removed)

 

[Mark Thornton]

That's an interesting article; thanks for pointing it out. The
article's premise is slightly flawed, but the code (the first
example, at least) works. I will therefore have to retrench, and say
that when you intern() a String you *may* ensure that a copy is
retained for the remainder of the VM's lifetime. Whether or not that
is is in fact ensured depends on the String implementation [not on
the VM implementation, as the JW article's author mistakenly implied].

JVMs do not have to follow the java source code when implementing
standard classes and methods. For example the java.Math class appears
to delegate to StrictMath, but many JVMs will replace that
implementation with (much faster) intrinsic methods.

If you mean that the Java source distributed with Sun's Java SDKs may
not correspond on all points to the actual class files in the platform
library, then I'm fine with that. String.intern() is a native method
anyway (in the Sun source) so I wasn't drawing anything from their
implementation. In addition, VMs certainly have leeway to manipulate
the bytecodes provided to them, at least in so much as compiling some of
them to native code or perhaps reorganizing them. If you are
suggesting, however, that VMs treat specific classes specially by
completely replacing some of their methods with alternative
implementations, then I have to object. It sounds unlikely -- kludgey
even -- and I'm not prepared to accept it on your word alone.

Since I don't believe that a VM will provide its own canned
implementation of any method of any class, I still maintain that
String.intern(), however implemented, is exclusively the domain of the
String class, and not the responsibility of the VM. Some
implementations of that method may indeed manage the pool of interned
Strings separately from the JVM's heap, and apparently some String
implementations have a way to release Strings from the pool, but that
need not depend on VM magic.

Well I have it from someone in the JVM implementation team that methods
such as Math.sin are replaced by intrinsic versions which do not even
necessarily return the same result as the byte code would imply (because
that invokes StrictMath). The result does however meet the contract in
that it deviates by at most 1ulp from the exact result. I suspect some
similar trickery is performed on parts of the java.nio package.

On older versions of the JVM it was quite easy to observe the
replacement because they left the argument reduction to the native cpu
method, which on x86 architecture is somewhat inaccurate for Math.PI.

Regards,
Mark Thornton

Mark Thornton

 

[Mark Thornton]

But it could still provide an efficient underlying implementation on
Unix, even if there's no API support from the OS. The class I was
thinking of should in no way be forced on the developer, but instead
left as an option when it makes sense. And *if* you need the
functionality, it would save you some coding even on Unix.

From what Mark wrote, the guys at Sun are actually planning to improve
on this in Java 1.5, so at least there is hope

1.6 unfortunately.

 

[Mark Thornton]

If you mean that the Java source distributed with Sun's Java SDKs may
not correspond on all points to the actual class files in the platform
library, then I'm fine with that. String.intern() is a native method
anyway (in the Sun source) so I wasn't drawing anything from their
implementation. In addition, VMs certainly have leeway to manipulate
the bytecodes provided to them, at least in so much as compiling some of
them to native code or perhaps reorganizing them. If you are
suggesting, however, that VMs treat specific classes specially by
completely replacing some of their methods with alternative
implementations, then I have to object. It sounds unlikely -- kludgey
even -- and I'm not prepared to accept it on your word alone.

http://www.javagaming.org/cgi-bin/JGNetForums/YaBB.cgi?board=Tuning;action=display;num=1094054295

 

[Chris Uppal]

He certainly seemed to imply that the VM was the responsible agent, and
I continue to disagree.

Perhaps you (both) would accept the formulation: "it is the responsibility of
the platform to ensure [etc]. Whether this is responsibility is discharged by
Java code in the implementation of String, or by some internal JVM operation,
or a combination of the two, is a private implementation detail".

He did claim in the discussion that interned String data is kept outside
the heap. Inasmuch as that behavior is neither required nor forbidden
by Java, I have to take issue with his blanket statement to that effect.

Me too. For some reason this seems to be a popular error in articles on core
Java -- even informative and interesting ones (as in this case) -- the writers
don't seem to (be able to) distinguish between what /does/ happen and what
/must/ happen. Perhaps it's their editors forcing them to make their language
"less abstract" ? Never fails to irritate me, anyway...

I wonder whether the part that was forgotten was
System.identityHashCode(); I can't think of any other way to observe the
effect. I'm not string on JNI, though; could there be a way to figure
it out from the native side?

I don't think so -- JNI works at one level of (logical) indirection away from
the "real" objects, so you never get a raw pointer to an object to play with.
(Actually, the "references" that it uses might be real pointers, you never
know, but you can't legally treat them as such).

I think you might be able to get another observable using phantom references to
spot Strings dying before their time. If so then "pinning" the identity hash
wouldn't be sufficient, the weak ref system would need to be beefed-up too. In
fact, I find it rather easier to imagine this causing some subtle bug than the
instability of identity hashes.

As it stands (and despite the article's assertion) I don't see any
reason to be confident that:

class Oddity
{
static final int aHash = System.identityHash("Hello");
static bool check() { return aHash == System.identityHash("Hello");
} }

cannot false from Oddity.check().

I'm not sure I follow. [...]

Sorry, my mistake -- I left out most of the necessary words. What I meant was
that if Java platform implementation is setting aside the language of the JLS
in this way, and if that is not to be treated as a simple bug, then I don't see
any reason to be confident that [etc.]

Maybe it /is/ intended that Oddity.check() can return false (in which case the
JLS is in need of fixing). Maybe it is intended that interning a string should
fix its identity for "ever". Maybe something inbetween, where String literals'
identities are guaranteed to remain stable for the lifetime of any one class.
The problem is that we don't know which.

-- chris

 

[Robert Mischke]

1.6 unfortunately.

Hmm... it seems you're right. I was referring to section 2.2 on
http://www.jcp.org/en/jsr/detail?id=203:

"This specification is intended to become part of the Java 2 Platform,
Standard Edition, version 1.5 ("Tiger") as specified by JSR 176."

But on http://www.jcp.org/en/jsr/detail?id=176, the final release
contents for 1.5, JSR-203 is not listed. Shame :/


Robert

 

[John C. Bollinger]

John C. Bollinger wrote:

If you mean that the Java source distributed with Sun's Java SDKs may
not correspond on all points to the actual class files in the platform
library, then I'm fine with that. String.intern() is a native method
anyway (in the Sun source) so I wasn't drawing anything from their
implementation. In addition, VMs certainly have leeway to manipulate
the bytecodes provided to them, at least in so much as compiling some
of them to native code or perhaps reorganizing them. If you are
suggesting, however, that VMs treat specific classes specially by
completely replacing some of their methods with alternative
implementations, then I have to object. It sounds unlikely -- kludgey
even -- and I'm not prepared to accept it on your word alone.

[...]

Well I have it from someone in the JVM implementation team that methods
such as Math.sin are replaced by intrinsic versions which do not even
necessarily return the same result as the byte code would imply (because
that invokes StrictMath). The result does however meet the contract in
that it deviates by at most 1ulp from the exact result. I suspect some
similar trickery is performed on parts of the java.nio package.

Assuming that to be an accurate description of what happens, I wonder
whether the VM recognizes and replaces whole method invocations, or
whether it instead leaves the invocations but replaces the method
bodies? The latter really ought to be done by changing the
implementation of java.lang.Math instead of by VM magic. The former
really ought to be done by allowing the VM's normal JIT to work on the
result of the latter.

I am distinctly uncomfortable with the concept of the VM failing to use
the class implementations provided to it, if for no other reason than
that it seems to violate the language and VM specs.

On older versions of the JVM it was quite easy to observe the
replacement because they left the argument reduction to the native cpu
method, which on x86 architecture is somewhat inaccurate for Math.PI.

And if they are going to try to pull some monkey business, then at least
they should make sure the resulting computations produce the same answers.


John Bollinger
(e-mail address removed)

 

[Chris Uppal]

I am distinctly uncomfortable with the concept of the VM failing to use
the class implementations provided to it, if for no other reason than
that it seems to violate the language and VM specs.

I don't think that the implementation of, say, math.Sin() is part of the spec.
There is nothing to say that it should be implemented by Java code, or by a
native method, or by some other mechanism that is internal and private to the
JVM.

Now, if the JVM started mucking about playing special tricks with /my/ code,
then that'd be different. But I think that any and all parts of the "standard"
library is up for grabs for the platform implementor to handle in whatever way
seems best. And if that involves on-the-fly substitution of methods, then so
be it.

In any case, the typical JITing JVM substitutes native code for "normal" Java
methods as a matter of routine, so what's the problem ?

Of course, the substitutions should produce no observable effect within the
contract. The language of lava.lang.Math permits implementations a certain
amount of slack here. I don't know if the current Sun JVMs /do/ stick within
the allowed limits (Mark seemed to be saying that some older ones didn't), but
if they don't then that would seem to be a simple bug, rather than a semantic
outrage (as it were ;-)

-- chris

 

[Robert Mischke]

Ok, just for the record: I have now created a solution in form of a
JNI Delphi DLL, which is used on Windows. On all other platforms, the
pure Java scanner I already had will be used. The Linux results that
some of you posted suggest that no native code will be necessary
there.

So far, this solution performs very well (approx. times for my 40.000
files test case, Win2000, FAT32):

pure Java / platform-independent:

- only filenames: 4 seconds
- filenames + size: 6 seconds
- filenames, size + timestamp: 30 seconds (the original problem)

Java + optimized native DLL:

- filenames, size + timestamp: 2.8 seconds


I have not measured comparable times on other platforms yet.


Thanks for all the comments & suggestions!

Robert

 

[John C. Bollinger]

John C. Bollinger wrote:




I don't think that the implementation of, say, math.Sin() is part of the spec.

That is a large part of my discomfort. Since java.lang.Math is not part
of the language or VM spec, I don't like the idea that a VM will
incorporate special handling for it. I don't see where the specs permit
a VM to completely ignore a method implementation provided to it in
favor of code of its own choice.

I'd be happier (though still a bit unsettled) if a VM recognized
specific class names and preemptively _compiled_ some of their methods
to native code at class initialization time, but that's different from
the VM thinking that it already knows what the native code is supposed
to be, based only on class and method names.

There is nothing to say that it should be implemented by Java code, or by a
native method, or by some other mechanism that is internal and private to the
JVM.

Now, if the JVM started mucking about playing special tricks with /my/ code,
then that'd be different. But I think that any and all parts of the "standard"
library is up for grabs for the platform implementor to handle in whatever way
seems best. And if that involves on-the-fly substitution of methods, then so
be it.

So, then, is the VM supposed to be tied to a particular implementation
of the platform class library? Because if it incorporates knowledge of
particular classes then suddenly it is. THAT is what I'm complaining
about. It's more of a theoretical problem than a practical one,
however, as I don't have any plan to write my own implementation of the
platform library.

Shortcuts like this have a way turning around and biting people on the
backside, although in this case that's more Sun's problem than mine.

In any case, the typical JITing JVM substitutes native code for "normal" Java
methods as a matter of routine, so what's the problem ?

The problem is with the VM assuming that it knows better than the class'
implementator what is an appropriate implementation of a method. If
performance requirements demand that the VM provide efficient
implementations of certain operations then the appropriate interfaces
should be written into the VM and language specs. That could get pretty
kludgy if binary class compatability is to be retained, but at some
point in the future Java will be well served by an overhaul of the VM
design, at which point [all] the kludges can be smoothed into a new,
better product.


John Bollinger
(e-mail address removed)

 

[Chris Uppal]

That is a large part of my discomfort. Since java.lang.Math is not part
of the language or VM spec, I don't like the idea that a VM will
incorporate special handling for it. I don't see where the specs permit
a VM to completely ignore a method implementation provided to it in
favor of code of its own choice.

Ah, right. I see your point. My position (unexamined) was that math.Sin() was
part of the standard platform, and that the JVM could therefore assume anything
it wanted. Examining that position, it looks a little shaky. In essence the
problem is that there is no indication of the boundaries of "standard": To my
mind 'standard' must include java.lang.Object, java.lang.String, and
java.lang.Class (if only because it isn't possible to create a conforming JVM
without assuming their existence and a fair bit of their behaviour -- in fact I
don't know how to create a JVM without special-casing those classes, at least
during bootstrapping). But does it include java.lang.math ? I'd be happy
enough to accept that the 'standard' included all of java.lang.*, but it's not
clear that it does. And does it extend to java.* ? Hmm...

So, then, is the VM supposed to be tied to a particular implementation
of the platform class library? Because if it incorporates knowledge of
particular classes then suddenly it is.

Agreed, and I suspect that that is exactly how Sun see it. (And is reflected
in their licensing, IIRC, both the language it uses, and the actual
provisions.)

Come to that, the version numbers in the classfile that are commonly thought to
indicate the version of the JVM and/or the format of the classfile, make a lot
more sense if you think of them as indicating the required version of the
platform library. (Since they have changed often when there have been no
semantic changes to either the classfile format or the JVM -- as recently
discussed in the "Different compilers = Different byte code?" thread.) Which
further supports the suspicion that Sun think of the JVM and library as an
indissoluble unit.

If
performance requirements demand that the VM provide efficient
implementations of certain operations then the appropriate interfaces
should be written into the VM and language specs.

That would be a definite improvement.

-- chris