- The AST would take up less space in the long term
- Since Strings cache their hashcodes, having each identical string in the AST be the same object would reduce the number of hash calculations.
Without interning AST strings:
real 1m19.894s
user 1m18.649s
sys 0m0.920s
With interning AST strings:
real 1m15.021s
user 1m13.785s
sys 0m0.948s
So it's very measurable...in this case 4-5 seconds out of 80 seconds, or about a 6% gain with interning.
However this week I realized the fallacy of the second point above. In order to intern each incoming string, Java must hash them. This causes all strings entering the AST to be hashed once anyway in order to get the interned version. In fact, it could reduce performance, since we're now forced to hash strings we might never encounter during execution.
I can't confirm that this is 100% true, but it's a reasonable theory. String.intern() is native code, but logic dictates that the fastest way to intern strings would be to use an internal hash/symbol table. So I proceeded this evening to try removing interning to see how it affected performance. I hoped to get a small gain during execution due to a large gain during parsing. The numbers above show that I lose a measurable amount overall by interning. However, I do see substantial parse performance gains:
With interning AST strings (Time.now - t method of measuring 100 parses):
11.101
Without interning AST strings:
9.404
About 1.7 seconds out of 11, or a whopping 15% gain in parse speed without interning. AARGH.
At this point I'm leaning toward removing interning and swallowing the 6% performance hit temporarily until we can figure out where it's coming from. Logically, interning everything should only add overhead, or so my brain tells me. Where's the flaw in my logic?
Yuri is right, but you might want to at least intern() all keywords and possibly operators. They are few enough but frequent enough that they should help a little without the negative impact on the size of interned strings table.
ReplyDeleteSpeaking of Strings though, I just had a quick look at the JRuby source. I noticed that there are quite a few heavily used calls to Ruby.newString() where a StringBuffer is being converted to a String before being passed as a parameter. Now the RubyString constructor that eventually gets called takes a CharSequence, so you could save the hit to GC by just passing the StringBuffer (provided the SB is a local variable that has no other references to it, which was the case in every call I saw). If you change the newString() parameter to take a CharSequence, you can incrementally change the rest of the code to use it.
BTW, I tried to SVN the code but it failed, at least with RapidSVN. I'd certainly consider contributing fixes (driven by inspection, manual tests and use of a profiler) but I'd need SVN access or at least a reasonable likelihood that my patches would be applied even if they were against a snapshot of the code.
Well, best of luck with JRuby performance!
From the Eclipse performance bloopers page (via javaperformancetuning.com):
ReplyDelete# String.intern() often degrades performance, dramatically in some cases depending on usage and JVM.Interning strings eagerly and early fills the intern table with increasingly more collisions - the intern table is often a static size.
# Use a private table rather than the String.intern table.
--------------------
java's HashMap is great, give a private table a shot.
One interesting idea to read about is "minimally perfect hashing" which is kind of relevant to the problem here.
I understand the attractiveness of low hanging fruit, but I'd take a whack at the problem with a profiler before doing much else.