Groups | Search | Server Info | Login | Register

Groups > comp.lang.java.programmer > #5621

Re: Passing a Method Name to a Method, Redux

Show all headers | View raw

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

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-23 16:03 -0700
  Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-23 16:26 -0700
    Re: Passing a Method Name to a Method, Redux blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-27 21:41 +0000
  Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-23 17:24 -0700
    Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-23 19:46 -0700
      Re: Passing a Method Name to a Method, Redux blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-04 03:26 +0000
        Re: Passing a Method Name to a Method, Redux lewbloch <lewbloch@gmail.com> - 2011-07-04 03:41 -0700
          Re: Passing a Method Name to a Method, Redux blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-07-05 19:07 +0000
  Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-23 17:34 -0700
    Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-23 19:42 -0700
  Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-23 18:30 -0700
    Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-23 19:48 -0700
      Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-23 21:02 -0700
        Re: Passing a Method Name to a Method, Redux lewbloch <lewbloch@gmail.com> - 2011-06-24 08:38 -0700
          Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-24 09:04 -0700
            Re: Passing a Method Name to a Method, Redux Lew <noone@lewscanon.com> - 2011-06-26 13:43 -0400
              Re: Passing a Method Name to a Method, Redux Lew <noone@lewscanon.com> - 2011-06-26 14:31 -0400
        Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-24 11:45 -0700
          Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-24 12:19 -0700
            Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-26 20:39 -0700
              Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-26 23:33 -0700
                Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-27 13:53 -0700
                Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-27 18:03 -0700
                Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-28 11:41 -0700
        Re: Passing a Method Name to a Method, Redux blmblm@myrealbox.com <blmblm.myrealbox@gmail.com> - 2011-06-24 19:19 +0000
  Re: Passing a Method Name to a Method, Redux Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-06-23 19:36 -0700
    Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-24 11:50 -0700
      Re: Passing a Method Name to a Method, Redux Jeff Higgins <jeff@invalid.invalid> - 2011-06-24 17:25 -0400
        Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-26 20:42 -0700
          Re: Passing a Method Name to a Method, Redux markspace <-@.> - 2011-06-26 23:27 -0700
          Re: Passing a Method Name to a Method, Redux Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-06-27 03:04 -0400
            Re: Passing a Method Name to a Method, Redux Gene Wirchenko <genew@ocis.net> - 2011-06-27 13:12 -0700
              Re: Passing a Method Name to a Method, Redux Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-06-27 13:36 -0700
      Re: Passing a Method Name to a Method, Redux Joshua Cranmer <Pidgeot18@verizon.invalid> - 2011-06-24 15:50 -0700

csiph-web