Upload the comparison directory

15 files changed, 531 insertions, 0 deletions

diff --git a/comparison/Inpla/Makefile b/comparison/Inpla/Makefile
new file mode 100644
index 0000000..8ca3630
--- /dev/null
+++ b/comparison/Inpla/Makefile
@@ -0,0 +1,8 @@
+.PHONY: all
+
+
+all:
+	sh main.sh
+
+clean:
+	rm -f ./inplaSeq ./inplaPara log-* *~
diff --git a/comparison/Inpla/main.sh b/comparison/Inpla/main.sh
new file mode 100644
index 0000000..b0da0e2
--- /dev/null
+++ b/comparison/Inpla/main.sh
@@ -0,0 +1,16 @@
+#!/bin/sh
+
+./sptestInpla.sh src/fib-38.in
+./sptestInpla.sh src/fib-38-reuse.in
+
+./sptestInpla.sh src/ack-stream_3-11.in
+./sptestInpla.sh src/ack-stream_3-11-reuse.in
+
+./sptestInpla.sh src/bsort-40000.in '-c 200000'
+./sptestInpla.sh src/bsort-40000-reuse.in '-c 200000'
+
+./sptestInpla.sh src/qsort-800000.in '-c 8000000'
+./sptestInpla.sh src/qsort-800000-reuse.in '-c 8000000'
+
+./sptestInpla.sh src/msort-800000.in '-c 8000000'
+./sptestInpla.sh src/msort-800000-reuse.in '-c 8000000'
diff --git a/comparison/Inpla/sptestInpla.sh b/comparison/Inpla/sptestInpla.sh
new file mode 100644
index 0000000..36044a6
--- /dev/null
+++ b/comparison/Inpla/sptestInpla.sh
@@ -0,0 +1,139 @@
+#!/bin/bash
+# $1: the source file name
+# $2: options
+# example: ./sptestInpla.sh A3_10.in '-x 100000'
+
+
+# repeat and waittime
+ct=1
+waittime=5
+
+max_threads=9
+
+# options
+source=$1
+inpla_seq='inplaSeq'
+inpla_para='inplaPara'
+opt=$2
+#dir_source='prog/'
+dir_make='../../'
+path_source="$dir_source$source"
+fname=`echo $1 | sed -e s'|.*/\(.*\)|\1|'`
+
+log="log-${fname}.txt"
+
+
+# main ------------------------------------------------------
+if [ -z $1 ]; then
+  echo "Usage: ./sptestInpla.sh filename option"
+  exit
+fi
+
+if [ ! -e $path_source ]; then
+  echo "$path_source is not found."
+  exit
+fi
+
+if [ ! -e $inpla_seq -a ! -e "${inpla_seq}.exe" ]; then
+  echo "Now making Inpla in the non-threaded version as '$inpla_seq'."
+  make -C "$dir_make" clean
+  make -C "$dir_make"
+if [ -e 'inpla.exe' ]; then
+  inpla_seq="${inpla_seq}.exe"
+  mv ../../inpla.exe ./$inpla_seq
+else
+  mv ../../inpla ./$inpla_seq
+fi
+fi
+
+if [ ! -e $inpla_para -a ! -e "${inpla_para}.exe" ]; then
+  echo "Now making Inpla in the multi-threaded version as '$inpla_para'."
+  make -C "$dir_make" clean
+  make -C "$dir_make" thread
+if [ -e 'inpla.exe' ]; then
+  inpla_para="${inpla_para}.exe"
+  mv ../../inpla.exe ./$inplla_para
+else
+  mv ../../inpla ./$inpla_para
+fi
+fi
+
+
+# -------------------------------------------------
+function mywait() {
+    for w in $(seq 1 $waittime) ; do
+	echo -n "."
+	sleep 1
+    done
+}
+
+function gettime() {
+  # $1: the execution command
+  rm -f _result.txt
+  for i in $(seq 1 $ct) ; do
+      (time $1) 2>> _result.txt
+      echo 
+      echo -n "Done ($i/$ct)"
+      if [[ $(($i + 1)) -le $ct ]]; then
+	  mywait
+	  echo 'Restart'
+      fi      
+  done
+  echo
+  echo
+  logtime=`grep real _result.txt | cut -f2 | sed -e "s/\(.*\)m\(.*\)s/\1 \2/" | awk -F' ' '{print ($1*60+$2)}'`
+  echo "Execution time"
+  echo "$logtime"
+  
+  # for return value
+  res=`echo "$logtime\n" | awk 'BEGIN{r=0;c=0} {r=r+$0;c++} END{print r/c}'` 
+ rm -f _result.txt
+}
+
+function puts_header() {
+  # $1: the name of the log file
+  # $2: a program name
+  # ex: puts_header $log
+
+  local alog
+  alog=$1
+
+  echo '' >> $alog
+  echo "$2,$ct" | awk -F',' '{printf("%-27s| avg. time over %d runs (sec)\n",$1,$2)}' >> $alog
+  echo '===========================+=============================' >> $alog
+}
+
+function do_experiment() {
+  # $1: execution command
+  # $2: the header string to put the logfile
+  # ex: do_experiment "$inpla -f $source $opt_special $opt"
+  echo -n 'Cooling CPU'
+  mywait
+  echo
+  echo "------------------"   
+  echo "$1"
+  gettime "$1"
+  echo "Average ${res}sec"
+  echo "$2,$res" | awk -F',' '{printf("%-27s| %.2f\n",$1,$2)}' >> $log
+}
+
+
+
+# clear the previous log
+rm -f $log
+
+
+puts_header $log "$source $opt"
+
+# Execution in sequential
+do_experiment "./$inpla_seq -f $path_source $opt" "non-thread"
+
+# Execution in parallel
+for ((thread=1; thread<=max_threads; thread++))
+do 
+  do_experiment "./$inpla_para -f $path_source $opt -t $thread" "-t $thread"
+done
+
+echo
+cat $log
+
diff --git a/comparison/Inpla/src/ack-stream_3-11-reuse.in b/comparison/Inpla/src/ack-stream_3-11-reuse.in
new file mode 100644
index 0000000..7d7c701
--- /dev/null
+++ b/comparison/Inpla/src/ack-stream_3-11-reuse.in
@@ -0,0 +1,42 @@
+// Ackermann Function: streaming version
+//
+// fun ack(0,n) = n+1
+// | ack(m,0) = ack(m-1,1)        
+// | ack(m,n) = ack(m-1,ack(m,n-1));
+
+// The below rule is wrong because there is no gurantee
+// such that cnt is an integer agent when Ack(r)~(m-1,cnt) is evaluated.
+//
+// Ack(r) >< (int m, int n)
+// | m==0 => r~(n+1)
+// | n==0 => Ack(r) ~ (m-1,1)
+// | _ => Ack(cnt)~(m,n-1), Ack(r)~(m-1,cnt);
+
+
+// When m==0, we should not have OneUp(ret)~n
+// because the n is correspoidng to cnt in Ack(ret,cnt)~(m-1),
+// and we have to wait for finishing evaluation of Ack(cnt,n-1)~m.
+// So, without waiting, we put ret~Inc(n) in order to continue evaluation.
+// The the number of Inc is evaluated later by using Sumup.
+
+Ack(ret, n) >< (int m)
+| m==0 => ret~(*L)Inc(n)
+| _ => (*L)Ackm(ret, m)~n;
+
+Ackm(ret, int m) >< (int n)
+| n==0 => Ack(ret,Inc(0)) ~ (m-1)
+| _ => (*L)Ack(cnt,n-1)~m, Ack(ret,cnt)~(m-1);
+
+Ackm(ret, int m) >< Inc(n)
+=> (*L)Ack(cnt,n)~m, (*R)Ack(ret,cnt)~(m-1);
+
+Sumup(ret, int sum) >< Inc(x) => (*L)Sumup(ret, sum+1)~x;
+Sumup(ret, int sum) >< (int n) => ret~sum+n;
+
+
+//AckMain(ret)><(int m, int n) => (*L)Ack(cnt,n)~m, (*R)Sumup(ret,0)~cnt;
+AckMain(ret)><(int m, int n) => Ack(cnt,n)~m, Sumup(ret,0)~cnt;
+
+AckMain(ret)~(3,11);
+ret;
+free ret;
diff --git a/comparison/Inpla/src/ack-stream_3-11.in b/comparison/Inpla/src/ack-stream_3-11.in
new file mode 100644
index 0000000..7b23d32
--- /dev/null
+++ b/comparison/Inpla/src/ack-stream_3-11.in
@@ -0,0 +1,41 @@
+// Ackermann Function: streaming version
+//
+// fun ack(0,n) = n+1
+// | ack(m,0) = ack(m-1,1)        
+// | ack(m,n) = ack(m-1,ack(m,n-1));
+
+// The below rule is wrong because there is no gurantee
+// such that cnt is an integer agent when Ack(r)~(m-1,cnt) is evaluated.
+//
+// Ack(r) >< (int m, int n)
+// | m==0 => r~(n+1)
+// | n==0 => Ack(r) ~ (m-1,1)
+// | _ => Ack(cnt)~(m,n-1), Ack(r)~(m-1,cnt);
+
+
+// When m==0, we should not have OneUp(ret)~n
+// because the n is correspoidng to cnt in Ack(ret,cnt)~(m-1),
+// and we have to wait for finishing evaluation of Ack(cnt,n-1)~m.
+// So, without waiting, we put ret~Inc(n) in order to continue evaluation.
+// The the number of Inc is evaluated later by using Sumup.
+
+Ack(ret, n) >< (int m)
+| m==0 => ret~Inc(n)
+| _ => Ackm(ret, m)~n;
+
+Ackm(ret, int m) >< (int n)
+| n==0 => Ack(ret,Inc(0)) ~ (m-1)
+| _ => Ack(cnt,n-1)~m, Ack(ret,cnt)~(m-1);
+
+Ackm(ret, int m) >< Inc(n)
+=> Ack(cnt,n)~m, Ack(ret,cnt)~(m-1);
+
+Sumup(ret, int sum) >< Inc(x) => Sumup(ret, sum+1)~x;
+Sumup(ret, int sum) >< (int n) => ret~sum+n;
+
+
+AckMain(ret)><(int m, int n) => Ack(cnt,n)~m, Sumup(ret,0)~cnt;
+
+AckMain(ret)~(3,11);
+ret;
+free ret;
diff --git a/comparison/Inpla/src/bsort-40000-reuse.in b/comparison/Inpla/src/bsort-40000-reuse.in
new file mode 100644
index 0000000..8b6a386
--- /dev/null
+++ b/comparison/Inpla/src/bsort-40000-reuse.in
@@ -0,0 +1,24 @@
+// Bubble sort
+BS(ret) >< [] => ret~[];
+BS(ret) >< x:xs => (*L)BS(ret)~cnt, (*R)B(cnt, x)~xs;
+BS(ret) >< M(x) => ret~x;
+
+B(ret, int x) >< [] => ret~M([x]);
+B(ret, int x) >< M(w) => ret~M(x:w);
+B(ret, int x) >< (int y):ys
+| x<y => ret~(*R)(x:cnt), (*L)B(cnt, y)~ys
+| _   => ret~(*R)(y:cnt), (*L)B(cnt, x)~ys;
+
+
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+BS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/bsort-40000.in b/comparison/Inpla/src/bsort-40000.in
new file mode 100644
index 0000000..0120900
--- /dev/null
+++ b/comparison/Inpla/src/bsort-40000.in
@@ -0,0 +1,24 @@
+// Bubble sort
+BS(ret) >< [] => ret~[];
+BS(ret) >< x:xs => BS(ret)~cnt, B(cnt, x)~xs;
+BS(ret) >< M(x) => ret~x;
+
+B(ret, int x) >< [] => ret~M([x]);
+B(ret, int x) >< M(w) => ret~M(x:w);
+B(ret, int x) >< (int y):ys
+| x<y => ret~(x:cnt), B(cnt, y)~ys
+| _   => ret~(y:cnt), B(cnt, x)~ys;
+
+
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+BS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/fib-38-reuse.in b/comparison/Inpla/src/fib-38-reuse.in
new file mode 100644
index 0000000..6b3d32b
--- /dev/null
+++ b/comparison/Inpla/src/fib-38-reuse.in
@@ -0,0 +1,17 @@
+// Fibonacci number
+Fib(r) >< (int n)
+| n == 0 => r~0
+| n == 1 => r~1
+| _ => Fib(cnt1)~(n-1), Fib(cnt2)~(n-2), (*L)Add(r,cnt2)~cnt1;
+
+/* Add is realised as built-in.
+Addd(r,n) >< (int m)
+=> Addd2(r,m) ~ n;
+
+Addd2(r,int m) >< (int n)
+=> r~(m+n);
+*/
+
+Fib(r)~38;
+r;
+free r;
diff --git a/comparison/Inpla/src/fib-38.in b/comparison/Inpla/src/fib-38.in
new file mode 100644
index 0000000..a79eb5b
--- /dev/null
+++ b/comparison/Inpla/src/fib-38.in
@@ -0,0 +1,17 @@
+// Fibonacci number
+Fib(r) >< (int n)
+| n == 0 => r~0
+| n == 1 => r~1
+| _ => Add(r,cnt2)~cnt1, Fib(cnt1)~(n-1), Fib(cnt2)~(n-2);
+
+/*
+Addd(r,n) >< (int m)
+=> Addd2(r,m) ~ n;
+
+Addd2(r,int m) >< (int n)
+=> r~(m+n);
+*/
+
+Fib(r)~38;
+r;
+free r;
diff --git a/comparison/Inpla/src/isort-40000-reuse.in b/comparison/Inpla/src/isort-40000-reuse.in
new file mode 100644
index 0000000..00f0ecc
--- /dev/null
+++ b/comparison/Inpla/src/isort-40000-reuse.in
@@ -0,0 +1,22 @@
+// Insertion sort
+IS(ret) >< [] => ret~[];
+IS(ret) >< x:xs => (*L)I(ret, x)~cnt, (*R)IS(cnt)~xs;
+
+I(ret, int x) >< [] => ret~[x];
+I(ret, int x) >< (int y):ys
+| x<=y => ret~(*L)(x:(*R)(y:ys))
+| _    => ret~(*L)(y:cnt), (*R)I(cnt, x)~ys;
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+IS(ret)~cnt;
+ret;
+
+
diff --git a/comparison/Inpla/src/isort-40000.in b/comparison/Inpla/src/isort-40000.in
new file mode 100644
index 0000000..ff831a3
--- /dev/null
+++ b/comparison/Inpla/src/isort-40000.in
@@ -0,0 +1,22 @@
+// Insertion sort
+IS(ret) >< [] => ret~[];
+IS(ret) >< x:xs => I(ret, x)~cnt, IS(cnt)~xs;
+
+I(ret, int x) >< [] => ret~[x];
+I(ret, int x) >< (int y):ys
+| x<=y => ret~(x:y:ys)
+| _    => ret~(y:cnt), I(cnt, x)~ys;
+
+
+const LIST_ELEM=40000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+IS(ret)~cnt;
+ret;
+
+
diff --git a/comparison/Inpla/src/msort-800000-reuse.in b/comparison/Inpla/src/msort-800000-reuse.in
new file mode 100644
index 0000000..36723b9
--- /dev/null
+++ b/comparison/Inpla/src/msort-800000-reuse.in
@@ -0,0 +1,67 @@
+// Merge sort
+MS(ret) >< [] => ret~[];
+MS(ret) >< x:xs => MS_tail(ret, x)~xs;
+
+MS_tail(ret, n) >< [] => ret~(*R)[n];
+MS_tail(ret, int n) >< x:xs => 
+//	MS(a)~left, MS(b)~right, Append(ret,a)~b,
+//	Split(0, left,right) ~ (n:x:xs);
+	MS(a)~left, MS(b)~right, Append(ret,a)~b,
+	(*L)Split(left,right) ~ (*R)(n:x:xs);
+
+
+/*
+Splitn(int flag, a, b) >< [] => a~[], b~[];
+Splitn(int flag, a, b) >< (int y):ys
+| flag==0 => b~(*R)(y:cnt), (*L)Splitn(1, a, cnt)~ys
+| _       => a~(*R)(y:cnt), (*L)Splitn(0, cnt, b)~ys;
+
+Split(a,b) >< x:xs => Splitn(0,a,b)~x:xs;
+*/
+
+Split(a,b) >< [] => a~[], b~[];
+Split(a,b) >< x:xs => a~(x:cntl), (*L)Split(b,cntl)~xs;
+
+
+
+// この実験から、Merge は悪くないことがわかる。
+// Part でも -t 5 6 7 順に速くなる。
+// つまり、Split が悪いと言える。
+
+/*
+MS_tail(ret, n) >< [] => ret~(*R)[n];
+MS_tail(ret, n) >< x:xs => 
+	MS(a)~left, MS(b)~right, Merge(ret,b)~a,
+	(*L)Split(left,right) ~ (*R)(n:x:xs);
+*/
+
+Merge(ret, snd) >< [] => ret~snd;
+Merge(ret, snd) >< x:xs => (*L)MergeCC(ret, x, xs)~snd;
+
+MergeCC(ret, int y, ys) >< [] => ret~(*R)(y:ys);
+MergeCC(ret, int y, ys) >< (int x):xs
+| x <= y => ret~(x:cnt), (*L)MergeCC(cnt, y, ys) ~ xs
+| _      => ret~(y:cnt), (*L)MergeCC(cnt, x, xs) ~ ys;
+// ret~(*R)(x:cnt) less improvement
+
+// *** I should make an option that outputs bytecodes to a file. ***
+// *** Then, I have to look the reason why 
+// *** ret~(*R)(x:cnt), MergeCC(cnt, y, ys) ~ xs becomes less improvement.
+
+
+
+
+//	left~cntr, (*L)Split(cntr,cntl)~xs, right~(x:cntl);
+// This also make it less efficient.
+
+
+const LIST_ELEM=1200000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(LIST_ELEM)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+MS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/msort-800000.in b/comparison/Inpla/src/msort-800000.in
new file mode 100644
index 0000000..e04803f
--- /dev/null
+++ b/comparison/Inpla/src/msort-800000.in
@@ -0,0 +1,34 @@
+// Merge sort
+MS(ret) >< [] => ret~[];
+MS(ret) >< x:xs => MS_tail(ret, x)~xs;
+
+MS_tail(ret, int n) >< [] => ret~[n];
+MS_tail(ret, int n) >< x:xs => 
+	Split(left,right) ~ (n:x:xs),
+	MS(a)~left, MS(b)~right, Merge(ret,b)~a;
+
+Merge(ret, snd) >< [] => ret~snd;
+Merge(ret, snd) >< x:xs => MergeC(ret, x, xs)~snd;
+
+MergeCC(ret, int y, ys) >< [] => ret~(y:ys);
+MergeCC(ret, int y, ys) >< (int x):xs
+| x <= y => ret~(x:cnt), MergeCC(cnt, y, ys) ~ xs
+| _      => ret~(y:cnt), MergeCC(cnt, x, xs) ~ ys;
+
+
+Split(right,left) >< [] => right~[], left~[];
+Split(right,left) >< x:xs =>
+	right~(x:cntl), left~cntr, Split(cntr,cntl)~xs;
+
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+MS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/qsort-800000-reuse.in b/comparison/Inpla/src/qsort-800000-reuse.in
new file mode 100644
index 0000000..8bf7a83
--- /dev/null
+++ b/comparison/Inpla/src/qsort-800000-reuse.in
@@ -0,0 +1,29 @@
+// Quick sort
+QS(ret) >< [] => ret~(*R)[];
+QS(ret) >< (int x):xs =>
+	(*R)Part(x, left, right)~xs,
+	(*L)QS(cntl)~left, QS(cntr)~right,
+	Append(ret, x:cntl)~cntr;
+
+// Note: `Append' is implemented as built-in.
+
+// Apnd(ret, a)~b  -->  ret ~ b@a
+//Apnd(ret, a) >< [] => ret~a;
+//Apnd(ret, a) >< x:xs => ret~(x:cnt), Apnd(cnt, a)~xs;
+
+Part(int x, a, b) >< [] => a~(*L)[], b~(*R)[];
+Part(int x, a, b) >< (int y):ys
+| y<x => b~(*R)(y:cnt), (*L)Part(x, a, cnt)~ys
+| _   => a~(*R)(y:cnt), (*L)Part(x, cnt, b)~ys;
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), (*L)MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+QS(ret)~cnt;
+ret;
diff --git a/comparison/Inpla/src/qsort-800000.in b/comparison/Inpla/src/qsort-800000.in
new file mode 100644
index 0000000..e8913e8
--- /dev/null
+++ b/comparison/Inpla/src/qsort-800000.in
@@ -0,0 +1,29 @@
+// Quick sort
+QS(ret) >< [] => ret~[];
+QS(ret) >< (int x):xs =>
+	Part(x, left, right)~xs,
+	QS(cntl)~left, QS(cntr)~right,
+	Append(ret, x:cntl)~cntr;
+
+// Note: `Append' is implemented as built-in.
+
+// Apnd(ret, a)~b  -->  ret ~ b@a
+//Apnd(ret, a) >< [] => ret~a;
+//Apnd(ret, a) >< x:xs => ret~(x:cnt), Apnd(cnt, a)~xs;
+
+Part(int x, a, b) >< [] => a~[], b~[];
+Part(int x, a, b) >< (int y):ys
+| y<x => b~(y:cnt), Part(x, a, cnt)~ys
+| _   => a~(y:cnt), Part(x, cnt, b)~ys;
+
+
+const LIST_ELEM=800000;
+
+MkRandList(ret) >< (int n)
+| n>0 => ret~(rd:cnt), MkRandList(cnt)~(n-1) 
+  where rd=rand(10000)
+| _ => ret~[];
+
+MkRandList(cnt)~(LIST_ELEM),
+QS(ret)~cnt;
+ret;