http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all

The reason is that D's mean degraded from 1.40 to 1.43. I wonder how that could happen.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all The reason is that D's mean degraded from 1.40 to 1.43. I wonder how that could happen.

They change often. Clean is also quite variable. I assume the differences are simply in the magnitude of the uncertainty of the measuring.

They change often. Clean is also quite variable. I assume the differences are simply in the magnitude of the uncertainty of the measuring.

No, I don't think so. I think it depends on weight you give to each benchmark. I always set all weight to 1 and consistently I got fpc always on the first place, gcc on the second. ;)

-Bee-

has Bee.ography at:
http://beeography.wordpress.com

I don't knwo what triggered the re-run of D. Bit recurisve and regexdna have become significantly slower, the rest has slightly improved: http://alioth.debian.org/plugins/scmcvs/cvsweb.php/shootout/website/websites/gp4/data/ndata.csv.diff?r1=1.911;r2=1.912;cvsroot=shootout

Vincent

I submitted this regex-dna program on 2007-10-31. It's still in limbo: neither accepted nor rejected.

{ The Computer Language Benchmarks Game
http://shootout.alioth.debian.org

contributed by Steve Fisher

compile with
fpc -O3 regex-dna.pp
}

uses regexpr, strutils;
function replace_matches( const target: pchar;  const repl: pchar;
                const str: ansistring;  var dest: ansistring ): longint;
var
  engine : tRegexprEngine;
  substr : ansistring;
  count, index, size : longint;
begin
  if not GenerateRegExprEngine( target, [], engine) then
  begin
    writeln( 'Failed to generate regex. engine for "',target,'".' );
    halt(1)
  end;
  count := 0;
  dest := '';
  substr := str;
  while length(substr) > 0 do
  begin
    if RegExprPos(engine, pchar(substr), index, size ) then
    begin
      count += 1;
      dest += ansiLeftStr( substr, index) + repl;
      substr := ansiRightStr(substr,length(substr)-index-size);
    end
    else
      break
  end;
  DestroyRegExprEngine( engine );
  dest += substr;
  exit(count)
end;
function count_matches( target: pchar; const str: ansistring ): longint;
var
  engine : tRegexprEngine;
  substr : ansistring;
  count, index, size : longint;
begin
  if not GenerateRegExprEngine( target, [ref_caseinsensitive], engine) then
  begin
    writeln( 'Failed to generate regex. engine for "',target,'".' );
    halt(1)
  end;
  count := 0;
  substr := str;
  while length(substr) > 0 do
  begin
    if RegExprPos(engine, pchar(substr), index, size ) then
    begin
      count += 1;
      substr := ansiRightStr(substr,length(substr)-index-size);
    end
    else
      break
  end;
  DestroyRegExprEngine( engine );
  exit(count)
end;

const
patterns : array[1..9] of pchar =
(
'(agggtaaa)|(tttaccct)',
'([cgt]gggtaaa)|(tttaccc[acg])',
'(a[act]ggtaaa)|(tttacc[agt]t)',
'(ag[act]gtaaa)|(tttac[agt]ct)',
'(agg[act]taaa)|(ttta[agt]cct)',
'(aggg[acg]aaa)|(ttt[cgt]ccct)',
'(agggt[cgt]aa)|(tt[acg]accct)',
'(agggta[cgt]a)|(t[acg]taccct)',
'(agggtaa[cgt])|([acg]ttaccct)'

    );
  replacements : array[1..11,1..2] of pchar =
  (
    ('B', '(c|g|t)'), ('D', '(a|g|t)'), ('H', '(a|c|t)'), ('K', '(g|t)'),
    ('M', '(a|c)'), ('N', '(a|c|g|t)'), ('R', '(a|g)'), ('S', '(c|t)'),
    ('V', '(a|c|g)'), ('W', '(a|t)'), ('Y', '(c|t)')
  );

var
  pattern : pchar;
  sequence, new_seq : ansiString;
  line, tmp: string[255];
  letter, repl : pchar;
  i, count, init_length, clean_length, reps : longint;
begin
  sequence := '';
  init_length := 0;
  while not eof do
  begin
    readln( line );
    init_length += length( line ) + 1;
    if line[1]  '>' then
      sequence := sequence + line;
  end;
  clean_length := length(sequence);
  for i := low(patterns) to high(patterns) do
  begin
    pattern := patterns[i];
    count := count_matches( pattern, sequence );
    tmp := delChars( delChars(pattern,'('), ')' );
    writeln( tmp, ' ', count);
  end;
  //  Replace.
  for i := low(replacements) to high(replacements) do
  begin
    letter := replacements[i][1];  repl := replacements[i][2];
    reps := replace_matches(letter,repl,sequence,new_seq);
    sequence := new_seq;
  end;
  writeln;
  writeln( init_length );
  writeln( clean_length );
  writeln( length(sequence) );
end.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Did you do any benchmarking so far?

It runs in about 0.25 seconds on a 3GHz machine using the 101,745 byte data file (the larger file doesn't seem to be available). I wasn't concerned about optimizing for speed; it just seemed essential to supply the last missing program.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

You can generate the test file yourself using the fasta program, IIRC.

I wasn't concerned about optimizing for speed;

it just seemed essential to supply the last missing program.

Well, it depends on you point of view.

It looks good to have all programs available.

If you want the improve the score, than the program should be not more than 1.4 times slower than the fastest program.

Vincent

Thanks, I've added it to the fpc repository so the source will not be lost

For me the code didn't finish in a reasonable time. It spend too much time in moving ansistrings around. I have update the program to use a pchar instead of an ansistring so it finishes within reasonable time. The updated source can be found in:

http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/regexdna.pp

But the code is a lot slower than gcc so there is still a lot of performance tuning to do:

100000 300000 500000
fpascal 1.169 4.581 11.754
gcc-2 1.033 3.078 5.111

Peter

http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/regexdna.pp

Much, much faster than the original. There was an off-by-one error that made the last line of the output incorrect.

{ The Computer Language Benchmarks Game
http://shootout.alioth.debian.org

contributed by Steve Fisher
modified by Peter Vreman

compile with
fpc -O3 regex-dna.pp
}

uses regexpr,strutils;
function replace_matches( const target: pchar;  const repl: ansistring;
                const str: ansistring;  var dest: ansistring ): longint;
var
  engine : tRegexprEngine;
  count, index, size : longint;
  pstart : pchar;
  starti : longint;
begin
  if not GenerateRegExprEngine( target, [], engine) then
  begin
    writeln( 'Failed to generate regex. engine for "',target,'".' );
    halt(1)
  end;
  count := 0;
  dest := '';
  starti := 1;
  pstart := pchar(str);
  while starti <= length(str) do
  begin
    if RegExprPos(engine, pstart, index, size ) then
    begin
      inc(count);
      dest := dest + Copy( str, starti, index) + repl;
      inc(pstart,index+size);
      inc(starti,index+size);
    end
    else
      break
  end;
  DestroyRegExprEngine( engine );
  dest:=dest+Copy( str, starti, length(str)-starti+1);
  exit(count);
end;
function count_matches( target: pchar; const str: ansistring ): longint;
var
  engine : tRegexprEngine;
  pstart : pchar;
  starti,
  count, index, size : longint;
begin
  if not GenerateRegExprEngine( target, [ref_caseinsensitive], engine) then
  begin
    writeln( 'Failed to generate regex. engine for "',target,'".' );
    halt(1)
  end;
  count := 0;
  pstart := pchar(str);
  starti := 1;
  while starti <= length(str) do
  begin
    if RegExprPos(engine, pstart, index, size ) then
    begin
      inc(count);
      inc(pstart,index+size);
      inc(starti,index+size);
    end
    else
      break
  end;
  DestroyRegExprEngine( engine );
  exit(count)
end;

const
patterns : array[1..9] of pchar =
(
'(agggtaaa)|(tttaccct)',
'([cgt]gggtaaa)|(tttaccc[acg])',
'(a[act]ggtaaa)|(tttacc[agt]t)',
'(ag[act]gtaaa)|(tttac[agt]ct)',
'(agg[act]taaa)|(ttta[agt]cct)',
'(aggg[acg]aaa)|(ttt[cgt]ccct)',
'(agggt[cgt]aa)|(tt[acg]accct)',
'(agggta[cgt]a)|(t[acg]taccct)',
'(agggtaa[cgt])|([acg]ttaccct)'

    );
  replacements : array[1..11,1..2] of pchar =
  (
    ('B', '(c|g|t)'), ('D', '(a|g|t)'), ('H', '(a|c|t)'), ('K', '(g|t)'),
    ('M', '(a|c)'), ('N', '(a|c|g|t)'), ('R', '(a|g)'), ('S', '(c|t)'),
    ('V', '(a|c|g)'), ('W', '(a|t)'), ('Y', '(c|t)')
  );

var
  pattern : pchar;
  sequence, new_seq : ansiString;
  line, tmp: string[255];
  letter, repl : pchar;
  i, count, init_length, clean_length, reps : longint;
  inbuf : array[0..64*1024] of char;
begin
  settextbuf(input,inbuf);
  sequence := '';
  init_length := 0;
  while not eof do
  begin
    readln( line );
    init_length += length( line ) + 1;
    if line[1]  '>' then
      sequence := sequence + line;
  end;
  clean_length := length(sequence);
  for i := low(patterns) to high(patterns) do
  begin
    pattern := patterns[i];
    count := count_matches( pattern, sequence );
    tmp := delChars( delChars(pattern,'('), ')' );
    writeln( tmp, ' ', count);
  end;
  //  Replace.
  for i := low(replacements) to high(replacements) do
  begin
    letter := replacements[i][1];  repl := replacements[i][2];
    reps := replace_matches(letter,repl,sequence,new_seq);
    sequence := new_seq;
  end;
  writeln;
  writeln( init_length );
  writeln( clean_length );
  writeln( length(sequence) );
end.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Thanks, fix applied.

Peter

Ok, now somebody has to fix the regexpr unit and accelerate it *g*

Can't we contact the author ? ;-)

Michael.

http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/regexdna.pp

Is it true that a slow program has a worse effect on the shootout results than a missing program? That seems wrong to me.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Op Mon, 5 Nov 2007, schreef S. Fisher:

There has been a long discussion on the Shootout forums about it. Isaac believes that it is more fair this way for languages that don't have all benchmarks implemented. Now we simply have to make him retract all our poor performing programs :)

Daniël

S. Fisher wrote

Is it true that a slow program has a worse effect on the shootout results than a missing program? That seems wrong to me.

To me is seems wrong too, but is nevertheless the case. Look carefully at the scoring rules at
http://shootout.alioth.debian.org/gp4/benchmark.php?test=all&lang=all#about

See http://alioth.debian.org/forum/forum.php?thread_id=2671&forum_id=999 for the discussion. Maybe as an indirect result result, two of the worst scoring benchmarks (both threading related) were removed from the default scoring set, the one you get when you choose "reset".

Vincent

For this benchmark you don't need extra unneeded code for checking conditions. If the test fails it fails, so don't worry on errors

Marc

Right. A missing program should be equal in its effect to a program that runs as slowly as the slowest program.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Good point.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

--- Peter Vreman wrote

reasonable time. The updated source can be found in:

http://svn.freepascal.org/svn/fpc/trunk/tests/bench/shootout/src/regexdna.pp

I made it somewhat faster by improving the speed of concatenating to an ansistring.

{ The Computer Language Benchmarks Game
http://shootout.alioth.debian.org

contributed by Steve Fisher
modified by Peter Vreman
modified by Steve Fisher

compile with
fpc -O3 regex-dna.pp
}

uses regexpr,strutils;
// Append 2 strings to an ansistring rapidly.  Note: the ansistring's
// length will be increased by a more than sufficient amount.
function append2( var dest: ansistring; len0: longint;
                  s1: pchar; len1: longint;
                  s2: pchar; len2: longint): longint; inline;
const  quantum = 599000;
var  newlength: longint;
begin
  newlength := len0 + len1 + len2;
  // Since setlength() is somewhat costly, we'll do it less
  // often than you would think.
  if length( dest ) < newlength then
    setlength( dest, newlength + quantum );
  move( s1^, dest[len0 + 1], len1 );
  move( s2^, dest[len0 + 1 + len1], len2 );
  exit( newlength );
end;
procedure replace_matches( const target: pchar;  const repl: ansistring;
                const str: ansistring;  var dest: ansistring );
var
  engine : tRegexprEngine;
  starti, index, size, truelength : longint;
  pstart : pchar;
begin
  GenerateRegExprEngine( target, [], engine);
  dest := '';   truelength := 0;
  starti := 1;
  pstart := pchar(str);
  while starti <= length(str) do
    if RegExprPos(engine, pstart, index, size ) then
    begin
      truelength := append2(
        dest, truelength, @str[starti], index, @repl[1], length(repl) );
      inc(pstart, index+size);
      inc(starti, index+size);
    end
    else
      break;
  DestroyRegExprEngine( engine );
  setlength( dest, truelength );
  dest := dest + Copy( str, starti, length(str)-starti+1);
end;
function count_matches( target: pchar; const str: ansistring ): longint;
var
  engine : tRegexprEngine;
  pstart : pchar;
  starti,
  count, index, size : longint;
begin
  GenerateRegExprEngine( target, [ref_caseinsensitive], engine);
  count := 0;
  pstart := pchar(str);
  starti := 1;
  while starti <= length(str) do
    if RegExprPos(engine, pstart, index, size ) then
    begin
      inc(count);
      inc(pstart,index+size);
      inc(starti,index+size);
    end
    else
      break;
  DestroyRegExprEngine( engine );
  exit(count)
end;

const
patterns : array[1..9] of pchar =
(
'(agggtaaa)|(tttaccct)',
'([cgt]gggtaaa)|(tttaccc[acg])',
'(a[act]ggtaaa)|(tttacc[agt]t)',
'(ag[act]gtaaa)|(tttac[agt]ct)',
'(agg[act]taaa)|(ttta[agt]cct)',
'(aggg[acg]aaa)|(ttt[cgt]ccct)',
'(agggt[cgt]aa)|(tt[acg]accct)',
'(agggta[cgt]a)|(t[acg]taccct)',
'(agggtaa[cgt])|([acg]ttaccct)'

    );
  replacements : array[1..11,1..2] of pchar =
  (
    ('B', '(c|g|t)'), ('D', '(a|g|t)'), ('H', '(a|c|t)'), ('K', '(g|t)'),
    ('M', '(a|c)'), ('N', '(a|c|g|t)'), ('R', '(a|g)'), ('S', '(c|t)'),
    ('V', '(a|c|g)'), ('W', '(a|t)'), ('Y', '(c|t)')
  );

var
  pattern : pchar;
  sequence, new_seq : ansiString;
  line, tmp: string[255];
  letter, repl : pchar;
  i, count, init_length, clean_length, reps : longint;
  inbuf : array[0..64*1024] of char;
begin
  settextbuf(input,inbuf);
  sequence := '';
  init_length := 0;
  while not eof do
  begin
    readln( line );
    init_length += length( line ) + 1;
    if line[1]  '>' then
      sequence := sequence + line;
  end;
  clean_length := length(sequence);
  for i := low(patterns) to high(patterns) do
  begin
    pattern := patterns[i];
    count := count_matches( pattern, sequence );
    tmp := delChars( delChars(pattern,'('), ')' );
    writeln( tmp, ' ', count);
  end;
  //  Replace.
  for i := low(replacements) to high(replacements) do
  begin
    letter := replacements[i][1];  repl := replacements[i][2];
    replace_matches(letter,repl,sequence,new_seq);
    sequence := new_seq;
  end;
  writeln;
  writeln( init_length );
  writeln( clean_length );
  writeln( length(sequence) );
end.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Exactly. A not very fast language can win the shootout if it is faster than every other language for just one benchmark and if only the program for that benchmark is submitted.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Well, as the website says, it's just a game. Nevertheless, in this extreme situation nobody would take the language seriously...

-Flávio

People will ignore the ones with just a single test anyway..

When I look at them, for example, I ignore the ones with only two or three tests.

I think they understand that some people have common sense enough not to count the ones with only 1 or 2 completed tests.

Instead of penalizing the ones with 1 or 2 tests, they should simply make it mandatory for the language to at least complete X amount of tests (i.e. 5 or 10 or however many).

The funny thing I see is everyone recommending Pchars. Why not setlength/uniquestring? Still too slow? Several years/months ago, when I posted something on the mailing lists about how trying to defeat the compiler with reference counting basically leads to more work than just taking matters into your own hands with pchars.. it led to some heated arguments. For example some said that the compiler didn't need to use pchars and it was fast.. hmm I wonder if maybe there are some reference counting slowdowns in the compiler that slow it down a bit. Although I realize it uses shortstrings for a lot of stuff.

For the really speed critical stuff FPC indeed uses shortstrings. Well written ansistring code reaches maybe 95% percent of the performance of pchar based code with the big disadvantage that pchar usage is very error prone and unproductive, see all those buffer overflows in c programs. However, for a benchmark this doesn't count. For a benchmark even the 5% advantage of pchar usage count.

Op Tue, 6 Nov 2007, schreef L:

The funny thing I see is everyone recommending Pchars. Why not setlength/uniquestring? Still too slow?

Memory management, especially when you get reallocations, is expensive. With case ansistrings can perform well. However, you do have to care, and Pchars can always be faster.

The compiler uses shortstrings internally, which are the fastest string type. Pchars are between ansistrings and strings, but offer the least comfort of all.

Daniël

The compiler uses shortstrings internally, which are the fastest string type. Pchars are between ansistrings and strings, but offer the least comfort of all.

With the exception that not having a compiler flag to check shorstrings' overflows make for for some tricky to debug problems ;-)

-Flávio

--- Florian Klaempfl wrote

Ok, now somebody has to fix the regexpr unit and accelerate it *g*

The C program in the shootout uses pcre (Perl-compatible regular expressions). It would be very nice if FPC came with pcre.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Well, that way we can never win :) Anyways, I think having an libc independent reg. expr. library for fpc is always nice.

Op Tue, 6 Nov 2007, schreef Florian Klaempfl:

If we want to win we could build in compler support and compile the regular expression into code....

Daniël

A nice idea. Have someone had a look at http://www.regexpstudio.com/TRegExpr/Help/About.html It is claimed to be freeware, it is fpc compatible, it compiles to P-Code (so it should be fast), and we use it sucessfully in our applications.

But i have no idea how fast/usable/feasible it is in the shootout contest ...

helmut

Creating the appropriate code at runtime is no problem either ;)

The compiler uses shortstrings internally, which are the fastest string type. Pchars are between ansistrings and strings, but offer the least comfort of all.

Also WordString or LongIntString would be as fast or faster than a 255 Bytestring..

But haven't implemented or supplied a patch yet ;-)

The C program in the shootout uses pcre (Perl-compatible regular expressions). It would be very nice if FPC came with pcre.

I am also looking to ship PCRE with Powtils too since TRegexp isn't the best in all situations.

We wrapped Tregexp too:
http://z505.com/cgi-bin/powtils/docs/1.6/idx.cgi?file=index-5&unit=regexp

But a PCRE unit would be nice also.

Is Jeff's PCRE header translation or any PCRE headers out there easily available and are they tested and stable? It would be nice if this was shipped as part of FCL or something.

Although I'm not a huge fan of regex abuse it is still a tool for certain jobs.

L505

But we don't have, and may never have, one that is as fast and bug-free as pcre and that is compatible with pcre. The user of a library doesn't care whether it's written in Pascal or C.

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

Offer both.
Include PCRE in the FCL and *if ever* include the pascal fanboy one too.

I'm trying to help by finding a download of Jeff's header.

Flavio mentioned JCL has PCRE header too.

+1

__________________________________________________ Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com

But we don't have, and may never have, one that is as fast and bug-free as pcre and that is compatible with pcre. The user of a library doesn't care whether it's written in Pascal or C.

True. But if native, it isn't a library but linked into the main (static) binary, with all deployment consequences.

P.s.
I recently ran 1998 Linux FPC binaries, and they STILL worked.