Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] StackOverflowError compiling XOM

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: cowwoc <cowwoc AT bbs.darktech.org>
  • To: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] StackOverflowError compiling XOM
  • Date: Tue, 15 Jul 2008 02:10:54 -0400


I've generated a replacement for UnicodeUtil.getCombiningClass() that consists of 223 lines of code and runs approximately 20x faster than the original code (which consists of 1143 lines of code). Please see the attached file.

The next thing I would recommend optimizing is "UnicodeUtil.decompose(int character)". It is a whopping 6934 lines of code and is likely causing the most pain for compilers and obfuscators. You could either break this method down into multiple methods (since most of its execution is linear anyway) or replace the if-else statements with a switch block to improve performance but then reducing the method size is not as obvious.

There is a "FIXME must recurse this" beside it, so maybe you already have ideas for breaking it down?

Gili

cowwoc wrote:

By the way, this also causes major StackOverflowErrors for Proguard. Increasing the stack-size allows it to proceed further but then it crashes with:

IllegalArgumentException: Branch instruction can't be widened (goto_w+56833)

I've reported the problem to the author but this is yet another example of the headache caused by this code: http://sourceforge.net/forum/forum.php?thread_id=2120087&forum_id=182456

What kind of performance impact would you see by splitting this code across two methods? Secondly, looking at UnicodeUtil.getCombiningClass() I see quite a bit of wasted instructions. For example,

if (c == 0x0028) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;
if (c == 0x0029) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;
if (c == 0x002A) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;
if (c == 0x002B) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;
if (c == 0x002C) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;
if (c == 0x002D) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;

could be replaced by

if (c >= 0x0028 && c <= 0x002D) return CANONICAL_COMBINING_CLASS_NOT_REORDERED;

There are literally hundreds of such lines that could be folded down into a single line of code. In other words, this bug is fixable. If I manually optimize this code would you merge my changes into future releases?

Thank you,
Gili

cowwoc wrote:

Normally I would agree with you, but seeing as the reference implementation JDK has this problem and they do not plan on fixing it I think you should seriously reconsider: http://bugs.sun.com/view_bug.do?bug_id=6453531

To be clear, not only are you risking compiler crashes here, but also a severe runtime performance drop. Unless you know of a way to get this fixed through OpenJDK I suggest you make sure none of your own code surpasses the 8000 byte limit.

Gili

Elliotte Harold wrote:
cowwoc wrote:

There should definitely be a better way of mapping characters than dumping a whole slew of if statements into a method. Have you tried asking on the Java discussion forums?


There are such ways and I use them, but the goal is maximum efficiency at runtime, not working around compiler bugs. This is a real hot spot in XOM and some serious effort has gone into optimizing every last millisecond out of this. Check out my chapter in Beautiful Code for the details sometime.

The simple fact is that the most efficient way is table lookup (O(1)) based on carefully constructed switch statements with no holes. If it's legal code and a compiler can't handle it, then get a better compiler. I'm not going to slow XOM down to work around compiler bugs.



private static int getCombiningClass(int c) {
if ((c >= 0x0 && c <= 0x2FF) || (c == 0x34F) || (c >= 0x358 && c <=
0x35C) ||
(c >= 0x370 && c <= 0x482) || (c >= 0x487 && c <= 0x590) || (c ==
0x5A2) ||
(c == 0x5BA) || (c == 0x5BE) || (c == 0x5C0) || (c == 0x5C3) || (c >=
0x5C5 && c <= 0x60F) || (c >= 0x616 && c <= 0x64A) || (c >= 0x659 && c
<=
0x66F) || (c >= 0x671 && c <= 0x6D5) || (c >= 0x6DD && c <= 0x6DE) ||
(c >= 0x6E5 && c <= 0x6E6) || (c == 0x6E9) || (c >= 0x6EE && c <=
0x710) ||
(c >= 0x712 && c <= 0x72F) || (c >= 0x74B && c <= 0x93B) || (c >= 0x93D
&&
c <= 0x94C) || (c >= 0x94E && c <= 0x950) || (c >= 0x955 && c <= 0x9BB)
||
(c >= 0x9BD && c <= 0x9CC) || (c >= 0x9CE && c <= 0xA3B) || (c >= 0xA3D
&&
c <= 0xA4C) || (c >= 0xA4E && c <= 0xABB) || (c >= 0xABD && c <= 0xACC)
||
(c >= 0xACE && c <= 0xB3B) || (c >= 0xB3D && c <= 0xB4C) || (c >= 0xB4E
&&
c <= 0xBCC) || (c >= 0xBCE && c <= 0xC4C) || (c >= 0xC4E && c <= 0xC54)
||
(c >= 0xC57 && c <= 0xCBB) || (c >= 0xCBD && c <= 0xCCC) || (c >= 0xCCE
&&
c <= 0xD4C) || (c >= 0xD4E && c <= 0xDC9) || (c >= 0xDCB && c <= 0xE37)
||
(c >= 0xE3B && c <= 0xE47) || (c >= 0xE4C && c <= 0xEB7) || (c >= 0xEBA
&&
c <= 0xEC7) || (c >= 0xECC && c <= 0xF17) || (c >= 0xF1A && c <= 0xF34)
||
(c == 0xF36) || (c == 0xF38) || (c >= 0xF3A && c <= 0xF70) || (c ==
0xF73) ||
(c >= 0xF75 && c <= 0xF79) || (c >= 0xF7E && c <= 0xF7F) || (c ==
0xF81) ||
(c == 0xF85) || (c >= 0xF88 && c <= 0xFC5) || (c >= 0xFC7 && c <=
0x1036) ||
(c == 0x1038) || (c >= 0x103A && c <= 0x1713) || (c >= 0x1715 && c <=
0x1733) || (c >= 0x1735 && c <= 0x17D1) || (c >= 0x17D3 && c <= 0x17DC)
||
(c >= 0x17DE && c <= 0x18A8) || (c >= 0x18AA && c <= 0x1938) || (c >=
0x193C && c <= 0x20CF) || (c >= 0x20DD && c <= 0x20E0) || (c >= 0x20E2
&&
c <= 0x20E4) || (c >= 0x20EB && c <= 0x3029) || (c >= 0x3030 && c <=
0x3098) || (c >= 0x309B && c <= 0xFB1D) || (c >= 0xFB1F && c <= 0xFE1F)
||
(c >= 0xFE24 && c <= 0x1D164) || (c >= 0x1D16A && c <= 0x1D16C) || (c >=
0x1D173 && c <= 0x1D17A) || (c >= 0x1D183 && c <= 0x1D184) || (c >=
0x1D18C && c <= 0x1D1A9) || (c >= 0x1D1AE && c <= 0x10FFFD))
return CANONICAL_COMBINING_CLASS_NOT_REORDERED;

if ((c >= 0x334 && c <= 0x338) || (c >= 0x20D2 && c <= 0x20D3) || (c >=
0x20D8 && c <= 0x20DA) || (c >= 0x20E5 && c <= 0x20E6) || (c == 0x20EA)
||
(c >= 0x1D167 && c <= 0x1D169))
return CANONICAL_COMBINING_CLASS_OVERLAY;

if ((c == 0x93C) || (c == 0x9BC) || (c == 0xA3C) || (c == 0xABC) || (c ==
0xB3C) || (c == 0xCBC) || (c == 0x1037))
return CANONICAL_COMBINING_CLASS_NUKTA;

if (c >= 0x3099 && c <= 0x309A)
return CANONICAL_COMBINING_CLASS_KANA_VOICING;

if ((c == 0x94D) || (c == 0x9CD) || (c == 0xA4D) || (c == 0xACD) || (c ==
0xB4D) || (c == 0xBCD) || (c == 0xC4D) || (c == 0xCCD) || (c == 0xD4D)
||
(c == 0xDCA) || (c == 0xE3A) || (c == 0xF84) || (c == 0x1039) || (c ==
0x1714) || (c == 0x1734) || (c == 0x17D2))
return 9;

if (c == 0x5B0)
return CANONICAL_COMBINING_CLASS_10;

if (c == 0x5B1)
return CANONICAL_COMBINING_CLASS_11;

if (c == 0x5B2)
return CANONICAL_COMBINING_CLASS_12;

if (c == 0x5B3)
return CANONICAL_COMBINING_CLASS_13;

if (c == 0x5B4)
return CANONICAL_COMBINING_CLASS_14;

if (c == 0x5B5)
return CANONICAL_COMBINING_CLASS_15;

if (c == 0x5B6)
return CANONICAL_COMBINING_CLASS_16;

if (c == 0x5B7)
return CANONICAL_COMBINING_CLASS_17;

if (c == 0x5B8)
return CANONICAL_COMBINING_CLASS_18;

if (c == 0x5B9)
return CANONICAL_COMBINING_CLASS_19;

if (c == 0x5BB)
return CANONICAL_COMBINING_CLASS_20;

if (c == 0x5BC)
return CANONICAL_COMBINING_CLASS_21;

if (c == 0x5BD)
return CANONICAL_COMBINING_CLASS_22;

if (c == 0x5BF)
return CANONICAL_COMBINING_CLASS_23;

if (c == 0x5C1)
return CANONICAL_COMBINING_CLASS_24;

if (c == 0x5C2)
return CANONICAL_COMBINING_CLASS_25;

if (c == 0xFB1E)
return CANONICAL_COMBINING_CLASS_26;

if (c == 0x64B)
return CANONICAL_COMBINING_CLASS_27;

if (c == 0x64C)
return CANONICAL_COMBINING_CLASS_28;

if (c == 0x64D)
return CANONICAL_COMBINING_CLASS_29;

if (c == 0x64E)
return CANONICAL_COMBINING_CLASS_30;

if (c == 0x64F)
return CANONICAL_COMBINING_CLASS_31;

if (c == 0x650)
return CANONICAL_COMBINING_CLASS_32;

if (c == 0x651)
return CANONICAL_COMBINING_CLASS_33;

if (c == 0x652)
return CANONICAL_COMBINING_CLASS_34;

if (c == 0x670)
return CANONICAL_COMBINING_CLASS_35;

if (c == 0x711)
return CANONICAL_COMBINING_CLASS_36;

if (c == 0xC55)
return CANONICAL_COMBINING_CLASS_84;

if (c == 0xC56)
return CANONICAL_COMBINING_CLASS_91;

if (c >= 0xE38 && c <= 0xE39)
return CANONICAL_COMBINING_CLASS_103;

if (c >= 0xE48 && c <= 0xE4B)
return CANONICAL_COMBINING_CLASS_107;

if (c >= 0xEB8 && c <= 0xEB9)
return CANONICAL_COMBINING_CLASS_118;

if (c >= 0xEC8 && c <= 0xECB)
return CANONICAL_COMBINING_CLASS_122;

if (c == 0xF71)
return CANONICAL_COMBINING_CLASS_129;

if ((c == 0xF72) || (c >= 0xF7A && c <= 0xF7D) || (c == 0xF80))
return CANONICAL_COMBINING_CLASS_130;

if (c == 0xF74)
return CANONICAL_COMBINING_CLASS_132;

if ((c >= 0x321 && c <= 0x322) || (c >= 0x327 && c <= 0x328))
return CANONICAL_COMBINING_CLASS_ATTACHED_BELOW;

if ((c == 0x31B) || (c == 0xF39) || (c >= 0x1D165 && c <= 0x1D166) || (c
>=
0x1D16E && c <= 0x1D172))
return CANONICAL_COMBINING_CLASS_ATTACHED_ABOVE_RIGHT;

if (c == 0x302A)
return CANONICAL_COMBINING_CLASS_BELOW_LEFT;

if ((c >= 0x316 && c <= 0x319) || (c >= 0x31C && c <= 0x320) ||
(c >= 0x323 && c <= 0x326) || (c >= 0x329 && c <= 0x333) || (c >= 0x339
&&
c <= 0x33C) || (c >= 0x347 && c <= 0x349) || (c >= 0x34D && c <= 0x34E)
||
(c >= 0x353 && c <= 0x356) || (c == 0x591) || (c == 0x596) || (c ==
0x59B) ||
(c >= 0x5A3 && c <= 0x5A7) || (c == 0x5AA) || (c >= 0x655 && c <=
0x656) ||
(c == 0x6E3) || (c == 0x6EA) || (c == 0x6ED) || (c == 0x731) || (c ==
0x734) || (c >= 0x737 && c <= 0x739) || (c >= 0x73B && c <= 0x73C) ||
(c == 0x73E) || (c == 0x742) || (c == 0x744) || (c == 0x746) || (c ==
0x748) || (c == 0x952) || (c >= 0xF18 && c <= 0xF19) || (c == 0xF35) ||
(c == 0xF37) || (c == 0xFC6) || (c == 0x193B) || (c == 0x20E8) || (c >=
0x1D17B && c <= 0x1D182) || (c >= 0x1D18A && c <= 0x1D18B))
return CANONICAL_COMBINING_CLASS_BELOW;

if ((c == 0x59A) || (c == 0x5AD) || (c == 0x1939) || (c == 0x302D))
return CANONICAL_COMBINING_CLASS_BELOW_RIGHT;

if (c >= 0x302E && c <= 0x302F)
return CANONICAL_COMBINING_CLASS_LEFT;

if (c == 0x1D16D)
return CANONICAL_COMBINING_CLASS_RIGHT;

if ((c == 0x5AE) || (c == 0x18A9) || (c == 0x302B))
return CANONICAL_COMBINING_CLASS_ABOVE_LEFT;

if ((c >= 0x300 && c <= 0x314) || (c >= 0x33D && c <= 0x344) || (c ==
0x346) ||
(c >= 0x34A && c <= 0x34C) || (c >= 0x350 && c <= 0x352) || (c ==
0x357) ||
(c >= 0x363 && c <= 0x36F) || (c >= 0x483 && c <= 0x486) || (c >= 0x592
&&
c <= 0x595) || (c >= 0x597 && c <= 0x599) || (c >= 0x59C && c <= 0x5A1)
||
(c >= 0x5A8 && c <= 0x5A9) || (c >= 0x5AB && c <= 0x5AC) || (c ==
0x5AF) ||
(c == 0x5C4) || (c >= 0x610 && c <= 0x615) || (c >= 0x653 && c <=
0x654) ||
(c >= 0x657 && c <= 0x658) || (c >= 0x6D6 && c <= 0x6DC) || (c >= 0x6DF
&&
c <= 0x6E2) || (c == 0x6E4) || (c >= 0x6E7 && c <= 0x6E8) ||
(c >= 0x6EB && c <= 0x6EC) || (c == 0x730) || (c >= 0x732 && c <=
0x733) ||
(c >= 0x735 && c <= 0x736) || (c == 0x73A) || (c == 0x73D) ||
(c >= 0x73F && c <= 0x741) || (c == 0x743) || (c == 0x745) || (c ==
0x747) ||
(c >= 0x749 && c <= 0x74A) || (c == 0x951) || (c >= 0x953 && c <=
0x954) ||
(c >= 0xF82 && c <= 0xF83) || (c >= 0xF86 && c <= 0xF87) || (c ==
0x17DD) ||
(c == 0x193A) || (c >= 0x20D0 && c <= 0x20D1) || (c >= 0x20D4 && c <=
0x20D7) || (c >= 0x20DB && c <= 0x20DC) || (c == 0x20E1) || (c ==
0x20E7) ||
(c == 0x20E9) || (c >= 0xFE20 && c <= 0xFE23) || (c >= 0x1D185 && c <=
0x1D189) || (c >= 0x1D1AA && c <= 0x1D1AD))
return CANONICAL_COMBINING_CLASS_ABOVE;

if ((c == 0x315) || (c == 0x31A) || (c == 0x302C))
return CANONICAL_COMBINING_CLASS_ABOVE_RIGHT;

if ((c == 0x35F) || (c == 0x362))
return CANONICAL_COMBINING_CLASS_DOUBLE_BELOW;

if ((c >= 0x35D && c <= 0x35E) || (c >= 0x360 && c <= 0x361))
return CANONICAL_COMBINING_CLASS_DOUBLE_ABOVE;

if (c == 0x345)
return CANONICAL_COMBINING_CLASS_IOTA_SUBSCRIPT;

throw new IndexOutOfBoundsException(String.valueOf(c));
}


Archive powered by MHonArc 2.6.24.

Top of Page