Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > Passing a Method Name to a Method, Redux

Reply
Thread Tools

Passing a Method Name to a Method, Redux

 
 
Gene Wirchenko
Guest
Posts: n/a
 
      06-23-2011
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
 
Reply With Quote
 
 
 
 
Stefan Ram
Guest
Posts: n/a
 
      06-23-2011
Gene Wirchenko <(E-Mail Removed)> 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
....

 
Reply With Quote
 
 
 
 
Gene Wirchenko
Guest
Posts: n/a
 
      06-23-2011
On 23 Jun 2011 23:11:50 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed)-berlin.de (Stefan Ram)
wrote:

>Gene Wirchenko <(E-Mail Removed)> 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
 
Reply With Quote
 
markspace
Guest
Posts: n/a
 
      06-24-2011
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.

 
Reply With Quote
 
markspace
Guest
Posts: n/a
 
      06-24-2011
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?

 
Reply With Quote
 
markspace
Guest
Posts: n/a
 
      06-24-2011
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>
 
Reply With Quote
 
Joshua Cranmer
Guest
Posts: n/a
 
      06-24-2011
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 < 12
isIdentifierChar[c] = true;
slowSearch = validChars;
}

static boolean isValidChar(char c) {
if (c >= 12
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
 
Reply With Quote
 
Gene Wirchenko
Guest
Posts: n/a
 
      06-24-2011
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
 
Reply With Quote
 
Gene Wirchenko
Guest
Posts: n/a
 
      06-24-2011
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
 
Reply With Quote
 
Gene Wirchenko
Guest
Posts: n/a
 
      06-24-2011
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Passing a Method Name to a Method Gene Wirchenko Java 33 06-25-2011 07:26 PM
Passing a method(reference) to an other method and calling themethod. Erik Java 11 03-29-2008 07:26 AM
Passing method name to method? Arfon Smith Ruby 3 09-28-2007 03:38 PM
Passing math method to another method? Neutek Ruby 11 01-18-2007 09:23 AM
Re: Urgent! how to get object name, method name and attribute name based on the strings? ding feng C++ 2 06-25-2003 01:18 PM



Advertisments