Table lookups - this is pretty definitive

Denis Shelomovskij verylonglogin.reg at gmail.com
Tue Apr 1 12:22:08 PDT 2014


01.04.2014 22:35, Walter Bright пишет:
> Try this benchmark comparing various classification schemes:
> ---------------------------------
> import core.stdc.stdlib;
> import core.stdc.string;
>
> import std.algorithm;
> import std.array;
> import std.ascii;
> import std.datetime;
> import std.range;
> import std.stdio;
> import std.traits;
>
> bool isIdentifierChar0(ubyte c)
> {
>      return isAlphaNum(c) || c == '_' || c == '$';
> }
>
> bool isIdentifierChar1(ubyte c)
> {
>      return ((c >= '0' || c == '$') &&
>              (c <= '9' || c >= 'A')  &&
>              (c <= 'Z' || c >= 'a' || c == '_') &&
>              (c <= 'z'));
> }
>
> immutable bool[256] tab2;
> static this()
> {
>      for (size_t u = 0; u < 0x100; ++u)
>      {
>          tab2[u] = isIdentifierChar0(cast(ubyte)u);
>      }
> }
>
> bool isIdentifierChar2(ubyte c)
> {
>      return tab2[c];
> }
>
> /*********************************************/
>
> int f0()
> {
>      int x;
>      for (uint u = 0; u < 0x100; ++u)
>      {
>          x += isIdentifierChar0(cast(ubyte)u);
>      }
>      return x;
> }
>
> int f1()
> {
>      int x;
>      for (uint u = 0; u < 0x100; ++u)
>      {
>          x += isIdentifierChar1(cast(ubyte)u);
>      }
>      return x;
> }
>
> int f2()
> {
>      int x;
>      for (uint u = 0; u < 0x100; ++u)
>      {
>          x += isIdentifierChar2(cast(ubyte)u);
>      }
>      return x;
> }
>
> void main()
> {
>      auto r = benchmark!(f0, f1, f2)(10_000);
>      writefln("Milliseconds %s %s %s", r[0].msecs, r[1].msecs, r[2].msecs);
> }

Some regular benchmark notes:

1. The first one passed to `benchmark` is always slower (e.g. pass `f2` 
and see).

2. Unexpected program behaviour changes:

Let's use `benchmark!(f1, f1, f1)(1_000_000)`:
Milliseconds 928 889 888

Then copy `isAlphaNum` in file (benchmark still shows same results) and 
change `dchar c` to `ubyte c`, result changes:
Milliseconds 849 815 827
The difference is sufficient but `isAlphaNum` not called in benchmark.

Also `f0` is faster than `f1`, benchmark!(f0, f0, f0)(1_000_000):
Milliseconds 731 694 702

And `f2` wins, it's the only obvious thing, benchmark!(f2, f2, 
f2)(1_000_000):
Milliseconds 227 184 184


Compiler used: dmd -O -inline -release

-- 
Денис В. Шеломовский
Denis V. Shelomovskij


More information about the Digitalmars-d mailing list