Albert van der Horst writes Re: meteor benchmark

Status from:
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=meteor&lang=all

meteor-contest (new) benchmark

Ratio Program & Logs Full CPU Time s
1.0 Lua LuaJIT #2 1.44
1.9 Lua LuaJIT 2.68
2.1 Lua #2 3.00
4.1 D Digital Mars #2 5.88
4.3 Lua 6.24
5.6 Forth bigForth 8.02
6.6 Oberon-2 OO2C 9.55

These benchmarks were run on a a single-processor 2GHz Intel Pentium 4 machine
with 512MB of RAM and an 80GB IDE disk drive.

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes Re: meteor benchmark
[..]

The current version is iForth version 2.1.2509, you are a bit behind
there. With the current version code/data separation is not an issue
anymore. Also I have succumbed to benchmark pressure and implemented
auto-inlining.

On Jan 25, 10:38 am, m...@iae.nl (Marcel Hendrix) wrote:

Sorry, you also need the following post because I swapped the
parameters to put-piece.

In any case, I uploaded Grams' island code and my optimizations to the
shootout, where it is 39%% faster than the previous version, but with
the same code size.

On Jan 25, 10:38 am, m...@iae.nl (Marcel Hendrix) wrote:

Oh, and my fill-leading idea was bogus. I should have tested it more
thoroughly.

Ian

I see that the meteor benchmark runs 14 minutes
(ciforth, Pentium I 90) against the pentomino program
2.5 minutes.

It is my estimation that both are about equally complex.
That would mean that introducing the bit field techniques from
mpent.frt could mean a speedup of upto a factor 5.

An advantage is that such techniques are not easily copied
by other computer languages.

A large part of my mpent.frt can be copied verbatim. The generation of
the bit-maps is different, and the meteor problem require that
different bit-maps are used in odd and even rows, but this doesn't
cost more time.

I'll see what I can do.

Groetjes Albert

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:

Albert van der Horst wrote:

The approach I've looked at uses:

A 64-bit double for the board, with a single end-of-row bit, filled with 1's at the end. Row 0 is bits 0-5, row 9 bits 54-59. Zero for empty, 1 for filled/fence. As rows are filled, arithmetic rshift fills upper bits with 1's. done when board is -1. slower to backtrack.

24 32-bit masks for the pieces (all orientations fit in 5 rows): separate sets for odd & even rows, 1 for filled, 0 for empty. AND of piece to board is 32-bit zero if it fits. Only need to check 32 bits of board. XOR piece to place it, XOR to remove it when backtracking.

Unresolved issue:

pruning/backtracking beyond the simplest. There may be an optimal order to testing the pieces in their various orientations to help this.

Maybe this will suggest speed-ups to the folks participating.

John Rible

In article ,
Albert van der Horst wrote:

Not so. But I have a meteor.frt that runs 4:50 which is three
times as fast. All measured on ciforth Pentium 90.

The following is ciforth specific, however I hope that the
technique used is sufficiently clear from the comment to be of
use.
So code follows here. Don't expect it to run on your Forth.
\ Copyright : Albert van der Horst by Gnu Public Licence
\ $Id: meteor.frt,v 1.14 2007/01/20 12:05:22 albert Exp $
\ Uses Stallman convention for comment.

In article ,
Albert van der Horst wrote:

Oeps!
There is a better more straightforward way.

Don't flip.
Have turn3 besides turn6.
: turn3 3 0 DO add snug1 add turn LOOP ;

Now redefine the bit-masks of piece p0.
This eliminates the orientations of p0 that are flipped version
flopped version or flipflopped version of other orientations
that are already there.
p0 &0 extract !orient ( !) turn3 add-pip

Albert van der Horst writes Re: 2 improvements Re: meteor benchmark

[..]

[..]

The BAG construct looks useful.

Thank you for reminding me why I hate object-oriented programming :-)