diff options
| -rw-r--r-- | Changelog.md | 8 | ||||
| -rw-r--r-- | README.md | 22 | ||||
| -rw-r--r-- | comparison/OCaml/Makefile | 36 | ||||
| -rw-r--r-- | comparison/OCaml/ack3_11.ml | 6 | ||||
| -rw-r--r-- | comparison/OCaml/bsort40000.ml | 23 | ||||
| -rw-r--r-- | comparison/OCaml/fib38.ml | 7 | ||||
| -rw-r--r-- | comparison/OCaml/isort40000.ml | 30 | ||||
| -rw-r--r-- | comparison/OCaml/msort800000.ml | 43 | ||||
| -rw-r--r-- | comparison/OCaml/qsort800000.ml | 30 | ||||
| -rw-r--r-- | comparison/README.txt | 2 | ||||
| -rw-r--r-- | comparison/SML/fib38.sml | 4 | ||||
| -rw-r--r-- | comparison/all.sh | 2 |
12 files changed, 197 insertions, 16 deletions
diff --git a/Changelog.md b/Changelog.md index 4df2d4a..3183485 100644 --- a/Changelog.md +++ b/Changelog.md @@ -1,7 +1,15 @@ # Change log +### Update on 16 April 2022 + +#### Polished + +* Several OCaml execution times have been added to the benchmark table. These programs are stored in `comparison/OCaml`. + + ### v0.8.1-1 minor update (released on 10 March 2022) + #### Polished * **Sample file (Tower of Hanoi)**: A new sample file for Tower of Hanoi is included in `sample` directory. @@ -10,26 +10,26 @@ Inpla is a multi-threaded parallel interpreter of interaction nets. Once you wri  -| | Haskell | SML | Python | Inpla1 | Inpla1_r | Inpla8 | Inpla8_r | -| -------------- | :------: | :------: | :----: | :----: | :------: | :----: | :------: | -| ack(3,11) | 2.31 | **0.41** | - | 4.32 | 3.49 | 0.82 | 0.70 | -| fib 38 | 1.60 | **0.26** | 8.49 | 2.29 | 2.80 | 0.38 | 0.40 | -| bsort 40000 | 34.81 | 11.17 | 76.72 | 18.01 | 16.42 | 3.03 | **2.42** | -| isort 40000 | **0.02** | 2.97 | 36.63 | 6.98 | 8.08 | 1.18 | 1.18 | -| qsort 800000 | **0.15** | 1.16 | 97.30 | 6.09 | 1.79 | 0.61 | 0.35 | -| msort 800000 | 0.46 | 1.00 | 98.27 | 3.93 | 1.35 | 0.48 | **0.35** | +| | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r | +| -------------- | :------: | :------: | :----: | :----: | :------: | :------: | +| ack(3,11) | 2.31 | 0.46 | **0.41** | - | 0.82 | 0.70 | +| fib 38 | 1.60 | **0.15** | 0.26 | 8.49 | 0.38 | 0.40 | +| bsort 40000 | 34.81 | 35.52 | 11.17 | 76.72 | 3.03 | **2.42** | +| isort 40000 | **0.02** | 7.44 | 2.97 | 36.63 | 1.18 | 1.18 | +| qsort 800000 | **0.15** | - | 1.16 | 97.30 | 0.61 | 0.35 | +| msort 800000 | 0.46 | - | 1.00 | 98.27 | 0.48 | **0.35** | -- **Comparison in execution time** with other implementations: **Haskell** (GHC version 8.10.7), **Standard ML of New Jersey** v110.74 (interpreter mode) and **Python** 3.8.5 in execution time. +- **Comparison in execution time** with other implementations: **Haskell** (GHC version 8.10.7), **OCaml** (ocamlopt, the native-code compiler, version 4.08.1), **Standard ML of New Jersey** v110.74 (interpreter mode) and **Python** 3.8.5 in execution time. - The above table contains execution time in second on average of ten times execution by using Linux PC (Core i7-9700 (8 threads, no Hyper-threading), 16GB memory). The fastest one is shown with bold style. Scripts for the comparison table are in the `comparison` directory. - - Inpla*n* and Inpla*n*_**r** mean *n* threads without/with reuse-annotated execution, respectively. + - Inpla8 and Inpla8r mean 8 threads without/with reuse-annotated execution, respectively. - "ack(3,11)" is computation of Ackermann function. Execution time of Python is a blank due to stack size limitation error. - "fib 38" is computation to get the 38th Fibonacci number. - - "bsort *n*", "isort *n*", "qsort *n*" and "msort *n*" are computation of bubble sort, insertion sort, quick sort and merge sort for random *n*-element lists, respectively. + - "bsort *n*", "isort *n*", "qsort *n*" and "msort *n*" are computation of bubble sort, insertion sort, quick sort and merge sort for random *n*-element lists, respectively. The blanks in OCaml are due to error: `Stack overflow during evaluation (looping recursion?).` diff --git a/comparison/OCaml/Makefile b/comparison/OCaml/Makefile new file mode 100644 index 0000000..94a4ffb --- /dev/null +++ b/comparison/OCaml/Makefile @@ -0,0 +1,36 @@ +CC = ocamlopt +CFLAGS = +BENCHMARK = bash ../tools/sptest_commands.sh +#TARGET = ack3_11 fib38 bsort40000 isort40000 qsort800000 msort800000 +TARGET = ack3_11 fib38 bsort40000 isort40000 +LOG = log.txt + + +.PHONY: all + +all: $(LOG) + +$(LOG): $(TARGET) + $(BENCHMARK) $(TARGET) + +ack3_11: ack3_11.ml + $(CC) $(CFLAGS) $< -o $@ + +fib38: fib38.ml + $(CC) $(CFLAGS) $< -o $@ + +bsort40000: bsort40000.ml + $(CC) $(CFLAGS) $< -o $@ + +isort40000: isort40000.ml + $(CC) $(CFLAGS) $< -o $@ + +qsort800000: qsort-800000.ml + $(CC) $(CFLAGS) $< -o $@ + +msort800000: msort-800000.ml + $(CC) $(CFLAGS) $< -o $@ + + +clean: + rm -f $(LOG) $(TARGET) *.o *.cmi *.cmx *~ diff --git a/comparison/OCaml/ack3_11.ml b/comparison/OCaml/ack3_11.ml new file mode 100644 index 0000000..6d4cdce --- /dev/null +++ b/comparison/OCaml/ack3_11.ml @@ -0,0 +1,6 @@ +let rec ack m n = + if m==0 then n+1 + else if n==0 then ack (m-1) 1 + else ack (m-1) (ack m (n-1)) + +let () = print_int (ack 3 11); diff --git a/comparison/OCaml/bsort40000.ml b/comparison/OCaml/bsort40000.ml new file mode 100644 index 0000000..45744bd --- /dev/null +++ b/comparison/OCaml/bsort40000.ml @@ -0,0 +1,23 @@ +let rec bs (alist : int list) n = + match alist with + (x::y::ys) -> + if x<y then x::(bs (y::ys) (n-1)) + else y::(bs (x::ys) (n-1)) + | xs -> xs;; + + +let rec go xs n = + match n with + 0 -> xs + | n -> go (bs xs n) (n-1);; + +let bsort xs = go xs (List.length(xs) - 1);; + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1));; + +let main = bsort (mkRandList 40000);; + diff --git a/comparison/OCaml/fib38.ml b/comparison/OCaml/fib38.ml new file mode 100644 index 0000000..2f7906d --- /dev/null +++ b/comparison/OCaml/fib38.ml @@ -0,0 +1,7 @@ +let rec fib n = + match n with + 0 -> 0 + | 1 -> 1 + | n -> fib(n-1) + fib (n-2) + +let () = print_int (fib 38); diff --git a/comparison/OCaml/isort40000.ml b/comparison/OCaml/isort40000.ml new file mode 100644 index 0000000..686a7f6 --- /dev/null +++ b/comparison/OCaml/isort40000.ml @@ -0,0 +1,30 @@ +(* +let rec insert x ylist = + match ylist with + [] -> [x] + | y::ys when x<=y -> x::y::ys + | y::ys -> y::(insert x ys);; +*) + +let rec insert x ylist = + match ylist with + [] -> [x] + | y::ys -> if x<=y + then x::y::ys + else y::(insert x ys);; + + +let rec isort (alist : int list) = + match alist with + [] -> [] + | x::xs -> insert x (isort xs);; + + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1));; + +let main = isort (mkRandList 40000);; + diff --git a/comparison/OCaml/msort800000.ml b/comparison/OCaml/msort800000.ml new file mode 100644 index 0000000..1835b98 --- /dev/null +++ b/comparison/OCaml/msort800000.ml @@ -0,0 +1,43 @@ +let rec split (alist : int list) = + match alist with + [] -> ([], []) + | [a] -> ([a], []) + | a::b::cs -> + let (m,n) = split cs in + (a::m, b::m) ;; + +let rec merge (alist : int list) (blist : int list) = + match alist with + [] -> blist + | x::xs -> + match blist with + [] -> x::xs + | y::ys -> + if x<y then x::(merge xs (y::ys)) + else y::(merge (x::xs) ys) ;; + + +let rec msort (alist : int list) = + match alist with + [] -> [] + | a::[] -> [a] + | a::b::[] -> if a<b then [a;b] else [b;a] + | xs -> + let (m,n) = split xs + in merge (msort m) (msort n) ;; + + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1)) ;; + +let main = msort (mkRandList 800000) ;; + + +(* +The following error arises: + +Stack overflow during evaluation (looping recursion?). +*) diff --git a/comparison/OCaml/qsort800000.ml b/comparison/OCaml/qsort800000.ml new file mode 100644 index 0000000..627abd2 --- /dev/null +++ b/comparison/OCaml/qsort800000.ml @@ -0,0 +1,30 @@ +let rec split pivot (alist : int list) = + match alist with + [] -> ([], []) + | (x::xs) -> + let (below, above) = split pivot xs in + if x<pivot then (x::below, above) + else (below, x::above) ;; + +let rec qsort (alist : int list) = + match alist with + [] -> [] + | pivot::rest -> + let (below, above) = split pivot rest + in (qsort below) @ [pivot] @ (qsort above) ;; + + + + +let rec mkRandList n = + match n with + 0 -> [] + | n -> (Random.int 10000)::(mkRandList (n-1)) ;; + +let main = qsort (mkRandList 800000) ;; + +(* +The following error arises: + +Stack overflow during evaluation (looping recursion?). +*) diff --git a/comparison/README.txt b/comparison/README.txt new file mode 100644 index 0000000..d5a1f57 --- /dev/null +++ b/comparison/README.txt @@ -0,0 +1,2 @@ +To get benchmark results, invoke the following command: +bash all.sh diff --git a/comparison/SML/fib38.sml b/comparison/SML/fib38.sml index c49ed14..504d4ac 100644 --- a/comparison/SML/fib38.sml +++ b/comparison/SML/fib38.sml @@ -2,8 +2,4 @@ fun fib 0 = 0 | fib 1 = 1 | fib n = (fib (n-1)) + (fib (n-2)); - - -(* ex *) -(* prnat(Ack (mknat 2) (mknat 3)); *) fib 38; diff --git a/comparison/all.sh b/comparison/all.sh index 424e50f..2c82c45 100644 --- a/comparison/all.sh +++ b/comparison/all.sh @@ -1,5 +1,5 @@ #!/usr/bin/bash -dir=(Haskell SML Python Inpla) +dir=(OCaml Haskell SML Python Inpla) for d in ${dir[@]} ; do # echo "cd $d; make clean; make; cd .."; # cd $d; make clean; make; cd .. |