Issue 312250043: #12873 RuleBasedBreakIterator clone() bug (Closed)
|
Created:
7 years, 3 months ago by andy.heninger Modified:
6 years, 11 months ago Reviewers:
sffc Base URL:
svn+ssh://source.icu-project.org/repos/icu/trunk/icu4j/ Visibility:
Public. |
Description#12873 RuleBasedBreakIterator clone() bug
Patch Set 1 #
Total comments: 11
Patch Set 2 : restore BreakEngine sharing. #
Total comments: 15
Patch Set 3 : Incorporate review comments. #
MessagesTotal messages: 12
https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1132: try { Note: the diff program is confused through here. The try...catch block is unchanged, aside from no longer being within an else block.
Sign in to reply to this message.
https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:271: private UnhandledBreakEngine fUnhandledBreakEngine = new UnhandledBreakEngine(); Why no more final? If it's only because of the clone function, you could consider making the clone function call a copy constructor instead, so that the copy constructor can write to the final fields. public Object clone() { return new RuleBasedBreakIterator(this); } private RuleBasedBreakIterator(RuleBasedBreakIterator other) { ... } https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:289: new ConcurrentHashMap<Integer, LanguageBreakEngine>(); Does this still need to be a ConcurrentHashMap, or would a HashMap be ok? (Concurrent data structures in Java are really slow) https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1117: for (LanguageBreakEngine candidate : fBreakEngines.values()) { I don't think you're ever using the map functionality of fBreakEngines. You always loop through it like an array when searching for the candidate. Should you add a line like this at the top of the function? LanguageBreakEngine candidate = fBreakEngines.get(script); if (candidate != null && candidate.handles(c, fBreakType)) { return candidate; } This would require moving the script-calculating code to the top of the function as well. The alternative would be to change the data structure of fBreakEngines from a HashMap to an ArrayList. https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1172: if (eng != null && eng != fUnhandledBreakEngine) { Is there a reason we aren't storing the reference to fUnhandledBreakEngine in fBreakEngines for the script? https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:55: public void handleChar(int c, int breakType) { What's the reason for removing the synchronized? Is RuleBasedBreakIterator the only other class that uses this class?
Sign in to reply to this message.
https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:271: private UnhandledBreakEngine fUnhandledBreakEngine = new UnhandledBreakEngine(); On 2017/01/07 22:39:39, sffc wrote: > Why no more final? If it's only because of the clone function, you could > consider making the clone function call a copy constructor instead, so that the > copy constructor can write to the final fields. > > public Object clone() { return new RuleBasedBreakIterator(this); } > private RuleBasedBreakIterator(RuleBasedBreakIterator other) { ... } It's only because of the clone function needing to set the field. There is no existing copy constructor. Even if there were, it wouldn't work if someone had made a subclass of RuleBasedBreakIterator, and tried to clone that. It's not a particularly likely scenario, but not forbidden, and should work if someone does do it. https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:289: new ConcurrentHashMap<Integer, LanguageBreakEngine>(); On 2017/01/07 22:39:39, sffc wrote: > Does this still need to be a ConcurrentHashMap, or would a HashMap be ok? > (Concurrent data structures in Java are really slow) No, it doesn't need to be concurrent, a plain hashmap would be fine. I left it concurrent because I think, in the long term, sharing makes sense and the Concurrent map might return. But it's probably less confusing to take it out. https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1117: for (LanguageBreakEngine candidate : fBreakEngines.values()) { On 2017/01/07 22:39:39, sffc wrote: > I don't think you're ever using the map functionality of fBreakEngines. You > always loop through it like an array when searching for the candidate. Should > you add a line like this at the top of the function? > > LanguageBreakEngine candidate = fBreakEngines.get(script); > if (candidate != null && candidate.handles(c, fBreakType)) { > return candidate; > } > > This would require moving the script-calculating code to the top of the function > as well. > > The alternative would be to change the data structure of fBreakEngines from a > HashMap to an ArrayList. You're right. As best as I can reconstruct it, fBreakEngines used to be a Set, was replaced with ConcurrentHashMap for the concurrency, which is no longer relevant. A list should be fine. https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1172: if (eng != null && eng != fUnhandledBreakEngine) { On 2017/01/07 22:39:39, sffc wrote: > Is there a reason we aren't storing the reference to fUnhandledBreakEngine in > fBreakEngines for the script? Not that I know of, but I don't want to change that logic in the context of fixing this specific bug. The C++ code does indeed add the UnhandledBreakEngine to the list. https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:55: public void handleChar(int c, int breakType) { On 2017/01/07 22:39:39, sffc wrote: > What's the reason for removing the synchronized? Is RuleBasedBreakIterator the > only other class that uses this class? Yes, the class is internal to ICU and RuleBasedBreakIterator is the only user. After the change to clone(), I don't think there is any way to share an UnhandledBreakEngine between break iterators, and the BreakIterator functions that can call to here are explicitly not thread safe when used on the same BreakIterator object. If the UnhandledBreakEngine were shared, handles() and findBreaks() would also need to be synchronized because they are referencing things (fHandled) that are modified by this function (handleChar()).
Sign in to reply to this message.
On 2017/01/09 00:20:09, andy.heninger wrote: > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:271: private > UnhandledBreakEngine fUnhandledBreakEngine = new UnhandledBreakEngine(); > On 2017/01/07 22:39:39, sffc wrote: > > Why no more final? If it's only because of the clone function, you could > > consider making the clone function call a copy constructor instead, so that > the > > copy constructor can write to the final fields. > > > > public Object clone() { return new RuleBasedBreakIterator(this); } > > private RuleBasedBreakIterator(RuleBasedBreakIterator other) { ... } > > It's only because of the clone function needing to set the field. > > There is no existing copy constructor. Even if there were, it wouldn't work if > someone had made a subclass of RuleBasedBreakIterator, and tried to clone that. > It's not a particularly likely scenario, but not forbidden, and should work if > someone does do it. > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:289: new > ConcurrentHashMap<Integer, LanguageBreakEngine>(); > On 2017/01/07 22:39:39, sffc wrote: > > Does this still need to be a ConcurrentHashMap, or would a HashMap be ok? > > (Concurrent data structures in Java are really slow) > > No, it doesn't need to be concurrent, a plain hashmap would be fine. > I left it concurrent because I think, in the long term, sharing makes sense and > the Concurrent map might return. But it's probably less confusing to take it > out. > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1117: for > (LanguageBreakEngine candidate : fBreakEngines.values()) { > On 2017/01/07 22:39:39, sffc wrote: > > I don't think you're ever using the map functionality of fBreakEngines. You > > always loop through it like an array when searching for the candidate. Should > > you add a line like this at the top of the function? > > > > LanguageBreakEngine candidate = fBreakEngines.get(script); > > if (candidate != null && candidate.handles(c, fBreakType)) { > > return candidate; > > } > > > > This would require moving the script-calculating code to the top of the > function > > as well. > > > > The alternative would be to change the data structure of fBreakEngines from a > > HashMap to an ArrayList. > > You're right. As best as I can reconstruct it, fBreakEngines used to be a Set, > was replaced with ConcurrentHashMap for the concurrency, which is no longer > relevant. A list should be fine. > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1172: if (eng > != null && eng != fUnhandledBreakEngine) { > On 2017/01/07 22:39:39, sffc wrote: > > Is there a reason we aren't storing the reference to fUnhandledBreakEngine in > > fBreakEngines for the script? > > Not that I know of, but I don't want to change that logic in the context of > fixing this specific bug. The C++ code does indeed add the UnhandledBreakEngine > to the list. > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): > > https://codereview.appspot.com/312250043/diff/1/main/classes/core/src/com/ibm... > main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:55: public void > handleChar(int c, int breakType) { > On 2017/01/07 22:39:39, sffc wrote: > > What's the reason for removing the synchronized? Is RuleBasedBreakIterator > the > > only other class that uses this class? > > Yes, the class is internal to ICU and RuleBasedBreakIterator is the only user. > After the change to clone(), I don't think there is any way to share an > UnhandledBreakEngine between break iterators, and the BreakIterator functions > that can call to here are explicitly not thread safe when used on the same > BreakIterator object. > > If the UnhandledBreakEngine were shared, handles() and findBreaks() would also > need to be synchronized because they are referencing things (fHandled) that are > modified by this function (handleChar()). Can you upload your latest patch if you made any changes? Thanks
Sign in to reply to this message.
restore BreakEngine sharing.
Sign in to reply to this message.
https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:276: private static UnhandledBreakEngine gUnhandledBreakEngine; You can make it final again. Bring the "gUnhandledBreakEngine = ..." line up here. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:286: private static List<LanguageBreakEngine> gAllBreakEngines; Again, make it final. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1153: fBreakEngines.add(candidate); I like this pattern a lot: having a global synchronized cache plus a local fast-access copy of any objects taken from the global cache. Straightforward and no weird concurrency issues. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:38: AtomicReferenceArray<UnicodeSet> fHandled = new AtomicReferenceArray<UnicodeSet>(BreakIterator.KIND_TITLE + 1); Why does this need to be an AtomicReferenceArray? (Also, you can make it final) https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:72: public synchronized void handleChar(int c, int breakType) { I don't think this needs to be synchronized any more, since this method is only called when you have a lock on gAllBreakEngines. Avoid the overhead of getting a lock on this object. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:76: // System.out.printf("UnhandledBreakEngine.handleChar(%x, %d)\n", c, breakType); Remove this line https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:78: UnicodeSet newSet = new UnicodeSet(); Can you call originalSet.clone() instead? Would that be faster? Or maybe the copy constructor? (Note: originalSet.clone() returns a frozen object if the source object is frozen.) https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:81: fHandled.set(breakType, newSet); Optional: you could freeze the UnicodeSet since you never modify it. You should benchmark though to make sure that the overhead of freezing the set is worth it.
Sign in to reply to this message.
https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:276: private static UnhandledBreakEngine gUnhandledBreakEngine; On 2017/01/13 07:01:01, sffc wrote: > You can make it final again. Bring the "gUnhandledBreakEngine = ..." line up > here. Acknowledged. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:286: private static List<LanguageBreakEngine> gAllBreakEngines; On 2017/01/13 07:01:01, sffc wrote: > Again, make it final. Acknowledged. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1153: fBreakEngines.add(candidate); On 2017/01/13 07:01:01, sffc wrote: > I like this pattern a lot: having a global synchronized cache plus a local > fast-access copy of any objects taken from the global cache. Straightforward > and no weird concurrency issues. Thanks! https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:38: AtomicReferenceArray<UnicodeSet> fHandled = new AtomicReferenceArray<UnicodeSet>(BreakIterator.KIND_TITLE + 1); On 2017/01/13 07:01:01, sffc wrote: > Why does this need to be an AtomicReferenceArray? (Also, you can make it final) It's needed because handles(), findBreaks() and handleChar() can be called concurrently, without synchronization. AtomicReferenceArray is really an array of volatiles, which have read-acquire and write-release memory behavior. Suppose thread A has called handleChar(), and is replacing the UnicodeSet reference in fHandled for some breakType, while thread B is calling handles() or findBreaks(). The write-release behavior from thread A ensures that no part of the initialization of the UnicodeSet itself is reordered after the store into fHandled. The read-acquire in thread B ensures that no access to the UnicodeSet (from contains()) is reordered before the read from fHandled, which is to say, no compiler optimized caching of the UnicodeSet reference. Yes, fHandled could be final. Maybe we should have a wider discussion on whether everything that could be final should be final. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:72: public synchronized void handleChar(int c, int breakType) { On 2017/01/13 07:01:01, sffc wrote: > I don't think this needs to be synchronized any more, since this method is only > called when you have a lock on gAllBreakEngines. Avoid the overhead of getting > a lock on this object. I think you're right. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:78: UnicodeSet newSet = new UnicodeSet(); On 2017/01/13 07:01:01, sffc wrote: > Can you call originalSet.clone() instead? Would that be faster? Or maybe the > copy constructor? (Note: originalSet.clone() returns a frozen object if the > source object is frozen.) No. applyIntPropertyValue() clears any previous set contents, so must be done first. The original code is buggy because of this. https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:81: fHandled.set(breakType, newSet); On 2017/01/13 07:01:01, sffc wrote: > Optional: you could freeze the UnicodeSet since you never modify it. You should > benchmark though to make sure that the overhead of freezing the set is worth it. As you say, would need benchmarking, not sure if it would be worth it.
Sign in to reply to this message.
On 2017/01/16 07:03:51, andy.heninger wrote: > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > File main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java (right): > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:276: private > static UnhandledBreakEngine gUnhandledBreakEngine; > On 2017/01/13 07:01:01, sffc wrote: > > You can make it final again. Bring the "gUnhandledBreakEngine = ..." line up > > here. > > Acknowledged. > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:286: private > static List<LanguageBreakEngine> gAllBreakEngines; > On 2017/01/13 07:01:01, sffc wrote: > > Again, make it final. > > Acknowledged. > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/RuleBasedBreakIterator.java:1153: > fBreakEngines.add(candidate); > On 2017/01/13 07:01:01, sffc wrote: > > I like this pattern a lot: having a global synchronized cache plus a local > > fast-access copy of any objects taken from the global cache. Straightforward > > and no weird concurrency issues. > > Thanks! > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > File main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java (right): > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:38: > AtomicReferenceArray<UnicodeSet> fHandled = new > AtomicReferenceArray<UnicodeSet>(BreakIterator.KIND_TITLE + 1); > On 2017/01/13 07:01:01, sffc wrote: > > Why does this need to be an AtomicReferenceArray? (Also, you can make it > final) > > It's needed because handles(), findBreaks() and handleChar() can be called > concurrently, without synchronization. AtomicReferenceArray is really an array > of volatiles, which have read-acquire and write-release memory behavior. Suppose > thread A has called handleChar(), and is replacing the UnicodeSet reference in > fHandled for some breakType, while thread B is calling handles() or > findBreaks(). The write-release behavior from thread A ensures that no part of > the initialization of the UnicodeSet itself is reordered after the store into > fHandled. The read-acquire in thread B ensures that no access to the UnicodeSet > (from contains()) is reordered before the read from fHandled, which is to say, > no compiler optimized caching of the UnicodeSet reference. > > Yes, fHandled could be final. Maybe we should have a wider discussion on whether > everything that could be final should be final. > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:72: public > synchronized void handleChar(int c, int breakType) { > On 2017/01/13 07:01:01, sffc wrote: > > I don't think this needs to be synchronized any more, since this method is > only > > called when you have a lock on gAllBreakEngines. Avoid the overhead of > getting > > a lock on this object. > > I think you're right. > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:78: UnicodeSet > newSet = new UnicodeSet(); > On 2017/01/13 07:01:01, sffc wrote: > > Can you call originalSet.clone() instead? Would that be faster? Or maybe the > > copy constructor? (Note: originalSet.clone() returns a frozen object if the > > source object is frozen.) > > No. applyIntPropertyValue() clears any previous set contents, so must be done > first. The original code is buggy because of this. > > https://codereview.appspot.com/312250043/diff/20001/main/classes/core/src/com... > main/classes/core/src/com/ibm/icu/text/UnhandledBreakEngine.java:81: > fHandled.set(breakType, newSet); > On 2017/01/13 07:01:01, sffc wrote: > > Optional: you could freeze the UnicodeSet since you never modify it. You > should > > benchmark though to make sure that the overhead of freezing the set is worth > it. > > As you say, would need benchmarking, not sure if it would be worth it. Hi, if there were any code changes can you upload them? Thanks.
Sign in to reply to this message.
Incorporate review comments.
Sign in to reply to this message.
On 2017/01/17 21:47:28, andy.heninger wrote: > Incorporate review comments. LSTM Please remember to add final to fHandled.
Sign in to reply to this message.
On 2017/01/17 22:42:41, sffc wrote: > On 2017/01/17 21:47:28, andy.heninger wrote: > > Incorporate review comments. > > LSTM > > Please remember to add final to fHandled. LGTM
Sign in to reply to this message.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
