Table lookups - this is pretty definitive
Denis Shelomovskij
verylonglogin.reg at gmail.com
Tue Apr 1 12:38:03 PDT 2014
01.04.2014 23:22, Denis Shelomovskij пишет:
> 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
>
Few more words about `dmd`:
"Hey, silly, you still use `== x` to compare with `x`? Use table
lookups! And never cast `size_t` to `ubyte`! See:
---
import std.datetime;
import std.stdio;
immutable bool[256] tab2;
static this()
{
foreach(size_t u; 0 .. 0x100)
tab2[u] = u == '_';
}
/*********************************************/
int f0()
{
int x;
foreach(uint u; 0 .. 0x100)
x += u == '_';
return x;
}
int f2()
{
int x;
foreach(uint u; 0 .. 0x100)
x += tab2[cast(ubyte)u];
return x;
}
int f2plus()
{
int x;
foreach(size_t u; 0 .. 0x100)
x += tab2[u];
return x;
}
void main()
{
auto r = benchmark!(f0, f0, f0)(1_000_000);
writefln("Milliseconds %s %s %s (f0)", r[0].msecs, r[1].msecs,
r[2].msecs);
r = benchmark!(f2, f2, f2)(1_000_000);
writefln("Milliseconds %s %s %s (f2)", r[0].msecs, r[1].msecs,
r[2].msecs);
r = benchmark!(f2plus, f2plus, f2plus)(1_000_000);
writefln("Milliseconds %s %s %s (f2plus)", r[0].msecs, r[1].msecs,
r[2].msecs);
}
---
Milliseconds 323 274 281 (f0)
Milliseconds 185 185 185 (f2)
Milliseconds 105 97 105 (f2plus)
---
P.S.
I don't want to say anything with these results. I just have no idea
what happens here and I don't want to investigate dmd's way of
optimizing things now.
--
Денис В. Шеломовский
Denis V. Shelomovskij
More information about the Digitalmars-d
mailing list