Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Java (http://www.velocityreviews.com/forums/f30-java.html)
-   -   Passing a Method Name to a Method, Redux (http://www.velocityreviews.com/forums/t750415-passing-a-method-name-to-a-method-redux.html)

Gene Wirchenko 06-23-2011 11:03 PM

Passing a Method Name to a Method, Redux
 
Dear Java'ers:

I have completed my benchmarking. The code is below. Note that
the difference in the bodies between ParseSequentialSearch(),
ParseBinarySearch(), and ParseTreesetSearch() is but one line. I
really would have preferred not having to duplicate the code.

Oddly, the timings have a LOT of noise in them. In some runs, a
sequential search has out-performed a binary search. Occasionally, a
sequential search has beaten both a binary search and a Treeset
search. The times for sequential searching are only a bit worse than
for binary searching. Treeset searching is about 20% faster. Any
explanations?

I had to kludge this:
cIdent=""+CurrChar;
cIdent is a String, CurrChar is a char.
cIdent=CurrChar;
does not compile.

So how would you have written this benchmark?

***** Start of Code *****
// TimingTesting
// Timing Testing of Character Searching
// Last Modification: 2011-06-23



import java.util.*;



class TimingTesting
{

static String cParseString=
"//identifier//IDENTIFIER//a_b_c abc123
4b5%$__dbl;one;two;three;END";

static String IdentChars=
"0123456789"+
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"+
"_"+
"abcdefghijklmnopqrstuvwxyz"; // sorted order!

static SortedSet<Character> IdentCharsSet=new TreeSet<Character>();

static int nRepetitions=1000000;



static boolean SequentialSearch
(
char CurrChar
)
{
boolean fFound=false;
for (int i=0; i<IdentChars.length() && !fFound; i++)
fFound=IdentChars.charAt(i)==CurrChar;
return fFound;
}



static boolean BinarySearch
(
char CurrChar
)
{
int xLow=0;
int xHigh=IdentChars.length()-1;
int xTry;
boolean fFound=false;
while (xLow<=xHigh)
{
xTry=(xLow+xHigh)/2;
if (CurrChar==IdentChars.charAt(xTry))
return true;
if (CurrChar<IdentChars.charAt(xTry))
xHigh=xTry-1;
else
xLow=xTry+1;
}
return false;
}



static boolean TreesetSearch
(
char CurrChar
)
{
return IdentCharsSet.contains(CurrChar);
}



static void ParseSequentialSearch()
{
int xScan=0;
boolean fBuildingIdent=false;
boolean fInIdentChars;
String cIdent=""; // fussy init
while (xScan<cParseString.length())
{
char CurrChar=cParseString.charAt(xScan);
fInIdentChars=SequentialSearch(CurrChar);
if (SequentialSearch(CurrChar)) // different code
if (fBuildingIdent)
cIdent+=CurrChar;
else
{
fBuildingIdent=true;
cIdent=""+CurrChar;
}
else
if (fBuildingIdent)
{
fBuildingIdent=false;
if (nRepetitions==1)
System.out.println(cIdent);
}
else
{}
xScan++;
}
if (fBuildingIdent)
if (nRepetitions==1)
System.out.println(cIdent);
}



static void ParseBinarySearch()
{
int xScan=0;
boolean fBuildingIdent=false;
boolean fInIdentChars;
String cIdent=""; // fussy init
while (xScan<cParseString.length())
{
char CurrChar=cParseString.charAt(xScan);
fInIdentChars=SequentialSearch(CurrChar);
if (SequentialSearch(CurrChar)) // different code
if (fBuildingIdent)
cIdent+=CurrChar;
else
{
fBuildingIdent=true;
cIdent=""+CurrChar;
}
else
if (fBuildingIdent)
{
fBuildingIdent=false;
if (nRepetitions==1)
System.out.println(cIdent);
}
else
{}
xScan++;
}
if (fBuildingIdent)
if (nRepetitions==1)
System.out.println(cIdent);
}



static void ParseTreesetSearch()
{
int xScan=0;
boolean fBuildingIdent=false;
boolean fInIdentChars;
String cIdent=""; // fussy init
while (xScan<cParseString.length())
{
char CurrChar=cParseString.charAt(xScan);
fInIdentChars=SequentialSearch(CurrChar);
if (TreesetSearch(CurrChar)) // different code
if (fBuildingIdent)
cIdent+=CurrChar;
else
{
fBuildingIdent=true;
cIdent=""+CurrChar;
}
else
if (fBuildingIdent)
{
fBuildingIdent=false;
if (nRepetitions==1)
System.out.println(cIdent);
}
else
{}
xScan++;
}
if (fBuildingIdent)
if (nRepetitions==1)
System.out.println(cIdent);
}



public static void main(String[] args)
{
int i;

long StartTime;
long EndTime;
long Duration;

System.out.println("Timing Testing of Character Searching");
System.out.println();

// Initialise Set.
for (i=0; i<IdentChars.length(); i++)
IdentCharsSet.add(IdentChars.charAt(i));

// Character Sequential
System.out.print("Character Sequential Search");
StartTime=System.nanoTime();
for (i=1; i<=nRepetitions; i++)
ParseSequentialSearch();
EndTime=System.nanoTime();
Duration=EndTime-StartTime;
System.out.println(" Duration="+Duration);

// Character Binary Search
System.out.print("Character Binary Search ");
StartTime=System.nanoTime();
for (i=1; i<=nRepetitions; i++)
ParseBinarySearch();
EndTime=System.nanoTime();
Duration=EndTime-StartTime;
System.out.println(" Duration="+Duration);

// Character Treeset
System.out.print("Character Treeset Search ");
StartTime=System.nanoTime();
for (i=1; i<=nRepetitions; i++)
ParseTreesetSearch();
EndTime=System.nanoTime();
Duration=EndTime-StartTime;
System.out.println(" Duration="+Duration);
}

}
***** End of Code *****

Sincerely,

Gene Wirchenko

Stefan Ram 06-23-2011 11:11 PM

Re: Passing a Method Name to a Method, Redux
 
Gene Wirchenko <genew@ocis.net> writes:
>So how would you have written this benchmark?


http://stackoverflow.com/questions/5...chmark-in-java
http://www.kdgregory.com/index.php?p...microBenchmark
http://www.ibm.com/developerworks/ja...225/index.html
....


Gene Wirchenko 06-23-2011 11:26 PM

Re: Passing a Method Name to a Method, Redux
 
On 23 Jun 2011 23:11:50 GMT, ram@zedat.fu-berlin.de (Stefan Ram)
wrote:

>Gene Wirchenko <genew@ocis.net> writes:
>>So how would you have written this benchmark?

>
>http://stackoverflow.com/questions/5...chmark-in-java
>http://www.kdgregory.com/index.php?p...microBenchmark
>http://www.ibm.com/developerworks/ja...225/index.html
>...


Good links. Thank you.

But my question was really about method calling to
SequentialSearch(), BinarySearch(), and TreesetSearch().

Sincerely,

Gene Wirchenko

markspace 06-24-2011 12:24 AM

Re: Passing a Method Name to a Method, Redux
 
On 6/23/2011 4:03 PM, Gene Wirchenko wrote:
>
> So how would you have written this benchmark?



Um, realistically? Is this really what you want to do?

static boolean TreesetSearch( char CurrChar ) {
return IdentCharsSet.contains( CurrChar );
}

All of the identifiers in your "language" are single characters?

I would have used actual strings, preferably from existing code so you
could test performance. Although I appreciate you making a
self-contained example for us'm here on usenet.


markspace 06-24-2011 12:34 AM

Re: Passing a Method Name to a Method, Redux
 
On 6/23/2011 4:03 PM, Gene Wirchenko wrote:
> search. The times for sequential searching are only a bit worse than
> for binary searching. Treeset searching is about 20% faster. Any
> explanations?



Why does your TreeSetSearch() call SequentialSearch? Doesn't that
defeat the purpose of your timing comparisons? I'm also not following
the parsing you are doing at all. What is the goal of that method?

static void ParseTreesetSearch()
{
int xScan = 0;
boolean fBuildingIdent = false;
boolean fInIdentChars;
String cIdent = ""; // fussy init
while( xScan < cParseString.length() ) {
char CurrChar = cParseString.charAt( xScan );
fInIdentChars = SequentialSearch( CurrChar );
^^^^^^^^^^^^^^^^
if( TreesetSearch( CurrChar ) ) // different code


Odd call indicated above. Doesn't that just do the exact same thing
that TreesetSearch does?


markspace 06-24-2011 01:30 AM

Re: Passing a Method Name to a Method, Redux
 
Some other things I'd do:


1. Make life easier on the Mark I eyeball and print out your timing in
seconds:

System.out.println( " Duration=" + (Duration/1e9) );


2. Specify your command line arguments. I found this affected the
timing greatly (over 100% faster than in the IDE) .


C:\Users\Brenden\Dev\Test2\src>javac -g:none test\CallingTest.java

C:\Users\Brenden\Dev\Test2\src>
C:\Users\Brenden\Dev\Test2\src>java -server test.CallingTest
Timing Testing of Character Searching

Character Sequential Search Duration=22.251718931
Character Binary Search Duration=21.492850347
Character Treeset Search Duration=19.472623928
Hash Test Duration=0.098741719

C:\Users\Brenden\Dev\Test2\src>

Joshua Cranmer 06-24-2011 02:36 AM

Re: Passing a Method Name to a Method, Redux
 
On 6/23/2011 4:03 PM, Gene Wirchenko wrote:
> Dear Java'ers:
>
> I have completed my benchmarking. The code is below. Note that
> the difference in the bodies between ParseSequentialSearch(),
> ParseBinarySearch(), and ParseTreesetSearch() is but one line. I
> really would have preferred not having to duplicate the code.
>
> Oddly, the timings have a LOT of noise in them. In some runs, a
> sequential search has out-performed a binary search. Occasionally, a
> sequential search has beaten both a binary search and a Treeset
> search. The times for sequential searching are only a bit worse than
> for binary searching. Treeset searching is about 20% faster. Any
> explanations?


Here is probably the best implementation:

static boolean[] isIdentifierChar;
static String slowSearch;
static void initIdentifierChars(String validChars) {
isIdentifierChar = new boolean[128];
for (char c : validChars.toCharArray())
if (c < 128)
isIdentifierChar[c] = true;
slowSearch = validChars;
}

static boolean isValidChar(char c) {
if (c >= 128)
return slowSearch.indexOf(c) >= 0;
return isIdentifieChar[c];
}

If it's really performance critical, you can just make the character
array the full 64K characters and skip the search, so testing for valid
identifiers is simply an index lookup.

There are other performance improvements:
1. Use StringBuilder. It's mutable, so it avoids copies (kind of like
ArrayList). Heck, that's what your code is doing, it just keeps copying
back and forth between strings.

2. It's probably better to throw out StringBuilder and use token extents
(i.e., from index 5 to 9 is this identifier). It saves copying and can
allow for better error messages in parsers by being able to pinpoint
line/column numbers accurately.

But yeah, I would have coded my benchmark like that. Since you seem to
be concerned with microoptimization here, anything which looks different
from what the real parser implementation would show up as having impact
in timing numbers.

Finally, I might add, if you're writing a full parser, it might be
better to just use an existing Java lexer rather than rolling your own
unless you have a *very* good reason not to.

--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth

Gene Wirchenko 06-24-2011 02:42 AM

Re: Passing a Method Name to a Method, Redux
 
On Thu, 23 Jun 2011 17:34:50 -0700, markspace <-@.> wrote:

>On 6/23/2011 4:03 PM, Gene Wirchenko wrote:
>> search. The times for sequential searching are only a bit worse than
>> for binary searching. Treeset searching is about 20% faster. Any
>> explanations?

>
>
>Why does your TreeSetSearch() call SequentialSearch? Doesn't that


I goofed.

>defeat the purpose of your timing comparisons? I'm also not following
>the parsing you are doing at all. What is the goal of that method?


I am parsing for identifiers. In this test, I just throw them
away.

[snip]

>Odd call indicated above. Doesn't that just do the exact same thing
>that TreesetSearch does?


Cut and paste did me in. Thank you for catching this.

Sincerely,

Gene Wirchenko

Gene Wirchenko 06-24-2011 02:46 AM

Re: Passing a Method Name to a Method, Redux
 
On Thu, 23 Jun 2011 17:24:43 -0700, markspace <-@.> wrote:

>On 6/23/2011 4:03 PM, Gene Wirchenko wrote:
>>
>> So how would you have written this benchmark?


>Um, realistically? Is this really what you want to do?
>
> static boolean TreesetSearch( char CurrChar ) {
> return IdentCharsSet.contains( CurrChar );
> }


Yes. I wanted a simple method call in the parser so I could
cut-and-paste. I did not know if I would need more than one call. I
am going to go with a Treeset so I will not have a separate method in
the implementation.

>All of the identifiers in your "language" are single characters?


No. An identifier is a sequence of one or more characters that
are in IdentChars (or IdentCharsSet).

>I would have used actual strings, preferably from existing code so you
>could test performance. Although I appreciate you making a
>self-contained example for us'm here on usenet.


I wanted an example. I have test files for when I have this
worked out.

Sincerely,

Gene Wirchenko

Gene Wirchenko 06-24-2011 02:48 AM

Re: Passing a Method Name to a Method, Redux
 
On Thu, 23 Jun 2011 18:30:21 -0700, markspace <-@.> wrote:

>Some other things I'd do:


>1. Make life easier on the Mark I eyeball and print out your timing in
>seconds:
>
> System.out.println( " Duration=" + (Duration/1e9) );


Yes, if this were not just test code.

>2. Specify your command line arguments. I found this affected the
>timing greatly (over 100% faster than in the IDE) .


There are none.

>C:\Users\Brenden\Dev\Test2\src>javac -g:none test\CallingTest.java
>
>C:\Users\Brenden\Dev\Test2\src>
>C:\Users\Brenden\Dev\Test2\src>java -server test.CallingTest
>Timing Testing of Character Searching
>
>Character Sequential Search Duration=22.251718931
>Character Binary Search Duration=21.492850347
>Character Treeset Search Duration=19.472623928
>Hash Test Duration=0.098741719

^^^^^^^^^
What is this one, please?

Sincerely,

Gene Wirchenko


All times are GMT. The time now is 12:44 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.