[ https://issues.apache.org/jira/browse/LANG-1206?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Pascal Schumacher resolved LANG-1206. ------------------------------------- Resolution: Fixed Assignee: Pascal Schumacher Fix Version/s: (was: 3.4) 3.5 Patch applied. Thanks! > Improve CharSetUtils.squeeze() performance > ------------------------------------------ > > Key: LANG-1206 > URL: https://issues.apache.org/jira/browse/LANG-1206 > Project: Commons Lang > Issue Type: Improvement > Components: lang.* > Affects Versions: 3.4 > Reporter: Mohammed Alfallaj > Assignee: Pascal Schumacher > Labels: patch, performance > Fix For: 3.5 > > Attachments: CharSetUtils_squeeze_performance_issue.patch, > Description_Squeeze.docx > > > Before reading the description below, please note that there was an issue > created in 10/Jul/2011 titled "CharSetUtils.squeeze() speedup" LANG-715. This > solution does not prevent the repetitive calls to the expensive contains() > method explained below. In addition, I updated this to (major) because of the > high CPU cost of the current solution. > A readable form of the description is attached in Description_Squeeze.docx. > Below is a text format of the description (in case the .docx does not work): > *********************************************************************** > Performance problems of current CharSetUtils.squeeze() algorithm: > *********************************************************************** > ************************************ > FIRST PROBLEM: > ************************************ > -Method org.apache.commons.lang3.CharSet.contains() is called in each > character iteration for a consecutive set of duplicated characters in str > (starting from the second character in the duplicated set). This large number > of calls to contains() are determined to increase the performance overhead > for squeeze() calls given the high computing cost of executing contains() > method. Note that only one call to contains() is needed for the second > character in this set of duplicated characters. There is no need to repeat > the calls to contains() method for the same duplicated character that we have > already checked in the second occurrence. For example, if str=”abbbbbc” and > set=”b”, then the algorithm should call contains() only once for the second b > character occurrence and prevent calling contains() again given that it has > already been called before for this block. The current algorithm adds high > performance overhead by calling contains() repetitively for each duplicated b > character starting from the second occurrence. For this example where > str=”abbbbbc” and set=”b”, the suggested solution will call contains() method > only once instead of 4 times which will largely reduce the performance > overhead of squeeze() method. > -Consider the following example, System.currentTimeMillis() testing shows a > performance improvement by around 83% if we run the suggested enhanced > solution with the following sample input data > str = > “abbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbc” > set = “b” > ************************************ > PROPOSED SOLUTION FOR FIRST PROBLEM: > ************************************ > -Using two character flags inChars and notInChars: > inChars: flag to record the recent character that has been determined > to be in chars CharSet > notInChars: flag to record the recent character that has been > determined to NOT be in chars CharSet > -Adding the following conditions to prevent unnecessary/expensive calls to > contains() method. Only one call to contains() method is needed starting from > the second character in the consecutive set of duplicated characters: > if ((inChars != null) && (ch == inChars)) > this if-statement checks if this ch char has recently been > determined to be in chars CharSet, this prevents calling contains() more than > once for a consecutive set of duplicated characters in str > if one of these conditions fails, it means that the consecutive > set of duplicated characters for this ch character has not yet been checked > for this block of duplicated characters (i.e. has not been checked = we have > not yet done the one-time call to contains method for this particular set of > duplicated characters) > if ((notInChars == null) || (ch != notInChars)) > if both conditions are false, it means that ch has recently > been determined to NOT be in chars CharSet > if (chars.contains(ch)) > here we call the expensive chars.contains() only once for this > consecutive set of duplicated characters. > -Note: this suggested solution does not break the functionality of > org.apache.commons.lang3.CharSetUtils.squeeze(String str, String… set). This > suggested solution is executed against the latest UnitTest > CharSetUtilsTest.java written by Apache. > ************************************ > SECOND PROBLEM: > ************************************ > the current algorithm starts the for-loop with i=0 which is not a necessary > step. This adds the overhead of executing the if condition (i != 0). In this > logic, the algorithm will always append the first character from str to the > buffer. So there is no need to execute (i != 0) for every character in the > consecutive set of duplicated characters. > ************************************ > PROPOSED SOLUTION FOR SECOND PROBLEM: > ************************************ > lastChar is assigned the first character in str and appended to buffer before > executing the for loop. Then the for loop begins with i=1 removing the > unnecessary (i != 0) executions. > END OF DESCRIPTION -- This message was sent by Atlassian JIRA (v6.3.4#6332)