You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@harmony.apache.org by Salikh Zakirov <Sa...@Intel.com> on 2006/07/28 17:38:46 UTC
[drlvm] string interning in java
Hi,
I have been looking to the string interning code in DRLVM recently.
The reason I have started to do this is that the following stress
test quickly causes OOM (OutOfMemoryError) on DRLVM:
public class StressIntern {
public static void main(String[] args) {
String s = "abc";
for (int i = 0; i < 100000; i++) {
s = (s + i + s).intern();
if (s.length() > 65536) s = "abc" + i;
if (i % 1000 == 0) trace(".");
}
}
public static void trace(Object o) {
System.out.print(o);
System.out.flush();
}
}
It turned out that DRLVM interns all of its strings in the permanent
manner, keeping the strong reference to the string instances forever.
Interned strings are never reclaimed and thus OOM occurs.
As far as I remember, the intern() contract has two requirements
1. s1.equals(s2) must imply s1.intern() == s2.intern()
2. for any string literal "abc" == "abc".intern()
In practical terms, the first requirement is satisfied by keeping
an authoritative pool of interned strings. The second requirement
is implemented by looking the string in authoritative pool upon
resolving constant pool entry.
Keeping interned strings forever is not a spec requirement, and it looks
like a flaw in the current design, because it allows any user application
to attack a containing VM by interning large number of strings.
The attached patches implement different approach to the interning strings.
To make interned string pool garbage collectable, I used WeakHashMap.
The native string pool is no longer used as authoritative, but is used to
cache object pointers obtained by interning strings in the WeakHashMap.
In this way, any strings originating from class files and loaded through LDC
bytecode, are still unreclaimable (at least until class unloading
is implemented properly in DRLVM). But the strings interned at runtime by explicit calling String.intern() method, do not have native counterpart any longer, and are fully garbage collectable.
Making class constant pool entries reclaimable does not look like an important
feature to me at this moment, because the fair number of native memory is still
used for each class pool entry, and complete solution must implement full class
unloading.
Performance-wise, using java string pool slows down execution a bit.
I used a HelloWorld-like application to measure startup time on my laptop.
unmodified DRLVM: 0.270s +/- 0.005 average, 0.257s fastest
java string pool: 0.277s +/- 0.005 average, 0.265s fastest
which is about 3% slowdown.
In exchange, it buys us improved robustness.
Now I am going to attempt optimization of java code by using a customized weak hashmap implementation. By using it, I will be able to create just one weak reference to the interned string instead of current two, and to perform just one hash lookup instead of two on interning new string.
--
Salikh Zakirov, Intel Middleware Products Division
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Salikh Zakirov wrote:
> The attached patches implement different approach to the interning strings.
> To make interned string pool garbage collectable, I used WeakHashMap.
Additional information that I think might be of interest.
The java implementation of interning changed the order
of static initializers execution during startup.
(I've run the DRLVM debug configuration with -Xtrace:class.init flags)
Before the change, the classes were initialized in order
java/lang/Thread
java/lang/System
java/io/FileDescriptor
org/apache/harmony/luni/platform/Platform
java/util/HashMap
java/lang/String
java/lang/System
java/util/HashMap
java/lang/ClassLoader
java/lang/VMExecutionEngine
and with the pure java interning, the new order is
org/apache/harmony/kernel/vm/VM
java/lang/String
java/lang/Thread
java/lang/System
java/io/FileDescriptor
org/apache/harmony/luni/platform/Platform
java/util/HashMap
java/lang/System
java/util/HashMap
java/lang/ClassLoader
I do not know for sure if this is important or not,
but want to let more smart people to know and spot potential problems if there are any.
The smoke tests pass with the change, and Eclipse on DRLVM behaviour
is exactly the same as before the change (not to say it works perfectly, but
the error dialog boxes look the same :)
--
Salikh Zakirov, Intel Middleware Products Division
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: [drlvm] string interning in java
Posted by Alex Blewitt <al...@gmail.com>.
On 29/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> Still, we need to have this functionality, because it is in spec.
True, intern() is part of the spec, and GC-intern() will be much better :-)
> > However, by hard-coding the message like this, you're
> > guaranteeing that the VM will intern() the string "how are you?", even
> > if it never prints this message out (because it's in the constant
> > pool).
>
> This is not the case, at least for DRLVM (I do not know about other JVMs).
> The string literal in the .java file is compiled to the constant
> pool entry in the class file, and essentially, the whole contents
> of the class file is loaded to memory (native memory).
> No java object instances are created at this point.
The memory (for the message key) is still taking up space in the
constant pool for the class, though as part of the class loading
process. From what I've seen, message keys tend to be longer than the
equivalent field names (also stored in the constant pool). And that's
before the String instance is created.
> We may consider the opportunity to save memory by not keeping the
> class file contents in memory, and loading it on demand, but
> I personally do not know for sure how is it done now.
Neither do I :-) It might only load constants from the constant pool
on demand, but my expectation is that the whole class's contents are
loaded into memory from whatever storage container (e.g. Jar) that
they came from. Perhaps the constants could be optimised in some kinds
of ways e.g. by writing them out to a memory mapped temporary file.
> The java specification does not require eager loading of the string
> literals, and DRLVM in fact does not do it.
Interesting. Perhaps I misunderstood the spec, but I was under the
impression that all String literals were interned like this. Perhaps
it's just because I've seen examples such as:
private static final MESSAGE_HELLO_WORLD_KEY = "hello.world";
which, of course, would be assigned when the class is loaded (and thus
the string literal interned approrpiately). Lazy instantiation of such
keys would delay this behaviour.
> It only keeps space in class file if it is never used.
> Saving space on class loading is a separate issue, not related
> to strings interning.
I think that they are related; but only in that the context of
internationalisation of messages and message keys is often where the
intern() is used (especially with respect to the way message key is
initialised). However, the relationship is not symmetric; it's
possible to discuss intern() without reference to any kind of message
keys.
> > Importantly, it explains why the Eclipse NLS class uses static string
> > variables to refer to messages, and not to String literals for exactly
> > this reason. If you use a static string variable that is dynamically
> > initialised from a properties file, you only take the memory up when
> > you need to refer to that message
>
> actually, I think, this should read "... when you need to refer
> to any of messages contained in the resource bundle ..."
True, the class loading will cause all messages in the same messages
class/file to be loaded at once. (Bundle might be misleading here; an
eclipse bundle/plug-in often has one messages class/file, but may have
several.)
> The interned strings design does not precludes from garbage collecting
> interned strings. The patches I've sent in fact do just that.
Yes, this sounds like a good plan.
> > In other words, all of the benefits of intern(), and yet none of the
> > disadvantages. Remind me again why we're not using this method for
> > doing messages in Harmony?
>
> The Eclipse approach for localizing messages from java code looks promising,
> but requires some work duplication or complex tooling support.
>
> As far as I understand, Eclipse approach is completely orthogonal to traditional
> localization approach, so it imposes no restrictions on using two approaches
> simultaneously. Feel free to submit patches to use it :)
Yes, it should be possible to use this too. Eclipse also has tooling
to search for string literals and propose replacements for them
automatically ...
http://dev.eclipse.org/viewcvs/index.cgi/~checkout~/platform-core-home/documents/3.1/message_bundles.html
http://help.eclipse.org/help32/topic/org.eclipse.jdt.doc.user/tasks/tasks-188.htm
http://help.eclipse.org/help32/topic/org.eclipse.jdt.doc.user/reference/ref-wizard-externalize-strings.htm
The only issue might be that Eclipse uses an NLS class to do the
in-lining of messages, so we'd either need to re-implement or to
re-use the Eclipse NLS file directly. I think that discussions
following on re: internationalisation should continue in the new
thread created for that purpose.
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Alex Blewitt wrote:
> Yes, but I disagree with your conclusion; to me, it doesn't make
> sense.
I see you point.
Still, we need to have this functionality, because it is in spec.
> However, by hard-coding the message like this, you're
> guaranteeing that the VM will intern() the string "how are you?", even
> if it never prints this message out (because it's in the constant
> pool).
This is not the case, at least for DRLVM (I do not know about other JVMs).
The string literal in the .java file is compiled to the constant
pool entry in the class file, and essentially, the whole contents
of the class file is loaded to memory (native memory).
No java object instances are created at this point.
Later, at execution time, LDC instruction is calling to the VM helper
to resolve the constant pool entry. Resolution is done lazy,
so if your code is never called, then the string literal will
never be resolved. The java string instance is created and interned
only at resolution time.
So, the issue you have described is not applicable to the DRLVM.
The interning is never done for the unused strings.
We may consider the opportunity to save memory by not keeping the
class file contents in memory, and loading it on demand, but
I personally do not know for sure how is it done now.
> Many, many, messages are never printed out in the course of a
> normal code flow; yet they're all cached in the intern() pool, and in
> fact, have to be because of the way that constant pools are supposed
> to work.
The java specification does not require eager loading of the string
literals, and DRLVM in fact does not do it.
> So this 'perfect sense' is trading off speed of lookup of a message
> for memory requirements, even if it's never used. If it's never used,
> the speed of lookup is irrelivant (think exception messages like
> 'Invalid URL format') but it still takes up space.
It only keeps space in class file if it is never used.
Saving space on class loading is a separate issue, not related
to strings interning.
> Reading the Eclipse Performance Bloopoers is a very good summary of
> the techniques taken by the Eclipse development team to try and limit
> the amount of memory used, and should be read by anyone with an
> interest in intern()'d strings, or for that matter, messages in
> general:
>
> http://wiki.eclipse.org/index.php/Performance_Bloopers
Thanks, this is very interesting reading.
> Importantly, it explains why the Eclipse NLS class uses static string
> variables to refer to messages, and not to String literals for exactly
> this reason. If you use a static string variable that is dynamically
> initialised from a properties file, you only take the memory up when
> you need to refer to that message
actually, I think, this should read "... when you need to refer
to any of messages contained in the resource bundle ..."
> Furthermore, because it's a
> dynamically read in string, it doesn't pollute the intern() pool, and
> thus when the class is unloaded, the string is unloaded too.
The interned strings design does not precludes from garbage collecting
interned strings. The patches I've sent in fact do just that.
Before the patch, the native interned string pool is used, and interned
strings are not garbage collectable. After the patch, the interned string
pool is implemented in java, and non-reachable interned strings are
reclaimed from interned pool too.
The literals are still referenced in a strong way from the constant pool,
so can be reclaimed only if the class is unloaded.
(and class unloading is not yet fully supported in DRLVM, though some prototype
exists).
> Once a
> String is intern()'d, it's like a memory leak -- you'll never see that
> memory again.
Not true for DRLVM with my patch.
> Lastly, the Eclipse approach ensures that there are no String values
> saved as keys anywhere in the system -- they're always referred to by
> the static field contents. So regardless of whether they're intern()'d
> or not, you are always comparing by reference anyway.
I would rather say that Eclipse approach eliminates the need of any lookup,
because static fields are compiled into immediate address access.
> In other words, all of the benefits of intern(), and yet none of the
> disadvantages. Remind me again why we're not using this method for
> doing messages in Harmony?
The Eclipse approach for localizing messages from java code looks promising,
but requires some work duplication or complex tooling support.
As far as I understand, Eclipse approach is completely orthogonal to traditional
localization approach, so it imposes no restrictions on using two approaches
simultaneously. Feel free to submit patches to use it :)
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
[i18n] Eclipse NLS apporach to localized strings
Posted by Salikh Zakirov <Sa...@Intel.com>.
(* I deliberately changed the subject to reflect the topic change *)
Alex Blewitt wrote:
> However, the argument is equivalent to:
> ...
Alex, thanks a lot for extensive explanation of why
Eclipse NLS approach is better. If I were in position
to decide how to localize the class library code,
you would have convinced me. However, I am mostly interested
in DRLVM and GC.
>From the general maintainability point of view, the NLS
approach requires complex tools to check consistency of
message catalogs and to help update them.
Are these tools available with the Eclipse?
The tasks I am thinking about are
1) Assume I need to print a localizable message. I would like Eclipse
to do automatically correct the code like
println("localizable string")
with a <magic key press> to
println(Messages.localizable_string);
and to have the field added to Messages.java automatically.
2) Assume I have been translating messages, and have the half-filled translations file.
How can I update it to get the yet untranslated strings and clean out the strings
no more referenced?
----8<---- below is the excellent explanation of advantages of Eclipse NLS approach by Alex
----8<---- for those who haven't read the thread " [drlvm] string interning in java"
Alex Blewitt wrote:
just to be clear; an intern()'d string (assuming GC on the intern()
pool, which I doubt it is) will stay around as long as there's a
reference, just like any other GC object in Java.
However, the argument is equivalent to:
public class Argument {
public void method() {
String local = reader.readLine();
}
}
versus
public class Argument {
private static List local = new ArrayList();
public void method() {
local.add(reader.readLine());
}
}
In the former, the object is eligible for GC at the end of the method.
In the latter, it's eligible for GC when the class is unloaded. It's
not a memory leak in the traditional C sense, but it *is* a leak of
resources that is programmer error. A constant string pool of:
public class Argument {
public void method() {
getMessage("Some Key That Is Going To Be In The Intern Table");
}
}
will remain in the constant pool/intern pool until Argument.class is
unloaded, whereas
public class Argument {
public void method() {
getMessage(Thing.message);
}
}
will *only* get loaded when the Thing.class is loaded (which will be
delayed until the method is invoked). Furthermore, if it is defined
as:
public class Thing {
private static String message;
static {
message = reader.readLine()
};
}
then there's *no* resource taken up by this until Thing.class is
loaded, which in turn only happens when the first class needs to use
it. Additionally, it doesn't pollute the intern() pool, and as such,
you get GC for free when Thing.class is unloaded (and thus doesn't
care whether the intern() pool is GC or not).
In the case we have a perfect intern() GC mechanism, there's no
significant difference. In the case we have an imperfect intern() GC
mechanism (like, there is no GC) then it's demonstrably better.
Regardless of which approach is used, it's also worth noting that if
there are several Thing.classes (e.g. one for exceptions, one for
debug messages, one for info messages) then you only load the class
(sic) of messages that you use. If you never do a
log.debug(Debug.message), then you'll never load the Debug.class, so
no resources would ever be taken up. (Same applies whether they're
dynamically read fields or hard-coded string literals.) OTOH our
current approach to messages (stick all messages in one place for one
module) somewhat defeats this benefit, because you trigger the loading
of all messages as soon as you need the first one. A slightly smarter
solution might be to have a single messages file (for ease of
management/translation) but many message classes (e.g. Info.class,
Debug.class, Exception.class) per module; that way, when the first
message is printed, you only load a sub-set of the messages for that
module.
Of course, one could put the argument forward that this is all
premature optimisation and thus we shouldn't do anything :-) But we
have a tool (Eclipse) that can do all of this for us at the moment,
and we've already got the experience of others investigating the
memory footprint of Eclipse and determining that the cause of memory
bloat was the String intern() calls; and the tools/mechanism to fix
this problem. We could, of course, reinvent the wheel (c.f. HashCode
object when there's a tool to generate decent hashCode()/equals()
implementations) -- but I'd be interested in knowing why our proposed
solution is better or what it gives us that the Eclipse NLS
infrastructure doesn't.
Oh, and for the record -- I think a GC intern() would be a cool idea.
Let's hope it happens, because there's bound to be programs that do
silly intern()'ing that need help. Hopefully Harmony doesn't need to
be one of them :-)
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: Re: [drlvm] string interning in java
Posted by Alex Blewitt <al...@gmail.com>.
On 29/07/06, Robert Lougher <ro...@gmail.com> wrote:
>
> Which implies that freeing of the dynamically loaded string when the
> class is unloaded is something special. It is not. Nor is an
> interned string a memory leak. It will be collected when there are no
> more references to it like any other object.
Just to be clear; an intern()'d string (assuming GC on the intern()
pool, which I doubt it is) will stay around as long as there's a
reference, just like any other GC object in Java.
However, the argument is equivalent to:
public class Argument {
public void method() {
String local = reader.readLine();
}
}
versus
public class Argument {
private static List local = new ArrayList();
public void method() {
local.add(reader.readLine());
}
}
In the former, the object is eligible for GC at the end of the method.
In the latter, it's eligible for GC when the class is unloaded. It's
not a memory leak in the traditional C sense, but it *is* a leak of
resources that is programmer error. A constant string pool of:
public class Argument {
public void method() {
getMessage("Some Key That Is Going To Be In The Intern Table");
}
}
will remain in the constant pool/intern pool until Argument.class is
unloaded, whereas
public class Argument {
public void method() {
getMessage(Thing.message);
}
}
will *only* get loaded when the Thing.class is loaded (which will be
delayed until the method is invoked). Furthermore, if it is defined
as:
public class Thing {
private static String message;
static {
message = reader.readLine()
};
}
then there's *no* resource taken up by this until Thing.class is
loaded, which in turn only happens when the first class needs to use
it. Additionally, it doesn't pollute the intern() pool, and as such,
you get GC for free when Thing.class is unloaded (and thus doesn't
care whether the intern() pool is GC or not).
In the case we have a perfect intern() GC mechanism, there's no
significant difference. In the case we have an imperfect intern() GC
mechanism (like, there is no GC) then it's demonstrably better.
Regardless of which approach is used, it's also worth noting that if
there are several Thing.classes (e.g. one for exceptions, one for
debug messages, one for info messages) then you only load the class
(sic) of messages that you use. If you never do a
log.debug(Debug.message), then you'll never load the Debug.class, so
no resources would ever be taken up. (Same applies whether they're
dynamically read fields or hard-coded string literals.) OTOH our
current approach to messages (stick all messages in one place for one
module) somewhat defeats this benefit, because you trigger the loading
of all messages as soon as you need the first one. A slightly smarter
solution might be to have a single messages file (for ease of
management/translation) but many message classes (e.g. Info.class,
Debug.class, Exception.class) per module; that way, when the first
message is printed, you only load a sub-set of the messages for that
module.
Of course, one could put the argument forward that this is all
premature optimisation and thus we shouldn't do anything :-) But we
have a tool (Eclipse) that can do all of this for us at the moment,
and we've already got the experience of others investigating the
memory footprint of Eclipse and determining that the cause of memory
bloat was the String intern() calls; and the tools/mechanism to fix
this problem. We could, of course, reinvent the wheel (c.f. HashCode
object when there's a tool to generate decent hashCode()/equals()
implementations) -- but I'd be interested in knowing why our proposed
solution is better or what it gives us that the Eclipse NLS
infrastructure doesn't.
Oh, and for the record -- I think a GC intern() would be a cool idea.
Let's hope it happens, because there's bound to be programs that do
silly intern()'ing that need help. Hopefully Harmony doesn't need to
be one of them :-)
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
RE: Re: [drlvm] string interning in java
Posted by Nathan Beyer <nb...@kc.rr.com>.
> -----Original Message-----
> From: Robert Lougher [mailto:rob.lougher@gmail.com]
> Sent: Saturday, July 29, 2006 5:28 AM
> To: harmony-dev@incubator.apache.org
> Subject: Re: Re: [drlvm] string interning in java
>
> On 7/29/06, Nathan Beyer <nb...@kc.rr.com> wrote:
> >
> >
> > > -----Original Message-----
> > > From: Robert Lougher [mailto:rob.lougher@gmail.com]
> > > Sent: Friday, July 28, 2006 7:40 PM
> > > To: harmony-dev@incubator.apache.org
> > > Subject: Re: Re: [drlvm] string interning in java
> > >
> > > Hi,
> > >
> > > On 7/29/06, Alex Blewitt <al...@gmail.com> wrote:
> > > > On 28/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> > > The interned String table should be garbage-collected. If the only
> > > reference to an interned String is from the class constant pool it
> > > will be collected when the class is unloaded. If the intern table is
> > > preventing Strings from being collected it's a bug in the VM!
> >
> > Can the String from a class constant pool be collected if the class is
> still
> > in use? I'm assuming it can't, so the above is an incomplete response to
> > Alex's points, as I imagine it's very possible to have many Strings in
> > constant pools that are never or rarely used, but the class objects are
> used
> > quite frequently and would never get collected. For example, the Strings
> > used in exceptions that rarely, if every get called in some classes.
> >
>
> It wasn't meant to be a complete response. I was responding to the
> following point:
I meant that your response to that point was incomplete and I still believe
it is.
>
> > > > Furthermore, because it's a
> > > > dynamically read in string, it doesn't pollute the intern() pool,
> and
> > > > thus when the class is unloaded, the string is unloaded too. Once a
> > > > String is intern()'d, it's like a memory leak -- you'll never see
> that
> > > > memory again.
>
> Which implies that freeing of the dynamically loaded string when the
> class is unloaded is something special. It is not. Nor is an
> interned string a memory leak. It will be collected when there are no
> more references to it like any other object.
>
> Rob.
This assumes that Classes will frequently get unloaded, which I don't
believe is the case, especially classes that are part of the core JRE
libraries.
Any String that's been placed into the constant pool of a Class couldn't be
collected until that Class is collected, correct? And all of the Strings in
the constant pool are taking up memory, correct? So, if you have a class and
the only Strings in the constant pool are those that represent exception
messages or keys to exception messages and those exceptions rarely get
executed, but the Class is frequently used (keeping it from being
collected), then you'd, theoretically, be wasting memory, correct?
-Nathan
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: [drlvm] string interning in java
Posted by Robert Lougher <ro...@gmail.com>.
On 7/29/06, Nathan Beyer <nb...@kc.rr.com> wrote:
>
>
> > -----Original Message-----
> > From: Robert Lougher [mailto:rob.lougher@gmail.com]
> > Sent: Friday, July 28, 2006 7:40 PM
> > To: harmony-dev@incubator.apache.org
> > Subject: Re: Re: [drlvm] string interning in java
> >
> > Hi,
> >
> > On 7/29/06, Alex Blewitt <al...@gmail.com> wrote:
> > > On 28/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> > The interned String table should be garbage-collected. If the only
> > reference to an interned String is from the class constant pool it
> > will be collected when the class is unloaded. If the intern table is
> > preventing Strings from being collected it's a bug in the VM!
>
> Can the String from a class constant pool be collected if the class is still
> in use? I'm assuming it can't, so the above is an incomplete response to
> Alex's points, as I imagine it's very possible to have many Strings in
> constant pools that are never or rarely used, but the class objects are used
> quite frequently and would never get collected. For example, the Strings
> used in exceptions that rarely, if every get called in some classes.
>
It wasn't meant to be a complete response. I was responding to the
following point:
> > > Furthermore, because it's a
> > > dynamically read in string, it doesn't pollute the intern() pool, and
> > > thus when the class is unloaded, the string is unloaded too. Once a
> > > String is intern()'d, it's like a memory leak -- you'll never see that
> > > memory again.
Which implies that freeing of the dynamically loaded string when the
class is unloaded is something special. It is not. Nor is an
interned string a memory leak. It will be collected when there are no
more references to it like any other object.
Rob.
> >
> -Nathan
>
> >
> > Rob.
> >
> > >
> > > Alex.
> > >
>
>
> ---------------------------------------------------------------------
> Terms of use : http://incubator.apache.org/harmony/mailing.html
> To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> For additional commands, e-mail: harmony-dev-help@incubator.apache.org
>
>
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
RE: Re: [drlvm] string interning in java
Posted by Nathan Beyer <nb...@kc.rr.com>.
> -----Original Message-----
> From: Robert Lougher [mailto:rob.lougher@gmail.com]
> Sent: Friday, July 28, 2006 7:40 PM
> To: harmony-dev@incubator.apache.org
> Subject: Re: Re: [drlvm] string interning in java
>
> Hi,
>
> On 7/29/06, Alex Blewitt <al...@gmail.com> wrote:
> > On 28/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> > > Alex Blewitt wrote:
> >
> > Importantly, it explains why the Eclipse NLS class uses static string
> > variables to refer to messages, and not to String literals for exactly
> > this reason. If you use a static string variable that is dynamically
> > initialised from a properties file, you only take the memory up when
> > you need to refer to that message (e.g. in the constructor of an
> > exception in an exceptional condition). Furthermore, because it's a
> > dynamically read in string, it doesn't pollute the intern() pool, and
> > thus when the class is unloaded, the string is unloaded too. Once a
> > String is intern()'d, it's like a memory leak -- you'll never see that
> > memory again.
>
> The interned String table should be garbage-collected. If the only
> reference to an interned String is from the class constant pool it
> will be collected when the class is unloaded. If the intern table is
> preventing Strings from being collected it's a bug in the VM!
Can the String from a class constant pool be collected if the class is still
in use? I'm assuming it can't, so the above is an incomplete response to
Alex's points, as I imagine it's very possible to have many Strings in
constant pools that are never or rarely used, but the class objects are used
quite frequently and would never get collected. For example, the Strings
used in exceptions that rarely, if every get called in some classes.
-Nathan
>
> Rob.
>
> >
> > Alex.
> >
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Robert Lougher wrote:
> The interned String table should be garbage-collected. If the only
> reference to an interned String is from the class constant pool it
> will be collected when the class is unloaded. If the intern table is
> preventing Strings from being collected it's a bug in the VM!
Exactly.
My original patch is intended at fixing this bug: making interned
strings garbage collectable.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: Re: [drlvm] string interning in java
Posted by Alex Blewitt <al...@gmail.com>.
On 29/07/06, Robert Lougher <ro...@gmail.com> wrote:
> The interned String table should be garbage-collected. If the only
> reference to an interned String is from the class constant pool it
> will be collected when the class is unloaded. If the intern table is
> preventing Strings from being collected it's a bug in the VM!
Garbage collection only occurs when there's no references left. String
literals in classes are stored in the constant pool; the constant pool
thus points to the (auto-intern()'d) Strings. So constant string
literals can never be garbage collected, regardless of whether an
intern()'d table is GC'd or not.
Ergo, any code of the form Message.get("some text") has just wasted
"somem text".length() chars in the intern() table permanently, until
that class gets unloaded, *regardless of whether that message is ever
used*
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: [drlvm] string interning in java
Posted by Robert Lougher <ro...@gmail.com>.
Hi,
On 7/29/06, Alex Blewitt <al...@gmail.com> wrote:
> On 28/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> > Alex Blewitt wrote:
>
> Importantly, it explains why the Eclipse NLS class uses static string
> variables to refer to messages, and not to String literals for exactly
> this reason. If you use a static string variable that is dynamically
> initialised from a properties file, you only take the memory up when
> you need to refer to that message (e.g. in the constructor of an
> exception in an exceptional condition). Furthermore, because it's a
> dynamically read in string, it doesn't pollute the intern() pool, and
> thus when the class is unloaded, the string is unloaded too. Once a
> String is intern()'d, it's like a memory leak -- you'll never see that
> memory again.
The interned String table should be garbage-collected. If the only
reference to an interned String is from the class constant pool it
will be collected when the class is unloaded. If the intern table is
preventing Strings from being collected it's a bug in the VM!
Rob.
>
> Alex.
>
> ---------------------------------------------------------------------
> Terms of use : http://incubator.apache.org/harmony/mailing.html
> To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> For additional commands, e-mail: harmony-dev-help@incubator.apache.org
>
>
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: [drlvm] string interning in java
Posted by Alex Blewitt <al...@gmail.com>.
On 28/07/06, Salikh Zakirov <Sa...@intel.com> wrote:
> Alex Blewitt wrote:
> > There's a heck of a lot wrong with intern()
>
> My original observation was that interning makes perfect sense
> for localized log messages, because the code like
>
> println(MessageBundle.get("how are you?"));
Yes, but I disagree with your conclusion; to me, it doesn't make
sense. Which is better, performance for printing out a message, or
memory requirements? Like I said, unless you are in a seriously
time-critical loop (in which case, you'd have to wonder why printing
out any kind of message at all is desired), the time taken to look up
the message from the bundle is really going to be of no/little
concern. However, by hard-coding the message like this, you're
guaranteeing that the VM will intern() the string "how are you?", even
if it never prints this message out (because it's in the constant
pool). Many, many, messages are never printed out in the course of a
normal code flow; yet they're all cached in the intern() pool, and in
fact, have to be because of the way that constant pools are supposed
to work.
So this 'perfect sense' is trading off speed of lookup of a message
for memory requirements, even if it's never used. If it's never used,
the speed of lookup is irrelivant (think exception messages like
'Invalid URL format') but it still takes up space.
Reading the Eclipse Performance Bloopoers is a very good summary of
the techniques taken by the Eclipse development team to try and limit
the amount of memory used, and should be read by anyone with an
interest in intern()'d strings, or for that matter, messages in
general:
http://wiki.eclipse.org/index.php/Performance_Bloopers
Importantly, it explains why the Eclipse NLS class uses static string
variables to refer to messages, and not to String literals for exactly
this reason. If you use a static string variable that is dynamically
initialised from a properties file, you only take the memory up when
you need to refer to that message (e.g. in the constructor of an
exception in an exceptional condition). Furthermore, because it's a
dynamically read in string, it doesn't pollute the intern() pool, and
thus when the class is unloaded, the string is unloaded too. Once a
String is intern()'d, it's like a memory leak -- you'll never see that
memory again.
Lastly, the Eclipse approach ensures that there are no String values
saved as keys anywhere in the system -- they're always referred to by
the static field contents. So regardless of whether they're intern()'d
or not, you are always comparing by reference anyway.
In other words, all of the benefits of intern(), and yet none of the
disadvantages. Remind me again why we're not using this method for
doing messages in Harmony?
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Mikhail Fursov <mi...@gmail.com>.
On 7/29/06, Salikh Zakirov <Sa...@intel.com> wrote:
>
> which is slowdown of about 1.5%.
>
> I will try to write a custom code instead of using WeakHashMap to reduce
> hash calculation.
>
> How about to make WeakHashMap (new empty subclass) final?
IMHO another one separate impl of HashMap could be a bad idea..
--
Mikhail Fursov
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Alex Blewitt wrote:
> There's a heck of a lot wrong with intern()
I agree with all of your points. Indeed, it makes little sense
doing a == b.intern() instead of a.equals(b).
My original observation was that interning makes perfect sense
for localized log messages, because the code like
println(MessageBundle.get("how are you?"));
is going to be translated to using LDC bytecode instruction,
which is in turn compiled into calling LDC runtime helper,
which interns string on the first call and caches it for
later invocations, so that for all subsequent executions
of this code will get interned string pointer very cheaply.
(it works this way in DRLVM)
So, I think the design of this particular part of Java system
is very clever.
Now, back to business. The pure java implementation I have tried
somewhat slows down the execution. Preallocation the hash array
large enough to avoid rehash() helps, but still it is slower
than the native code. I have measured the time to run Hello application on my laptop
(abount 300 total interned strings)
native intern: avg 0.267 +/- 0.001 = 26.980 / 101, min 0.257, max 0.347
java intern: avg 0.270 +/- 0.001 = 27.285 / 101, min 0.261, max 0.345
which is slowdown of about 1.5%.
I will try to write a custom code instead of using WeakHashMap to reduce hash calculation.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: Re: [drlvm] string interning in java
Posted by Alex Blewitt <al...@gmail.com>.
There's a heck of a lot wrong with intern().
1) People claim inefficiencies, without actually measuring them (see
other points I've made about permature optimisation)
2) The claim that performing an intern() reduces comparisons (because
you just do a pointer compare) is, in most cases, completely
irrelivant. When you perform an intern(), it has to search through all
previously intern()'d strings, and perform hashCode() and equals() on
each match it considers. Thus, a == b.intern() is equivalent to
a.hashCode()==b.hashCode() && a.equals(b) anyway. All you're doing is
moving where the delay happens.
It *really* gets on my nerves when developers do things like a ==
bufferedReader.readLine().intern() claiming that it speeds things up,
when the cost is just moving place. And in these situations, it's
their fault if they get out of OOM messages :-)
And with the point regarding 'fast lookup of messages' -- the Eclipse
messaging mechanism (by loading them into static variables) has
*exactly* the same effect, whilst not polluting any global pools.
Remember that pointer comparison will work when it's the same pointer,
and in the case it's not, it will do the equals() comparison. Unless
you're providing a really, really, really fast logging system then the
cost of printing/looking up a message is an unbelivably minor part of
a system. You probably have much more wastage in (e.g.)
StringBuffer().append(msg1).append(object).append(msg2), instead of
writer.write(msg1),write(object),write(msg2). For that matter,
parameterised messages (e.g. File {0} is broken) are going to cause
exactly these kind of StringBuffer-related horribleness.
The only time intern() should be used is by the compiler when
interning string literals in compiled source code. I'd go as far as
saying that the use of intern() should be marked as a warning, if not
an error, in any decent IDE.
Alex.
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Mikhail Fursov <mi...@gmail.com>.
Salikh,
I wonder why such an elegant solution haven't been made before?
The benefit of String.intern I know:
1) Fast comparison (May be we can speedup some internal algorithms like
reflection this way?)
2) Low memory consumption if there are a lot of duplicates
The overhead:
1) AFAIK every access to the weakmap must be synchronized.
On 7/28/06, Salikh Zakirov <Sa...@intel.com> wrote:
>
> Salikh Zakirov wrote:
> >> Subject: [PATCH] Pure java string intern()
>
> I have just been privately asked by a fellow colleague
> what the interning is used for.
> So I figured it would be nice to describe the answer on the list
> too, especially because I am interested in learning something new
> on the subject :)
>
> The most important reason I know is that interning
> is required by the specification.
>
> A particular use case I know is message localization: having string
> literals interned by default allows to optimize the lookup
> in the message bundles, as we can intern the keys on loading
> the bundle, and use object reference comparison later at lookup time.
>
> While I was working on the patch, there was a moment when I screwed
> the condition in intern() function, and it worked incorrectly,
> and returned incorrect strings sometimes. When I tried to run
> Eclipse with the bug, it complained about missing localization
> string and terminated by exception.
>
> Any other insights?
>
>
> ---------------------------------------------------------------------
> Terms of use : http://incubator.apache.org/harmony/mailing.html
> To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
> For additional commands, e-mail: harmony-dev-help@incubator.apache.org
>
>
--
Mikhail Fursov
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Salikh Zakirov wrote:
>> Subject: [PATCH] Pure java string intern()
I have just been privately asked by a fellow colleague
what the interning is used for.
So I figured it would be nice to describe the answer on the list
too, especially because I am interested in learning something new
on the subject :)
The most important reason I know is that interning
is required by the specification.
A particular use case I know is message localization: having string
literals interned by default allows to optimize the lookup
in the message bundles, as we can intern the keys on loading
the bundle, and use object reference comparison later at lookup time.
While I was working on the patch, there was a moment when I screwed
the condition in intern() function, and it worked incorrectly,
and returned incorrect strings sometimes. When I tried to run
Eclipse with the bug, it complained about missing localization
string and terminated by exception.
Any other insights?
---------------------------------------------------------------------
Terms of use : http://incubator.apache.org/harmony/mailing.html
To unsubscribe, e-mail: harmony-dev-unsubscribe@incubator.apache.org
For additional commands, e-mail: harmony-dev-help@incubator.apache.org
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
oops, forgot to include patches.
Salikh Zakirov wrote:
> Hi,
>
> I have been looking to the string interning code in DRLVM recently.
> The reason I have started to do this is that the following stress
> test quickly causes OOM (OutOfMemoryError) on DRLVM:
> ...
Re: [drlvm] string interning in java
Posted by Salikh Zakirov <Sa...@Intel.com>.
Salikh Zakirov wrote:
> I have been looking to the string interning code in DRLVM recently.
> ...
> Now I am going to attempt optimization of java code by using
> a customized weak hashmap implementation.
> By using it, I will be able to create just one weak reference
> to the interned string instead of current two, and to perform
> just one hash lookup instead of two on interning new string.
So I did it.
I have taken java.lang.WeakHashMap, trimmed all the irrelevant
code, and implemented intern() method, which returns the key
if the string is already present in the table, and stores
the string if it was not.
The optimized implementation brings little advantage,
here is the data (again, running Hello application on my laptop)
baseline: avg 0.265 +/- 0.001 = 26.511 / 100, min 0.254, max 0.319
WeakHashMap: avg 0.270 +/- 0.001 = 26.952 / 100, min 0.258, max 0.310
customized: avg 0.268 +/- 0.001 = 26.815 / 100, min 0.256, max 0.309
Thus, the optimized java implementation of interned strings
brings overhead down about 1%.
The patch to implement customized InternMap, based on WeakHashMap code
is attached.
Is anyone reviewing patches? I think it is genarally more convenient
to review patches sent to the list, because it is easy to hit "reply"
and put the comments inline to the particular code.
(This practice is widely used in other mailing lists I am looking through, e.g. Git)
I will file a JIRA with patches anyway to make sure the patch is not lost.
(in hope that it will be eventually applied)
--
Salikh Zakirov, Intel Middleware Products Division