From 554fd8c5195424bdbcabf5de30fdc183aba391bd Mon Sep 17 00:00:00 2001 From: upstream source tree Date: Sun, 15 Mar 2015 20:14:05 -0400 Subject: obtained gcc-4.6.4.tar.bz2 from upstream website; verified gcc-4.6.4.tar.bz2.sig; imported gcc-4.6.4 source tree from verified upstream tarball. downloading a git-generated archive based on the 'upstream' tag should provide you with a source tree that is binary identical to the one extracted from the above tarball. if you have obtained the source via the command 'git clone', however, do note that line-endings of files in your working directory might differ from line-endings of the respective files in the upstream repository. --- .../go.test/test/bench/binary-tree-freelist.go | 129 ++++ .../go.test/test/bench/binary-tree-freelist.txt | 8 + gcc/testsuite/go.test/test/bench/binary-tree.c | 165 +++++ gcc/testsuite/go.test/test/bench/binary-tree.go | 92 +++ gcc/testsuite/go.test/test/bench/binary-tree.txt | 8 + gcc/testsuite/go.test/test/bench/chameneosredux.c | 330 ++++++++++ gcc/testsuite/go.test/test/bench/chameneosredux.go | 180 ++++++ .../go.test/test/bench/chameneosredux.txt | 29 + gcc/testsuite/go.test/test/bench/clean.bash | 4 + .../go.test/test/bench/fannkuch-parallel.go | 224 +++++++ .../go.test/test/bench/fannkuch-parallel.txt | 31 + gcc/testsuite/go.test/test/bench/fannkuch.c | 134 +++++ gcc/testsuite/go.test/test/bench/fannkuch.go | 122 ++++ gcc/testsuite/go.test/test/bench/fannkuch.txt | 31 + gcc/testsuite/go.test/test/bench/fasta-1000.out | 171 ++++++ gcc/testsuite/go.test/test/bench/fasta.c | 217 +++++++ gcc/testsuite/go.test/test/bench/fasta.go | 209 +++++++ gcc/testsuite/go.test/test/bench/fasta.txt | 171 ++++++ .../go.test/test/bench/k-nucleotide-parallel.go | 155 +++++ .../go.test/test/bench/k-nucleotide-parallel.txt | 27 + gcc/testsuite/go.test/test/bench/k-nucleotide.c | 228 +++++++ gcc/testsuite/go.test/test/bench/k-nucleotide.go | 140 +++++ gcc/testsuite/go.test/test/bench/k-nucleotide.txt | 27 + gcc/testsuite/go.test/test/bench/mandelbrot.c | 91 +++ gcc/testsuite/go.test/test/bench/mandelbrot.go | 95 +++ gcc/testsuite/go.test/test/bench/mandelbrot.txt | Bin 0 -> 5011 bytes gcc/testsuite/go.test/test/bench/meteor-contest.c | 626 +++++++++++++++++++ gcc/testsuite/go.test/test/bench/meteor-contest.go | 665 +++++++++++++++++++++ .../go.test/test/bench/meteor-contest.txt | 24 + gcc/testsuite/go.test/test/bench/nbody.c | 170 ++++++ gcc/testsuite/go.test/test/bench/nbody.go | 177 ++++++ gcc/testsuite/go.test/test/bench/nbody.txt | 2 + gcc/testsuite/go.test/test/bench/pidigits.c | 123 ++++ gcc/testsuite/go.test/test/bench/pidigits.go | 135 +++++ gcc/testsuite/go.test/test/bench/pidigits.txt | 3 + .../go.test/test/bench/regex-dna-parallel.go | 124 ++++ .../go.test/test/bench/regex-dna-parallel.txt | 13 + gcc/testsuite/go.test/test/bench/regex-dna.c | 154 +++++ gcc/testsuite/go.test/test/bench/regex-dna.go | 106 ++++ gcc/testsuite/go.test/test/bench/regex-dna.txt | 13 + .../go.test/test/bench/reverse-complement.c | 100 ++++ .../go.test/test/bench/reverse-complement.go | 105 ++++ .../go.test/test/bench/reverse-complement.txt | 171 ++++++ .../go.test/test/bench/spectral-norm-parallel.go | 111 ++++ gcc/testsuite/go.test/test/bench/spectral-norm.c | 82 +++ gcc/testsuite/go.test/test/bench/spectral-norm.go | 93 +++ gcc/testsuite/go.test/test/bench/spectral-norm.txt | 1 + gcc/testsuite/go.test/test/bench/threadring.c | 102 ++++ gcc/testsuite/go.test/test/bench/threadring.go | 71 +++ gcc/testsuite/go.test/test/bench/threadring.txt | 1 + gcc/testsuite/go.test/test/bench/timing.log | 500 ++++++++++++++++ gcc/testsuite/go.test/test/bench/timing.sh | 196 ++++++ 52 files changed, 6886 insertions(+) create mode 100644 gcc/testsuite/go.test/test/bench/binary-tree-freelist.go create mode 100644 gcc/testsuite/go.test/test/bench/binary-tree-freelist.txt create mode 100644 gcc/testsuite/go.test/test/bench/binary-tree.c create mode 100644 gcc/testsuite/go.test/test/bench/binary-tree.go create mode 100644 gcc/testsuite/go.test/test/bench/binary-tree.txt create mode 100644 gcc/testsuite/go.test/test/bench/chameneosredux.c create mode 100644 gcc/testsuite/go.test/test/bench/chameneosredux.go create mode 100644 gcc/testsuite/go.test/test/bench/chameneosredux.txt create mode 100755 gcc/testsuite/go.test/test/bench/clean.bash create mode 100644 gcc/testsuite/go.test/test/bench/fannkuch-parallel.go create mode 100644 gcc/testsuite/go.test/test/bench/fannkuch-parallel.txt create mode 100644 gcc/testsuite/go.test/test/bench/fannkuch.c create mode 100644 gcc/testsuite/go.test/test/bench/fannkuch.go create mode 100644 gcc/testsuite/go.test/test/bench/fannkuch.txt create mode 100644 gcc/testsuite/go.test/test/bench/fasta-1000.out create mode 100644 gcc/testsuite/go.test/test/bench/fasta.c create mode 100644 gcc/testsuite/go.test/test/bench/fasta.go create mode 100644 gcc/testsuite/go.test/test/bench/fasta.txt create mode 100644 gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.go create mode 100644 gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.txt create mode 100644 gcc/testsuite/go.test/test/bench/k-nucleotide.c create mode 100644 gcc/testsuite/go.test/test/bench/k-nucleotide.go create mode 100644 gcc/testsuite/go.test/test/bench/k-nucleotide.txt create mode 100644 gcc/testsuite/go.test/test/bench/mandelbrot.c create mode 100644 gcc/testsuite/go.test/test/bench/mandelbrot.go create mode 100644 gcc/testsuite/go.test/test/bench/mandelbrot.txt create mode 100644 gcc/testsuite/go.test/test/bench/meteor-contest.c create mode 100644 gcc/testsuite/go.test/test/bench/meteor-contest.go create mode 100644 gcc/testsuite/go.test/test/bench/meteor-contest.txt create mode 100644 gcc/testsuite/go.test/test/bench/nbody.c create mode 100644 gcc/testsuite/go.test/test/bench/nbody.go create mode 100644 gcc/testsuite/go.test/test/bench/nbody.txt create mode 100644 gcc/testsuite/go.test/test/bench/pidigits.c create mode 100644 gcc/testsuite/go.test/test/bench/pidigits.go create mode 100644 gcc/testsuite/go.test/test/bench/pidigits.txt create mode 100644 gcc/testsuite/go.test/test/bench/regex-dna-parallel.go create mode 100644 gcc/testsuite/go.test/test/bench/regex-dna-parallel.txt create mode 100644 gcc/testsuite/go.test/test/bench/regex-dna.c create mode 100644 gcc/testsuite/go.test/test/bench/regex-dna.go create mode 100644 gcc/testsuite/go.test/test/bench/regex-dna.txt create mode 100644 gcc/testsuite/go.test/test/bench/reverse-complement.c create mode 100644 gcc/testsuite/go.test/test/bench/reverse-complement.go create mode 100644 gcc/testsuite/go.test/test/bench/reverse-complement.txt create mode 100644 gcc/testsuite/go.test/test/bench/spectral-norm-parallel.go create mode 100644 gcc/testsuite/go.test/test/bench/spectral-norm.c create mode 100644 gcc/testsuite/go.test/test/bench/spectral-norm.go create mode 100644 gcc/testsuite/go.test/test/bench/spectral-norm.txt create mode 100644 gcc/testsuite/go.test/test/bench/threadring.c create mode 100644 gcc/testsuite/go.test/test/bench/threadring.go create mode 100644 gcc/testsuite/go.test/test/bench/threadring.txt create mode 100644 gcc/testsuite/go.test/test/bench/timing.log create mode 100755 gcc/testsuite/go.test/test/bench/timing.sh (limited to 'gcc/testsuite/go.test/test/bench') diff --git a/gcc/testsuite/go.test/test/bench/binary-tree-freelist.go b/gcc/testsuite/go.test/test/bench/binary-tree-freelist.go new file mode 100644 index 000000000..071a4e06e --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/binary-tree-freelist.go @@ -0,0 +1,129 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on C program by Kevin Carson + */ + +package main + +import ( + "flag" + "fmt" +) + +var n = flag.Int("n", 15, "depth") + +type Node struct { + item int + left, right *Node +} + +type Arena struct { + head *Node +} + +var arena Arena + +func (n *Node) free() { + if n.left != nil { + n.left.free() + } + if n.right != nil { + n.right.free() + } + n.left = arena.head + arena.head = n +} + +func (a *Arena) New(item int, left, right *Node) *Node { + if a.head == nil { + nodes := make([]Node, 3< *n { + maxDepth = minDepth + 2 + } + stretchDepth := maxDepth + 1 + + check := bottomUpTree(0, stretchDepth).itemCheck() + fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check) + + longLivedTree := bottomUpTree(0, maxDepth) + + for depth := minDepth; depth <= maxDepth; depth += 2 { + iterations := 1 << uint(maxDepth-depth+minDepth) + check = 0 + + for i := 1; i <= iterations; i++ { + t := bottomUpTree(i, depth) + check += t.itemCheck() + t.free() + t = bottomUpTree(-i, depth) + check += t.itemCheck() + t.free() + } + fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check) + } + fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck()) +} diff --git a/gcc/testsuite/go.test/test/bench/binary-tree-freelist.txt b/gcc/testsuite/go.test/test/bench/binary-tree-freelist.txt new file mode 100644 index 000000000..f8286dd88 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/binary-tree-freelist.txt @@ -0,0 +1,8 @@ +stretch tree of depth 16 check: -1 +65536 trees of depth 4 check: -65536 +16384 trees of depth 6 check: -16384 +4096 trees of depth 8 check: -4096 +1024 trees of depth 10 check: -1024 +256 trees of depth 12 check: -256 +64 trees of depth 14 check: -64 +long lived tree of depth 15 check: -1 diff --git a/gcc/testsuite/go.test/test/bench/binary-tree.c b/gcc/testsuite/go.test/test/bench/binary-tree.c new file mode 100644 index 000000000..1b4070406 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/binary-tree.c @@ -0,0 +1,165 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Shootout Benchmarks + http://shootout.alioth.debian.org/ + + contributed by Kevin Carson + compilation: + gcc -O3 -fomit-frame-pointer -funroll-loops -static binary-trees.c -lm + icc -O3 -ip -unroll -static binary-trees.c -lm +*/ + +#include +#include +#include +#include + + +typedef struct tn { + struct tn* left; + struct tn* right; + long item; +} treeNode; + + +treeNode* NewTreeNode(treeNode* left, treeNode* right, long item) +{ + treeNode* new; + + new = (treeNode*)malloc(sizeof(treeNode)); + + new->left = left; + new->right = right; + new->item = item; + + return new; +} /* NewTreeNode() */ + + +long ItemCheck(treeNode* tree) +{ + if (tree->left == NULL) + return tree->item; + else + return tree->item + ItemCheck(tree->left) - ItemCheck(tree->right); +} /* ItemCheck() */ + + +treeNode* BottomUpTree(long item, unsigned depth) +{ + if (depth > 0) + return NewTreeNode + ( + BottomUpTree(2 * item - 1, depth - 1), + BottomUpTree(2 * item, depth - 1), + item + ); + else + return NewTreeNode(NULL, NULL, item); +} /* BottomUpTree() */ + + +void DeleteTree(treeNode* tree) +{ + if (tree->left != NULL) + { + DeleteTree(tree->left); + DeleteTree(tree->right); + } + + free(tree); +} /* DeleteTree() */ + + +int main(int argc, char* argv[]) +{ + unsigned N, depth, minDepth, maxDepth, stretchDepth; + treeNode *stretchTree, *longLivedTree, *tempTree; + + N = atol(argv[1]); + + minDepth = 4; + + if ((minDepth + 2) > N) + maxDepth = minDepth + 2; + else + maxDepth = N; + + stretchDepth = maxDepth + 1; + + stretchTree = BottomUpTree(0, stretchDepth); + printf + ( + "stretch tree of depth %u\t check: %li\n", + stretchDepth, + ItemCheck(stretchTree) + ); + + DeleteTree(stretchTree); + + longLivedTree = BottomUpTree(0, maxDepth); + + for (depth = minDepth; depth <= maxDepth; depth += 2) + { + long i, iterations, check; + + iterations = pow(2, maxDepth - depth + minDepth); + + check = 0; + + for (i = 1; i <= iterations; i++) + { + tempTree = BottomUpTree(i, depth); + check += ItemCheck(tempTree); + DeleteTree(tempTree); + + tempTree = BottomUpTree(-i, depth); + check += ItemCheck(tempTree); + DeleteTree(tempTree); + } /* for(i = 1...) */ + + printf + ( + "%li\t trees of depth %u\t check: %li\n", + iterations * 2, + depth, + check + ); + } /* for(depth = minDepth...) */ + + printf + ( + "long lived tree of depth %u\t check: %li\n", + maxDepth, + ItemCheck(longLivedTree) + ); + + return 0; +} /* main() */ diff --git a/gcc/testsuite/go.test/test/bench/binary-tree.go b/gcc/testsuite/go.test/test/bench/binary-tree.go new file mode 100644 index 000000000..9f867d11a --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/binary-tree.go @@ -0,0 +1,92 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on C program by Kevin Carson + */ + +package main + +import ( + "flag" + "fmt" +) + +var n = flag.Int("n", 15, "depth") + +type Node struct { + item int + left, right *Node +} + +func bottomUpTree(item, depth int) *Node { + if depth <= 0 { + return &Node{item: item} + } + return &Node{item, bottomUpTree(2*item-1, depth-1), bottomUpTree(2*item, depth-1)} +} + +func (n *Node) itemCheck() int { + if n.left == nil { + return n.item + } + return n.item + n.left.itemCheck() - n.right.itemCheck() +} + +const minDepth = 4 + +func main() { + flag.Parse() + + maxDepth := *n + if minDepth+2 > *n { + maxDepth = minDepth + 2 + } + stretchDepth := maxDepth + 1 + + check := bottomUpTree(0, stretchDepth).itemCheck() + fmt.Printf("stretch tree of depth %d\t check: %d\n", stretchDepth, check) + + longLivedTree := bottomUpTree(0, maxDepth) + + for depth := minDepth; depth <= maxDepth; depth += 2 { + iterations := 1 << uint(maxDepth-depth+minDepth) + check = 0 + + for i := 1; i <= iterations; i++ { + check += bottomUpTree(i, depth).itemCheck() + check += bottomUpTree(-i, depth).itemCheck() + } + fmt.Printf("%d\t trees of depth %d\t check: %d\n", iterations*2, depth, check) + } + fmt.Printf("long lived tree of depth %d\t check: %d\n", maxDepth, longLivedTree.itemCheck()) +} diff --git a/gcc/testsuite/go.test/test/bench/binary-tree.txt b/gcc/testsuite/go.test/test/bench/binary-tree.txt new file mode 100644 index 000000000..f8286dd88 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/binary-tree.txt @@ -0,0 +1,8 @@ +stretch tree of depth 16 check: -1 +65536 trees of depth 4 check: -65536 +16384 trees of depth 6 check: -16384 +4096 trees of depth 8 check: -4096 +1024 trees of depth 10 check: -1024 +256 trees of depth 12 check: -256 +64 trees of depth 14 check: -64 +long lived tree of depth 15 check: -1 diff --git a/gcc/testsuite/go.test/test/bench/chameneosredux.c b/gcc/testsuite/go.test/test/bench/chameneosredux.c new file mode 100644 index 000000000..ed78c31d7 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/chameneosredux.c @@ -0,0 +1,330 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + http://shootout.alioth.debian.org/ + + contributed by Michael Barker + based on a Java contribution by Luzius Meisser + + convert to C by dualamd +*/ + +#include +#include +#include + + +enum Colour +{ + blue = 0, + red = 1, + yellow = 2, + Invalid = 3 +}; + +const char* ColourName[] = {"blue", "red", "yellow"}; +const int STACK_SIZE = 32*1024; + +typedef unsigned int BOOL; +const BOOL TRUE = 1; +const BOOL FALSE = 0; + +int CreatureID = 0; + + +enum Colour doCompliment(enum Colour c1, enum Colour c2) +{ + switch (c1) + { + case blue: + switch (c2) + { + case blue: + return blue; + case red: + return yellow; + case yellow: + return red; + default: + goto errlb; + } + case red: + switch (c2) + { + case blue: + return yellow; + case red: + return red; + case yellow: + return blue; + default: + goto errlb; + } + case yellow: + switch (c2) + { + case blue: + return red; + case red: + return blue; + case yellow: + return yellow; + default: + goto errlb; + } + default: + break; + } + +errlb: + printf("Invalid colour\n"); + exit( 1 ); +} + +/* convert integer to number string: 1234 -> "one two three four" */ +char* formatNumber(int n, char* outbuf) +{ + int ochar = 0, ichar = 0; + int i; + char tmp[64]; + + const char* NUMBERS[] = + { + "zero", "one", "two", "three", "four", "five", + "six", "seven", "eight", "nine" + }; + + ichar = sprintf(tmp, "%d", n); + + for (i = 0; i < ichar; i++) + ochar += sprintf( outbuf + ochar, " %s", NUMBERS[ tmp[i] - '0' ] ); + + return outbuf; +} + + +struct MeetingPlace +{ + pthread_mutex_t mutex; + int meetingsLeft; + struct Creature* firstCreature; +}; + +struct Creature +{ + pthread_t ht; + pthread_attr_t stack_att; + + struct MeetingPlace* place; + int count; + int sameCount; + + enum Colour colour; + int id; + + BOOL two_met; + BOOL sameid; +}; + + +void MeetingPlace_Init(struct MeetingPlace* m, int meetings ) +{ + pthread_mutex_init( &m->mutex, 0 ); + m->meetingsLeft = meetings; + m->firstCreature = 0; +} + + +BOOL Meet( struct Creature* cr) +{ + BOOL retval = TRUE; + + struct MeetingPlace* mp = cr->place; + pthread_mutex_lock( &(mp->mutex) ); + + if ( mp->meetingsLeft > 0 ) + { + if ( mp->firstCreature == 0 ) + { + cr->two_met = FALSE; + mp->firstCreature = cr; + } + else + { + struct Creature* first; + enum Colour newColour; + + first = mp->firstCreature; + newColour = doCompliment( cr->colour, first->colour ); + + cr->sameid = cr->id == first->id; + cr->colour = newColour; + cr->two_met = TRUE; + + first->sameid = cr->sameid; + first->colour = newColour; + first->two_met = TRUE; + + mp->firstCreature = 0; + mp->meetingsLeft--; + } + } + else + retval = FALSE; + + pthread_mutex_unlock( &(mp->mutex) ); + return retval; +} + + +void* CreatureThreadRun(void* param) +{ + struct Creature* cr = (struct Creature*)param; + + while (TRUE) + { + if ( Meet(cr) ) + { + while (cr->two_met == FALSE) + sched_yield(); + + if (cr->sameid) + cr->sameCount++; + cr->count++; + } + else + break; + } + + return 0; +} + +void Creature_Init( struct Creature *cr, struct MeetingPlace* place, enum Colour colour ) +{ + cr->place = place; + cr->count = cr->sameCount = 0; + + cr->id = ++CreatureID; + cr->colour = colour; + cr->two_met = FALSE; + + pthread_attr_init( &cr->stack_att ); + pthread_attr_setstacksize( &cr->stack_att, STACK_SIZE ); + pthread_create( &cr->ht, &cr->stack_att, &CreatureThreadRun, (void*)(cr) ); +} + +/* format meeting times of each creature to string */ +char* Creature_getResult(struct Creature* cr, char* str) +{ + char numstr[256]; + formatNumber(cr->sameCount, numstr); + + sprintf( str, "%u%s", cr->count, numstr ); + return str; +} + + +void runGame( int n_meeting, int ncolor, const enum Colour* colours ) +{ + int i; + int total = 0; + char str[256]; + + struct MeetingPlace place; + struct Creature *creatures = (struct Creature*) calloc( ncolor, sizeof(struct Creature) ); + + MeetingPlace_Init( &place, n_meeting ); + + /* print initial color of each creature */ + for (i = 0; i < ncolor; i++) + { + printf( "%s ", ColourName[ colours[i] ] ); + Creature_Init( &(creatures[i]), &place, colours[i] ); + } + printf("\n"); + + /* wait for them to meet */ + for (i = 0; i < ncolor; i++) + pthread_join( creatures[i].ht, 0 ); + + /* print meeting times of each creature */ + for (i = 0; i < ncolor; i++) + { + printf( "%s\n", Creature_getResult(&(creatures[i]), str) ); + total += creatures[i].count; + } + + /* print total meeting times, should equal n_meeting */ + printf( "%s\n\n", formatNumber(total, str) ); + + /* cleaup & quit */ + pthread_mutex_destroy( &place.mutex ); + free( creatures ); +} + + +void printColours( enum Colour c1, enum Colour c2 ) +{ + printf( "%s + %s -> %s\n", + ColourName[c1], + ColourName[c2], + ColourName[doCompliment(c1, c2)] ); +} + +void printColoursTable(void) +{ + printColours(blue, blue); + printColours(blue, red); + printColours(blue, yellow); + printColours(red, blue); + printColours(red, red); + printColours(red, yellow); + printColours(yellow, blue); + printColours(yellow, red); + printColours(yellow, yellow); +} + +int main(int argc, char** argv) +{ + int n = (argc == 2) ? atoi(argv[1]) : 600; + + printColoursTable(); + printf("\n"); + + const enum Colour r1[] = { blue, red, yellow }; + const enum Colour r2[] = { blue, red, yellow, + red, yellow, blue, + red, yellow, red, blue }; + + runGame( n, sizeof(r1) / sizeof(r1[0]), r1 ); + runGame( n, sizeof(r2) / sizeof(r2[0]), r2 ); + + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/chameneosredux.go b/gcc/testsuite/go.test/test/bench/chameneosredux.go new file mode 100644 index 000000000..2cb144004 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/chameneosredux.go @@ -0,0 +1,180 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "flag" + "fmt" + "strconv" +) + +const ( + blue = iota + red + yellow + ncol +) + +var complement = [...]int{ + red | red<<2: red, + red | yellow<<2: blue, + red | blue<<2: yellow, + yellow | red<<2: blue, + yellow | yellow<<2: yellow, + yellow | blue<<2: red, + blue | red<<2: yellow, + blue | yellow<<2: red, + blue | blue<<2: blue, +} + +var colname = [...]string{ + blue: "blue", + red: "red", + yellow: "yellow", +} + +// information about the current state of a creature. +type info struct { + colour int // creature's current colour. + name int // creature's name. +} + +// exclusive access data-structure kept inside meetingplace. +// if mate is nil, it indicates there's no creature currently waiting; +// otherwise the creature's info is stored in info, and +// it is waiting to receive its mate's information on the mate channel. +type rendez struct { + n int // current number of encounters. + mate chan<- info // creature waiting when non-nil. + info info // info about creature waiting. +} + +// result sent by each creature at the end of processing. +type result struct { + met int + same int +} + +var n = 600 + +func main() { + flag.Parse() + if flag.NArg() > 0 { + n, _ = strconv.Atoi(flag.Arg(0)) + } + + for c0 := 0; c0 < ncol; c0++ { + for c1 := 0; c1 < ncol; c1++ { + fmt.Printf("%s + %s -> %s\n", colname[c0], colname[c1], colname[complement[c0|c1<<2]]) + } + } + fmt.Print("\n") + + pallmall([]int{blue, red, yellow}) + pallmall([]int{blue, red, yellow, red, yellow, blue, red, yellow, red, blue}) +} + +func pallmall(cols []int) { + + // invariant: meetingplace always contains a value unless a creature + // is currently dealing with it (whereupon it must put it back). + meetingplace := make(chan rendez, 1) + meetingplace <- rendez{n: 0} + + ended := make(chan result) + msg := "" + for i, col := range cols { + go creature(info{col, i}, meetingplace, ended) + msg += " " + colname[col] + } + fmt.Println(msg) + tot := 0 + // wait for all results + for _ = range cols { + result := <-ended + tot += result.met + fmt.Printf("%v%v\n", result.met, spell(result.same, true)) + } + fmt.Printf("%v\n\n", spell(tot, true)) +} + +// in this function, variables ending in 0 refer to the local creature, +// variables ending in 1 to the creature we've met. +func creature(info0 info, meetingplace chan rendez, ended chan result) { + c0 := make(chan info) + met := 0 + same := 0 + for { + var othername int + // get access to rendez data and decide what to do. + switch r := <-meetingplace; { + case r.n >= n: + // if no more meetings left, then send our result data and exit. + meetingplace <- rendez{n: r.n} + ended <- result{met, same} + return + case r.mate == nil: + // no creature waiting; wait for someone to meet us, + // get their info and send our info in reply. + meetingplace <- rendez{n: r.n, info: info0, mate: c0} + info1 := <-c0 + othername = info1.name + info0.colour = complement[info0.colour|info1.colour<<2] + default: + // another creature is waiting for us with its info; + // increment meeting count, + // send them our info in reply. + r.n++ + meetingplace <- rendez{n: r.n, mate: nil} + r.mate <- info0 + othername = r.info.name + info0.colour = complement[info0.colour|r.info.colour<<2] + } + if othername == info0.name { + same++ + } + met++ + } +} + +var digits = [...]string{"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"} + +func spell(n int, required bool) string { + if n == 0 && !required { + return "" + } + return spell(n/10, false) + " " + digits[n%10] +} diff --git a/gcc/testsuite/go.test/test/bench/chameneosredux.txt b/gcc/testsuite/go.test/test/bench/chameneosredux.txt new file mode 100644 index 000000000..6016d59a8 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/chameneosredux.txt @@ -0,0 +1,29 @@ +blue + blue -> blue +blue + red -> yellow +blue + yellow -> red +red + blue -> yellow +red + red -> red +red + yellow -> blue +yellow + blue -> red +yellow + red -> blue +yellow + yellow -> yellow + + blue red yellow +400 zero +400 zero +400 zero + one two zero zero + + blue red yellow red yellow blue red yellow red blue +120 zero +120 zero +120 zero +120 zero +120 zero +120 zero +120 zero +120 zero +120 zero +120 zero + one two zero zero + diff --git a/gcc/testsuite/go.test/test/bench/clean.bash b/gcc/testsuite/go.test/test/bench/clean.bash new file mode 100755 index 000000000..d56c0e394 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/clean.bash @@ -0,0 +1,4 @@ +#!/bin/sh + +OS=568 +rm -f [$OS].out *.[$OS] diff --git a/gcc/testsuite/go.test/test/bench/fannkuch-parallel.go b/gcc/testsuite/go.test/test/bench/fannkuch-parallel.go new file mode 100644 index 000000000..7897eac05 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fannkuch-parallel.go @@ -0,0 +1,224 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on fannkuch.scala by Rex Kerr + */ + +package main + +import ( + "flag" + "fmt" + "runtime" +) + +var n = flag.Int("n", 7, "count") +var nCPU = flag.Int("ncpu", 2, "number of cpus") + +type Job struct { + start []int + n int +} + +type Found struct { + who *Kucher + k int +} + +type Kucher struct { + perm []int + temp []int + flip []int + in chan Job +} + +func NewKucher(length int) *Kucher { + return &Kucher{ + perm: make([]int, length), + temp: make([]int, length), + flip: make([]int, length), + in: make(chan Job), + } +} + +func (k *Kucher) permute(n int) bool { + i := 0 + for ; i < n-1 && k.flip[i] == 0; i++ { + t := k.perm[0] + j := 0 + for ; j <= i; j++ { + k.perm[j] = k.perm[j+1] + } + k.perm[j] = t + } + k.flip[i]-- + for i > 0 { + i-- + k.flip[i] = i + } + return k.flip[n-1] >= 0 +} + +func (k *Kucher) count() int { + K := 0 + copy(k.temp, k.perm) + for k.temp[0] != 0 { + m := k.temp[0] + for i := 0; i < m; i++ { + k.temp[i], k.temp[m] = k.temp[m], k.temp[i] + m-- + } + K++ + } + return K +} + +func (k *Kucher) Run(foreman chan<- Found) { + for job := range k.in { + verbose := 30 + copy(k.perm, job.start) + for i, v := range k.perm { + if v != i { + verbose = 0 + } + k.flip[i] = i + } + K := 0 + for { + if verbose > 0 { + for _, p := range k.perm { + fmt.Print(p + 1) + } + fmt.Println() + verbose-- + } + count := k.count() + if count > K { + K = count + } + if !k.permute(job.n) { + break + } + } + foreman <- Found{k, K} + } +} + +type Fanner struct { + jobind int + jobsdone int + k int + jobs []Job + workers []*Kucher + in chan Found + result chan int +} + +func NewFanner(jobs []Job, workers []*Kucher) *Fanner { + return &Fanner{ + jobs: jobs, workers: workers, + in: make(chan Found), + result: make(chan int), + } +} + +func (f *Fanner) Run(N int) { + for msg := range f.in { + if msg.k > f.k { + f.k = msg.k + } + if msg.k >= 0 { + f.jobsdone++ + } + if f.jobind < len(f.jobs) { + msg.who.in <- f.jobs[f.jobind] + f.jobind++ + } else if f.jobsdone == len(f.jobs) { + f.result <- f.k + return + } + } +} + +func swapped(a []int, i, j int) []int { + b := make([]int, len(a)) + copy(b, a) + b[i], b[j] = a[j], a[i] + return b +} + +func main() { + flag.Parse() + runtime.GOMAXPROCS(*nCPU) + N := *n + base := make([]int, N) + for i := range base { + base[i] = i + } + + njobs := 1 + if N > 8 { + njobs += (N*(N-1))/2 - 28 // njobs = 1 + sum(8..N-1) = 1 + sum(1..N-1) - sum(1..7) + } + jobs := make([]Job, njobs) + jobsind := 0 + + firstN := N + if firstN > 8 { + firstN = 8 + } + jobs[jobsind] = Job{base, firstN} + jobsind++ + for i := N - 1; i >= 8; i-- { + for j := 0; j < i; j++ { + jobs[jobsind] = Job{swapped(base, i, j), i} + jobsind++ + } + } + + nworkers := *nCPU + if njobs < nworkers { + nworkers = njobs + } + workers := make([]*Kucher, nworkers) + foreman := NewFanner(jobs, workers) + go foreman.Run(N) + for i := range workers { + k := NewKucher(N) + workers[i] = k + go k.Run(foreman.in) + foreman.in <- Found{k, -1} + } + fmt.Printf("Pfannkuchen(%d) = %d\n", N, <-foreman.result) +} diff --git a/gcc/testsuite/go.test/test/bench/fannkuch-parallel.txt b/gcc/testsuite/go.test/test/bench/fannkuch-parallel.txt new file mode 100644 index 000000000..e66f779ea --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fannkuch-parallel.txt @@ -0,0 +1,31 @@ +1234567 +2134567 +2314567 +3214567 +3124567 +1324567 +2341567 +3241567 +3421567 +4321567 +4231567 +2431567 +3412567 +4312567 +4132567 +1432567 +1342567 +3142567 +4123567 +1423567 +1243567 +2143567 +2413567 +4213567 +2345167 +3245167 +3425167 +4325167 +4235167 +2435167 +Pfannkuchen(7) = 16 diff --git a/gcc/testsuite/go.test/test/bench/fannkuch.c b/gcc/testsuite/go.test/test/bench/fannkuch.c new file mode 100644 index 000000000..e576b5441 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fannkuch.c @@ -0,0 +1,134 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Shootout + * http://shootout.alioth.debian.org/ + * Contributed by Heiner Marxen + * + * "fannkuch" for C gcc + * + * $Id: fannkuch.1.gcc.code,v 1.15 2009-04-28 15:39:31 igouy-guest Exp $ + */ + +#include +#include + +#define Int int +#define Aint int + + static long +fannkuch( int n ) +{ + Aint* perm; + Aint* perm1; + Aint* count; + long flips; + long flipsMax; + Int r; + Int i; + Int k; + Int didpr; + const Int n1 = n - 1; + + if( n < 1 ) return 0; + + perm = calloc(n, sizeof(*perm )); + perm1 = calloc(n, sizeof(*perm1)); + count = calloc(n, sizeof(*count)); + + for( i=0 ; i k>0 */ + Int j; + for( i=1, j=k-1 ; i 0 ) { + break; + } + ++r; + } + } +} + + int +main( int argc, char* argv[] ) +{ + int n = (argc>1) ? atoi(argv[1]) : 0; + + printf("Pfannkuchen(%d) = %ld\n", n, fannkuch(n)); + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/fannkuch.go b/gcc/testsuite/go.test/test/bench/fannkuch.go new file mode 100644 index 000000000..b554c77b1 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fannkuch.go @@ -0,0 +1,122 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on fannkuch.c by Heiner Marxen + */ + +package main + +import ( + "flag" + "fmt" +) + +var n = flag.Int("n", 7, "count") + +func fannkuch(n int) int { + if n < 1 { + return 0 + } + + n1 := n - 1 + perm := make([]int, n) + perm1 := make([]int, n) + count := make([]int, n) + + for i := 0; i < n; i++ { + perm1[i] = i // initial (trivial) permutation + } + + r := n + didpr := 0 + flipsMax := 0 + for { + if didpr < 30 { + for i := 0; i < n; i++ { + fmt.Printf("%d", 1+perm1[i]) + } + fmt.Printf("\n") + didpr++ + } + for ; r != 1; r-- { + count[r-1] = r + } + + if perm1[0] != 0 && perm1[n1] != n1 { + flips := 0 + for i := 1; i < n; i++ { // perm = perm1 + perm[i] = perm1[i] + } + k := perm1[0] // cache perm[0] in k + for { // k!=0 ==> k>0 + for i, j := 1, k-1; i < j; i, j = i+1, j-1 { + perm[i], perm[j] = perm[j], perm[i] + } + flips++ + // Now exchange k (caching perm[0]) and perm[k]... with care! + j := perm[k] + perm[k] = k + k = j + if k == 0 { + break + } + } + if flipsMax < flips { + flipsMax = flips + } + } + + for ; r < n; r++ { + // rotate down perm[0..r] by one + perm0 := perm1[0] + for i := 0; i < r; i++ { + perm1[i] = perm1[i+1] + } + perm1[r] = perm0 + count[r]-- + if count[r] > 0 { + break + } + } + if r == n { + return flipsMax + } + } + return 0 +} + +func main() { + flag.Parse() + fmt.Printf("Pfannkuchen(%d) = %d\n", *n, fannkuch(*n)) +} diff --git a/gcc/testsuite/go.test/test/bench/fannkuch.txt b/gcc/testsuite/go.test/test/bench/fannkuch.txt new file mode 100644 index 000000000..e66f779ea --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fannkuch.txt @@ -0,0 +1,31 @@ +1234567 +2134567 +2314567 +3214567 +3124567 +1324567 +2341567 +3241567 +3421567 +4321567 +4231567 +2431567 +3412567 +4312567 +4132567 +1432567 +1342567 +3142567 +4123567 +1423567 +1243567 +2143567 +2413567 +4213567 +2345167 +3245167 +3425167 +4325167 +4235167 +2435167 +Pfannkuchen(7) = 16 diff --git a/gcc/testsuite/go.test/test/bench/fasta-1000.out b/gcc/testsuite/go.test/test/bench/fasta-1000.out new file mode 100644 index 000000000..f1caba0d6 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fasta-1000.out @@ -0,0 +1,171 @@ +>ONE Homo sapiens alu +GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA +TCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACT +AAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAG +GCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCG +CCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGT +GGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCA +GGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAA +TTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAG +AATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCA +GCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGT +AATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGACC +AGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGCCGGGCGTG +GTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACC +CGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTGGGCGACAG +AGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTT +TGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACA +TGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCT +GTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGG +TTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGT +CTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG +CGGGCGGATCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCG +TCTCTACTAAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTA +CTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCG +AGATCGCGCCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCG +GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACC +TGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAA +TACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGA +GGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACT +GCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTC +ACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGT +TCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGC +CGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCG +CTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTG +GGCGACAGAGCGAGACTCCG +>TWO IUB ambiguity codes +cttBtatcatatgctaKggNcataaaSatgtaaaDcDRtBggDtctttataattcBgtcg +tactDtDagcctatttSVHtHttKtgtHMaSattgWaHKHttttagacatWatgtRgaaa +NtactMcSMtYtcMgRtacttctWBacgaaatatagScDtttgaagacacatagtVgYgt +cattHWtMMWcStgttaggKtSgaYaaccWStcgBttgcgaMttBYatcWtgacaYcaga +gtaBDtRacttttcWatMttDBcatWtatcttactaBgaYtcttgttttttttYaaScYa +HgtgttNtSatcMtcVaaaStccRcctDaataataStcYtRDSaMtDttgttSagtRRca +tttHatSttMtWgtcgtatSSagactYaaattcaMtWatttaSgYttaRgKaRtccactt +tattRggaMcDaWaWagttttgacatgttctacaaaRaatataataaMttcgDacgaSSt +acaStYRctVaNMtMgtaggcKatcttttattaaaaagVWaHKYagtttttatttaacct +tacgtVtcVaattVMBcttaMtttaStgacttagattWWacVtgWYagWVRctDattBYt +gtttaagaagattattgacVatMaacattVctgtBSgaVtgWWggaKHaatKWcBScSWa +accRVacacaaactaccScattRatatKVtactatatttHttaagtttSKtRtacaaagt +RDttcaaaaWgcacatWaDgtDKacgaacaattacaRNWaatHtttStgttattaaMtgt +tgDcgtMgcatBtgcttcgcgaDWgagctgcgaggggVtaaScNatttacttaatgacag +cccccacatYScaMgtaggtYaNgttctgaMaacNaMRaacaaacaKctacatagYWctg +ttWaaataaaataRattagHacacaagcgKatacBttRttaagtatttccgatctHSaat +actcNttMaagtattMtgRtgaMgcataatHcMtaBSaRattagttgatHtMttaaKagg +YtaaBataSaVatactWtataVWgKgttaaaacagtgcgRatatacatVtHRtVYataSa +KtWaStVcNKHKttactatccctcatgWHatWaRcttactaggatctataDtDHBttata +aaaHgtacVtagaYttYaKcctattcttcttaataNDaaggaaaDYgcggctaaWSctBa +aNtgctggMBaKctaMVKagBaactaWaDaMaccYVtNtaHtVWtKgRtcaaNtYaNacg +gtttNattgVtttctgtBaWgtaattcaagtcaVWtactNggattctttaYtaaagccgc +tcttagHVggaYtgtNcDaVagctctctKgacgtatagYcctRYHDtgBattDaaDgccK +tcHaaStttMcctagtattgcRgWBaVatHaaaataYtgtttagMDMRtaataaggatMt +ttctWgtNtgtgaaaaMaatatRtttMtDgHHtgtcattttcWattRSHcVagaagtacg +ggtaKVattKYagactNaatgtttgKMMgYNtcccgSKttctaStatatNVataYHgtNa +BKRgNacaactgatttcctttaNcgatttctctataScaHtataRagtcRVttacDSDtt +aRtSatacHgtSKacYagttMHtWataggatgactNtatSaNctataVtttRNKtgRacc +tttYtatgttactttttcctttaaacatacaHactMacacggtWataMtBVacRaSaatc +cgtaBVttccagccBcttaRKtgtgcctttttRtgtcagcRttKtaaacKtaaatctcac +aattgcaNtSBaaccgggttattaaBcKatDagttactcttcattVtttHaaggctKKga +tacatcBggScagtVcacattttgaHaDSgHatRMaHWggtatatRgccDttcgtatcga +aacaHtaagttaRatgaVacttagattVKtaaYttaaatcaNatccRttRRaMScNaaaD +gttVHWgtcHaaHgacVaWtgttScactaagSgttatcttagggDtaccagWattWtRtg +ttHWHacgattBtgVcaYatcggttgagKcWtKKcaVtgaYgWctgYggVctgtHgaNcV +taBtWaaYatcDRaaRtSctgaHaYRttagatMatgcatttNattaDttaattgttctaa +ccctcccctagaWBtttHtBccttagaVaatMcBHagaVcWcagBVttcBtaYMccagat +gaaaaHctctaacgttagNWRtcggattNatcRaNHttcagtKttttgWatWttcSaNgg +gaWtactKKMaacatKatacNattgctWtatctaVgagctatgtRaHtYcWcttagccaa +tYttWttaWSSttaHcaaaaagVacVgtaVaRMgattaVcDactttcHHggHRtgNcctt +tYatcatKgctcctctatVcaaaaKaaaagtatatctgMtWtaaaacaStttMtcgactt +taSatcgDataaactaaacaagtaaVctaggaSccaatMVtaaSKNVattttgHccatca +cBVctgcaVatVttRtactgtVcaattHgtaaattaaattttYtatattaaRSgYtgBag +aHSBDgtagcacRHtYcBgtcacttacactaYcgctWtattgSHtSatcataaatataHt +cgtYaaMNgBaatttaRgaMaatatttBtttaaaHHKaatctgatWatYaacttMctctt +ttVctagctDaaagtaVaKaKRtaacBgtatccaaccactHHaagaagaaggaNaaatBW +attccgStaMSaMatBttgcatgRSacgttVVtaaDMtcSgVatWcaSatcttttVatag +ttactttacgatcaccNtaDVgSRcgVcgtgaacgaNtaNatatagtHtMgtHcMtagaa +attBgtataRaaaacaYKgtRccYtatgaagtaataKgtaaMttgaaRVatgcagaKStc +tHNaaatctBBtcttaYaBWHgtVtgacagcaRcataWctcaBcYacYgatDgtDHccta +>THREE Homo sapiens frequency +aacacttcaccaggtatcgtgaaggctcaagattacccagagaacctttgcaatataaga +atatgtatgcagcattaccctaagtaattatattctttttctgactcaaagtgacaagcc +ctagtgtatattaaatcggtatatttgggaaattcctcaaactatcctaatcaggtagcc +atgaaagtgatcaaaaaagttcgtacttataccatacatgaattctggccaagtaaaaaa +tagattgcgcaaaattcgtaccttaagtctctcgccaagatattaggatcctattactca +tatcgtgtttttctttattgccgccatccccggagtatctcacccatccttctcttaaag +gcctaatattacctatgcaaataaacatatattgttgaaaattgagaacctgatcgtgat +tcttatgtgtaccatatgtatagtaatcacgcgactatatagtgctttagtatcgcccgt +gggtgagtgaatattctgggctagcgtgagatagtttcttgtcctaatatttttcagatc +gaatagcttctatttttgtgtttattgacatatgtcgaaactccttactcagtgaaagtc +atgaccagatccacgaacaatcttcggaatcagtctcgttttacggcggaatcttgagtc +taacttatatcccgtcgcttactttctaacaccccttatgtatttttaaaattacgttta +ttcgaacgtacttggcggaagcgttattttttgaagtaagttacattgggcagactcttg +acattttcgatacgactttctttcatccatcacaggactcgttcgtattgatatcagaag +ctcgtgatgattagttgtcttctttaccaatactttgaggcctattctgcgaaatttttg +ttgccctgcgaacttcacataccaaggaacacctcgcaacatgccttcatatccatcgtt +cattgtaattcttacacaatgaatcctaagtaattacatccctgcgtaaaagatggtagg +ggcactgaggatatattaccaagcatttagttatgagtaatcagcaatgtttcttgtatt +aagttctctaaaatagttacatcgtaatgttatctcgggttccgcgaataaacgagatag +attcattatatatggccctaagcaaaaacctcctcgtattctgttggtaattagaatcac +acaatacgggttgagatattaattatttgtagtacgaagagatataaaaagatgaacaat +tactcaagtcaagatgtatacgggatttataataaaaatcgggtagagatctgctttgca +attcagacgtgccactaaatcgtaatatgtcgcgttacatcagaaagggtaactattatt +aattaataaagggcttaatcactacatattagatcttatccgatagtcttatctattcgt +tgtatttttaagcggttctaattcagtcattatatcagtgctccgagttctttattattg +ttttaaggatgacaaaatgcctcttgttataacgctgggagaagcagactaagagtcgga +gcagttggtagaatgaggctgcaaaagacggtctcgacgaatggacagactttactaaac +caatgaaagacagaagtagagcaaagtctgaagtggtatcagcttaattatgacaaccct +taatacttccctttcgccgaatactggcgtggaaaggttttaaaagtcgaagtagttaga +ggcatctctcgctcataaataggtagactactcgcaatccaatgtgactatgtaatactg +ggaacatcagtccgcgatgcagcgtgtttatcaaccgtccccactcgcctggggagacat +gagaccacccccgtggggattattagtccgcagtaatcgactcttgacaatccttttcga +ttatgtcatagcaatttacgacagttcagcgaagtgactactcggcgaaatggtattact +aaagcattcgaacccacatgaatgtgattcttggcaatttctaatccactaaagcttttc +cgttgaatctggttgtagatatttatataagttcactaattaagatcacggtagtatatt +gatagtgatgtctttgcaagaggttggccgaggaatttacggattctctattgatacaat +ttgtctggcttataactcttaaggctgaaccaggcgtttttagacgacttgatcagctgt +tagaatggtttggactccctctttcatgtcagtaacatttcagccgttattgttacgata +tgcttgaacaatattgatctaccacacacccatagtatattttataggtcatgctgttac +ctacgagcatggtattccacttcccattcaatgagtattcaacatcactagcctcagaga +tgatgacccacctctaataacgtcacgttgcggccatgtgaaacctgaacttgagtagac +gatatcaagcgctttaaattgcatataacatttgagggtaaagctaagcggatgctttat +ataatcaatactcaataataagatttgattgcattttagagttatgacacgacatagttc +actaacgagttactattcccagatctagactgaagtactgatcgagacgatccttacgtc +gatgatcgttagttatcgacttaggtcgggtctctagcggtattggtacttaaccggaca +ctatactaataacccatgatcaaagcataacagaatacagacgataatttcgccaacata +tatgtacagaccccaagcatgagaagctcattgaaagctatcattgaagtcccgctcaca +atgtgtcttttccagacggtttaactggttcccgggagtcctggagtttcgacttacata +aatggaaacaatgtattttgctaatttatctatagcgtcatttggaccaatacagaatat +tatgttgcctagtaatccactataacccgcaagtgctgatagaaaatttttagacgattt +ataaatgccccaagtatccctcccgtgaatcctccgttatactaattagtattcgttcat +acgtataccgcgcatatatgaacatttggcgataaggcgcgtgaattgttacgtgacaga +gatagcagtttcttgtgatatggttaacagacgtacatgaagggaaactttatatctata +gtgatgcttccgtagaaataccgccactggtctgccaatgatgaagtatgtagctttagg +tttgtactatgaggctttcgtttgtttgcagagtataacagttgcgagtgaaaaaccgac +gaatttatactaatacgctttcactattggctacaaaatagggaagagtttcaatcatga +gagggagtatatggatgctttgtagctaaaggtagaacgtatgtatatgctgccgttcat +tcttgaaagatacataagcgataagttacgacaattataagcaacatccctaccttcgta +acgatttcactgttactgcgcttgaaatacactatggggctattggcggagagaagcaga +tcgcgccgagcatatacgagacctataatgttgatgatagagaaggcgtctgaattgata +catcgaagtacactttctttcgtagtatctctcgtcctctttctatctccggacacaaga +attaagttatatatatagagtcttaccaatcatgttgaatcctgattctcagagttcttt +ggcgggccttgtgatgactgagaaacaatgcaatattgctccaaatttcctaagcaaatt +ctcggttatgttatgttatcagcaaagcgttacgttatgttatttaaatctggaatgacg +gagcgaagttcttatgtcggtgtgggaataattcttttgaagacagcactccttaaataa +tatcgctccgtgtttgtatttatcgaatgggtctgtaaccttgcacaagcaaatcggtgg +tgtatatatcggataacaattaatacgatgttcatagtgacagtatactgatcgagtcct +ctaaagtcaattacctcacttaacaatctcattgatgttgtgtcattcccggtatcgccc +gtagtatgtgctctgattgaccgagtgtgaaccaaggaacatctactaatgcctttgtta +ggtaagatctctctgaattccttcgtgccaacttaaaacattatcaaaatttcttctact +tggattaactacttttacgagcatggcaaattcccctgtggaagacggttcattattatc +ggaaaccttatagaaattgcgtgttgactgaaattagatttttattgtaagagttgcatc +tttgcgattcctctggtctagcttccaatgaacagtcctcccttctattcgacatcgggt +ccttcgtacatgtctttgcgatgtaataattaggttcggagtgtggccttaatgggtgca +actaggaatacaacgcaaatttgctgacatgatagcaaatcggtatgccggcaccaaaac +gtgctccttgcttagcttgtgaatgagactcagtagttaaataaatccatatctgcaatc +gattccacaggtattgtccactatctttgaactactctaagagatacaagcttagctgag +accgaggtgtatatgactacgctgatatctgtaaggtaccaatgcaggcaaagtatgcga +gaagctaataccggctgtttccagctttataagattaaaatttggctgtcctggcggcct +cagaattgttctatcgtaatcagttggttcattaattagctaagtacgaggtacaactta +tctgtcccagaacagctccacaagtttttttacagccgaaacccctgtgtgaatcttaat +atccaagcgcgttatctgattagagtttacaactcagtattttatcagtacgttttgttt +ccaacattacccggtatgacaaaatgacgccacgtgtcgaataatggtctgaccaatgta +ggaagtgaaaagataaatat diff --git a/gcc/testsuite/go.test/test/bench/fasta.c b/gcc/testsuite/go.test/test/bench/fasta.c new file mode 100644 index 000000000..78a8490d7 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fasta.c @@ -0,0 +1,217 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * http://shootout.alioth.debian.org/u32/program.php?test=fasta&lang=gcc&id=3 + */ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by Petr Prokhorenkov + */ + +#include +#include +#include + +// not available on OS X +#define fwrite_unlocked fwrite +#define fputc_unlocked fputc +#define fputs_unlocked fputs + +#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0])) +#define unlikely(x) __builtin_expect((x), 0) + +#define IM 139968 +#define IA 3877 +#define IC 29573 + +#define LINE_LEN 60 +#define LOOKUP_SIZE 4096 +#define LOOKUP_SCALE ((float)(LOOKUP_SIZE - 1)) + +typedef unsigned random_t; + +void +random_init(random_t *random) { + *random = 42; +} + +// Special version with result rescaled to LOOKUP_SCALE. +static inline +float +random_next_lookup(random_t *random) { + *random = (*random*IA + IC)%IM; + + return (*random)*(LOOKUP_SCALE/IM); +} + +struct amino_acid { + char sym; + float prob; + float cprob_lookup; +}; + +void +repeat(const char *alu, const char *title, int n) { + int len = strlen(alu); + char buffer[len + LINE_LEN]; + int pos = 0; + + memcpy(buffer, alu, len); + memcpy(buffer + len, alu, LINE_LEN); + + fputs_unlocked(title, stdout); + while (n > 0) { + int bytes = n > LINE_LEN ? LINE_LEN : n; + + fwrite_unlocked(buffer + pos, bytes, 1, stdout); + pos += bytes; + if (pos > len) { + pos -= len; + } + fputc_unlocked('\n', stdout); + n -= bytes; + } +} + +/* + * Lookup table contains mapping from real values to cumulative + * probabilities. Careful selection of table size allows lookup + * virtually in constant time. + * + * All cumulative probabilities are rescaled to LOOKUP_SCALE, + * this allows to save one multiplication operation on each iteration + * in randomize(). + */ + +void * +fill_lookup(struct amino_acid **lookup, struct amino_acid *amino_acid, int amino_acid_size) { + float p = 0; + int i, j; + + for (i = 0; i < amino_acid_size; i++) { + p += amino_acid[i].prob; + amino_acid[i].cprob_lookup = p*LOOKUP_SCALE; + } + + // Prevent rounding error. + amino_acid[amino_acid_size - 1].cprob_lookup = LOOKUP_SIZE - 1; + + for (i = 0, j = 0; i < LOOKUP_SIZE; i++) { + while (amino_acid[j].cprob_lookup < i) { + j++; + } + lookup[i] = &amino_acid[j]; + } + + return 0; +} + +void +randomize(struct amino_acid *amino_acid, int amino_acid_size, + const char *title, int n, random_t *rand) { + struct amino_acid *lookup[LOOKUP_SIZE]; + char line_buffer[LINE_LEN + 1]; + int i, j; + + line_buffer[LINE_LEN] = '\n'; + + fill_lookup(lookup, amino_acid, amino_acid_size); + + fputs_unlocked(title, stdout); + + for (i = 0, j = 0; i < n; i++, j++) { + if (j == LINE_LEN) { + fwrite_unlocked(line_buffer, LINE_LEN + 1, 1, stdout); + j = 0; + } + + float r = random_next_lookup(rand); + struct amino_acid *u = lookup[(short)r]; + while (unlikely(u->cprob_lookup < r)) { + ++u; + } + line_buffer[j] = u->sym; + } + line_buffer[j] = '\n'; + fwrite_unlocked(line_buffer, j + 1, 1, stdout); +} + +struct amino_acid amino_acid[] = { + { 'a', 0.27 }, + { 'c', 0.12 }, + { 'g', 0.12 }, + { 't', 0.27 }, + + { 'B', 0.02 }, + { 'D', 0.02 }, + { 'H', 0.02 }, + { 'K', 0.02 }, + { 'M', 0.02 }, + { 'N', 0.02 }, + { 'R', 0.02 }, + { 'S', 0.02 }, + { 'V', 0.02 }, + { 'W', 0.02 }, + { 'Y', 0.02 }, +}; + +struct amino_acid homo_sapiens[] = { + { 'a', 0.3029549426680 }, + { 'c', 0.1979883004921 }, + { 'g', 0.1975473066391 }, + { 't', 0.3015094502008 }, +}; + +static const char alu[] = + "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTG" + "GGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGA" + "GACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAA" + "AATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAAT" + "CCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAAC" + "CCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTG" + "CACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA"; + +int +main(int argc, const char **argv) { + int n = argc > 1 ? atoi( argv[1] ) : 512; + random_t rand; + + random_init(&rand); + + repeat(alu, ">ONE Homo sapiens alu\n", n*2); + randomize(amino_acid, ARRAY_SIZE(amino_acid), + ">TWO IUB ambiguity codes\n", n*3, &rand); + randomize(homo_sapiens, ARRAY_SIZE(homo_sapiens), + ">THREE Homo sapiens frequency\n", n*5, &rand); + + return 0; +} \ No newline at end of file diff --git a/gcc/testsuite/go.test/test/bench/fasta.go b/gcc/testsuite/go.test/test/bench/fasta.go new file mode 100644 index 000000000..470bdb328 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fasta.go @@ -0,0 +1,209 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on C program by by Petr Prokhorenkov. + */ + +package main + +import ( + "bytes" + "flag" + "os" +) + +var out = make(buffer, 0, 32768) + +var n = flag.Int("n", 1000, "length of result") + +const Line = 60 + +func Repeat(alu []byte, n int) { + buf := bytes.Add(alu, alu) + off := 0 + for n > 0 { + m := n + if m > Line { + m = Line + } + buf1 := out.NextWrite(m + 1) + copy(buf1, buf[off:]) + buf1[m] = '\n' + if off += m; off >= len(alu) { + off -= len(alu) + } + n -= m + } +} + +const ( + IM = 139968 + IA = 3877 + IC = 29573 + + LookupSize = 4096 + LookupScale float64 = LookupSize - 1 +) + +var rand uint32 = 42 + +type Acid struct { + sym byte + prob float64 + cprob float64 + next *Acid +} + +func computeLookup(acid []Acid) *[LookupSize]*Acid { + var lookup [LookupSize]*Acid + var p float64 + for i := range acid { + p += acid[i].prob + acid[i].cprob = p * LookupScale + if i > 0 { + acid[i-1].next = &acid[i] + } + } + acid[len(acid)-1].cprob = 1.0 * LookupScale + + j := 0 + for i := range lookup { + for acid[j].cprob < float64(i) { + j++ + } + lookup[i] = &acid[j] + } + + return &lookup +} + +func Random(acid []Acid, n int) { + lookup := computeLookup(acid) + for n > 0 { + m := n + if m > Line { + m = Line + } + buf := out.NextWrite(m + 1) + f := LookupScale / IM + myrand := rand + for i := 0; i < m; i++ { + myrand = (myrand*IA + IC) % IM + r := float64(int(myrand)) * f + a := lookup[int(r)] + for a.cprob < r { + a = a.next + } + buf[i] = a.sym + } + rand = myrand + buf[m] = '\n' + n -= m + } +} + +func main() { + defer out.Flush() + + flag.Parse() + + iub := []Acid{ + Acid{prob: 0.27, sym: 'a'}, + Acid{prob: 0.12, sym: 'c'}, + Acid{prob: 0.12, sym: 'g'}, + Acid{prob: 0.27, sym: 't'}, + Acid{prob: 0.02, sym: 'B'}, + Acid{prob: 0.02, sym: 'D'}, + Acid{prob: 0.02, sym: 'H'}, + Acid{prob: 0.02, sym: 'K'}, + Acid{prob: 0.02, sym: 'M'}, + Acid{prob: 0.02, sym: 'N'}, + Acid{prob: 0.02, sym: 'R'}, + Acid{prob: 0.02, sym: 'S'}, + Acid{prob: 0.02, sym: 'V'}, + Acid{prob: 0.02, sym: 'W'}, + Acid{prob: 0.02, sym: 'Y'}, + } + + homosapiens := []Acid{ + Acid{prob: 0.3029549426680, sym: 'a'}, + Acid{prob: 0.1979883004921, sym: 'c'}, + Acid{prob: 0.1975473066391, sym: 'g'}, + Acid{prob: 0.3015094502008, sym: 't'}, + } + + alu := []byte( + "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGG" + + "GAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGA" + + "CCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAAT" + + "ACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCA" + + "GCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGG" + + "AGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCC" + + "AGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA") + + out.WriteString(">ONE Homo sapiens alu\n") + Repeat(alu, 2**n) + out.WriteString(">TWO IUB ambiguity codes\n") + Random(iub, 3**n) + out.WriteString(">THREE Homo sapiens frequency\n") + Random(homosapiens, 5**n) +} + + +type buffer []byte + +func (b *buffer) Flush() { + p := *b + if len(p) > 0 { + os.Stdout.Write(p) + } + *b = p[0:0] +} + +func (b *buffer) WriteString(s string) { + p := b.NextWrite(len(s)) + for i := 0; i < len(s); i++ { + p[i] = s[i] + } +} + +func (b *buffer) NextWrite(n int) []byte { + p := *b + if len(p)+n > cap(p) { + b.Flush() + p = *b + } + out := p[len(p) : len(p)+n] + *b = p[0 : len(p)+n] + return out +} diff --git a/gcc/testsuite/go.test/test/bench/fasta.txt b/gcc/testsuite/go.test/test/bench/fasta.txt new file mode 100644 index 000000000..f1caba0d6 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/fasta.txt @@ -0,0 +1,171 @@ +>ONE Homo sapiens alu +GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA +TCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACT +AAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAG +GCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCG +CCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGT +GGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCA +GGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAA +TTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAG +AATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCA +GCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGT +AATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGACC +AGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGCCGGGCGTG +GTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACC +CGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTGGGCGACAG +AGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTT +TGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACA +TGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCT +GTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGG +TTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGT +CTCAAAAAGGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGG +CGGGCGGATCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCG +TCTCTACTAAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTA +CTCGGGAGGCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCG +AGATCGCGCCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCG +GGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACC +TGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAA +TACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGA +GGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACT +GCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAAGGCCGGGCGCGGTGGCTC +ACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGATCACCTGAGGTCAGGAGT +TCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACTAAAAATACAAAAATTAGC +CGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAGGCTGAGGCAGGAGAATCG +CTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCGCCACTGCACTCCAGCCTG +GGCGACAGAGCGAGACTCCG +>TWO IUB ambiguity codes +cttBtatcatatgctaKggNcataaaSatgtaaaDcDRtBggDtctttataattcBgtcg +tactDtDagcctatttSVHtHttKtgtHMaSattgWaHKHttttagacatWatgtRgaaa +NtactMcSMtYtcMgRtacttctWBacgaaatatagScDtttgaagacacatagtVgYgt +cattHWtMMWcStgttaggKtSgaYaaccWStcgBttgcgaMttBYatcWtgacaYcaga +gtaBDtRacttttcWatMttDBcatWtatcttactaBgaYtcttgttttttttYaaScYa +HgtgttNtSatcMtcVaaaStccRcctDaataataStcYtRDSaMtDttgttSagtRRca +tttHatSttMtWgtcgtatSSagactYaaattcaMtWatttaSgYttaRgKaRtccactt +tattRggaMcDaWaWagttttgacatgttctacaaaRaatataataaMttcgDacgaSSt +acaStYRctVaNMtMgtaggcKatcttttattaaaaagVWaHKYagtttttatttaacct +tacgtVtcVaattVMBcttaMtttaStgacttagattWWacVtgWYagWVRctDattBYt +gtttaagaagattattgacVatMaacattVctgtBSgaVtgWWggaKHaatKWcBScSWa +accRVacacaaactaccScattRatatKVtactatatttHttaagtttSKtRtacaaagt +RDttcaaaaWgcacatWaDgtDKacgaacaattacaRNWaatHtttStgttattaaMtgt +tgDcgtMgcatBtgcttcgcgaDWgagctgcgaggggVtaaScNatttacttaatgacag +cccccacatYScaMgtaggtYaNgttctgaMaacNaMRaacaaacaKctacatagYWctg +ttWaaataaaataRattagHacacaagcgKatacBttRttaagtatttccgatctHSaat +actcNttMaagtattMtgRtgaMgcataatHcMtaBSaRattagttgatHtMttaaKagg +YtaaBataSaVatactWtataVWgKgttaaaacagtgcgRatatacatVtHRtVYataSa +KtWaStVcNKHKttactatccctcatgWHatWaRcttactaggatctataDtDHBttata +aaaHgtacVtagaYttYaKcctattcttcttaataNDaaggaaaDYgcggctaaWSctBa +aNtgctggMBaKctaMVKagBaactaWaDaMaccYVtNtaHtVWtKgRtcaaNtYaNacg +gtttNattgVtttctgtBaWgtaattcaagtcaVWtactNggattctttaYtaaagccgc +tcttagHVggaYtgtNcDaVagctctctKgacgtatagYcctRYHDtgBattDaaDgccK +tcHaaStttMcctagtattgcRgWBaVatHaaaataYtgtttagMDMRtaataaggatMt +ttctWgtNtgtgaaaaMaatatRtttMtDgHHtgtcattttcWattRSHcVagaagtacg +ggtaKVattKYagactNaatgtttgKMMgYNtcccgSKttctaStatatNVataYHgtNa +BKRgNacaactgatttcctttaNcgatttctctataScaHtataRagtcRVttacDSDtt +aRtSatacHgtSKacYagttMHtWataggatgactNtatSaNctataVtttRNKtgRacc +tttYtatgttactttttcctttaaacatacaHactMacacggtWataMtBVacRaSaatc +cgtaBVttccagccBcttaRKtgtgcctttttRtgtcagcRttKtaaacKtaaatctcac +aattgcaNtSBaaccgggttattaaBcKatDagttactcttcattVtttHaaggctKKga +tacatcBggScagtVcacattttgaHaDSgHatRMaHWggtatatRgccDttcgtatcga +aacaHtaagttaRatgaVacttagattVKtaaYttaaatcaNatccRttRRaMScNaaaD +gttVHWgtcHaaHgacVaWtgttScactaagSgttatcttagggDtaccagWattWtRtg +ttHWHacgattBtgVcaYatcggttgagKcWtKKcaVtgaYgWctgYggVctgtHgaNcV +taBtWaaYatcDRaaRtSctgaHaYRttagatMatgcatttNattaDttaattgttctaa +ccctcccctagaWBtttHtBccttagaVaatMcBHagaVcWcagBVttcBtaYMccagat +gaaaaHctctaacgttagNWRtcggattNatcRaNHttcagtKttttgWatWttcSaNgg +gaWtactKKMaacatKatacNattgctWtatctaVgagctatgtRaHtYcWcttagccaa +tYttWttaWSSttaHcaaaaagVacVgtaVaRMgattaVcDactttcHHggHRtgNcctt +tYatcatKgctcctctatVcaaaaKaaaagtatatctgMtWtaaaacaStttMtcgactt +taSatcgDataaactaaacaagtaaVctaggaSccaatMVtaaSKNVattttgHccatca +cBVctgcaVatVttRtactgtVcaattHgtaaattaaattttYtatattaaRSgYtgBag +aHSBDgtagcacRHtYcBgtcacttacactaYcgctWtattgSHtSatcataaatataHt +cgtYaaMNgBaatttaRgaMaatatttBtttaaaHHKaatctgatWatYaacttMctctt +ttVctagctDaaagtaVaKaKRtaacBgtatccaaccactHHaagaagaaggaNaaatBW +attccgStaMSaMatBttgcatgRSacgttVVtaaDMtcSgVatWcaSatcttttVatag +ttactttacgatcaccNtaDVgSRcgVcgtgaacgaNtaNatatagtHtMgtHcMtagaa +attBgtataRaaaacaYKgtRccYtatgaagtaataKgtaaMttgaaRVatgcagaKStc +tHNaaatctBBtcttaYaBWHgtVtgacagcaRcataWctcaBcYacYgatDgtDHccta +>THREE Homo sapiens frequency +aacacttcaccaggtatcgtgaaggctcaagattacccagagaacctttgcaatataaga +atatgtatgcagcattaccctaagtaattatattctttttctgactcaaagtgacaagcc +ctagtgtatattaaatcggtatatttgggaaattcctcaaactatcctaatcaggtagcc +atgaaagtgatcaaaaaagttcgtacttataccatacatgaattctggccaagtaaaaaa +tagattgcgcaaaattcgtaccttaagtctctcgccaagatattaggatcctattactca +tatcgtgtttttctttattgccgccatccccggagtatctcacccatccttctcttaaag +gcctaatattacctatgcaaataaacatatattgttgaaaattgagaacctgatcgtgat +tcttatgtgtaccatatgtatagtaatcacgcgactatatagtgctttagtatcgcccgt +gggtgagtgaatattctgggctagcgtgagatagtttcttgtcctaatatttttcagatc +gaatagcttctatttttgtgtttattgacatatgtcgaaactccttactcagtgaaagtc +atgaccagatccacgaacaatcttcggaatcagtctcgttttacggcggaatcttgagtc +taacttatatcccgtcgcttactttctaacaccccttatgtatttttaaaattacgttta +ttcgaacgtacttggcggaagcgttattttttgaagtaagttacattgggcagactcttg +acattttcgatacgactttctttcatccatcacaggactcgttcgtattgatatcagaag +ctcgtgatgattagttgtcttctttaccaatactttgaggcctattctgcgaaatttttg +ttgccctgcgaacttcacataccaaggaacacctcgcaacatgccttcatatccatcgtt +cattgtaattcttacacaatgaatcctaagtaattacatccctgcgtaaaagatggtagg +ggcactgaggatatattaccaagcatttagttatgagtaatcagcaatgtttcttgtatt +aagttctctaaaatagttacatcgtaatgttatctcgggttccgcgaataaacgagatag +attcattatatatggccctaagcaaaaacctcctcgtattctgttggtaattagaatcac +acaatacgggttgagatattaattatttgtagtacgaagagatataaaaagatgaacaat +tactcaagtcaagatgtatacgggatttataataaaaatcgggtagagatctgctttgca +attcagacgtgccactaaatcgtaatatgtcgcgttacatcagaaagggtaactattatt +aattaataaagggcttaatcactacatattagatcttatccgatagtcttatctattcgt +tgtatttttaagcggttctaattcagtcattatatcagtgctccgagttctttattattg +ttttaaggatgacaaaatgcctcttgttataacgctgggagaagcagactaagagtcgga +gcagttggtagaatgaggctgcaaaagacggtctcgacgaatggacagactttactaaac +caatgaaagacagaagtagagcaaagtctgaagtggtatcagcttaattatgacaaccct +taatacttccctttcgccgaatactggcgtggaaaggttttaaaagtcgaagtagttaga +ggcatctctcgctcataaataggtagactactcgcaatccaatgtgactatgtaatactg +ggaacatcagtccgcgatgcagcgtgtttatcaaccgtccccactcgcctggggagacat +gagaccacccccgtggggattattagtccgcagtaatcgactcttgacaatccttttcga +ttatgtcatagcaatttacgacagttcagcgaagtgactactcggcgaaatggtattact +aaagcattcgaacccacatgaatgtgattcttggcaatttctaatccactaaagcttttc +cgttgaatctggttgtagatatttatataagttcactaattaagatcacggtagtatatt +gatagtgatgtctttgcaagaggttggccgaggaatttacggattctctattgatacaat +ttgtctggcttataactcttaaggctgaaccaggcgtttttagacgacttgatcagctgt +tagaatggtttggactccctctttcatgtcagtaacatttcagccgttattgttacgata +tgcttgaacaatattgatctaccacacacccatagtatattttataggtcatgctgttac +ctacgagcatggtattccacttcccattcaatgagtattcaacatcactagcctcagaga +tgatgacccacctctaataacgtcacgttgcggccatgtgaaacctgaacttgagtagac +gatatcaagcgctttaaattgcatataacatttgagggtaaagctaagcggatgctttat +ataatcaatactcaataataagatttgattgcattttagagttatgacacgacatagttc +actaacgagttactattcccagatctagactgaagtactgatcgagacgatccttacgtc +gatgatcgttagttatcgacttaggtcgggtctctagcggtattggtacttaaccggaca +ctatactaataacccatgatcaaagcataacagaatacagacgataatttcgccaacata +tatgtacagaccccaagcatgagaagctcattgaaagctatcattgaagtcccgctcaca +atgtgtcttttccagacggtttaactggttcccgggagtcctggagtttcgacttacata +aatggaaacaatgtattttgctaatttatctatagcgtcatttggaccaatacagaatat +tatgttgcctagtaatccactataacccgcaagtgctgatagaaaatttttagacgattt +ataaatgccccaagtatccctcccgtgaatcctccgttatactaattagtattcgttcat +acgtataccgcgcatatatgaacatttggcgataaggcgcgtgaattgttacgtgacaga +gatagcagtttcttgtgatatggttaacagacgtacatgaagggaaactttatatctata +gtgatgcttccgtagaaataccgccactggtctgccaatgatgaagtatgtagctttagg +tttgtactatgaggctttcgtttgtttgcagagtataacagttgcgagtgaaaaaccgac +gaatttatactaatacgctttcactattggctacaaaatagggaagagtttcaatcatga +gagggagtatatggatgctttgtagctaaaggtagaacgtatgtatatgctgccgttcat +tcttgaaagatacataagcgataagttacgacaattataagcaacatccctaccttcgta +acgatttcactgttactgcgcttgaaatacactatggggctattggcggagagaagcaga +tcgcgccgagcatatacgagacctataatgttgatgatagagaaggcgtctgaattgata +catcgaagtacactttctttcgtagtatctctcgtcctctttctatctccggacacaaga +attaagttatatatatagagtcttaccaatcatgttgaatcctgattctcagagttcttt +ggcgggccttgtgatgactgagaaacaatgcaatattgctccaaatttcctaagcaaatt +ctcggttatgttatgttatcagcaaagcgttacgttatgttatttaaatctggaatgacg +gagcgaagttcttatgtcggtgtgggaataattcttttgaagacagcactccttaaataa +tatcgctccgtgtttgtatttatcgaatgggtctgtaaccttgcacaagcaaatcggtgg +tgtatatatcggataacaattaatacgatgttcatagtgacagtatactgatcgagtcct +ctaaagtcaattacctcacttaacaatctcattgatgttgtgtcattcccggtatcgccc +gtagtatgtgctctgattgaccgagtgtgaaccaaggaacatctactaatgcctttgtta +ggtaagatctctctgaattccttcgtgccaacttaaaacattatcaaaatttcttctact +tggattaactacttttacgagcatggcaaattcccctgtggaagacggttcattattatc +ggaaaccttatagaaattgcgtgttgactgaaattagatttttattgtaagagttgcatc +tttgcgattcctctggtctagcttccaatgaacagtcctcccttctattcgacatcgggt +ccttcgtacatgtctttgcgatgtaataattaggttcggagtgtggccttaatgggtgca +actaggaatacaacgcaaatttgctgacatgatagcaaatcggtatgccggcaccaaaac +gtgctccttgcttagcttgtgaatgagactcagtagttaaataaatccatatctgcaatc +gattccacaggtattgtccactatctttgaactactctaagagatacaagcttagctgag +accgaggtgtatatgactacgctgatatctgtaaggtaccaatgcaggcaaagtatgcga +gaagctaataccggctgtttccagctttataagattaaaatttggctgtcctggcggcct +cagaattgttctatcgtaatcagttggttcattaattagctaagtacgaggtacaactta +tctgtcccagaacagctccacaagtttttttacagccgaaacccctgtgtgaatcttaat +atccaagcgcgttatctgattagagtttacaactcagtattttatcagtacgttttgttt +ccaacattacccggtatgacaaaatgacgccacgtgtcgaataatggtctgaccaatgta +ggaagtgaaaagataaatat diff --git a/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.go b/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.go new file mode 100644 index 000000000..0234f33d1 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.go @@ -0,0 +1,155 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "bufio" + "bytes" + "fmt" + "io/ioutil" + "os" + "sort" +) + +func count(data string, n int) map[string]int { + counts := make(map[string]int) + top := len(data) - n + for i := 0; i <= top; i++ { + s := data[i : i+n] + counts[s]++ + } + return counts +} + +func countOne(data string, s string) int { + return count(data, len(s))[s] +} + +type kNuc struct { + name string + count int +} + +type kNucArray []kNuc + +func (kn kNucArray) Len() int { return len(kn) } +func (kn kNucArray) Swap(i, j int) { kn[i], kn[j] = kn[j], kn[i] } +func (kn kNucArray) Less(i, j int) bool { + if kn[i].count == kn[j].count { + return kn[i].name > kn[j].name // sort down + } + return kn[i].count > kn[j].count +} + +func sortedArray(m map[string]int) kNucArray { + kn := make(kNucArray, len(m)) + i := 0 + for k, v := range m { + kn[i] = kNuc{k, v} + i++ + } + sort.Sort(kn) + return kn +} + +func printKnucs(a kNucArray) { + sum := 0 + for _, kn := range a { + sum += kn.count + } + for _, kn := range a { + fmt.Printf("%s %.3f\n", kn.name, 100*float64(kn.count)/float64(sum)) + } + fmt.Print("\n") +} + +func main() { + in := bufio.NewReader(os.Stdin) + three := []byte(">THREE ") + for { + line, err := in.ReadSlice('\n') + if err != nil { + fmt.Fprintln(os.Stderr, "ReadLine err:", err) + os.Exit(2) + } + if line[0] == '>' && bytes.Equal(line[0:len(three)], three) { + break + } + } + data, err := ioutil.ReadAll(in) + if err != nil { + fmt.Fprintln(os.Stderr, "ReadAll err:", err) + os.Exit(2) + } + // delete the newlines and convert to upper case + j := 0 + for i := 0; i < len(data); i++ { + if data[i] != '\n' { + data[j] = data[i] &^ ' ' // upper case + j++ + } + } + str := string(data[0:j]) + + var arr1, arr2 kNucArray + countsdone := make(chan bool) + go func() { + arr1 = sortedArray(count(str, 1)) + countsdone <- true + }() + go func() { + arr2 = sortedArray(count(str, 2)) + countsdone <- true + }() + + interests := []string{"GGT", "GGTA", "GGTATT", "GGTATTTTAATT", "GGTATTTTAATTTATAGT"} + results := make([]chan string, len(interests)) + for i, s := range interests { + ch := make(chan string) + results[i] = ch + go func(result chan string, ss string) { + result <- fmt.Sprintf("%d %s\n", countOne(str, ss), ss) + }(ch, s) + } + <-countsdone + <-countsdone + printKnucs(arr1) + printKnucs(arr2) + for _, rc := range results { + fmt.Print(<-rc) + } + +} diff --git a/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.txt b/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.txt new file mode 100644 index 000000000..84169b8ec --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/k-nucleotide-parallel.txt @@ -0,0 +1,27 @@ +T 31.520 +A 29.600 +C 19.480 +G 19.400 + +AT 9.922 +TT 9.602 +TA 9.402 +AA 8.402 +GA 6.321 +TC 6.301 +TG 6.201 +GT 6.041 +CT 5.961 +AG 5.841 +CA 5.461 +AC 5.441 +CC 4.041 +CG 4.021 +GC 3.701 +GG 3.341 + +54 GGT +24 GGTA +4 GGTATT +0 GGTATTTTAATT +0 GGTATTTTAATTTATAGT diff --git a/gcc/testsuite/go.test/test/bench/k-nucleotide.c b/gcc/testsuite/go.test/test/bench/k-nucleotide.c new file mode 100644 index 000000000..3bace391c --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/k-nucleotide.c @@ -0,0 +1,228 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +#include +#include +#include +#include +#include + +typedef struct stat_s stat_t; +struct stat_s +{ + const gchar *key; + long stat; +}; + +#define MAX_ELM (8192 / sizeof (stat_t)) + +static int +generate_frequencies (int fl, char *buffer, long buflen, + GHashTable *ht, GTrashStack **ts, GPtrArray *roots, GStringChunk *sc) +{ + gchar *key; + long i; + + if (fl > buflen) return 0; + if (fl == 0) return 0; + + for (i = 0; i < buflen - fl + 1; ++i) + { + char nulled; + stat_t *stat; + + nulled = buffer[i + fl]; + buffer[i + fl] = '\0'; + + key = g_string_chunk_insert_const(sc, buffer + i); + + stat = g_hash_table_lookup(ht, key); + if (!stat) + { + stat = g_trash_stack_pop(ts); + if (!stat) + { + int j; + + stat = malloc(sizeof (stat_t) * MAX_ELM); + g_ptr_array_add(roots, stat); + + for (j = 1; j < MAX_ELM; ++j) + g_trash_stack_push(ts, stat + j); + } + stat->stat = 1; + stat->key = key; + + g_hash_table_insert(ht, key, stat); + } + else + stat->stat++; + + buffer[i + fl] = nulled; + } + + return buflen - fl + 1; +} + +static int +cmp_func(gconstpointer a, gconstpointer b) +{ + const stat_t *left = a; + const stat_t *right = b; + + return right->stat - left->stat; +} + +static void +sorted_list(gpointer key, gpointer value, gpointer user_data) +{ + stat_t *data = value; + GList **lst = user_data; + + *lst = g_list_insert_sorted(*lst, data, cmp_func); +} + +static void +display_stat(gpointer data, gpointer user_data) +{ + long *total = user_data; + stat_t *st = data; + + printf("%s %.3f\n", st->key, 100 * (float) st->stat / *total); +} + +void +write_frequencies (int fl, char *buffer, long buflen, GTrashStack **ts, GPtrArray *roots) +{ + GStringChunk *sc; + GHashTable *ht; + GList *lst; + long total; + + ht = g_hash_table_new_full(g_str_hash, g_str_equal, NULL /* free key */, NULL /* free value */); + sc = g_string_chunk_new(buflen); + lst = NULL; + + total = generate_frequencies (fl, buffer, buflen, ht, ts, roots, sc); + + if (!total) goto on_error; + + g_hash_table_foreach(ht, sorted_list, &lst); + g_list_foreach(lst, display_stat, &total); + g_list_free(lst); + + on_error: + g_hash_table_destroy(ht); + g_string_chunk_free(sc); +} + +void +write_count (char *searchFor, char *buffer, long buflen, GTrashStack **ts, GPtrArray *roots) +{ + GStringChunk *sc; + GHashTable *ht; + stat_t *result; + GList *lst; + long total; + long fl; + + fl = strlen(searchFor); + + ht = g_hash_table_new_full(g_str_hash, g_str_equal, NULL /* free key */, NULL /* free value */); + sc = g_string_chunk_new(buflen); + lst = NULL; + result = NULL; + + total = generate_frequencies (fl, buffer, buflen, ht, ts, roots, sc); + + if (!total) goto on_error; + + result = g_hash_table_lookup(ht, searchFor); + + on_error: + printf("%ld\t%s\n", result ? result->stat : 0, searchFor); + + g_hash_table_destroy(ht); + g_string_chunk_free(sc); +} + +int +main () +{ + char buffer[4096]; + GTrashStack *ts; + GPtrArray *roots; + GString *stuff; + gchar *s; + int len; + + roots = g_ptr_array_new(); + ts = NULL; + + while (fgets(buffer, sizeof (buffer), stdin)) + if (strncmp(buffer, ">THREE", 6) == 0) + break; + + stuff = g_string_new(NULL); + + while (fgets(buffer, sizeof (buffer), stdin)) + { + size_t sz; + + if (buffer[0] == '>') + break; + + sz = strlen(buffer); + if (buffer[sz - 1] == '\n') + --sz; + + stuff = g_string_append_len(stuff, buffer, sz); + } + + stuff = g_string_ascii_up(stuff); + len = stuff->len; + s = g_string_free(stuff, FALSE); + + write_frequencies(1, s, len, &ts, roots); + printf("\n"); + write_frequencies(2, s, len, &ts, roots); + printf("\n"); + write_count("GGT", s, len, &ts, roots); + write_count("GGTA", s, len, &ts, roots); + write_count("GGTATT", s, len, &ts, roots); + write_count("GGTATTTTAATT", s, len, &ts, roots); + write_count("GGTATTTTAATTTATAGT", s, len, &ts, roots); + + free(s); + + g_ptr_array_foreach(roots, free, NULL); + g_ptr_array_free(roots, TRUE); + + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/k-nucleotide.go b/gcc/testsuite/go.test/test/bench/k-nucleotide.go new file mode 100644 index 000000000..fdc98ed47 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/k-nucleotide.go @@ -0,0 +1,140 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "bufio" + "bytes" + "fmt" + "io/ioutil" + "os" + "sort" +) + +var in *bufio.Reader + +func count(data string, n int) map[string]int { + counts := make(map[string]int) + top := len(data) - n + for i := 0; i <= top; i++ { + s := data[i : i+n] + counts[s]++ + } + return counts +} + +func countOne(data string, s string) int { + return count(data, len(s))[s] +} + +type kNuc struct { + name string + count int +} + +type kNucArray []kNuc + +func (kn kNucArray) Len() int { return len(kn) } +func (kn kNucArray) Swap(i, j int) { kn[i], kn[j] = kn[j], kn[i] } +func (kn kNucArray) Less(i, j int) bool { + if kn[i].count == kn[j].count { + return kn[i].name > kn[j].name // sort down + } + return kn[i].count > kn[j].count +} + +func sortedArray(m map[string]int) kNucArray { + kn := make(kNucArray, len(m)) + i := 0 + for k, v := range m { + kn[i].name = k + kn[i].count = v + i++ + } + sort.Sort(kn) + return kn +} + +func print(m map[string]int) { + a := sortedArray(m) + sum := 0 + for _, kn := range a { + sum += kn.count + } + for _, kn := range a { + fmt.Printf("%s %.3f\n", kn.name, 100*float64(kn.count)/float64(sum)) + } +} + +func main() { + in = bufio.NewReader(os.Stdin) + three := []byte(">THREE ") + for { + line, err := in.ReadSlice('\n') + if err != nil { + fmt.Fprintln(os.Stderr, "ReadLine err:", err) + os.Exit(2) + } + if line[0] == '>' && bytes.Equal(line[0:len(three)], three) { + break + } + } + data, err := ioutil.ReadAll(in) + if err != nil { + fmt.Fprintln(os.Stderr, "ReadAll err:", err) + os.Exit(2) + } + // delete the newlines and convert to upper case + j := 0 + for i := 0; i < len(data); i++ { + if data[i] != '\n' { + data[j] = data[i] &^ ' ' // upper case + j++ + } + } + str := string(data[0:j]) + + print(count(str, 1)) + fmt.Print("\n") + + print(count(str, 2)) + fmt.Print("\n") + + interests := []string{"GGT", "GGTA", "GGTATT", "GGTATTTTAATT", "GGTATTTTAATTTATAGT"} + for _, s := range interests { + fmt.Printf("%d %s\n", countOne(str, s), s) + } +} diff --git a/gcc/testsuite/go.test/test/bench/k-nucleotide.txt b/gcc/testsuite/go.test/test/bench/k-nucleotide.txt new file mode 100644 index 000000000..84169b8ec --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/k-nucleotide.txt @@ -0,0 +1,27 @@ +T 31.520 +A 29.600 +C 19.480 +G 19.400 + +AT 9.922 +TT 9.602 +TA 9.402 +AA 8.402 +GA 6.321 +TC 6.301 +TG 6.201 +GT 6.041 +CT 5.961 +AG 5.841 +CA 5.461 +AC 5.441 +CC 4.041 +CG 4.021 +GC 3.701 +GG 3.341 + +54 GGT +24 GGTA +4 GGTATT +0 GGTATTTTAATT +0 GGTATTTTAATTTATAGT diff --git a/gcc/testsuite/go.test/test/bench/mandelbrot.c b/gcc/testsuite/go.test/test/bench/mandelbrot.c new file mode 100644 index 000000000..c177c088c --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/mandelbrot.c @@ -0,0 +1,91 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Shootout + http://shootout.alioth.debian.org/ + + contributed by Greg Buchholz + + for the debian (AMD) machine... + compile flags: -O3 -ffast-math -march=athlon-xp -funroll-loops + + for the gp4 (Intel) machine... + compile flags: -O3 -ffast-math -march=pentium4 -funroll-loops +*/ + +#include + +int main (int argc, char **argv) +{ + int w, h, bit_num = 0; + char byte_acc = 0; + int i, iter = 50; + double x, y, limit = 2.0; + double Zr, Zi, Cr, Ci, Tr, Ti; + + w = h = atoi(argv[1]); + + printf("P4\n%d %d\n",w,h); + + for(y=0;y +#include +#define TRUE 1 +#define FALSE 0 + +/* The board is a 50 cell hexagonal pattern. For . . . . . + * maximum speed the board will be implemented as . . . . . + * 50 bits, which will fit into a 64 bit long long . . . . . + * int. . . . . . + * . . . . . + * I will represent 0's as empty cells and 1's . . . . . + * as full cells. . . . . . + * . . . . . + * . . . . . + * . . . . . + */ + +unsigned long long board = 0xFFFC000000000000ULL; + +/* The puzzle pieces must be specified by the path followed + * from one end to the other along 12 hexagonal directions. + * + * Piece 0 Piece 1 Piece 2 Piece 3 Piece 4 + * + * O O O O O O O O O O O O O O O + * O O O O O O O + * O O O + * + * Piece 5 Piece 6 Piece 7 Piece 8 Piece 9 + * + * O O O O O O O O O O O O O + * O O O O O O O O O + * O O O + * + * I had to make it 12 directions because I wanted all of the + * piece definitions to fit into the same size arrays. It is + * not possible to define piece 4 in terms of the 6 cardinal + * directions in 4 moves. + */ + +#define E 0 +#define ESE 1 +#define SE 2 +#define S 3 +#define SW 4 +#define WSW 5 +#define W 6 +#define WNW 7 +#define NW 8 +#define N 9 +#define NE 10 +#define ENE 11 +#define PIVOT 12 + +char piece_def[10][4] = { + { E, E, E, SE}, + { SE, E, NE, E}, + { E, E, SE, SW}, + { E, E, SW, SE}, + { SE, E, NE, S}, + { E, E, SW, E}, + { E, SE, SE, NE}, + { E, SE, SE, W}, + { E, SE, E, E}, + { E, E, E, SW} +}; + + +/* To minimize the amount of work done in the recursive solve function below, + * I'm going to allocate enough space for all legal rotations of each piece + * at each position on the board. That's 10 pieces x 50 board positions x + * 12 rotations. However, not all 12 rotations will fit on every cell, so + * I'll have to keep count of the actual number that do. + * The pieces are going to be unsigned long long ints just like the board so + * they can be bitwise-anded with the board to determine if they fit. + * I'm also going to record the next possible open cell for each piece and + * location to reduce the burden on the solve function. + */ +unsigned long long pieces[10][50][12]; +int piece_counts[10][50]; +char next_cell[10][50][12]; + +/* Returns the direction rotated 60 degrees clockwise */ +char rotate(char dir) { + return (dir + 2) % PIVOT; +} + +/* Returns the direction flipped on the horizontal axis */ +char flip(char dir) { + return (PIVOT - dir) % PIVOT; +} + + +/* Returns the new cell index from the specified cell in the + * specified direction. The index is only valid if the + * starting cell and direction have been checked by the + * out_of_bounds function first. + */ +char shift(char cell, char dir) { + switch(dir) { + case E: + return cell + 1; + case ESE: + if((cell / 5) % 2) + return cell + 7; + else + return cell + 6; + case SE: + if((cell / 5) % 2) + return cell + 6; + else + return cell + 5; + case S: + return cell + 10; + case SW: + if((cell / 5) % 2) + return cell + 5; + else + return cell + 4; + case WSW: + if((cell / 5) % 2) + return cell + 4; + else + return cell + 3; + case W: + return cell - 1; + case WNW: + if((cell / 5) % 2) + return cell - 6; + else + return cell - 7; + case NW: + if((cell / 5) % 2) + return cell - 5; + else + return cell - 6; + case N: + return cell - 10; + case NE: + if((cell / 5) % 2) + return cell - 4; + else + return cell - 5; + case ENE: + if((cell / 5) % 2) + return cell - 3; + else + return cell - 4; + default: + return cell; + } +} + +/* Returns wether the specified cell and direction will land outside + * of the board. Used to determine if a piece is at a legal board + * location or not. + */ +char out_of_bounds(char cell, char dir) { + char i; + switch(dir) { + case E: + return cell % 5 == 4; + case ESE: + i = cell % 10; + return i == 4 || i == 8 || i == 9 || cell >= 45; + case SE: + return cell % 10 == 9 || cell >= 45; + case S: + return cell >= 40; + case SW: + return cell % 10 == 0 || cell >= 45; + case WSW: + i = cell % 10; + return i == 0 || i == 1 || i == 5 || cell >= 45; + case W: + return cell % 5 == 0; + case WNW: + i = cell % 10; + return i == 0 || i == 1 || i == 5 || cell < 5; + case NW: + return cell % 10 == 0 || cell < 5; + case N: + return cell < 10; + case NE: + return cell % 10 == 9 || cell < 5; + case ENE: + i = cell % 10; + return i == 4 || i == 8 || i == 9 || cell < 5; + default: + return FALSE; + } +} + +/* Rotate a piece 60 degrees clockwise */ +void rotate_piece(int piece) { + int i; + for(i = 0; i < 4; i++) + piece_def[piece][i] = rotate(piece_def[piece][i]); +} + +/* Flip a piece along the horizontal axis */ +void flip_piece(int piece) { + int i; + for(i = 0; i < 4; i++) + piece_def[piece][i] = flip(piece_def[piece][i]); +} + +/* Convenience function to quickly calculate all of the indices for a piece */ +void calc_cell_indices(char *cell, int piece, char index) { + cell[0] = index; + cell[1] = shift(cell[0], piece_def[piece][0]); + cell[2] = shift(cell[1], piece_def[piece][1]); + cell[3] = shift(cell[2], piece_def[piece][2]); + cell[4] = shift(cell[3], piece_def[piece][3]); +} + +/* Convenience function to quickly calculate if a piece fits on the board */ +int cells_fit_on_board(char *cell, int piece) { + return (!out_of_bounds(cell[0], piece_def[piece][0]) && + !out_of_bounds(cell[1], piece_def[piece][1]) && + !out_of_bounds(cell[2], piece_def[piece][2]) && + !out_of_bounds(cell[3], piece_def[piece][3])); +} + +/* Returns the lowest index of the cells of a piece. + * I use the lowest index that a piece occupies as the index for looking up + * the piece in the solve function. + */ +char minimum_of_cells(char *cell) { + char minimum = cell[0]; + minimum = cell[1] < minimum ? cell[1] : minimum; + minimum = cell[2] < minimum ? cell[2] : minimum; + minimum = cell[3] < minimum ? cell[3] : minimum; + minimum = cell[4] < minimum ? cell[4] : minimum; + return minimum; +} + +/* Calculate the lowest possible open cell if the piece is placed on the board. + * Used to later reduce the amount of time searching for open cells in the + * solve function. + */ +char first_empty_cell(char *cell, char minimum) { + char first_empty = minimum; + while(first_empty == cell[0] || first_empty == cell[1] || + first_empty == cell[2] || first_empty == cell[3] || + first_empty == cell[4]) + first_empty++; + return first_empty; +} + +/* Generate the unsigned long long int that will later be anded with the + * board to determine if it fits. + */ +unsigned long long bitmask_from_cells(char *cell) { + unsigned long long piece_mask = 0ULL; + int i; + for(i = 0; i < 5; i++) + piece_mask |= 1ULL << cell[i]; + return piece_mask; +} + +/* Record the piece and other important information in arrays that will + * later be used by the solve function. + */ +void record_piece(int piece, int minimum, char first_empty, + unsigned long long piece_mask) { + pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask; + next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty; + piece_counts[piece][minimum]++; +} + + +/* Fill the entire board going cell by cell. If any cells are "trapped" + * they will be left alone. + */ +void fill_contiguous_space(char *board, int index) { + if(board[index] == 1) + return; + board[index] = 1; + if(!out_of_bounds(index, E)) + fill_contiguous_space(board, shift(index, E)); + if(!out_of_bounds(index, SE)) + fill_contiguous_space(board, shift(index, SE)); + if(!out_of_bounds(index, SW)) + fill_contiguous_space(board, shift(index, SW)); + if(!out_of_bounds(index, W)) + fill_contiguous_space(board, shift(index, W)); + if(!out_of_bounds(index, NW)) + fill_contiguous_space(board, shift(index, NW)); + if(!out_of_bounds(index, NE)) + fill_contiguous_space(board, shift(index, NE)); +} + + +/* To thin the number of pieces, I calculate if any of them trap any empty + * cells at the edges. There are only a handful of exceptions where the + * the board can be solved with the trapped cells. For example: piece 8 can + * trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0 + * can split the board in half where both halves are viable. + */ +int has_island(char *cell, int piece) { + char temp_board[50]; + char c; + int i; + for(i = 0; i < 50; i++) + temp_board[i] = 0; + for(i = 0; i < 5; i++) + temp_board[((int)cell[i])] = 1; + i = 49; + while(temp_board[i] == 1) + i--; + fill_contiguous_space(temp_board, i); + c = 0; + for(i = 0; i < 50; i++) + if(temp_board[i] == 0) + c++; + if(c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) || + (c % 5 == 0 && piece == 0)) + return FALSE; + else + return TRUE; +} + + +/* Calculate all six rotations of the specified piece at the specified index. + * We calculate only half of piece 3's rotations. This is because any solution + * found has an identical solution rotated 180 degrees. Thus we can reduce the + * number of attempted pieces in the solve algorithm by not including the 180- + * degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave + * me the best time ;) + */ + void calc_six_rotations(char piece, char index) { + char rotation, cell[5]; + char minimum, first_empty; + unsigned long long piece_mask; + + for(rotation = 0; rotation < 6; rotation++) { + if(piece != 3 || rotation < 3) { + calc_cell_indices(cell, piece, index); + if(cells_fit_on_board(cell, piece) && !has_island(cell, piece)) { + minimum = minimum_of_cells(cell); + first_empty = first_empty_cell(cell, minimum); + piece_mask = bitmask_from_cells(cell); + record_piece(piece, minimum, first_empty, piece_mask); + } + } + rotate_piece(piece); + } +} + +/* Calculate every legal rotation for each piece at each board location. */ +void calc_pieces(void) { + char piece, index; + + for(piece = 0; piece < 10; piece++) { + for(index = 0; index < 50; index++) { + calc_six_rotations(piece, index); + flip_piece(piece); + calc_six_rotations(piece, index); + } + } +} + + + +/* Calculate all 32 possible states for a 5-bit row and all rows that will + * create islands that follow any of the 32 possible rows. These pre- + * calculated 5-bit rows will be used to find islands in a partially solved + * board in the solve function. + */ +#define ROW_MASK 0x1F +#define TRIPLE_MASK 0x7FFF +char all_rows[32] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, + 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31}; +int bad_even_rows[32][32]; +int bad_odd_rows[32][32]; +int bad_even_triple[32768]; +int bad_odd_triple[32768]; + +int rows_bad(char row1, char row2, int even) { + /* even is referring to row1 */ + int i, in_zeroes, group_okay; + char block, row2_shift; + /* Test for blockages at same index and shifted index */ + if(even) + row2_shift = ((row2 << 1) & ROW_MASK) | 0x01; + else + row2_shift = (row2 >> 1) | 0x10; + block = ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift); + /* Test for groups of 0's */ + in_zeroes = FALSE; + group_okay = FALSE; + for(i = 0; i < 5; i++) { + if(row1 & (1 << i)) { + if(in_zeroes) { + if(!group_okay) + return TRUE; + in_zeroes = FALSE; + group_okay = FALSE; + } + } else { + if(!in_zeroes) + in_zeroes = TRUE; + if(!(block & (1 << i))) + group_okay = TRUE; + } + } + if(in_zeroes) + return !group_okay; + else + return FALSE; +} + +/* Check for cases where three rows checked sequentially cause a false + * positive. One scenario is when 5 cells may be surrounded where piece 5 + * or 7 can fit. The other scenario is when piece 2 creates a hook shape. + */ +int triple_is_okay(char row1, char row2, char row3, int even) { + if(even) { + /* There are four cases: + * row1: 00011 00001 11001 10101 + * row2: 01011 00101 10001 10001 + * row3: 011?? 00110 ????? ????? + */ + return ((row1 == 0x03) && (row2 == 0x0B) && ((row3 & 0x1C) == 0x0C)) || + ((row1 == 0x01) && (row2 == 0x05) && (row3 == 0x06)) || + ((row1 == 0x19) && (row2 == 0x11)) || + ((row1 == 0x15) && (row2 == 0x11)); + } else { + /* There are two cases: + * row1: 10011 10101 + * row2: 10001 10001 + * row3: ????? ????? + */ + return ((row1 == 0x13) && (row2 == 0x11)) || + ((row1 == 0x15) && (row2 == 0x11)); + } +} + + +void calc_rows(void) { + int row1, row2, row3; + int result1, result2; + for(row1 = 0; row1 < 32; row1++) { + for(row2 = 0; row2 < 32; row2++) { + bad_even_rows[row1][row2] = rows_bad(row1, row2, TRUE); + bad_odd_rows[row1][row2] = rows_bad(row1, row2, FALSE); + } + } + for(row1 = 0; row1 < 32; row1++) { + for(row2 = 0; row2 < 32; row2++) { + for(row3 = 0; row3 < 32; row3++) { + result1 = bad_even_rows[row1][row2]; + result2 = bad_odd_rows[row2][row3]; + if(result1 == FALSE && result2 == TRUE + && triple_is_okay(row1, row2, row3, TRUE)) + bad_even_triple[row1+(row2*32)+(row3*1024)] = FALSE; + else + bad_even_triple[row1+(row2*32)+(row3*1024)] = result1 || result2; + + result1 = bad_odd_rows[row1][row2]; + result2 = bad_even_rows[row2][row3]; + if(result1 == FALSE && result2 == TRUE + && triple_is_okay(row1, row2, row3, FALSE)) + bad_odd_triple[row1+(row2*32)+(row3*1024)] = FALSE; + else + bad_odd_triple[row1+(row2*32)+(row3*1024)] = result1 || result2; + } + } + } +} + + + +/* Calculate islands while solving the board. + */ +int boardHasIslands(char cell) { + /* Too low on board, don't bother checking */ + if(cell >= 40) + return FALSE; + int current_triple = (board >> ((cell / 5) * 5)) & TRIPLE_MASK; + if((cell / 5) % 2) + return bad_odd_triple[current_triple]; + else + return bad_even_triple[current_triple]; +} + + +/* The recursive solve algorithm. Try to place each permutation in the upper- + * leftmost empty cell. Mark off available pieces as it goes along. + * Because the board is a bit mask, the piece number and bit mask must be saved + * at each successful piece placement. This data is used to create a 50 char + * array if a solution is found. + */ +short avail = 0x03FF; +char sol_nums[10]; +unsigned long long sol_masks[10]; +signed char solutions[2100][50]; +int solution_count = 0; +int max_solutions = 2100; + +void record_solution(void) { + int sol_no, index; + unsigned long long sol_mask; + for(sol_no = 0; sol_no < 10; sol_no++) { + sol_mask = sol_masks[sol_no]; + for(index = 0; index < 50; index++) { + if(sol_mask & 1ULL) { + solutions[solution_count][index] = sol_nums[sol_no]; + /* Board rotated 180 degrees is a solution too! */ + solutions[solution_count+1][49-index] = sol_nums[sol_no]; + } + sol_mask = sol_mask >> 1; + } + } + solution_count += 2; +} + +void solve(int depth, int cell) { + int piece, rotation, max_rots; + unsigned long long *piece_mask; + short piece_no_mask; + + if(solution_count >= max_solutions) + return; + + while(board & (1ULL << cell)) + cell++; + + for(piece = 0; piece < 10; piece++) { + piece_no_mask = 1 << piece; + if(!(avail & piece_no_mask)) + continue; + avail ^= piece_no_mask; + max_rots = piece_counts[piece][cell]; + piece_mask = pieces[piece][cell]; + for(rotation = 0; rotation < max_rots; rotation++) { + if(!(board & *(piece_mask + rotation))) { + sol_nums[depth] = piece; + sol_masks[depth] = *(piece_mask + rotation); + if(depth == 9) { + /* Solution found!!!!!11!!ONE! */ + record_solution(); + avail ^= piece_no_mask; + return; + } + board |= *(piece_mask + rotation); + if(!boardHasIslands(next_cell[piece][cell][rotation])) + solve(depth + 1, next_cell[piece][cell][rotation]); + board ^= *(piece_mask + rotation); + } + } + avail ^= piece_no_mask; + } +} + + +/* qsort comparator - used to find first and last solutions */ +int solution_sort(const void *elem1, const void *elem2) { + signed char *char1 = (signed char *) elem1; + signed char *char2 = (signed char *) elem2; + int i = 0; + while(i < 50 && char1[i] == char2[i]) + i++; + return char1[i] - char2[i]; +} + + +/* pretty print a board in the specified hexagonal format */ +void pretty(signed char *b) { + int i; + for(i = 0; i < 50; i += 10) { + printf("%c %c %c %c %c \n %c %c %c %c %c \n", b[i]+'0', b[i+1]+'0', + b[i+2]+'0', b[i+3]+'0', b[i+4]+'0', b[i+5]+'0', b[i+6]+'0', + b[i+7]+'0', b[i+8]+'0', b[i+9]+'0'); + } + printf("\n"); +} + +int main(int argc, char **argv) { + if(argc > 1) + max_solutions = atoi(argv[1]); + calc_pieces(); + calc_rows(); + solve(0, 0); + printf("%d solutions found\n\n", solution_count); + qsort(solutions, solution_count, 50 * sizeof(signed char), solution_sort); + pretty(solutions[0]); + pretty(solutions[solution_count-1]); + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/meteor-contest.go b/gcc/testsuite/go.test/test/bench/meteor-contest.go new file mode 100644 index 000000000..6660810eb --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/meteor-contest.go @@ -0,0 +1,665 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on meteor-contest.c by Christian Vosteen + */ + +package main + +import ( + "flag" + "fmt" +) + +var max_solutions = flag.Int("n", 2100, "maximum number of solutions") + + +func boolInt(b bool) int8 { + if b { + return 1 + } + return 0 +} + +/* The board is a 50 cell hexagonal pattern. For . . . . . + * maximum speed the board will be implemented as . . . . . + * 50 bits, which will fit into a 64 bit long long . . . . . + * int. . . . . . + * . . . . . + * I will represent 0's as empty cells and 1's . . . . . + * as full cells. . . . . . + * . . . . . + * . . . . . + * . . . . . + */ + +var board uint64 = 0xFFFC000000000000 + +/* The puzzle pieces must be specified by the path followed + * from one end to the other along 12 hexagonal directions. + * + * Piece 0 Piece 1 Piece 2 Piece 3 Piece 4 + * + * O O O O O O O O O O O O O O O + * O O O O O O O + * O O O + * + * Piece 5 Piece 6 Piece 7 Piece 8 Piece 9 + * + * O O O O O O O O O O O O O + * O O O O O O O O O + * O O O + * + * I had to make it 12 directions because I wanted all of the + * piece definitions to fit into the same size arrays. It is + * not possible to define piece 4 in terms of the 6 cardinal + * directions in 4 moves. + */ + +const ( + E = iota + ESE + SE + S + SW + WSW + W + WNW + NW + N + NE + ENE + PIVOT +) + +var piece_def = [10][4]int8{ + [4]int8{E, E, E, SE}, + [4]int8{SE, E, NE, E}, + [4]int8{E, E, SE, SW}, + [4]int8{E, E, SW, SE}, + [4]int8{SE, E, NE, S}, + [4]int8{E, E, SW, E}, + [4]int8{E, SE, SE, NE}, + [4]int8{E, SE, SE, W}, + [4]int8{E, SE, E, E}, + [4]int8{E, E, E, SW}, +} + + +/* To minimize the amount of work done in the recursive solve function below, + * I'm going to allocate enough space for all legal rotations of each piece + * at each position on the board. That's 10 pieces x 50 board positions x + * 12 rotations. However, not all 12 rotations will fit on every cell, so + * I'll have to keep count of the actual number that do. + * The pieces are going to be unsigned long long ints just like the board so + * they can be bitwise-anded with the board to determine if they fit. + * I'm also going to record the next possible open cell for each piece and + * location to reduce the burden on the solve function. + */ +var ( + pieces [10][50][12]uint64 + piece_counts [10][50]int + next_cell [10][50][12]int8 +) + +/* Returns the direction rotated 60 degrees clockwise */ +func rotate(dir int8) int8 { return (dir + 2) % PIVOT } + +/* Returns the direction flipped on the horizontal axis */ +func flip(dir int8) int8 { return (PIVOT - dir) % PIVOT } + + +/* Returns the new cell index from the specified cell in the + * specified direction. The index is only valid if the + * starting cell and direction have been checked by the + * out_of_bounds function first. + */ +func shift(cell, dir int8) int8 { + switch dir { + case E: + return cell + 1 + case ESE: + if ((cell / 5) % 2) != 0 { + return cell + 7 + } else { + return cell + 6 + } + case SE: + if ((cell / 5) % 2) != 0 { + return cell + 6 + } else { + return cell + 5 + } + case S: + return cell + 10 + case SW: + if ((cell / 5) % 2) != 0 { + return cell + 5 + } else { + return cell + 4 + } + case WSW: + if ((cell / 5) % 2) != 0 { + return cell + 4 + } else { + return cell + 3 + } + case W: + return cell - 1 + case WNW: + if ((cell / 5) % 2) != 0 { + return cell - 6 + } else { + return cell - 7 + } + case NW: + if ((cell / 5) % 2) != 0 { + return cell - 5 + } else { + return cell - 6 + } + case N: + return cell - 10 + case NE: + if ((cell / 5) % 2) != 0 { + return cell - 4 + } else { + return cell - 5 + } + case ENE: + if ((cell / 5) % 2) != 0 { + return cell - 3 + } else { + return cell - 4 + } + } + return cell +} + +/* Returns wether the specified cell and direction will land outside + * of the board. Used to determine if a piece is at a legal board + * location or not. + */ +func out_of_bounds(cell, dir int8) bool { + switch dir { + case E: + return cell%5 == 4 + case ESE: + i := cell % 10 + return i == 4 || i == 8 || i == 9 || cell >= 45 + case SE: + return cell%10 == 9 || cell >= 45 + case S: + return cell >= 40 + case SW: + return cell%10 == 0 || cell >= 45 + case WSW: + i := cell % 10 + return i == 0 || i == 1 || i == 5 || cell >= 45 + case W: + return cell%5 == 0 + case WNW: + i := cell % 10 + return i == 0 || i == 1 || i == 5 || cell < 5 + case NW: + return cell%10 == 0 || cell < 5 + case N: + return cell < 10 + case NE: + return cell%10 == 9 || cell < 5 + case ENE: + i := cell % 10 + return i == 4 || i == 8 || i == 9 || cell < 5 + } + return false +} + +/* Rotate a piece 60 degrees clockwise */ +func rotate_piece(piece int) { + for i := 0; i < 4; i++ { + piece_def[piece][i] = rotate(piece_def[piece][i]) + } +} + +/* Flip a piece along the horizontal axis */ +func flip_piece(piece int) { + for i := 0; i < 4; i++ { + piece_def[piece][i] = flip(piece_def[piece][i]) + } +} + +/* Convenience function to quickly calculate all of the indices for a piece */ +func calc_cell_indices(cell []int8, piece int, index int8) { + cell[0] = index + for i := 1; i < 5; i++ { + cell[i] = shift(cell[i-1], piece_def[piece][i-1]) + } +} + +/* Convenience function to quickly calculate if a piece fits on the board */ +func cells_fit_on_board(cell []int8, piece int) bool { + return !out_of_bounds(cell[0], piece_def[piece][0]) && + !out_of_bounds(cell[1], piece_def[piece][1]) && + !out_of_bounds(cell[2], piece_def[piece][2]) && + !out_of_bounds(cell[3], piece_def[piece][3]) +} + +/* Returns the lowest index of the cells of a piece. + * I use the lowest index that a piece occupies as the index for looking up + * the piece in the solve function. + */ +func minimum_of_cells(cell []int8) int8 { + minimum := cell[0] + for i := 1; i < 5; i++ { + if cell[i] < minimum { + minimum = cell[i] + } + } + return minimum +} + +/* Calculate the lowest possible open cell if the piece is placed on the board. + * Used to later reduce the amount of time searching for open cells in the + * solve function. + */ +func first_empty_cell(cell []int8, minimum int8) int8 { + first_empty := minimum + for first_empty == cell[0] || first_empty == cell[1] || + first_empty == cell[2] || first_empty == cell[3] || + first_empty == cell[4] { + first_empty++ + } + return first_empty +} + +/* Generate the unsigned long long int that will later be anded with the + * board to determine if it fits. + */ +func bitmask_from_cells(cell []int8) uint64 { + var piece_mask uint64 + for i := 0; i < 5; i++ { + piece_mask |= 1 << uint(cell[i]) + } + return piece_mask +} + +/* Record the piece and other important information in arrays that will + * later be used by the solve function. + */ +func record_piece(piece int, minimum int8, first_empty int8, piece_mask uint64) { + pieces[piece][minimum][piece_counts[piece][minimum]] = piece_mask + next_cell[piece][minimum][piece_counts[piece][minimum]] = first_empty + piece_counts[piece][minimum]++ +} + + +/* Fill the entire board going cell by cell. If any cells are "trapped" + * they will be left alone. + */ +func fill_contiguous_space(board []int8, index int8) { + if board[index] == 1 { + return + } + board[index] = 1 + if !out_of_bounds(index, E) { + fill_contiguous_space(board, shift(index, E)) + } + if !out_of_bounds(index, SE) { + fill_contiguous_space(board, shift(index, SE)) + } + if !out_of_bounds(index, SW) { + fill_contiguous_space(board, shift(index, SW)) + } + if !out_of_bounds(index, W) { + fill_contiguous_space(board, shift(index, W)) + } + if !out_of_bounds(index, NW) { + fill_contiguous_space(board, shift(index, NW)) + } + if !out_of_bounds(index, NE) { + fill_contiguous_space(board, shift(index, NE)) + } +} + + +/* To thin the number of pieces, I calculate if any of them trap any empty + * cells at the edges. There are only a handful of exceptions where the + * the board can be solved with the trapped cells. For example: piece 8 can + * trap 5 cells in the corner, but piece 3 can fit in those cells, or piece 0 + * can split the board in half where both halves are viable. + */ +func has_island(cell []int8, piece int) bool { + temp_board := make([]int8, 50) + var i int + for i = 0; i < 5; i++ { + temp_board[cell[i]] = 1 + } + i = 49 + for temp_board[i] == 1 { + i-- + } + fill_contiguous_space(temp_board, int8(i)) + c := 0 + for i = 0; i < 50; i++ { + if temp_board[i] == 0 { + c++ + } + } + if c == 0 || (c == 5 && piece == 8) || (c == 40 && piece == 8) || + (c%5 == 0 && piece == 0) { + return false + } + return true +} + + +/* Calculate all six rotations of the specified piece at the specified index. + * We calculate only half of piece 3's rotations. This is because any solution + * found has an identical solution rotated 180 degrees. Thus we can reduce the + * number of attempted pieces in the solve algorithm by not including the 180- + * degree-rotated pieces of ONE of the pieces. I chose piece 3 because it gave + * me the best time ;) + */ +func calc_six_rotations(piece, index int) { + cell := make([]int8, 5) + for rotation := 0; rotation < 6; rotation++ { + if piece != 3 || rotation < 3 { + calc_cell_indices(cell, piece, int8(index)) + if cells_fit_on_board(cell, piece) && !has_island(cell, piece) { + minimum := minimum_of_cells(cell) + first_empty := first_empty_cell(cell, minimum) + piece_mask := bitmask_from_cells(cell) + record_piece(piece, minimum, first_empty, piece_mask) + } + } + rotate_piece(piece) + } +} + +/* Calculate every legal rotation for each piece at each board location. */ +func calc_pieces() { + for piece := 0; piece < 10; piece++ { + for index := 0; index < 50; index++ { + calc_six_rotations(piece, index) + flip_piece(piece) + calc_six_rotations(piece, index) + } + } +} + + +/* Calculate all 32 possible states for a 5-bit row and all rows that will + * create islands that follow any of the 32 possible rows. These pre- + * calculated 5-bit rows will be used to find islands in a partially solved + * board in the solve function. + */ +const ( + ROW_MASK = 0x1F + TRIPLE_MASK = 0x7FFF +) + +var ( + all_rows = [32]int8{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, + 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, + } + bad_even_rows [32][32]int8 + bad_odd_rows [32][32]int8 + bad_even_triple [32768]int8 + bad_odd_triple [32768]int8 +) + +func rows_bad(row1, row2 int8, even bool) int8 { + /* even is referring to row1 */ + var row2_shift int8 + /* Test for blockages at same index and shifted index */ + if even { + row2_shift = ((row2 << 1) & ROW_MASK) | 0x01 + } else { + row2_shift = (row2 >> 1) | 0x10 + } + block := ((row1 ^ row2) & row2) & ((row1 ^ row2_shift) & row2_shift) + /* Test for groups of 0's */ + in_zeroes := false + group_okay := false + for i := uint8(0); i < 5; i++ { + if row1&(1<= 40 { + return 0 + } + current_triple := (board >> uint((cell/5)*5)) & TRIPLE_MASK + if (cell/5)%2 != 0 { + return bad_odd_triple[current_triple] + } + return bad_even_triple[current_triple] +} + + +/* The recursive solve algorithm. Try to place each permutation in the upper- + * leftmost empty cell. Mark off available pieces as it goes along. + * Because the board is a bit mask, the piece number and bit mask must be saved + * at each successful piece placement. This data is used to create a 50 char + * array if a solution is found. + */ +var ( + avail uint16 = 0x03FF + sol_nums [10]int8 + sol_masks [10]uint64 + solutions [2100][50]int8 + solution_count = 0 +) + +func record_solution() { + for sol_no := 0; sol_no < 10; sol_no++ { + sol_mask := sol_masks[sol_no] + for index := 0; index < 50; index++ { + if sol_mask&1 == 1 { + solutions[solution_count][index] = sol_nums[sol_no] + /* Board rotated 180 degrees is a solution too! */ + solutions[solution_count+1][49-index] = sol_nums[sol_no] + } + sol_mask = sol_mask >> 1 + } + } + solution_count += 2 +} + +func solve(depth, cell int8) { + if solution_count >= *max_solutions { + return + } + + for board&(1< s { + largest = candidate + } + break + } + } + return +} + +func main() { + flag.Parse() + calc_pieces() + calc_rows() + solve(0, 0) + fmt.Printf("%d solutions found\n\n", solution_count) + smallest, largest := smallest_largest() + pretty(smallest) + pretty(largest) +} diff --git a/gcc/testsuite/go.test/test/bench/meteor-contest.txt b/gcc/testsuite/go.test/test/bench/meteor-contest.txt new file mode 100644 index 000000000..38d9783d6 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/meteor-contest.txt @@ -0,0 +1,24 @@ +2098 solutions found + +0 0 0 0 1 + 2 2 2 0 1 +2 6 6 1 1 + 2 6 1 5 5 +8 6 5 5 5 + 8 6 3 3 3 +4 8 8 9 3 + 4 4 8 9 3 +4 7 4 7 9 + 7 7 7 9 9 + +9 9 9 9 8 + 9 6 6 8 5 +6 6 8 8 5 + 6 8 2 5 5 +7 7 7 2 5 + 7 4 7 2 0 +1 4 2 2 0 + 1 4 4 0 3 +1 4 0 0 3 + 1 1 3 3 3 + diff --git a/gcc/testsuite/go.test/test/bench/nbody.c b/gcc/testsuite/go.test/test/bench/nbody.c new file mode 100644 index 000000000..3b95b0592 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/nbody.c @@ -0,0 +1,170 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Great Computer Language Shootout + * http://shootout.alioth.debian.org/ + * + * contributed by Christoph Bauer + * + */ + +#include +#include +#include + +#define pi 3.141592653589793 +#define solar_mass (4 * pi * pi) +#define days_per_year 365.24 + +struct planet { + double x, y, z; + double vx, vy, vz; + double mass; +}; + +void advance(int nbodies, struct planet * bodies, double dt) +{ + int i, j; + + for (i = 0; i < nbodies; i++) { + struct planet * b = &(bodies[i]); + for (j = i + 1; j < nbodies; j++) { + struct planet * b2 = &(bodies[j]); + double dx = b->x - b2->x; + double dy = b->y - b2->y; + double dz = b->z - b2->z; + double distance = sqrt(dx * dx + dy * dy + dz * dz); + double mag = dt / (distance * distance * distance); + b->vx -= dx * b2->mass * mag; + b->vy -= dy * b2->mass * mag; + b->vz -= dz * b2->mass * mag; + b2->vx += dx * b->mass * mag; + b2->vy += dy * b->mass * mag; + b2->vz += dz * b->mass * mag; + } + } + for (i = 0; i < nbodies; i++) { + struct planet * b = &(bodies[i]); + b->x += dt * b->vx; + b->y += dt * b->vy; + b->z += dt * b->vz; + } +} + +double energy(int nbodies, struct planet * bodies) +{ + double e; + int i, j; + + e = 0.0; + for (i = 0; i < nbodies; i++) { + struct planet * b = &(bodies[i]); + e += 0.5 * b->mass * (b->vx * b->vx + b->vy * b->vy + b->vz * b->vz); + for (j = i + 1; j < nbodies; j++) { + struct planet * b2 = &(bodies[j]); + double dx = b->x - b2->x; + double dy = b->y - b2->y; + double dz = b->z - b2->z; + double distance = sqrt(dx * dx + dy * dy + dz * dz); + e -= (b->mass * b2->mass) / distance; + } + } + return e; +} + +void offset_momentum(int nbodies, struct planet * bodies) +{ + double px = 0.0, py = 0.0, pz = 0.0; + int i; + for (i = 0; i < nbodies; i++) { + px += bodies[i].vx * bodies[i].mass; + py += bodies[i].vy * bodies[i].mass; + pz += bodies[i].vz * bodies[i].mass; + } + bodies[0].vx = - px / solar_mass; + bodies[0].vy = - py / solar_mass; + bodies[0].vz = - pz / solar_mass; +} + +#define NBODIES 5 +struct planet bodies[NBODIES] = { + { /* sun */ + 0, 0, 0, 0, 0, 0, solar_mass + }, + { /* jupiter */ + 4.84143144246472090e+00, + -1.16032004402742839e+00, + -1.03622044471123109e-01, + 1.66007664274403694e-03 * days_per_year, + 7.69901118419740425e-03 * days_per_year, + -6.90460016972063023e-05 * days_per_year, + 9.54791938424326609e-04 * solar_mass + }, + { /* saturn */ + 8.34336671824457987e+00, + 4.12479856412430479e+00, + -4.03523417114321381e-01, + -2.76742510726862411e-03 * days_per_year, + 4.99852801234917238e-03 * days_per_year, + 2.30417297573763929e-05 * days_per_year, + 2.85885980666130812e-04 * solar_mass + }, + { /* uranus */ + 1.28943695621391310e+01, + -1.51111514016986312e+01, + -2.23307578892655734e-01, + 2.96460137564761618e-03 * days_per_year, + 2.37847173959480950e-03 * days_per_year, + -2.96589568540237556e-05 * days_per_year, + 4.36624404335156298e-05 * solar_mass + }, + { /* neptune */ + 1.53796971148509165e+01, + -2.59193146099879641e+01, + 1.79258772950371181e-01, + 2.68067772490389322e-03 * days_per_year, + 1.62824170038242295e-03 * days_per_year, + -9.51592254519715870e-05 * days_per_year, + 5.15138902046611451e-05 * solar_mass + } +}; + +int main(int argc, char ** argv) +{ + int n = atoi(argv[1]); + int i; + + offset_momentum(NBODIES, bodies); + printf ("%.9f\n", energy(NBODIES, bodies)); + for (i = 1; i <= n; i++) + advance(NBODIES, bodies, 0.01); + printf ("%.9f\n", energy(NBODIES, bodies)); + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/nbody.go b/gcc/testsuite/go.test/test/bench/nbody.go new file mode 100644 index 000000000..e9f4517e8 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/nbody.go @@ -0,0 +1,177 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on C program by Christoph Bauer + */ + +package main + +import ( + "flag" + "fmt" + "math" +) + +var n = flag.Int("n", 1000, "number of iterations") + +type Body struct { + x, y, z, vx, vy, vz, mass float64 +} + +const ( + solarMass = 4 * math.Pi * math.Pi + daysPerYear = 365.24 +) + +func (b *Body) offsetMomentum(px, py, pz float64) { + b.vx = -px / solarMass + b.vy = -py / solarMass + b.vz = -pz / solarMass +} + +type System []*Body + +func NewSystem(body []Body) System { + n := make(System, len(body)) + for i := 0; i < len(body); i++ { + n[i] = new(Body) // copy to avoid overwriting the inputs + *n[i] = body[i] + } + var px, py, pz float64 + for _, body := range n { + px += body.vx * body.mass + py += body.vy * body.mass + pz += body.vz * body.mass + } + n[0].offsetMomentum(px, py, pz) + return n +} + +func (sys System) energy() float64 { + var e float64 + for i, body := range sys { + e += 0.5 * body.mass * + (body.vx*body.vx + body.vy*body.vy + body.vz*body.vz) + for j := i + 1; j < len(sys); j++ { + body2 := sys[j] + dx := body.x - body2.x + dy := body.y - body2.y + dz := body.z - body2.z + distance := math.Sqrt(dx*dx + dy*dy + dz*dz) + e -= (body.mass * body2.mass) / distance + } + } + return e +} + +func (sys System) advance(dt float64) { + for i, body := range sys { + for j := i + 1; j < len(sys); j++ { + body2 := sys[j] + dx := body.x - body2.x + dy := body.y - body2.y + dz := body.z - body2.z + + dSquared := dx*dx + dy*dy + dz*dz + distance := math.Sqrt(dSquared) + mag := dt / (dSquared * distance) + + body.vx -= dx * body2.mass * mag + body.vy -= dy * body2.mass * mag + body.vz -= dz * body2.mass * mag + + body2.vx += dx * body.mass * mag + body2.vy += dy * body.mass * mag + body2.vz += dz * body.mass * mag + } + } + + for _, body := range sys { + body.x += dt * body.vx + body.y += dt * body.vy + body.z += dt * body.vz + } +} + +var ( + jupiter = Body{ + x: 4.84143144246472090e+00, + y: -1.16032004402742839e+00, + z: -1.03622044471123109e-01, + vx: 1.66007664274403694e-03 * daysPerYear, + vy: 7.69901118419740425e-03 * daysPerYear, + vz: -6.90460016972063023e-05 * daysPerYear, + mass: 9.54791938424326609e-04 * solarMass, + } + saturn = Body{ + x: 8.34336671824457987e+00, + y: 4.12479856412430479e+00, + z: -4.03523417114321381e-01, + vx: -2.76742510726862411e-03 * daysPerYear, + vy: 4.99852801234917238e-03 * daysPerYear, + vz: 2.30417297573763929e-05 * daysPerYear, + mass: 2.85885980666130812e-04 * solarMass, + } + uranus = Body{ + x: 1.28943695621391310e+01, + y: -1.51111514016986312e+01, + z: -2.23307578892655734e-01, + vx: 2.96460137564761618e-03 * daysPerYear, + vy: 2.37847173959480950e-03 * daysPerYear, + vz: -2.96589568540237556e-05 * daysPerYear, + mass: 4.36624404335156298e-05 * solarMass, + } + neptune = Body{ + x: 1.53796971148509165e+01, + y: -2.59193146099879641e+01, + z: 1.79258772950371181e-01, + vx: 2.68067772490389322e-03 * daysPerYear, + vy: 1.62824170038242295e-03 * daysPerYear, + vz: -9.51592254519715870e-05 * daysPerYear, + mass: 5.15138902046611451e-05 * solarMass, + } + sun = Body{ + mass: solarMass, + } +) + +func main() { + flag.Parse() + + system := NewSystem([]Body{sun, jupiter, saturn, uranus, neptune}) + fmt.Printf("%.9f\n", system.energy()) + for i := 0; i < *n; i++ { + system.advance(0.01) + } + fmt.Printf("%.9f\n", system.energy()) +} diff --git a/gcc/testsuite/go.test/test/bench/nbody.txt b/gcc/testsuite/go.test/test/bench/nbody.txt new file mode 100644 index 000000000..1731557ce --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/nbody.txt @@ -0,0 +1,2 @@ +-0.169075164 +-0.169087605 diff --git a/gcc/testsuite/go.test/test/bench/pidigits.c b/gcc/testsuite/go.test/test/bench/pidigits.c new file mode 100644 index 000000000..c064da0dd --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/pidigits.c @@ -0,0 +1,123 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + http://shootout.alioth.debian.org/ + + contributed by Paolo Bonzini & Sean Bartlett + modified by Michael Mellor +*/ + +#include +#include +#include + +static mpz_t numer, accum, denom, tmp1, tmp2; + +static int extract_digit() +{ + if (mpz_cmp(numer, accum) > 0) + return -1; + + /* Compute (numer * 3 + accum) / denom */ + mpz_mul_2exp(tmp1, numer, 1); + mpz_add(tmp1, tmp1, numer); + mpz_add(tmp1, tmp1, accum); + mpz_fdiv_qr(tmp1, tmp2, tmp1, denom); + + /* Now, if (numer * 4 + accum) % denom... */ + mpz_add(tmp2, tmp2, numer); + + /* ... is normalized, then the two divisions have the same result. */ + if (mpz_cmp(tmp2, denom) >= 0) + return -1; + + return mpz_get_ui(tmp1); +} + +static void next_term(unsigned int k) +{ + unsigned int y2 = k*2 + 1; + + mpz_mul_2exp(tmp1, numer, 1); + mpz_add(accum, accum, tmp1); + mpz_mul_ui(accum, accum, y2); + mpz_mul_ui(numer, numer, k); + mpz_mul_ui(denom, denom, y2); +} + +static void eliminate_digit(unsigned int d) +{ + mpz_submul_ui(accum, denom, d); + mpz_mul_ui(accum, accum, 10); + mpz_mul_ui(numer, numer, 10); +} + +static void pidigits(unsigned int n) +{ + int d; + unsigned int i = 0, k = 0, m; + mpz_init(tmp1); + mpz_init(tmp2); + mpz_init_set_ui(numer, 1); + mpz_init_set_ui(accum, 0); + mpz_init_set_ui(denom, 1); + + for(;;) + { + do { + k++; + next_term(k); + d = extract_digit(); + } while(d == -1); + + putchar(d + '0'); + + i++; + m = i%10; + if(m == 0) + printf("\t:%d\n", i); + if(i >= n) + break; + eliminate_digit(d); + } + + if(m) { + m = 10 - m; + while(m--) + putchar(' '); + printf("\t:%d\n", n); + } +} + +int main(int argc, char **argv) +{ + pidigits(argc > 1 ? atoi(argv[1]) : 27); + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/pidigits.go b/gcc/testsuite/go.test/test/bench/pidigits.go new file mode 100644 index 000000000..dcfb502ce --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/pidigits.go @@ -0,0 +1,135 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * based on pidigits.c (by Paolo Bonzini & Sean Bartlett, + * modified by Michael Mellor) + */ + +package main + +import ( + "big" + "flag" + "fmt" +) + +var n = flag.Int("n", 27, "number of digits") +var silent = flag.Bool("s", false, "don't print result") + +var ( + tmp1 = big.NewInt(0) + tmp2 = big.NewInt(0) + y2 = big.NewInt(0) + bigk = big.NewInt(0) + numer = big.NewInt(1) + accum = big.NewInt(0) + denom = big.NewInt(1) + ten = big.NewInt(10) +) + +func extract_digit() int64 { + if numer.Cmp(accum) > 0 { + return -1 + } + + // Compute (numer * 3 + accum) / denom + tmp1.Lsh(numer, 1) + tmp1.Add(tmp1, numer) + tmp1.Add(tmp1, accum) + tmp1.DivMod(tmp1, denom, tmp2) + + // Now, if (numer * 4 + accum) % denom... + tmp2.Add(tmp2, numer) + + // ... is normalized, then the two divisions have the same result. + if tmp2.Cmp(denom) >= 0 { + return -1 + } + + return tmp1.Int64() +} + +func next_term(k int64) { + // TODO(eds) If big.Int ever gets a Scale method, y2 and bigk could be int64 + y2.SetInt64(k*2 + 1) + bigk.SetInt64(k) + + tmp1.Lsh(numer, 1) + accum.Add(accum, tmp1) + accum.Mul(accum, y2) + numer.Mul(numer, bigk) + denom.Mul(denom, y2) +} + +func eliminate_digit(d int64) { + tmp := big.NewInt(0).Set(denom) + accum.Sub(accum, tmp.Mul(tmp, big.NewInt(d))) + accum.Mul(accum, ten) + numer.Mul(numer, ten) +} + +func printf(s string, arg ...interface{}) { + if !*silent { + fmt.Printf(s, arg) + } +} + +func main() { + flag.Parse() + + var m int // 0 <= m < 10 + for i, k := 0, int64(0); ; { + d := int64(-1) + for d < 0 { + k++ + next_term(k) + d = extract_digit() + } + + printf("%c", d+'0') + + i++ + m = i % 10 + if m == 0 { + printf("\t:%d\n", i) + } + if i >= *n { + break + } + eliminate_digit(d) + } + + if m > 0 { + printf("%s\t:%d\n", " "[m:10], *n) + } +} diff --git a/gcc/testsuite/go.test/test/bench/pidigits.txt b/gcc/testsuite/go.test/test/bench/pidigits.txt new file mode 100644 index 000000000..ad946a9e8 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/pidigits.txt @@ -0,0 +1,3 @@ +3141592653 :10 +5897932384 :20 +6264338 :27 diff --git a/gcc/testsuite/go.test/test/bench/regex-dna-parallel.go b/gcc/testsuite/go.test/test/bench/regex-dna-parallel.go new file mode 100644 index 000000000..e8e62b806 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/regex-dna-parallel.go @@ -0,0 +1,124 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "fmt" + "io/ioutil" + "os" + "runtime" + "regexp" +) + +var variants = []string{ + "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", +} + +type Subst struct { + pat, repl string +} + +var substs = []Subst{ + Subst{"B", "(c|g|t)"}, + Subst{"D", "(a|g|t)"}, + Subst{"H", "(a|c|t)"}, + Subst{"K", "(g|t)"}, + Subst{"M", "(a|c)"}, + Subst{"N", "(a|c|g|t)"}, + Subst{"R", "(a|g)"}, + Subst{"S", "(c|g)"}, + Subst{"V", "(a|c|g)"}, + Subst{"W", "(a|t)"}, + Subst{"Y", "(c|t)"}, +} + +func countMatches(pat string, bytes []byte) int { + re := regexp.MustCompile(pat) + n := 0 + for { + e := re.FindIndex(bytes) + if e == nil { + break + } + n++ + bytes = bytes[e[1]:] + } + return n +} + +func main() { + runtime.GOMAXPROCS(4) + bytes, err := ioutil.ReadFile("/dev/stdin") + if err != nil { + fmt.Fprintf(os.Stderr, "can't read input: %s\n", err) + os.Exit(2) + } + ilen := len(bytes) + // Delete the comment lines and newlines + bytes = regexp.MustCompile("(>[^\n]+)?\n").ReplaceAll(bytes, []byte{}) + clen := len(bytes) + + mresults := make([]chan int, len(variants)) + for i, s := range variants { + ch := make(chan int) + mresults[i] = ch + go func(ss string) { + ch <- countMatches(ss, bytes) + }(s) + } + + lenresult := make(chan int) + bb := bytes + go func() { + for _, sub := range substs { + bb = regexp.MustCompile(sub.pat).ReplaceAll(bb, []byte(sub.repl)) + } + lenresult <- len(bb) + }() + + for i, s := range variants { + fmt.Printf("%s %d\n", s, <-mresults[i]) + } + fmt.Printf("\n%d\n%d\n%d\n", ilen, clen, <-lenresult) +} diff --git a/gcc/testsuite/go.test/test/bench/regex-dna-parallel.txt b/gcc/testsuite/go.test/test/bench/regex-dna-parallel.txt new file mode 100644 index 000000000..e23e71fd6 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/regex-dna-parallel.txt @@ -0,0 +1,13 @@ +agggtaaa|tttaccct 1 +[cgt]gggtaaa|tttaccc[acg] 0 +a[act]ggtaaa|tttacc[agt]t 0 +ag[act]gtaaa|tttac[agt]ct 0 +agg[act]taaa|ttta[agt]cct 1 +aggg[acg]aaa|ttt[cgt]ccct 0 +agggt[cgt]aa|tt[acg]accct 0 +agggta[cgt]a|t[acg]taccct 0 +agggtaa[cgt]|[acg]ttaccct 2 + +10245 +10000 +13348 diff --git a/gcc/testsuite/go.test/test/bench/regex-dna.c b/gcc/testsuite/go.test/test/bench/regex-dna.c new file mode 100644 index 000000000..134f8215c --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/regex-dna.c @@ -0,0 +1,154 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* +** The Computer Language Shootout +** http://shootout.alioth.debian.org/ +** contributed by Mike Pall +** +** regex-dna benchmark using PCRE +** +** compile with: +** gcc -O3 -fomit-frame-pointer -o regexdna regexdna.c -lpcre +*/ + +#define __USE_STRING_INLINES +#include +#include +#include +#include + +typedef struct fbuf { + char *buf; + size_t size, len; +} fbuf_t; + +static void fb_init(fbuf_t *b) +{ + b->buf = NULL; + b->len = b->size = 0; +} + +static char *fb_need(fbuf_t *b, size_t need) +{ + need += b->len; + if (need > b->size) { + if (b->size == 0) b->size = need; + else while (need > b->size) b->size += b->size; + if (!(b->buf = realloc(b->buf, b->size))) exit(1); + } + return b->buf+b->len; +} + +#define FB_MINREAD (3<<16) + +/* Read all of a stdio stream into dst buffer. */ +static size_t fb_readall(fbuf_t *dst, FILE *fp) +{ + char *dp; + int n; + for (dp = fb_need(dst, FB_MINREAD); + (n = fread(dp, 1, dst->size-dst->len, fp)) > 0; + dp = fb_need(dst, FB_MINREAD)) dst->len += n; + if (ferror(fp)) exit(1); + return dst->len; +} + +/* Substitute pattern p with replacement r, copying from src to dst buffer. */ +static size_t fb_subst(fbuf_t *dst, fbuf_t *src, const char *p, const char *r) +{ + pcre *re; + pcre_extra *re_ex; + const char *re_e; + char *dp; + int re_eo, m[3], pos, rlen, clen; + if (!(re = pcre_compile(p, PCRE_CASELESS, &re_e, &re_eo, NULL))) exit(1); + re_ex = pcre_study(re, 0, &re_e); + for (dst->len = 0, rlen = strlen(r), pos = 0; + pcre_exec(re, re_ex, src->buf, src->len, pos, 0, m, 3) >= 0; + pos = m[1]) { + clen = m[0]-pos; + dp = fb_need(dst, clen+rlen); + dst->len += clen+rlen; + memcpy(dp, src->buf+pos, clen); + memcpy(dp+clen, r, rlen); + } + clen = src->len-pos; + dp = fb_need(dst, clen); + dst->len += clen; + memcpy(dp, src->buf+pos, clen); + return dst->len; +} + +/* Count all matches with pattern p in src buffer. */ +static int fb_countmatches(fbuf_t *src, const char *p) +{ + pcre *re; + pcre_extra *re_ex; + const char *re_e; + int re_eo, m[3], pos, count; + if (!(re = pcre_compile(p, PCRE_CASELESS, &re_e, &re_eo, NULL))) exit(1); + re_ex = pcre_study(re, 0, &re_e); + for (count = 0, pos = 0; + pcre_exec(re, re_ex, src->buf, src->len, pos, 0, m, 3) >= 0; + pos = m[1]) count++; + return count; +} + +static const char *variants[] = { + "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", NULL +}; + +static const char *subst[] = { + "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|g)", + "V", "(a|c|g)", "W", "(a|t)", "Y", "(c|t)", NULL +}; + +int main(int argc, char **argv) +{ + fbuf_t seq[2]; + const char **pp; + size_t ilen, clen, slen; + int flip; + fb_init(&seq[0]); + fb_init(&seq[1]); + ilen = fb_readall(&seq[0], stdin); + clen = fb_subst(&seq[1], &seq[0], ">.*|\n", ""); + for (pp = variants; *pp; pp++) + printf("%s %d\n", *pp, fb_countmatches(&seq[1], *pp)); + for (slen = 0, flip = 1, pp = subst; *pp; pp += 2, flip = 1-flip) + slen = fb_subst(&seq[1-flip], &seq[flip], *pp, pp[1]); + printf("\n%zu\n%zu\n%zu\n", ilen, clen, slen); + return 0; +} diff --git a/gcc/testsuite/go.test/test/bench/regex-dna.go b/gcc/testsuite/go.test/test/bench/regex-dna.go new file mode 100644 index 000000000..dc31db768 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/regex-dna.go @@ -0,0 +1,106 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "fmt" + "io/ioutil" + "os" + "regexp" +) + +var variants = []string{ + "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", +} + +type Subst struct { + pat, repl string +} + +var substs = []Subst{ + Subst{"B", "(c|g|t)"}, + Subst{"D", "(a|g|t)"}, + Subst{"H", "(a|c|t)"}, + Subst{"K", "(g|t)"}, + Subst{"M", "(a|c)"}, + Subst{"N", "(a|c|g|t)"}, + Subst{"R", "(a|g)"}, + Subst{"S", "(c|g)"}, + Subst{"V", "(a|c|g)"}, + Subst{"W", "(a|t)"}, + Subst{"Y", "(c|t)"}, +} + +func countMatches(pat string, bytes []byte) int { + re := regexp.MustCompile(pat) + n := 0 + for { + e := re.FindIndex(bytes) + if len(e) == 0 { + break + } + n++ + bytes = bytes[e[1]:] + } + return n +} + +func main() { + bytes, err := ioutil.ReadFile("/dev/stdin") + if err != nil { + fmt.Fprintf(os.Stderr, "can't read input: %s\n", err) + os.Exit(2) + } + ilen := len(bytes) + // Delete the comment lines and newlines + bytes = regexp.MustCompile("(>[^\n]+)?\n").ReplaceAll(bytes, []byte{}) + clen := len(bytes) + for _, s := range variants { + fmt.Printf("%s %d\n", s, countMatches(s, bytes)) + } + for _, sub := range substs { + bytes = regexp.MustCompile(sub.pat).ReplaceAll(bytes, []byte(sub.repl)) + } + fmt.Printf("\n%d\n%d\n%d\n", ilen, clen, len(bytes)) +} diff --git a/gcc/testsuite/go.test/test/bench/regex-dna.txt b/gcc/testsuite/go.test/test/bench/regex-dna.txt new file mode 100644 index 000000000..e23e71fd6 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/regex-dna.txt @@ -0,0 +1,13 @@ +agggtaaa|tttaccct 1 +[cgt]gggtaaa|tttaccc[acg] 0 +a[act]ggtaaa|tttacc[agt]t 0 +ag[act]gtaaa|tttac[agt]ct 0 +agg[act]taaa|ttta[agt]cct 1 +aggg[acg]aaa|ttt[cgt]ccct 0 +agggt[cgt]aa|tt[acg]accct 0 +agggta[cgt]a|t[acg]taccct 0 +agggtaa[cgt]|[acg]ttaccct 2 + +10245 +10000 +13348 diff --git a/gcc/testsuite/go.test/test/bench/reverse-complement.c b/gcc/testsuite/go.test/test/bench/reverse-complement.c new file mode 100644 index 000000000..b34c84696 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/reverse-complement.c @@ -0,0 +1,100 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + * The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org + * + * contributed by Bob W + */ + +#include +#include + +#define JBFSIZE 82 // line input buffer size +#define QBFSIZE 5200 // output buffer initial size +#define Z16 "\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0" +#define V32 "\0TVGH\0\0CD\0\0M\0KN\0\0\0YSA\0BW\0R\0\0\0\0\0\0" +#define VALL Z16 Z16 Z16 Z16 V32 V32 Z16 Z16 Z16 Z16 Z16 Z16 Z16 Z16 + +int errex(char *s, int n) { // error message+value, return 1 + fprintf(stderr,"\n*** Error: %s [%d]!\n", s, n); + return 1; +} + +int main () { // ***** main ***** + char *pj, *pq, *pr; // buffer pointers: inp,out,/out + char *jjj = malloc(JBFSIZE); // allocate input line buffer + char *qqq = malloc(QBFSIZE); // output buffer (dyn. size) + char *pqstop = qqq+QBFSIZE; // end-of-buffer pointer + char xtab[256] = VALL; // char conversion table + + if (!jjj || !qqq) + return errex("Buffer allocation", !jjj + !qqq); + pj = fgets(jjj,JBFSIZE,stdin); // fetch 1st line + if (!pj) + return errex("No input data",0); + if (*jjj != '>') + return errex("1st char not '>'", 0); + + while (pj) { // MAIN LOOP: process data + fputs(jjj, stdout); // output ID line + + for (pq=qqq+1, pr=pqstop; ; pq++) { // LOOP: fill output buffer + pj = fgets(jjj, JBFSIZE, stdin); // get line from stdin + if (!pj || (*jjj=='>')) break; // EOF or new ID line + if (pr <= (pq+61)) { // need to resize buffer + char *newstop = pqstop + 12777888; + char *newptr = realloc(qqq, newstop-qqq); + if (!newptr) + return errex("Out of memory", 0); + if (newptr != qqq) { // new base: adj. pointers + size_t x = newptr-qqq; // offset for pointer update + pq+=x; pr+=x; qqq+=x; + newstop+=x; pqstop+=x; + } + pr = __builtin_memmove(newstop-(pqstop-pr), pr, pqstop-pr); + pqstop = newstop; // buffer resize complete + } + while (*pj) { // LOOP: conv. & revert line + char c = xtab[(unsigned char)(*pj++)]; + if (c) // conversion valid + *(--pr) = c; + } + } + + for (pq = qqq; pr' { + break + } + line = line[0 : len(line)-1] + nchar += len(line) + if len(line)+nchar/60+128 >= w { + nbuf := make([]byte, len(buf)*5) + copy(nbuf[len(nbuf)-len(buf):], buf) + w += len(nbuf) - len(buf) + buf = nbuf + } + + // This loop is the bottleneck. + for _, c := range line { + w-- + buf[w] = complement[c] + } + } + + // Copy down to beginning of buffer, inserting newlines. + // The loop left room for the newlines and 128 bytes of padding. + i := 0 + for j := w; j < len(buf); j += 60 { + n := copy(buf[i:i+60], buf[j:]) + buf[i+n] = '\n' + i += n + 1 + } + os.Stdout.Write(buf[0:i]) + } +} diff --git a/gcc/testsuite/go.test/test/bench/reverse-complement.txt b/gcc/testsuite/go.test/test/bench/reverse-complement.txt new file mode 100644 index 000000000..14d792ade --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/reverse-complement.txt @@ -0,0 +1,171 @@ +>ONE Homo sapiens alu +CGGAGTCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCGCGATCTCGGCTCACTGCAAC +CTCCGCCTCCCGGGTTCAAGCGATTCTCCTGCCTCAGCCTCCCGAGTAGCTGGGATTACA +GGCGCGCGCCACCACGCCCGGCTAATTTTTGTATTTTTAGTAGAGACGGGGTTTCACCAT +GTTGGCCAGGCTGGTCTCGAACTCCTGACCTCAGGTGATCCGCCCGCCTCGGCCTCCCAA +AGTGCTGGGATTACAGGCGTGAGCCACCGCGCCCGGCCTTTTTGAGACGGAGTCTCGCTC +TGTCGCCCAGGCTGGAGTGCAGTGGCGCGATCTCGGCTCACTGCAACCTCCGCCTCCCGG +GTTCAAGCGATTCTCCTGCCTCAGCCTCCCGAGTAGCTGGGATTACAGGCGCGCGCCACC +ACGCCCGGCTAATTTTTGTATTTTTAGTAGAGACGGGGTTTCACCATGTTGGCCAGGCTG +GTCTCGAACTCCTGACCTCAGGTGATCCGCCCGCCTCGGCCTCCCAAAGTGCTGGGATTA +CAGGCGTGAGCCACCGCGCCCGGCCTTTTTGAGACGGAGTCTCGCTCTGTCGCCCAGGCT +GGAGTGCAGTGGCGCGATCTCGGCTCACTGCAACCTCCGCCTCCCGGGTTCAAGCGATTC +TCCTGCCTCAGCCTCCCGAGTAGCTGGGATTACAGGCGCGCGCCACCACGCCCGGCTAAT +TTTTGTATTTTTAGTAGAGACGGGGTTTCACCATGTTGGCCAGGCTGGTCTCGAACTCCT +GACCTCAGGTGATCCGCCCGCCTCGGCCTCCCAAAGTGCTGGGATTACAGGCGTGAGCCA +CCGCGCCCGGCCTTTTTGAGACGGAGTCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGC +GCGATCTCGGCTCACTGCAACCTCCGCCTCCCGGGTTCAAGCGATTCTCCTGCCTCAGCC +TCCCGAGTAGCTGGGATTACAGGCGCGCGCCACCACGCCCGGCTAATTTTTGTATTTTTA +GTAGAGACGGGGTTTCACCATGTTGGCCAGGCTGGTCTCGAACTCCTGACCTCAGGTGAT +CCGCCCGCCTCGGCCTCCCAAAGTGCTGGGATTACAGGCGTGAGCCACCGCGCCCGGCCT +TTTTGAGACGGAGTCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCGCGATCTCGGCTC +ACTGCAACCTCCGCCTCCCGGGTTCAAGCGATTCTCCTGCCTCAGCCTCCCGAGTAGCTG +GGATTACAGGCGCGCGCCACCACGCCCGGCTAATTTTTGTATTTTTAGTAGAGACGGGGT +TTCACCATGTTGGCCAGGCTGGTCTCGAACTCCTGACCTCAGGTGATCCGCCCGCCTCGG +CCTCCCAAAGTGCTGGGATTACAGGCGTGAGCCACCGCGCCCGGCCTTTTTGAGACGGAG +TCTCGCTCTGTCGCCCAGGCTGGAGTGCAGTGGCGCGATCTCGGCTCACTGCAACCTCCG +CCTCCCGGGTTCAAGCGATTCTCCTGCCTCAGCCTCCCGAGTAGCTGGGATTACAGGCGC +GCGCCACCACGCCCGGCTAATTTTTGTATTTTTAGTAGAGACGGGGTTTCACCATGTTGG +CCAGGCTGGTCTCGAACTCCTGACCTCAGGTGATCCGCCCGCCTCGGCCTCCCAAAGTGC +TGGGATTACAGGCGTGAGCCACCGCGCCCGGCCTTTTTGAGACGGAGTCTCGCTCTGTCG +CCCAGGCTGGAGTGCAGTGGCGCGATCTCGGCTCACTGCAACCTCCGCCTCCCGGGTTCA +AGCGATTCTCCTGCCTCAGCCTCCCGAGTAGCTGGGATTACAGGCGCGCGCCACCACGCC +CGGCTAATTTTTGTATTTTTAGTAGAGACGGGGTTTCACCATGTTGGCCAGGCTGGTCTC +GAACTCCTGACCTCAGGTGATCCGCCCGCCTCGGCCTCCCAAAGTGCTGGGATTACAGGC +GTGAGCCACCGCGCCCGGCC +>TWO IUB ambiguity codes +TAGGDHACHATCRGTRGVTGAGWTATGYTGCTGTCABACDWVTRTAAGAVVAGATTTNDA +GASMTCTGCATBYTTCAAKTTACMTATTACTTCATARGGYACMRTGTTTTYTATACVAAT +TTCTAKGDACKADACTATATNTANTCGTTCACGBCGYSCBHTANGGTGATCGTAAAGTAA +CTATBAAAAGATSTGWATBCSGAKHTTABBAACGTSYCATGCAAVATKTSKTASCGGAAT +WVATTTNTCCTTCTTCTTDDAGTGGTTGGATACVGTTAYMTMTBTACTTTHAGCTAGBAA +AAGAGKAAGTTRATWATCAGATTMDDTTTAAAVAAATATTKTCYTAAATTVCNKTTRACG +ADTATATTTATGATSADSCAATAWAGCGRTAGTGTAAGTGACVGRADYGTGCTACHVSDT +CTVCARCSYTTAATATARAAAATTTAATTTACDAATTGBACAGTAYAABATBTGCAGBVG +TGATGGDCAAAATBNMSTTABKATTGGSTCCTAGBTTACTTGTTTAGTTTATHCGATSTA +AAGTCGAKAAASTGTTTTAWAKCAGATATACTTTTMTTTTGBATAGAGGAGCMATGATRA +AAGGNCAYDCCDDGAAAGTHGBTAATCKYTBTACBGTBCTTTTTGDTAASSWTAAWAARA +TTGGCTAAGWGRADTYACATAGCTCBTAGATAWAGCAATNGTATMATGTTKMMAGTAWTC +CCNTSGAAWATWCAAAAMACTGAADNTYGATNAATCCGAYWNCTAACGTTAGAGDTTTTC +ATCTGGKRTAVGAABVCTGWGBTCTDVGKATTBTCTAAGGVADAAAVWTCTAGGGGAGGG +TTAGAACAATTAAHTAATNAAATGCATKATCTAAYRTDTCAGSAYTTYHGATRTTWAVTA +BGNTCDACAGBCCRCAGWCRTCABTGMMAWGMCTCAACCGATRTGBCAVAATCGTDWDAA +CAYAWAATWCTGGTAHCCCTAAGATAACSCTTAGTGSAACAWTBGTCDTTDGACWDBAAC +HTTTNGSKTYYAAYGGATNTGATTTAARTTAMBAATCTAAGTBTCATYTAACTTADTGTT +TCGATACGAAHGGCYATATACCWDTKYATDCSHTDTCAAAATGTGBACTGSCCVGATGTA +TCMMAGCCTTDAAABAATGAAGAGTAACTHATMGVTTAATAACCCGGTTVSANTGCAATT +GTGAGATTTAMGTTTAMAAYGCTGACAYAAAAAGGCACAMYTAAGVGGCTGGAABVTACG +GATTSTYGTBVAKTATWACCGTGTKAGTDTGTATGTTTAAAGGAAAAAGTAACATARAAA +GGTYCAMNYAAABTATAGNTSATANAGTCATCCTATWADKAACTRGTMSACDGTATSAYT +AAHSHGTAABYGACTYTATADTGSTATAGAGAAATCGNTAAAGGAAATCAGTTGTNCYMV +TNACDRTATBNATATASTAGAAMSCGGGANRCKKMCAAACATTNAGTCTRMAATBMTACC +CGTACTTCTBGDSYAATWGAAAATGACADDCHAKAAAYATATTKTTTTCACANACWAGAA +AKATCCTTATTAYKHKCTAAACARTATTTTDATBTVWCYGCAATACTAGGKAAASTTDGA +MGGCHTTHAATVCAHDRYAGGRCTATACGTCMAGAGAGCTBTHGNACARTCCBDCTAAGA +GCGGCTTTARTAAAGAATCCNAGTAWBTGACTTGAATTACWTVACAGAAABCAATNAAAC +CGTNTRANTTGAYCMAWBADTANABRGGTKTHTWTAGTTVCTMBKTAGMTVKCCAGCANT +TVAGSWTTAGCCGCRHTTTCCTTHNTATTAAGAAGAATAGGMTRAARTCTABGTACDTTT +TATAAVDHAHTATAGATCCTAGTAAGYTWATDWCATGAGGGATAGTAAMDMNGBASTWAM +TSTATRBAYDABATGTATATYCGCACTGTTTTAACMCWBTATAWAGTATBTSTATVTTAR +CCTMTTAAKADATCAACTAATYTSVTAKGDATTATGCKTCAYCAKAATACTTKAANGAGT +ATTSDAGATCGGAAATACTTAAYAAVGTATMCGCTTGTGTDCTAATYTATTTTATTTWAA +CAGWRCTATGTAGMTGTTTGTTYKTNGTTKTCAGAACNTRACCTACKTGSRATGTGGGGG +CTGTCATTAAGTAAATNGSTTABCCCCTCGCAGCTCWHTCGCGAAGCAVATGCKACGHCA +ACAKTTAATAACASAAADATTWNYTGTAATTGTTCGTMHACHTWATGTGCWTTTTGAAHY +ACTTTGTAYAMSAAACTTAADAAATATAGTABMATATYAATGSGGTAGTTTGTGTBYGGT +TWSGSVGWMATTDMTCCWWCABTCSVACAGBAATGTTKATBGTCAATAATCTTCTTAAAC +ARVAATHAGYBWCTRWCABGTWWAATCTAAGTCASTAAAKTAAGVKBAATTBGABACGTA +AGGTTAAATAAAAACTRMDTWBCTTTTTAATAAAAGATMGCCTACKAKNTBAGYRASTGT +ASSTCGTHCGAAKTTATTATATTYTTTGTAGAACATGTCAAAACTWTWTHGKTCCYAATA +AAGTGGAYTMCYTAARCSTAAATWAKTGAATTTRAGTCTSSATACGACWAKAASATDAAA +TGYYACTSAACAAHAKTSHYARGASTATTATTHAGGYGGASTTTBGAKGATSANAACACD +TRGSTTRAAAAAAAACAAGARTCVTAGTAAGATAWATGVHAAKATWGAAAAGTYAHVTAC +TCTGRTGTCAWGATRVAAKTCGCAAVCGASWGGTTRTCSAMCCTAACASGWKKAWDAATG +ACRCBACTATGTGTCTTCAAAHGSCTATATTTCGTVWAGAAGTAYCKGARAKSGKAGTAN +TTTCYACATWATGTCTAAAADMDTWCAATSTKDACAMAADADBSAAATAGGCTHAHAGTA +CGACVGAATTATAAAGAHCCVAYHGHTTTACATSTTTATGNCCMTAGCATATGATAVAAG +>THREE Homo sapiens frequency +ATATTTATCTTTTCACTTCCTACATTGGTCAGACCATTATTCGACACGTGGCGTCATTTT +GTCATACCGGGTAATGTTGGAAACAAAACGTACTGATAAAATACTGAGTTGTAAACTCTA +ATCAGATAACGCGCTTGGATATTAAGATTCACACAGGGGTTTCGGCTGTAAAAAAACTTG +TGGAGCTGTTCTGGGACAGATAAGTTGTACCTCGTACTTAGCTAATTAATGAACCAACTG +ATTACGATAGAACAATTCTGAGGCCGCCAGGACAGCCAAATTTTAATCTTATAAAGCTGG +AAACAGCCGGTATTAGCTTCTCGCATACTTTGCCTGCATTGGTACCTTACAGATATCAGC +GTAGTCATATACACCTCGGTCTCAGCTAAGCTTGTATCTCTTAGAGTAGTTCAAAGATAG +TGGACAATACCTGTGGAATCGATTGCAGATATGGATTTATTTAACTACTGAGTCTCATTC +ACAAGCTAAGCAAGGAGCACGTTTTGGTGCCGGCATACCGATTTGCTATCATGTCAGCAA +ATTTGCGTTGTATTCCTAGTTGCACCCATTAAGGCCACACTCCGAACCTAATTATTACAT +CGCAAAGACATGTACGAAGGACCCGATGTCGAATAGAAGGGAGGACTGTTCATTGGAAGC +TAGACCAGAGGAATCGCAAAGATGCAACTCTTACAATAAAAATCTAATTTCAGTCAACAC +GCAATTTCTATAAGGTTTCCGATAATAATGAACCGTCTTCCACAGGGGAATTTGCCATGC +TCGTAAAAGTAGTTAATCCAAGTAGAAGAAATTTTGATAATGTTTTAAGTTGGCACGAAG +GAATTCAGAGAGATCTTACCTAACAAAGGCATTAGTAGATGTTCCTTGGTTCACACTCGG +TCAATCAGAGCACATACTACGGGCGATACCGGGAATGACACAACATCAATGAGATTGTTA +AGTGAGGTAATTGACTTTAGAGGACTCGATCAGTATACTGTCACTATGAACATCGTATTA +ATTGTTATCCGATATATACACCACCGATTTGCTTGTGCAAGGTTACAGACCCATTCGATA +AATACAAACACGGAGCGATATTATTTAAGGAGTGCTGTCTTCAAAAGAATTATTCCCACA +CCGACATAAGAACTTCGCTCCGTCATTCCAGATTTAAATAACATAACGTAACGCTTTGCT +GATAACATAACATAACCGAGAATTTGCTTAGGAAATTTGGAGCAATATTGCATTGTTTCT +CAGTCATCACAAGGCCCGCCAAAGAACTCTGAGAATCAGGATTCAACATGATTGGTAAGA +CTCTATATATATAACTTAATTCTTGTGTCCGGAGATAGAAAGAGGACGAGAGATACTACG +AAAGAAAGTGTACTTCGATGTATCAATTCAGACGCCTTCTCTATCATCAACATTATAGGT +CTCGTATATGCTCGGCGCGATCTGCTTCTCTCCGCCAATAGCCCCATAGTGTATTTCAAG +CGCAGTAACAGTGAAATCGTTACGAAGGTAGGGATGTTGCTTATAATTGTCGTAACTTAT +CGCTTATGTATCTTTCAAGAATGAACGGCAGCATATACATACGTTCTACCTTTAGCTACA +AAGCATCCATATACTCCCTCTCATGATTGAAACTCTTCCCTATTTTGTAGCCAATAGTGA +AAGCGTATTAGTATAAATTCGTCGGTTTTTCACTCGCAACTGTTATACTCTGCAAACAAA +CGAAAGCCTCATAGTACAAACCTAAAGCTACATACTTCATCATTGGCAGACCAGTGGCGG +TATTTCTACGGAAGCATCACTATAGATATAAAGTTTCCCTTCATGTACGTCTGTTAACCA +TATCACAAGAAACTGCTATCTCTGTCACGTAACAATTCACGCGCCTTATCGCCAAATGTT +CATATATGCGCGGTATACGTATGAACGAATACTAATTAGTATAACGGAGGATTCACGGGA +GGGATACTTGGGGCATTTATAAATCGTCTAAAAATTTTCTATCAGCACTTGCGGGTTATA +GTGGATTACTAGGCAACATAATATTCTGTATTGGTCCAAATGACGCTATAGATAAATTAG +CAAAATACATTGTTTCCATTTATGTAAGTCGAAACTCCAGGACTCCCGGGAACCAGTTAA +ACCGTCTGGAAAAGACACATTGTGAGCGGGACTTCAATGATAGCTTTCAATGAGCTTCTC +ATGCTTGGGGTCTGTACATATATGTTGGCGAAATTATCGTCTGTATTCTGTTATGCTTTG +ATCATGGGTTATTAGTATAGTGTCCGGTTAAGTACCAATACCGCTAGAGACCCGACCTAA +GTCGATAACTAACGATCATCGACGTAAGGATCGTCTCGATCAGTACTTCAGTCTAGATCT +GGGAATAGTAACTCGTTAGTGAACTATGTCGTGTCATAACTCTAAAATGCAATCAAATCT +TATTATTGAGTATTGATTATATAAAGCATCCGCTTAGCTTTACCCTCAAATGTTATATGC +AATTTAAAGCGCTTGATATCGTCTACTCAAGTTCAGGTTTCACATGGCCGCAACGTGACG +TTATTAGAGGTGGGTCATCATCTCTGAGGCTAGTGATGTTGAATACTCATTGAATGGGAA +GTGGAATACCATGCTCGTAGGTAACAGCATGACCTATAAAATATACTATGGGTGTGTGGT +AGATCAATATTGTTCAAGCATATCGTAACAATAACGGCTGAAATGTTACTGACATGAAAG +AGGGAGTCCAAACCATTCTAACAGCTGATCAAGTCGTCTAAAAACGCCTGGTTCAGCCTT +AAGAGTTATAAGCCAGACAAATTGTATCAATAGAGAATCCGTAAATTCCTCGGCCAACCT +CTTGCAAAGACATCACTATCAATATACTACCGTGATCTTAATTAGTGAACTTATATAAAT +ATCTACAACCAGATTCAACGGAAAAGCTTTAGTGGATTAGAAATTGCCAAGAATCACATT +CATGTGGGTTCGAATGCTTTAGTAATACCATTTCGCCGAGTAGTCACTTCGCTGAACTGT +CGTAAATTGCTATGACATAATCGAAAAGGATTGTCAAGAGTCGATTACTGCGGACTAATA +ATCCCCACGGGGGTGGTCTCATGTCTCCCCAGGCGAGTGGGGACGGTTGATAAACACGCT +GCATCGCGGACTGATGTTCCCAGTATTACATAGTCACATTGGATTGCGAGTAGTCTACCT +ATTTATGAGCGAGAGATGCCTCTAACTACTTCGACTTTTAAAACCTTTCCACGCCAGTAT +TCGGCGAAAGGGAAGTATTAAGGGTTGTCATAATTAAGCTGATACCACTTCAGACTTTGC +TCTACTTCTGTCTTTCATTGGTTTAGTAAAGTCTGTCCATTCGTCGAGACCGTCTTTTGC +AGCCTCATTCTACCAACTGCTCCGACTCTTAGTCTGCTTCTCCCAGCGTTATAACAAGAG +GCATTTTGTCATCCTTAAAACAATAATAAAGAACTCGGAGCACTGATATAATGACTGAAT +TAGAACCGCTTAAAAATACAACGAATAGATAAGACTATCGGATAAGATCTAATATGTAGT +GATTAAGCCCTTTATTAATTAATAATAGTTACCCTTTCTGATGTAACGCGACATATTACG +ATTTAGTGGCACGTCTGAATTGCAAAGCAGATCTCTACCCGATTTTTATTATAAATCCCG +TATACATCTTGACTTGAGTAATTGTTCATCTTTTTATATCTCTTCGTACTACAAATAATT +AATATCTCAACCCGTATTGTGTGATTCTAATTACCAACAGAATACGAGGAGGTTTTTGCT +TAGGGCCATATATAATGAATCTATCTCGTTTATTCGCGGAACCCGAGATAACATTACGAT +GTAACTATTTTAGAGAACTTAATACAAGAAACATTGCTGATTACTCATAACTAAATGCTT +GGTAATATATCCTCAGTGCCCCTACCATCTTTTACGCAGGGATGTAATTACTTAGGATTC +ATTGTGTAAGAATTACAATGAACGATGGATATGAAGGCATGTTGCGAGGTGTTCCTTGGT +ATGTGAAGTTCGCAGGGCAACAAAAATTTCGCAGAATAGGCCTCAAAGTATTGGTAAAGA +AGACAACTAATCATCACGAGCTTCTGATATCAATACGAACGAGTCCTGTGATGGATGAAA +GAAAGTCGTATCGAAAATGTCAAGAGTCTGCCCAATGTAACTTACTTCAAAAAATAACGC +TTCCGCCAAGTACGTTCGAATAAACGTAATTTTAAAAATACATAAGGGGTGTTAGAAAGT +AAGCGACGGGATATAAGTTAGACTCAAGATTCCGCCGTAAAACGAGACTGATTCCGAAGA +TTGTTCGTGGATCTGGTCATGACTTTCACTGAGTAAGGAGTTTCGACATATGTCAATAAA +CACAAAAATAGAAGCTATTCGATCTGAAAAATATTAGGACAAGAAACTATCTCACGCTAG +CCCAGAATATTCACTCACCCACGGGCGATACTAAAGCACTATATAGTCGCGTGATTACTA +TACATATGGTACACATAAGAATCACGATCAGGTTCTCAATTTTCAACAATATATGTTTAT +TTGCATAGGTAATATTAGGCCTTTAAGAGAAGGATGGGTGAGATACTCCGGGGATGGCGG +CAATAAAGAAAAACACGATATGAGTAATAGGATCCTAATATCTTGGCGAGAGACTTAAGG +TACGAATTTTGCGCAATCTATTTTTTACTTGGCCAGAATTCATGTATGGTATAAGTACGA +ACTTTTTTGATCACTTTCATGGCTACCTGATTAGGATAGTTTGAGGAATTTCCCAAATAT +ACCGATTTAATATACACTAGGGCTTGTCACTTTGAGTCAGAAAAAGAATATAATTACTTA +GGGTAATGCTGCATACATATTCTTATATTGCAAAGGTTCTCTGGGTAATCTTGAGCCTTC +ACGATACCTGGTGAAGTGTT diff --git a/gcc/testsuite/go.test/test/bench/spectral-norm-parallel.go b/gcc/testsuite/go.test/test/bench/spectral-norm-parallel.go new file mode 100644 index 000000000..2706f39ec --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/spectral-norm-parallel.go @@ -0,0 +1,111 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + * Based on spectral-norm.c by Sebastien Loisel + */ + +package main + +import ( + "flag" + "fmt" + "math" + "runtime" +) + +var n = flag.Int("n", 2000, "count") +var nCPU = flag.Int("ncpu", 4, "number of cpus") + +func evalA(i, j int) float64 { return 1 / float64(((i+j)*(i+j+1)/2 + i + 1)) } + +type Vec []float64 + +func (v Vec) Times(i, n int, u Vec, c chan int) { + for ; i < n; i++ { + v[i] = 0 + for j := 0; j < len(u); j++ { + v[i] += evalA(i, j) * u[j] + } + } + c <- 1 +} + +func (v Vec) TimesTransp(i, n int, u Vec, c chan int) { + for ; i < n; i++ { + v[i] = 0 + for j := 0; j < len(u); j++ { + v[i] += evalA(j, i) * u[j] + } + } + c <- 1 +} + +func wait(c chan int) { + for i := 0; i < *nCPU; i++ { + <-c + } +} + +func (v Vec) ATimesTransp(u Vec) { + x := make(Vec, len(u)) + c := make(chan int, *nCPU) + for i := 0; i < *nCPU; i++ { + go x.Times(i*len(v) / *nCPU, (i+1)*len(v) / *nCPU, u, c) + } + wait(c) + for i := 0; i < *nCPU; i++ { + go v.TimesTransp(i*len(v) / *nCPU, (i+1)*len(v) / *nCPU, x, c) + } + wait(c) +} + +func main() { + flag.Parse() + runtime.GOMAXPROCS(*nCPU) + N := *n + u := make(Vec, N) + for i := 0; i < N; i++ { + u[i] = 1 + } + v := make(Vec, N) + for i := 0; i < 10; i++ { + v.ATimesTransp(u) + u.ATimesTransp(v) + } + var vBv, vv float64 + for i := 0; i < N; i++ { + vBv += u[i] * v[i] + vv += v[i] * v[i] + } + fmt.Printf("%0.9f\n", math.Sqrt(vBv/vv)) +} diff --git a/gcc/testsuite/go.test/test/bench/spectral-norm.c b/gcc/testsuite/go.test/test/bench/spectral-norm.c new file mode 100644 index 000000000..832eb3d21 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/spectral-norm.c @@ -0,0 +1,82 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* -*- mode: c -*- + * + * The Great Computer Language Shootout + * http://shootout.alioth.debian.org/ + * + * Contributed by Sebastien Loisel + */ + +#include +#include +#include + +double eval_A(int i, int j) { return 1.0/((i+j)*(i+j+1)/2+i+1); } + +void eval_A_times_u(int N, const double u[], double Au[]) +{ + int i,j; + for(i=0;i +#include +#include +#include +#include + +#define THREADS (503) + + +struct stack { + char x[PTHREAD_STACK_MIN]; +}; + + +/* staticaly initialize mutex[0] mutex */ +static pthread_mutex_t mutex[THREADS]; +static int data[THREADS]; +static struct stack stacks[THREADS]; +/* stacks must be defined staticaly, or my i386 box run of virtual memory for this + * process while creating thread +- #400 */ + +static void* thread(void *num) +{ + int l = (int)num; + int r = (l+1) % THREADS; + int token; + + while(1) { + pthread_mutex_lock(mutex + l); + token = data[l]; + if (token) { + data[r] = token - 1; + pthread_mutex_unlock(mutex + r); + } + else { + printf("%i\n", l+1); + exit(0); + } + } +} + + + +int main(int argc, char **argv) +{ + int i; + pthread_t cthread; + pthread_attr_t stack_attr; + + if (argc != 2) + exit(255); + data[0] = atoi(argv[1]); + + pthread_attr_init(&stack_attr); + + for (i = 0; i < THREADS; i++) { + pthread_mutex_init(mutex + i, NULL); + pthread_mutex_lock(mutex + i); + + pthread_attr_setstack(&stack_attr, &stacks[i], sizeof(struct stack)); + pthread_create(&cthread, &stack_attr, thread, (void*)i); + } + + pthread_mutex_unlock(mutex + 0); + pthread_join(cthread, NULL); +} diff --git a/gcc/testsuite/go.test/test/bench/threadring.go b/gcc/testsuite/go.test/test/bench/threadring.go new file mode 100644 index 000000000..031908a20 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/threadring.go @@ -0,0 +1,71 @@ +/* +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + * Neither the name of "The Computer Language Benchmarks Game" nor the + name of "The Computer Language Shootout Benchmarks" nor the names of + its contributors may be used to endorse or promote products derived + from this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* The Computer Language Benchmarks Game + * http://shootout.alioth.debian.org/ + * + * contributed by The Go Authors. + */ + +package main + +import ( + "flag" + "fmt" + "os" +) + +var n = flag.Int("n", 1000, "how many passes") + +const Nthread = 503 + +func f(i int, in <-chan int, out chan<- int) { + for { + n := <-in + if n == 0 { + fmt.Printf("%d\n", i) + os.Exit(0) + } + out <- n-1 + } +} + +func main() { + flag.Parse() + + one := make(chan int) // will be input to thread 1 + var in, out chan int = nil, one + for i := 1; i <= Nthread-1; i++ { + in, out = out, make(chan int) + go f(i, in, out) + } + go f(Nthread, out, one) + one <- *n + <-make(chan int) // hang until ring completes +} diff --git a/gcc/testsuite/go.test/test/bench/threadring.txt b/gcc/testsuite/go.test/test/bench/threadring.txt new file mode 100644 index 000000000..f9aaa4d56 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/threadring.txt @@ -0,0 +1 @@ +498 diff --git a/gcc/testsuite/go.test/test/bench/timing.log b/gcc/testsuite/go.test/test/bench/timing.log new file mode 100644 index 000000000..e7b0b48c1 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/timing.log @@ -0,0 +1,500 @@ +All tests on r45 or r70 + +Aug 3 2009 + +First version of fasta. Translation of fasta.c, fetched from + http://shootout.alioth.debian.org/u32q/benchmark.php?test=fasta&lang=gpp&id=4 + +fasta -n 25000000 + gcc -O2 fasta.c 5.98u 0.00s 6.01r + gccgo -O2 fasta.go 8.82u 0.02s 8.85r + 6g fasta.go 13.50u 0.02s 13.53r + 6g -B fata.go 12.99u 0.02s 13.02r + +Aug 4 2009 +[added timing.sh] + +# myrandom: +# hand-written optimization of integer division +# use int32->float conversion +fasta -n 25000000 + # probably I/O library inefficiencies + gcc -O2 fasta.c 5.99u 0.00s 6.00r + gccgo -O2 fasta.go 8.82u 0.02s 8.85r + gc fasta 10.70u 0.00s 10.77r + gc_B fasta 10.09u 0.03s 10.12r + +reverse-complement < output-of-fasta-25000000 + # we don't know - memory cache behavior? + gcc -O2 reverse-complement.c 2.04u 0.94s 10.54r + gccgo -O2 reverse-complement.go 6.54u 0.63s 7.17r + gc reverse-complement 6.55u 0.70s 7.26r + gc_B reverse-complement 6.32u 0.70s 7.10r + +nbody 50000000 + # math.Sqrt needs to be in assembly; inlining is probably the other 50% + gcc -O2 nbody.c 21.61u 0.01s 24.80r + gccgo -O2 nbody.go 118.55u 0.02s 120.32r + gc nbody 100.84u 0.00s 100.85r + gc_B nbody 103.33u 0.00s 103.39r +[ +hacked Sqrt in assembler + gc nbody 31.97u 0.00s 32.01r +] + +binary-tree 15 # too slow to use 20 + # memory allocation and garbage collection + gcc -O2 binary-tree.c -lm 0.86u 0.00s 0.87r + gccgo -O2 binary-tree.go 1.69u 0.46s 2.15r + gccgo -O2 binary-tree-freelist.go 8.48u 0.00s 8.48r + gc binary-tree 9.60u 0.01s 9.62r + gc binary-tree-freelist 0.48u 0.01s 0.50r + +August 5, 2009 + +fannkuch 12 + # bounds checking is half the difference + # rest might be registerization + gcc -O2 fannkuch.c 60.09u 0.01s 60.32r + gccgo -O2 fannkuch.go 64.89u 0.00s 64.92r + gc fannkuch 124.59u 0.00s 124.67r + gc_B fannkuch 91.14u 0.00s 91.16r + +regex-dna 100000 + # regexp code is slow on trivial regexp + gcc -O2 regex-dna.c -lpcre 0.92u 0.00s 0.99r + gc regexp-dna 26.94u 0.18s 28.75r + gc_B regexp-dna 26.51u 0.09s 26.75r + +spectral-norm 5500 + gcc -O2 spectral-norm.c -lm 11.54u 0.00s 11.55r + gccgo -O2 spectral-norm.go 12.20u 0.00s 12.23r + gc spectral-norm 50.23u 0.00s 50.36r + gc_B spectral-norm 49.69u 0.01s 49.83r + gc spectral-norm-parallel 24.47u 0.03s 11.05r # has shift >>1 not div /2 + [using >>1 instead of /2 : gc gives 24.33u 0.00s 24.33r] + +August 6, 2009 + +k-nucleotide 5000000 + # string maps are slower than glib string maps + gcc -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include k-nucleotide.c -lglib-2.0 k-nucleotide.c: 10.72u 0.01s 10.74r + gccgo -O2 k-nucleotide.go 21.64u 0.83s 22.78r + gc k-nucleotide 16.08u 0.06s 16.50r + gc_B k-nucleotide 17.32u 0.02s 17.37r + +mandelbrot 5500 + # floating point code generator should use more registers + gcc -O2 mandelbrot.c 56.13u 0.02s 56.17r + gccgo -O2 mandelbrot.go 57.49u 0.01s 57.51r + gc mandelbrot 74.32u 0.00s 74.35r + gc_B mandelbrot 74.28u 0.01s 74.31r + +meteor 16000 + # we don't know + gcc -O2 meteor-contest.c 0.10u 0.00s 0.10r + gccgo -O2 meteor-contest.go 0.12u 0.00s 0.14r + gc meteor-contest 0.24u 0.00s 0.26r + gc_B meteor-contest 0.23u 0.00s 0.24r + +pidigits 10000 + # bignum is slower than gmp + gcc -O2 pidigits.c -lgmp 2.60u 0.00s 2.62r + gc pidigits 77.69u 0.14s 78.18r + gc_B pidigits 74.26u 0.18s 75.41r + gc_B pidigits 68.48u 0.20s 69.31r # special case: no bounds checking in bignum + +August 7 2009 + +# New gc does better division by powers of 2. Significant improvements: + +spectral-norm 5500 + # floating point code generator should use more registers; possibly inline evalA + gcc -O2 spectral-norm.c -lm 11.50u 0.00s 11.50r + gccgo -O2 spectral-norm.go 12.02u 0.00s 12.02r + gc spectral-norm 23.98u 0.00s 24.00r # new time is 0.48 times old time, 52% faster + gc_B spectral-norm 23.71u 0.01s 23.72r # ditto + gc spectral-norm-parallel 24.04u 0.00s 6.26r # /2 put back. note: 4x faster (on r70, idle) + +k-nucleotide 1000000 + # string maps are slower than glib string maps + gcc -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include k-nucleotide.c -lglib-2.0 10.82u 0.04s 10.87r + gccgo -O2 k-nucleotide.go 22.73u 0.89s 23.63r + gc k-nucleotide 15.97u 0.03s 16.04r + gc_B k-nucleotide 15.86u 0.06s 15.93r # 8.5% faster, but probably due to weird cache effeccts in previous version + +pidigits 10000 + # bignum is slower than gmp + gcc -O2 pidigits.c -lgmp 2.58u 0.00s 2.58r + gc pidigits 71.24u 0.04s 71.28r # 8.5% faster + gc_B pidigits 71.25u 0.03s 71.29r # 4% faster + +threadring 50000000 + gcc -O2 threadring.c -lpthread 35.51u 160.21s 199.50r + gccgo -O2 threadring.go 90.33u 459.95s 448.03r + gc threadring 33.11u 0.00s 33.14r + GOMAXPROCS=4 gc threadring 114.48u 226.65s 371.59r + # change wait code to do <-make(chan int) instead of time.Sleep + gc threadring 28.41u 0.01s 29.35r + GOMAXPROCS=4 gc threadring 112.59u 232.83s 384.72r + +chameneos 6000000 + gcc -O2 chameneosredux.c -lpthread 18.14u 276.52s 76.93r + gc chameneosredux 20.19u 0.01s 20.23r + +Aug 10 2009 + +# new 6g with better fp registers, fast div and mod of integers +# complete set of timings listed. significant changes marked *** + +fasta -n 25000000 + # probably I/O library inefficiencies + gcc -O2 fasta.c 5.96u 0.00s 5.97r + gc fasta 10.59u 0.01s 10.61r + gc_B fasta 9.92u 0.02s 9.95r + +reverse-complement < output-of-fasta-25000000 + # we don't know - memory cache behavior? + gcc -O2 reverse-complement.c 1.96u 1.56s 16.23r + gccgo -O2 reverse-complement.go 6.41u 0.62s 7.05r + gc reverse-complement 6.46u 0.70s 7.17r + gc_B reverse-complement 6.22u 0.72s 6.95r + +nbody 50000000 + # math.Sqrt needs to be in assembly; inlining is probably the other 50% + gcc -O2 nbody.c 21.26u 0.01s 21.28r + gccgo -O2 nbody.go 116.68u 0.07s 116.80r + gc nbody 86.64u 0.01s 86.68r # -14% + gc_B nbody 85.72u 0.02s 85.77r # *** -17% + +binary-tree 15 # too slow to use 20 + # memory allocation and garbage collection + gcc -O2 binary-tree.c -lm 0.87u 0.00s 0.87r + gccgo -O2 binary-tree.go 1.61u 0.47s 2.09r + gccgo -O2 binary-tree-freelist.go 0.00u 0.00s 0.01r + gc binary-tree 9.11u 0.01s 9.13r # *** -5% + gc binary-tree-freelist 0.47u 0.01s 0.48r + +fannkuch 12 + # bounds checking is half the difference + # rest might be registerization + gcc -O2 fannkuch.c 59.92u 0.00s 59.94r + gccgo -O2 fannkuch.go 65.54u 0.00s 65.58r + gc fannkuch 123.98u 0.01s 124.04r + gc_B fannkuch 90.75u 0.00s 90.78r + +regex-dna 100000 + # regexp code is slow on trivial regexp + gcc -O2 regex-dna.c -lpcre 0.91u 0.00s 0.92r + gc regex-dna 27.25u 0.02s 27.28r + gc_B regex-dna 29.51u 0.03s 29.55r + +spectral-norm 5500 + # possibly inline evalA + gcc -O2 spectral-norm.c -lm 11.57u 0.00s 11.57r + gccgo -O2 spectral-norm.go 12.07u 0.01s 12.08r + gc spectral-norm 23.99u 0.00s 24.00r + gc_B spectral-norm 23.73u 0.00s 23.75r + +k-nucleotide 1000000 + # string maps are slower than glib string maps + gcc -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include k-nucleotide.c -lglib-2.0 10.63u 0.02s 10.69r + gccgo -O2 k-nucleotide.go 23.19u 0.91s 24.12r + gc k-nucleotide 16.73u 0.04s 16.78r # *** +5% (but this one seems to vary by more than that) + gc_B k-nucleotide 16.46u 0.04s 16.51r # *** +5% + +mandelbrot 16000 + gcc -O2 mandelbrot.c 56.16u 0.00s 56.16r + gccgo -O2 mandelbrot.go 57.41u 0.01s 57.42r + gc mandelbrot 64.05u 0.02s 64.08r # *** -14% + gc_B mandelbrot 64.10u 0.02s 64.14r # *** -14% + +meteor 16000 + # we don't know + gcc -O2 meteor-contest.c 0.10u 0.00s 0.10r + gccgo -O2 meteor-contest.go 0.12u 0.00s 0.12r + gc meteor-contest 0.18u 0.00s 0.20r # *** -25% + gc_B meteor-contest 0.17u 0.00s 0.18r # *** -24% + +pidigits 10000 + # bignum is slower than gmp + gcc -O2 pidigits.c -lgmp 2.57u 0.00s 2.57r + gc pidigits 71.82u 0.04s 71.89r + gc_B pidigits 71.84u 0.08s 71.98r + +threadring 50000000 + gcc -O2 threadring.c -lpthread 30.91u 164.33s 204.57r + gccgo -O2 threadring.go 87.12u 460.04s 447.61r + gc threadring 38.55u 0.00s 38.56r # *** +16% + +chameneos 6000000 + gcc -O2 chameneosredux.c -lpthread 17.93u 323.65s 88.47r + gc chameneosredux 21.72u 0.00s 21.73r + +August 10 2009 + +# In-place versions for some bignum operations. +pidigits 10000 + gcc -O2 pidigits.c -lgmp 2.56u 0.00s 2.57r + gc pidigits 55.22u 0.04s 55.29r # *** -23% + gc_B pidigits 55.49u 0.02s 55.60r # *** -23% + +September 3 2009 + +# New 6g inlines slices, has a few other tweaks. +# Complete rerun. Significant changes marked. + +fasta -n 25000000 + # probably I/O library inefficiencies + gcc -O2 fasta.c 5.96u 0.00s 5.96r + gc fasta 10.63u 0.02s 10.66r + gc_B fasta 9.92u 0.01s 9.94r + +reverse-complement < output-of-fasta-25000000 + # we don't know - memory cache behavior? + gcc -O2 reverse-complement.c 1.92u 0.33s 2.93r + gccgo -O2 reverse-complement.go 6.76u 0.72s 7.58r # +5% + gc reverse-complement 6.59u 0.70s 7.29r # +2% + gc_B reverse-complement 5.57u 0.80s 6.37r # -10% + +nbody 50000000 + # math.Sqrt needs to be in assembly; inlining is probably the other 50% + # also loop alignment appears to be critical + gcc -O2 nbody.c 21.28u 0.00s 21.28r + gccgo -O2 nbody.go 119.21u 0.00s 119.22r # +2% + gc nbody 109.72u 0.00s 109.78r # + 28% ***** + gc_B nbody 85.90u 0.00s 85.91r + +binary-tree 15 # too slow to use 20 + # memory allocation and garbage collection + gcc -O2 binary-tree.c -lm 0.86u 0.00s 0.87r + gccgo -O2 binary-tree.go 1.88u 0.54s 2.42r # +17% + gccgo -O2 binary-tree-freelist.go 0.01u 0.01s 0.02r + gc binary-tree 8.94u 0.01s 8.96r # -2% + gc binary-tree-freelist 0.47u 0.01s 0.48r + +fannkuch 12 + # bounds checking is half the difference + # rest might be registerization + gcc -O2 fannkuch.c 60.12u 0.00s 60.12r + gccgo -O2 fannkuch.go 92.62u 0.00s 92.66r # +41% *** + gc fannkuch 123.90u 0.00s 123.92r + gc_B fannkuch 89.71u 0.00s 89.74r # -1% + +regex-dna 100000 + # regexp code is slow on trivial regexp + gcc -O2 regex-dna.c -lpcre 0.88u 0.00s 0.88r + gc regex-dna 25.77u 0.01s 25.79r # -5% + gc_B regex-dna 26.05u 0.02s 26.09r # -12% *** + +spectral-norm 5500 + # possibly inline evalA + gcc -O2 spectral-norm.c -lm 11.51u 0.00s 11.51r + gccgo -O2 spectral-norm.go 11.95u 0.00s 11.96r + gc spectral-norm 24.23u 0.00s 24.23r + gc_B spectral-norm 23.83u 0.00s 23.84r + +k-nucleotide 1000000 + # string maps are slower than glib string maps + gcc -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include k-nucleotide.c -lglib-2.0 10.68u 0.04s 10.72r + gccgo -O2 k-nucleotide.go 23.03u 0.88s 23.92r + gc k-nucleotide 15.79u 0.05s 15.85r # -5% (but this one seems to vary by more than that) + gc_B k-nucleotide 17.88u 0.05s 17.95r # +8% (ditto) + +mandelbrot 16000 + gcc -O2 mandelbrot.c 56.17u 0.02s 56.20r + gccgo -O2 mandelbrot.go 56.74u 0.02s 56.79r # -1% + gc mandelbrot 63.31u 0.01s 63.35r # -1% + gc_B mandelbrot 63.29u 0.00s 63.31r # -1% + +meteor 16000 + # we don't know + gcc -O2 meteor-contest.c 0.10u 0.00s 0.10r + gccgo -O2 meteor-contest.go 0.11u 0.00s 0.12r + gc meteor-contest 0.18u 0.00s 0.19r + gc_B meteor-contest 0.17u 0.00s 0.18r + +pidigits 10000 + # bignum is slower than gmp + gcc -O2 pidigits.c -lgmp 2.56u 0.00s 2.57r + gc pidigits 55.87u 0.03s 55.91r + gc_B pidigits 55.93u 0.03s 55.99r + +# these tests are compared using real time, since they run multiple processors +# accuracy probably low +threadring 50000000 + gcc -O2 threadring.c -lpthread 26.31u 164.69s 199.92r # -2% + gccgo -O2 threadring.go 87.90u 487.26s 472.81r # +6% + gc threadring 28.89u 0.00s 28.90r # -25% *** + +chameneos 6000000 + gcc -O2 chameneosredux.c -lpthread 16.41u 296.91s 81.17r # -8% + gc chameneosredux 19.97u 0.00s 19.97r # -8% + +Sep 22, 2009 + +# 6g inlines sliceslice in most cases. + +fasta -n 25000000 + # probably I/O library inefficiencies + gc fasta 10.24u 0.00s 10.25r # -4% + gc_B fasta 9.68u 0.01s 9.69r # -3% + +reverse-complement < output-of-fasta-25000000 + # we don't know - memory cache behavior? + gc reverse-complement 6.67u 0.69s 7.37r # +1% + gc_B reverse-complement 6.00u 0.64s 6.65r # +7% + +nbody -n 50000000 + # math.Sqrt needs to be in assembly; inlining is probably the other 50% + # also loop alignment appears to be critical + gc nbody 86.27u 0.00s 86.29r # -21% + gc_B nbody 104.52u 0.00s 104.54r # +22% + +fannkuch 12 + # bounds checking is half the difference + # rest might be registerization + gc fannkuch 128.36u 0.00s 128.37r # +4% + gc_B fannkuch 89.32u 0.00s 89.34r + +regex-dna 100000 + # regexp code is slow on trivial regexp + gc regex-dna 24.82u 0.01s 24.86r # -4% + gc_B regex-dna 24.55u 0.01s 24.57r # -6% + +spectral-norm 5500 + # possibly inline evalA + gc spectral-norm 24.05u 0.00s 24.07r # -1% + gc_B spectral-norm 23.60u 0.00s 23.65r # -1% + +k-nucleotide 1000000 + # string maps are slower than glib string maps + gc k-nucleotide 17.84u 0.04s 17.89r # +13% but mysterious variation continues + gc_B k-nucleotide 15.56u 0.08s 15.65r # -13% (ditto) + +mandelbrot 16000 + gc mandelbrot 64.08u 0.01s 64.11r # +1% + gc_B mandelbrot 64.04u 0.00s 64.05r # +1% + +pidigits 10000 + # bignum is slower than gmp + gc pidigits 58.68u 0.02s 58.72r # +5% + gc_B pidigits 58.86u 0.05s 58.99r # +5% + +# these tests are compared using real time, since they run multiple processors +# accuracy probably low +threadring 50000000 + gc threadring 32.70u 0.02s 32.77r # +13% + +chameneos 6000000 + gc chameneosredux 26.62u 0.00s 26.63r # +13% + +Sep 24, 2009 + +# Sqrt now in assembler for 6g. +nbody -n 50000000 + # remember, at least for 6g, alignment of loops may be important + gcc -O2 nbody.c 21.24u 0.00s 21.25r + gccgo -O2 nbody.go 121.03u 0.00s 121.04r + gc nbody 30.26u 0.00s 30.27r # -65% *** + gc_B nbody 30.20u 0.02s 30.22r # -72% *** + +Nov 13 2009 + +# fix bug in regexp; take performance hit. good regexps will come in time. +regex-dna 100000 + gcc -O2 regex-dna.c -lpcre 0.92u 0.00s 0.94r + gc regex-dna 29.78u 0.03s 29.83r + gc_B regex-dna 32.63u 0.03s 32.74r + +Nov 24 2009 + +# Roger Peppe's rewrite of the benchmark +chameneos 6000000 + gcc -O2 chameneosredux.c -lpthread 18.00u 303.29s 83.64r + gc chameneosredux 12.10u 0.00s 12.10r # 2.22X faster + +Jan 6, 2009 + +# Long-overdue update. All numbers included in this complete run. +# Some programs (e.g. reverse-complement) rewritten for speed. +# Regular expressions much faster in common cases (although still far behind PCRE) +# Bignum stuff improved +# Better (but sometimes slower) locking in channels. + +fasta -n 25000000 + gcc -O2 fasta.c 5.99u 0.01s 6.00r + gc fasta 9.11u 0.00s 9.12r # -11% + gc_B fasta 8.60u 0.00s 8.62r # +12% ?? + +reverse-complement < output-of-fasta-25000000 + gcc -O2 reverse-complement.c 2.00u 0.80s 9.54r + gccgo -O2 reverse-complement.go 4.57u 0.35s 4.94r # 33% faster + gc reverse-complement 2.01u 0.38s 2.40r # 3.3X faster + gc_B reverse-complement 1.88u 0.36s 2.24r # 3.2X faster +GOGC=off + gc reverse-complement 2.01u 0.35s 2.37r + gc_B reverse-complement 1.86u 0.32s 2.19r + +nbody -n 50000000 + gcc -O2 nbody.c 21.28u 0.00s 21.31r + gccgo -O2 nbody.go 80.02u 0.00s 80.05r # 33% faster + gc nbody 30.13u 0.00s 30.13r + gc_B nbody 29.89u 0.01s 29.91r + +binary-tree 15 # too slow to use 20 + gcc -O2 binary-tree.c -lm 0.86u 0.00s 0.87r + gccgo -O2 binary-tree.go 4.82u 0.41s 5.24r # 2.5X slower + gccgo -O2 binary-tree-freelist.go 0.00u 0.00s 0.00r + gc binary-tree 7.23u 0.01s 7.25r # # -19% + gc binary-tree-freelist 0.43u 0.00s 0.44r # -9% + +fannkuch 12 + gcc -O2 fannkuch.c 60.17u 0.00s 60.17r + gccgo -O2 fannkuch.go 78.47u 0.01s 78.49r + gc fannkuch 128.86u 0.00s 128.96r + gc_B fannkuch 90.17u 0.00s 90.21r + +regex-dna 100000 + gcc -O2 regex-dna.c -lpcre 0.90u 0.00s 0.92r + gc regex-dna 9.48u 0.01s 9.50r # 3.1X faster + gc_B regex-dna 9.08u 0.00s 9.10r # 3.6X faster + +spectral-norm 5500 + gcc -O2 spectral-norm.c -lm 11.48u 0.00s 11.48r + gccgo -O2 spectral-norm.go 11.68u 0.00s 11.70r + gc spectral-norm 23.98u 0.00s 23.99r + gc_B spectral-norm 23.68u 0.00s 23.69r + +k-nucleotide 1000000 + gcc -O2 k-nucleotide.c 10.85u 0.04s 10.90r + gccgo -O2 k-nucleotide.go 25.26u 0.87s 26.14r + gc k-nucleotide 15.28u 0.06s 15.37r # restored; mysterious variation continues + gc_B k-nucleotide 15.97u 0.03s 16.00r + +mandelbrot 16000 + gcc -O2 mandelbrot.c 56.12u 0.01s 56.15r + gccgo -O2 mandelbrot.go 56.86u 0.01s 56.89r + gc mandelbrot 66.05u 0.00s 66.07r # -3% + gc_B mandelbrot 66.06u 0.00s 66.07r # -3% + +meteor 16000 + gcc -O2 meteor-contest.c 0.10u 0.00s 0.10r + gccgo -O2 meteor-contest.go 0.12u 0.00s 0.12r + gc meteor-contest 0.17u 0.00s 0.17r + gc_B meteor-contest 0.15u 0.00s 0.16r + +pidigits 10000 + gcc -O2 pidigits.c -lgmp 2.57u 0.00s 2.59r + gc pidigits 38.27u 0.02s 38.30r # 1.5X faster + gc_B pidigits 38.27u 0.02s 38.31r # 1.5X faster + +threadring 50000000 + gcc -O2 threadring.c 37.11u 170.59s 212.75r + gccgo -O2 threadring.go 89.67u 447.56s 442.55r # -6.5% + gc threadring 36.08u 0.04s 36.15r # +10% + +chameneos 6000000 + gcc -O2 chameneosredux.c -lpthread 19.02u 331.08s 90.79r + gc chameneosredux 12.54u 0.00s 12.55r + diff --git a/gcc/testsuite/go.test/test/bench/timing.sh b/gcc/testsuite/go.test/test/bench/timing.sh new file mode 100755 index 000000000..c52c0af94 --- /dev/null +++ b/gcc/testsuite/go.test/test/bench/timing.sh @@ -0,0 +1,196 @@ +#!/usr/bin/env bash +# Copyright 2009 The Go Authors. All rights reserved. +# Use of this source code is governed by a BSD-style +# license that can be found in the LICENSE file. + +set -e + +eval $(gomake --no-print-directory -f ../../src/Make.inc go-env) +PATH=.:$PATH + +mode=run +case X"$1" in +X-test) + mode=test + shift +esac + +gc() { + $GC $1.go; $LD $1.$O +} + +gc_B() { + $GC -B $1.go; $LD $1.$O +} + +runonly() { + if [ $mode = run ] + then + "$@" + fi +} + + + +run() { + if [ $mode = test ] + then + if echo $1 | grep -q '^gc ' + then + $1 # compile the program + program=$(echo $1 | sed 's/gc //') + shift + echo $program + $1 /tmp/$$ + case $program in + chameneosredux) + # exact numbers may vary but non-numbers should match + grep -v '[0-9]' /tmp/$$ > /tmp/$$x + grep -v '[0-9]' chameneosredux.txt > /tmp/$$y + cmp /tmp/$$x /tmp/$$y + rm -f /tmp/$$ /tmp/$$x /tmp/$$y + ;; + *) + cmp /tmp/$$ $program.txt + rm -f /tmp/$$ + esac + fi + return + fi + echo -n ' '$1' ' + $1 + shift + + echo $((time -p $* >/dev/null) 2>&1) | awk '{print $4 "u " $6 "s " $2 "r"}' +} + +fasta() { + runonly echo 'fasta -n 25000000' + run 'gcc -O2 fasta.c' a.out 25000000 + #run 'gccgo -O2 fasta.go' a.out -n 25000000 #commented out until WriteString is in bufio + run 'gc fasta' $O.out -n 25000000 + run 'gc_B fasta' $O.out -n 25000000 +} + +revcomp() { + runonly gcc -O2 fasta.c + runonly a.out 25000000 > x + runonly echo 'reverse-complement < output-of-fasta-25000000' + run 'gcc -O2 reverse-complement.c' a.out < x + run 'gccgo -O2 reverse-complement.go' a.out < x + run 'gc reverse-complement' $O.out < x + run 'gc_B reverse-complement' $O.out < x + rm x +} + +nbody() { + runonly echo 'nbody -n 50000000' + run 'gcc -O2 nbody.c' a.out 50000000 + run 'gccgo -O2 nbody.go' a.out -n 50000000 + run 'gc nbody' $O.out -n 50000000 + run 'gc_B nbody' $O.out -n 50000000 +} + +binarytree() { + runonly echo 'binary-tree 15 # too slow to use 20' + run 'gcc -O2 binary-tree.c -lm' a.out 15 + run 'gccgo -O2 binary-tree.go' a.out -n 15 + run 'gccgo -O2 binary-tree-freelist.go' $O.out -n 15 + run 'gc binary-tree' $O.out -n 15 + run 'gc binary-tree-freelist' $O.out -n 15 +} + +fannkuch() { + runonly echo 'fannkuch 12' + run 'gcc -O2 fannkuch.c' a.out 12 + run 'gccgo -O2 fannkuch.go' a.out -n 12 + run 'gccgo -O2 fannkuch-parallel.go' a.out -n 12 + run 'gc fannkuch' $O.out -n 12 + run 'gc fannkuch-parallel' $O.out -n 12 + run 'gc_B fannkuch' $O.out -n 12 +} + +regexdna() { + runonly gcc -O2 fasta.c + runonly a.out 100000 > x + runonly echo 'regex-dna 100000' + run 'gcc -O2 regex-dna.c -lpcre' a.out x # should be using 25000000 + runonly echo 'k-nucleotide 1000000' + run 'gcc -O2 -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include k-nucleotide.c -lglib-2.0' a.out