You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by "Gaz Davidson (JIRA)" <ji...@apache.org> on 2010/08/26 10:21:53 UTC

[jira] Created: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

FloatingPointParser uses toLowerCase unnecessarily
--------------------------------------------------

                 Key: HARMONY-6635
                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
             Project: Harmony
          Issue Type: Improvement
         Environment: Android 2.2
            Reporter: Gaz Davidson


A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.

> if (s.toLowerCase().indexOf("0x") != -1) 

I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.

I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:

> if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 


-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Resolved: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Tim Ellison resolved HARMONY-6635.
----------------------------------

         Assignee: Tim Ellison
    Fix Version/s: 5.0M15
       Resolution: Fixed

Fair comment, so I changed it to parse
"0x1.P1", "0x113D4cc.P22", "3.141592654", "2.7182818284590452353602875"

and the results were as follows:

Current code, runs (ms) = 1281, 1266, 1360, 1390, 1266
New code, runs (ms) = 1156, 1157, 1141, 1141, 1157

Seems to show the new code is faster, but given I'm doing 40k parses here I'm not claiming its going to make a huge difference unless your application is really hammering the parse code.

I applied the patch to the LUNI module at repo revision r999724.

Gaz please can you confirm this is fixed to your satisfaction?


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Gaz Davidson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913355#action_12913355 ] 

Gaz Davidson commented on HARMONY-6635:
---------------------------------------

I'm quite new to this whole Java business and haven't recompiled Android yet, so can't really test it with the app I used to benchmark it in the first place, however, I've stuck a bunch of floats from an SVG file into an array of strings then run the offending line and its replacement in isolation. It's worth noting that this is a worst case scenario, these are the minimum size floats you're likely to see in the wild as it looks like they've been rounded by an SVG optimizer. Usually printf style floats are around 8 characters long.

The results are:

Test1: 313ms, 300ms, 198ms, 195ms, 192ms, 
Test2: 26ms, 24ms, 24ms, 38ms, 34ms,

So the new method is an order of magnitude faster. Nice work :-)


Test code and data follows:

public class FloatParserTest {

	private static String strings[] = { "-129.83", "103.065", "-129.327", "109.113", "-128.339", "115.682", "-126.6", "118.801", "-126.6", "118.801", "-130.2", "131.201", "-121.4", "144.401", "-121.4", "144.401", "-121.8", "151.601", "-120.2", "154.801", "-120.2", "154.801", "-116.2", "163.201", "-111.4", "164.001", "-107.516", "164.648", "-98.793", "167.717", "-88.932", "169.121", "-88.932", "169.121", "-71.8", "183.201", "-75", "196.001", "-75", "196.001", "-75.4", "212.401", "-79", "214.001", "-79", "214.001", "-67.4", "202.801", "-77", "219.601", "-81.4", "238.401", "-81.4", "238.401", "-55.8", "216.801", "-71.4", "235.201", "-81.4", "261.201", "-81.4", "261.201", "-61.8", "242.801", "-69", "251.201", "-72.2", "260.001", "-72.2", "260.001", "-29", "232.801", "-59.8", "262.401", "-59.8", "262.401", "-51.8", "258.801", "-47.4", "261.601", "-47.4", "261.601", "-40.6", "260.401", "-41.4", "262.001", "-41.4", "262.001", "-62.2", "272.401", "-65.8", "290.801", "-65.8", "290.801", "-57.4", "280.801", "-60.6", "291.601", "-60.2", "303.201", "-60.2", "303.201", "-56.2", "281.601", "-56.6", "319.201", "-56.6", "319.201", "-37.4", "301.201", "-49", "322.001", "-49", "338.801", "-49", "338.801", "-33.8", "322.401", "-40.2", "335.201", "-40.2", "335.201", "-30.2", "326.401", "-34.2", "341.601", "-34.2", "341.601", "-35", "352.001", "-30.6", "340.801", "-30.6", "340.801", "-14.6", "310.201", "-20.6", "336.401", "-20.6", "336.401", "-21.4", "355.601", "-16.6", "340.801", "-16.6", "340.801", "-16.2", "351.201", "-7", "358.401", "-7", "358.401", "-8.2", "307.601", "4.6", "343.601", "8.6", "360.001", "8.6", "360.001", "11.4", "350.801", "11", "345.601", "11", "345.601", "25.8", "329.201", "19", "353.601", "19", "353.601", "34.2", "330.801", "31", "344.001", "31", "344.001", "23.4", "360.001", "25", "364.801", "25", "364.801", "41.8", "330.001", "43", "328.401", "43", "328.401", "41", "370.802", "51.8", "334.801", "51.8", "334.801", "57.4", "346.801", "54.6", "351.201", "54.6", "351.201", "62.6", "343.201", "61.8", "340.001", "61.8", "340.001", "66.4", "331.801", "69.2", "345.401", "69.2", "345.401", "71", "354.801", "72.6", "351.601", "72.6", "351.601", "76.6", "375.602", "77.8", "352.801", "77.8", "352.801", "79.4", "339.201", "72.2", "327.601", "72.2", "327.601", "73", "324.401", "70.2", "320.401", "70.2", "320.401", "83.8", "342.001", "76.6", "313.201", "76.6", "313.201", "87.801", "321.201", "89.001", "321.201", "89.001", "321.201", "75.4", "298.001", "84.2", "302.801", "84.2", "302.801", "79", "292.401", "97.001", "304.401", "97.001", "304.401", "81", "288.401", "98.601", "298.001", "98.601", "298.001", "106.601", "304.401", "99.001", "294.401", "99.001", "294.401", "84.6", "278.401", "106.601", "296.401", "106.601", "296.401", "118.201", "312.801", "119.001", "315.601", "119.001", "315.601", "109.001", "286.401", "104.601", "283.601", "104.601", "283.601", "113.001", "247.201", "154.201", "262.801", "154.201", "262.801", "161.001", "280.001", "165.401", "261.601", "165.401", "261.601", "178.201", "255.201", "189.401", "282.801", "189.401", "282.801", "193.401", "269.201", "192.601", "266.401", "192.601", "266.401", "199.401", "267.601", "198.601", "266.401", "198.601", "266.401", "211.801", "270.801", "213.001", "270.001", "213.001", "270.001", "219.801", "276.801", "220.201", "273.201", "220.201", "273.201", "229.401", "276.001", "227.401", "272.401", "227.401", "272.401", "236.201", "288.001", "236.601", "291.601", "239.001", "277.601", "241.001", "280.401", "241.001", "280.401", "242.601", "272.801", "241.801", "271.601", "241.001", "270.401", "261.801", "278.401", "266.601", "299.201", "268.601", "307.601", "268.601", "307.601", "274.601", "292.801", "273.001", "288.801", "273.001", "288.801", "278.201", "289.601", "278.601", "294.001", "278.601", "294.001", "282.601", "270.801", "277.801", "264.801", "277.801", "264.801", "282.201", "264.001", "283.401", "267.601", "283.401", "260.401", "283.401", "260.401", "290.601", "261.201", "290.601", "258.801", "290.601", "258.801", "295.001", "254.801", "297.001", "259.601", "297.001", "259.601", "284.601", "224.401", "303.001", "243.601", "303.001", "243.601", "310.201", "254.401", "306.601", "235.601", "303.001", "216.801", "299.001", "215.201", "303.801", "214.801", "303.801", "214.801", "304.601", "211.201", "302.601", "209.601", "300.601", "208.001", "303.801", "209.601", "303.801", "209.601", "303.801", "209.601", "308.601", "213.601", "303.401", "191.601", "303.401", "191.601", "309.801", "193.201", "297.801", "164.001", "297.801", "164.001", "300.601", "161.601", "296.601", "153.201", "296.601", "153.201", "304.601", "157.601", "307.401", "156.001", "307.401", "156.001", "307.001", "154.401", "303.801", "150.401", "303.801", "150.401", "282.201", "95.6", "302.601", "117.601", "302.601", "117.601", "314.451", "131.151", "308.051", "108.351", "308.051", "108.351", "298.94", "84.341", "299.717", "80.045", "-129.83", "103.065"};
	
	public static void main(String[] args) {
		
		long start, time;
		int loops = 500000;
		
		System.out.print("Test1: ");
		
		for (int j=0; j < 5; ++j) {
			start = System.currentTimeMillis();
			for (int i=0; i < loops; ++i) {
				test1(strings[i % strings.length]);
			}
			time = System.currentTimeMillis() - start;
			System.out.print(String.valueOf(time) + "ms, ");
		}
		
		System.out.print("\nTest2: ");
		for (int j=0; j < 5; ++j) {
			start = System.currentTimeMillis();
			for (int i=0; i < loops; ++i) {
				test2(strings[i % strings.length]);
			}
			time = System.currentTimeMillis() - start;
			System.out.print(String.valueOf(time) + "ms, ");
		}
	}
	
	private static boolean test1(String s) { return (s.toLowerCase().indexOf("0x") != -1);  }

	private static boolean test2(String s) {
		int length = s.length();
		    if (length < 2) {
		        return false;
		    }
		    char first = s.charAt(0);
		    char second = s.charAt(1);
		    if (first == '+' || first == '-') {
		        // Move along
		        if (length < 3) {
		            return false;
		        }
		        first = second;
		        second = s.charAt(2);
		    }
		    return (first == '0') && (second == 'x' || second == 'X');
		}
}


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Hudson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913490#action_12913490 ] 

Hudson commented on HARMONY-6635:
---------------------------------

Integrated in Harmony-select-1.5-head-linux-x86_64 #115 (See [https://hudson.apache.org/hudson/job/Harmony-select-1.5-head-linux-x86_64/115/])
    Apply patch for HARMONY-6635 (FloatingPointParser uses toLowerCase unnecessarily)


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Gaz Davidson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913357#action_12913357 ] 

Gaz Davidson commented on HARMONY-6635:
---------------------------------------

Oh, I meant *best* case scenario.

And yes, very happy with the fix, thanks! I hope this makes it into Android 3.0 so I can begin using it!

> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Mark Hindess (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913293#action_12913293 ] 

Mark Hindess commented on HARMONY-6635:
---------------------------------------

Tim,

I imagine if your benchmark used a more typical selection of random floats - i.e. very few if any hex floats rather than only hex flows - then the times would be significantly better for the charAt version.  Obviously with 0x floats both find the 0x quickly but in long floats with no 0x the charAt should be a clear win since it only has to check the first 2-3 chars not the whole string.


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Closed: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Tim Ellison closed HARMONY-6635.
--------------------------------


Thanks Gaz.  I can't  influence if/when it goes into Android I'm afraid.

Send more issues :-)

> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Updated: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Tim Ellison (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Tim Ellison updated HARMONY-6635:
---------------------------------

    Attachment: harmony-6635.patch

I agree -- and the use of "indexOf" to search the entire string looks strange too.

It's a bit more complex than you suggest (but not much more), since there is an optional sign indicator.  Patch attached.

I wrote a simple benchmark with the toLowerCase/indexOf compared to a direct check, and there isn't too much in it..

--
Parse "0x1.P1" and "0x113D4cc.P22" about 40k times

Current code, runs (ms) =  2157, 2125, 2032, 2204, 2141
New code, runs (ms) = 1843, 1984, 2032, 1953
--

Do you have some benchmark or application you can try that might shows the difference more starkly?


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


[jira] Commented: (HARMONY-6635) FloatingPointParser uses toLowerCase unnecessarily

Posted by "Hudson (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/HARMONY-6635?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12913457#action_12913457 ] 

Hudson commented on HARMONY-6635:
---------------------------------

Integrated in Harmony-1.5-head-linux-x86_64 #956 (See [https://hudson.apache.org/hudson/job/Harmony-1.5-head-linux-x86_64/956/])
    Apply patch for HARMONY-6635 (FloatingPointParser uses toLowerCase unnecessarily)


> FloatingPointParser uses toLowerCase unnecessarily
> --------------------------------------------------
>
>                 Key: HARMONY-6635
>                 URL: https://issues.apache.org/jira/browse/HARMONY-6635
>             Project: Harmony
>          Issue Type: Improvement
>         Environment: Android 2.2
>            Reporter: Gaz Davidson
>            Assignee: Tim Ellison
>             Fix For: 5.0M15
>
>         Attachments: harmony-6635.patch
>
>
> A lot of time is being eaten inside FloatingPointParser.java calling String.toLowerCase when testing for "hex float" types.
> > if (s.toLowerCase().indexOf("0x") != -1) 
> I imagine that such hex float numbers are very rare, so this is a huge waste of time in the general case.
> I haven't tested this, but it looks to me like the string is already trimmed and so checking at a specific location should speed this up considerably:
> > if (s.size() > 2 && s.charAt(0) =='0' && (s.charAt(1) == 'x' || s.charAt(1) == 'X')) 

-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.