aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorShinya Sato <shinnya.sato@gmail.com>2023-02-06 23:38:33 +0900
committerShinya Sato <shinnya.sato@gmail.com>2023-02-06 23:38:33 +0900
commit1d0f6bf7b2da6c35d25d6c1d21b0870218f0c0d3 (patch)
treef4f5d034b9805d729715ab45e26f24388b215569
parent984ea57be734a32a440cfc2f6bf5ffcab9e7df63 (diff)
parentff42726a5062fb7badc5ae325196963c7b0ad025 (diff)
downloadinpla-1d0f6bf7b2da6c35d25d6c1d21b0870218f0c0d3.tar.gz
inpla-1d0f6bf7b2da6c35d25d6c1d21b0870218f0c0d3.zip
Merge branch 'develop'
-rw-r--r--Changelog.md43
-rw-r--r--README.md20
-rw-r--r--pic/benchmark_reuse_v0.10.6.pngbin0 -> 38912 bytes
-rw-r--r--src/config.h3
-rw-r--r--src/inpla.y80
5 files changed, 103 insertions, 43 deletions
diff --git a/Changelog.md b/Changelog.md
index 99f5cb6..b26692b 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -1,10 +1,34 @@
# Change log
+### v0.10.6 (released on 6 February 2023)
+
+| | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r |
+| ------------ | :-----------------------------------------: | :-------------------------------------: | :-------------------------------------: | :----------------------------------------: | :---------------------------------------------: | :----------------------------------------------------: |
+| n-queens 12 | [**0.23**](comparison/Haskell/nqueen-12.hs) | [0.44](comparison/OCaml/nqueen12.ml) | [0.60](comparison/SML/ack3-11.sml) | [3.79](comparison/Python/nqueen-12.py) | [0.53](comparison/Inpla/src/nqueen-12.in) | [0.36](comparison/Inpla/src/nqueen-12-reuse.in) |
+| ack(3,11) | [2.37](comparison/Haskell/ack3-11.hs) | [0.57](comparison/OCaml/ack3_11.ml) | [**0.42**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.86](comparison/Inpla/src/ack-stream_3-11.in) | [0.75](comparison/Inpla/src/ack-stream_3-11-reuse.in) |
+| fib 38 | [1.61](comparison/Haskell/fib-38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib-38.sml) | [9.27](comparison/Python/fib-38.py) | [0.41](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) |
+| bsort 20000 | [5.03](comparison/Haskell/bsort-20000.hs) | [6.47](comparison/OCaml/bsort20000.ml) | [2.39](comparison/SML/bsort-20000.sml) | [20.02](comparison/Python/bsort-20000.py) | [2.23](comparison/Inpla/src/bsort-20000.in) | [**1.48**](comparison/Inpla/src/bsort-20000-reuse.in) |
+| isort 20000 | [2.15](comparison/Haskell/isort-20000.hs) | [1.48](comparison/OCaml/isort20000.ml) | [0.60](comparison/SML/isort-20000.sml) | [8.83](comparison/Python/isort-20000.py) | [**0.31**](comparison/Inpla/src/isort-20000.in) | [0.33](comparison/Inpla/src/isort-20000-reuse.in) |
+| qsort 260000 | [0.36](comparison/Haskell/qsort-800000.hs) | [0.22](comparison/OCaml/qsort260000.ml) | [0.27](comparison/SML/qsort-260000.sml) | [10.33](comparison/Python/qsort-260000.py) | [0.15](comparison/Inpla/src/qsort-260000.in) | [**0.12**](comparison/Inpla/src/qsort-260000-reuse.in) |
+| msort 260000 | [0.38](comparison/Haskell/msort-800000.hs) | [0.17](comparison/OCaml/msort260000.ml) | [0.29](comparison/SML/msort-260000.sml) | [11.09](comparison/Python/msort-260000.py) | [0.15](comparison/Inpla/src/msort-260000.in) | [**0.15**](comparison/Inpla/src/msort-260000-reuse.in) |
+
+#### Polished
+
+- **Two-addressing for mkagent4**: Two-addressing, which reduces the number of operands by one, is now available for `mkagent4` by default. To disable it, comment out the following line in `config.h`:
+
+ ```
+ #define OPTIMISE_TWO_ADDRESS_MKAGENT4 // For MKAGENT4
+ ```
+
+ In the benchmark result, we could expect that `n-queen` could be performed faster in the `Inpla8` execution, but it seems that the effect is small and just within the noise margin.
+
+
+
### v0.10.5 (released on 3 February 2023)
#### Bug fix
-- **Code generation for Tail Call Optimisation**: Tail Call Optimisation turns an active pair execution into a loop operation. When the loop is executed, each port information needs to be updated, but some were skipped if the names in the ports were the same but changed during execution. This is now fixed.
+- **Code generation for Tail Call Optimisation**: Tail Call Optimisation turns an active pair execution into a loop operation. When the loop is executed, each port information needs to be updated, but some were skipped if the argument names in the ports were the same and their assigned registers are changed during execution. This is now fixed.
### v0.10.4 (released on 28 January 2023)
@@ -16,7 +40,7 @@
foo(r) >< (int n)
| n == 0 => r~n
| _ => r << (*L)foo(n-1);
- // ^ The (*L) setting caused a parse error in a previous version.
+ // ^ This (*L) setting caused a parse error in a previous version.
```
@@ -84,7 +108,7 @@
Warning: `y' is used as a property variable, although is is not declared as so.
```
#### Minor change
-* **Messages of applying Tail Call Optimisation** : A message was put when the optimisation is applied, but now it turns off because this is for developers. To change it on, make the following line uncommented in `config.h`:
+* **Messages of applying Tail Call Optimisation** : A message was put when the optimisation is applied, but now it turns off because this is for developers. To enable this, make the following line uncommented in `config.h`:
```
//#define VERBOSE_TCO // Put message when TCO is enable.
@@ -93,6 +117,17 @@
### v0.10.0 (released on 17 September 2022)
+
+| | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r |
+| ------------ | :-----------------------------------------: | :-------------------------------------: | :-------------------------------------: | :----------------------------------------: | :---------------------------------------------: | :----------------------------------------------------: |
+| n-queens 12 | [**0.23**](comparison/Haskell/nqueen-12.hs) | [0.44](comparison/OCaml/nqueen12.ml) | [0.60](comparison/SML/ack3-11.sml) | [3.81](comparison/Python/nqueen-12.py) | [0.54](comparison/Inpla/src/nqueen-12.in) | [0.36](comparison/Inpla/src/nqueen-12-reuse.in) |
+| ack(3,11) | [2.36](comparison/Haskell/ack3-11.hs) | [0.57](comparison/OCaml/ack3_11.ml) | [**0.42**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.88](comparison/Inpla/src/ack-stream_3-11.in) | [0.76](comparison/Inpla/src/ack-stream_3-11-reuse.in) |
+| fib 38 | [1.61](comparison/Haskell/fib-38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib-38.sml) | [9.17](comparison/Python/fib-38.py) | [0.42](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) |
+| bsort 20000 | [5.01](comparison/Haskell/bsort-20000.hs) | [6.44](comparison/OCaml/bsort20000.ml) | [2.37](comparison/SML/bsort-20000.sml) | [20.58](comparison/Python/bsort-20000.py) | [2.17](comparison/Inpla/src/bsort-20000.in) | [**1.49**](comparison/Inpla/src/bsort-20000-reuse.in) |
+| isort 20000 | [2.16](comparison/Haskell/isort-20000.hs) | [1.48](comparison/OCaml/isort20000.ml) | [0.60](comparison/SML/isort-20000.sml) | [9.34](comparison/Python/isort-20000.py) | [**0.30**](comparison/Inpla/src/isort-20000.in) | [0.33](comparison/Inpla/src/isort-20000-reuse.in) |
+| qsort 260000 | [0.36](comparison/Haskell/qsort-800000.hs) | [0.22](comparison/OCaml/qsort260000.ml) | [0.27](comparison/SML/qsort-260000.sml) | [15.04](comparison/Python/qsort-260000.py) | [0.16](comparison/Inpla/src/qsort-260000.in) | [**0.12**](comparison/Inpla/src/qsort-260000-reuse.in) |
+| msort 260000 | [0.38](comparison/Haskell/msort-800000.hs) | [0.17](comparison/OCaml/msort260000.ml) | [0.26](comparison/SML/msort-260000.sml) | [15.55](comparison/Python/msort-260000.py) | [0.16](comparison/Inpla/src/msort-260000.in) | [**0.15**](comparison/Inpla/src/msort-260000-reuse.in) |
+
#### Polished (inner)
* **New instruction set for reuse active pairs**: Inpla supports annotations to reuse active active pairs by putting (\*L) and (\*R) in front of agents in rules as an experiment option. It was just to reuse only nodes for active pairs, but now we can specify the reuse method in the level of ports. As an example, we take the following rule:
@@ -115,7 +150,7 @@
```
It becomes quite reasonable, but there is no significant improvement in terms of execution speed than I expected. It becomes useful to demonstrate the execution performance obtained by the theoretical analysis.
- To keep using the old version, make the following uncommented in `config.h`:
+ To keep using the old version, uncomment the following in `config.h`:
```
//#define OLD_REUSEAGENT
diff --git a/README.md b/README.md
index 8a737c7..23aedb7 100644
--- a/README.md
+++ b/README.md
@@ -6,24 +6,24 @@
Inpla is a multi-threaded parallel interpreter of interaction nets. Once you write programs for sequential execution, it works also in multi-threaded parallel execution. Each thread is managed on each CPU-core with POSIX-thread library.
-* The current version is 0.10.5 (bug fix), released on **3 February 2023**. (See [Changelog.md](Changelog.md) for details.)
+* The current version is 0.10.6, released on **6 February 2023**. (See [Changelog.md](Changelog.md) for details.)
* The below graph shows speed-up ratio to threads numbers for programs in the following benchmark table.
-![speedup-ratio](pic/benchmark_reuse_v0.10.0.png)
+![speedup-ratio](pic/benchmark_reuse_v0.10.6.png)
-- **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.
+- **Comparison in execution time** with other implementations: **Haskell** (GHC version 8.10.7), **OCaml** (ocamlopt, the native-code compiler, version 4.13.1), **Standard ML of New Jersey** v110.74 (interpreter mode) and **Python** 3.10.6 in execution time.
| | Haskell | OCaml | SML | Python | Inpla8 | Inpla8r |
| -------------- | :------: | :------: | :----: | :----: | :------: | :------: |
-| n-queens 12 | [**0.23**](comparison/Haskell/nqueen-12.hs) | [0.44](comparison/OCaml/nqueen12.ml) | [0.60](comparison/SML/ack3-11.sml) | [3.81](comparison/Python/nqueen-12.py) | [0.54](comparison/Inpla/src/nqueen-12.in) | [0.36](comparison/Inpla/src/nqueen-12-reuse.in) |
-| ack(3,11) | [2.36](comparison/Haskell/ack3-11.hs) | [0.57](comparison/OCaml/ack3_11.ml) | [**0.42**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.88](comparison/Inpla/src/ack-stream_3-11.in) | [0.76](comparison/Inpla/src/ack-stream_3-11-reuse.in) |
-| fib 38 | [1.61](comparison/Haskell/fib-38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib-38.sml) | [9.17](comparison/Python/fib-38.py) | [0.42](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) |
-| bsort 20000 | [5.01](comparison/Haskell/bsort-20000.hs) | [6.44](comparison/OCaml/bsort20000.ml) | [2.37](comparison/SML/bsort-20000.sml) | [20.58](comparison/Python/bsort-20000.py) | [2.17](comparison/Inpla/src/bsort-20000.in) | [**1.49**](comparison/Inpla/src/bsort-20000-reuse.in) |
-| isort 20000 | [2.16](comparison/Haskell/isort-20000.hs) | [1.48](comparison/OCaml/isort20000.ml) | [0.60](comparison/SML/isort-20000.sml) | [9.34](comparison/Python/isort-20000.py) | [**0.30**](comparison/Inpla/src/isort-20000.in) | [0.33](comparison/Inpla/src/isort-20000-reuse.in) |
-| qsort 260000 | [0.36](comparison/Haskell/qsort-800000.hs) | [0.22](comparison/OCaml/qsort260000.ml) | [0.27](comparison/SML/qsort-260000.sml) | [15.04](comparison/Python/qsort-260000.py) | [0.16](comparison/Inpla/src/qsort-260000.in) | [**0.12**](comparison/Inpla/src/qsort-260000-reuse.in) |
-| msort 260000 | [0.38](comparison/Haskell/msort-800000.hs) | [0.17](comparison/OCaml/msort260000.ml) | [0.26](comparison/SML/msort-260000.sml) | [15.55](comparison/Python/msort-260000.py) | [0.16](comparison/Inpla/src/msort-260000.in) | [**0.15**](comparison/Inpla/src/msort-260000-reuse.in) |
+| n-queens 12 | [**0.23**](comparison/Haskell/nqueen-12.hs) | [0.44](comparison/OCaml/nqueen12.ml) | [0.60](comparison/SML/ack3-11.sml) | [3.79](comparison/Python/nqueen-12.py) | [0.53](comparison/Inpla/src/nqueen-12.in) | [0.36](comparison/Inpla/src/nqueen-12-reuse.in) |
+| ack(3,11) | [2.37](comparison/Haskell/ack3-11.hs) | [0.57](comparison/OCaml/ack3_11.ml) | [**0.42**](comparison/SML/ack3-11.sml) | [-](comparison/Python/ack3-11.py) | [0.86](comparison/Inpla/src/ack-stream_3-11.in) | [0.75](comparison/Inpla/src/ack-stream_3-11-reuse.in) |
+| fib 38 | [1.61](comparison/Haskell/fib-38.hs) | [**0.15**](comparison/OCaml/fib38.ml) | [0.27](comparison/SML/fib-38.sml) | [9.27](comparison/Python/fib-38.py) | [0.41](comparison/Inpla/src/fib-38.in) | [0.43](comparison/Inpla/src/fib-38-reuse.in) |
+| bsort 20000 | [5.03](comparison/Haskell/bsort-20000.hs) | [6.47](comparison/OCaml/bsort20000.ml) | [2.39](comparison/SML/bsort-20000.sml) | [20.02](comparison/Python/bsort-20000.py) | [2.23](comparison/Inpla/src/bsort-20000.in) | [**1.48**](comparison/Inpla/src/bsort-20000-reuse.in) |
+| isort 20000 | [2.15](comparison/Haskell/isort-20000.hs) | [1.48](comparison/OCaml/isort20000.ml) | [0.60](comparison/SML/isort-20000.sml) | [8.83](comparison/Python/isort-20000.py) | [**0.31**](comparison/Inpla/src/isort-20000.in) | [0.33](comparison/Inpla/src/isort-20000-reuse.in) |
+| qsort 260000 | [0.36](comparison/Haskell/qsort-800000.hs) | [0.22](comparison/OCaml/qsort260000.ml) | [0.27](comparison/SML/qsort-260000.sml) | [10.33](comparison/Python/qsort-260000.py) | [0.15](comparison/Inpla/src/qsort-260000.in) | [**0.12**](comparison/Inpla/src/qsort-260000-reuse.in) |
+| msort 260000 | [0.38](comparison/Haskell/msort-800000.hs) | [0.17](comparison/OCaml/msort260000.ml) | [0.29](comparison/SML/msort-260000.sml) | [11.09](comparison/Python/msort-260000.py) | [0.15](comparison/Inpla/src/msort-260000.in) | [**0.15**](comparison/Inpla/src/msort-260000-reuse.in) |
diff --git a/pic/benchmark_reuse_v0.10.6.png b/pic/benchmark_reuse_v0.10.6.png
new file mode 100644
index 0000000..e052faa
--- /dev/null
+++ b/pic/benchmark_reuse_v0.10.6.png
Binary files differ
diff --git a/src/config.h b/src/config.h
index 77b8d91..7d3ea52 100644
--- a/src/config.h
+++ b/src/config.h
@@ -97,7 +97,10 @@
#define OPTIMISE_TWO_ADDRESS_MKAGENT1 // For MKAGENT1
#define OPTIMISE_TWO_ADDRESS_MKAGENT2 // For MKAGENT2
#define OPTIMISE_TWO_ADDRESS_MKAGENT3 // For MKAGENT3
+#define OPTIMISE_TWO_ADDRESS_MKAGENT4 // For MKAGENT4
+
//#define OPTIMISE_TWO_ADDRESS_UNARY // For Unary operator like INC, DEC
+ // (Unfinished)
#endif
diff --git a/src/inpla.y b/src/inpla.y
index a0901e2..47a2242 100644
--- a/src/inpla.y
+++ b/src/inpla.y
@@ -22,8 +22,8 @@
// ----------------------------------------------
-#define VERSION "0.10.5"
-#define BUILT_DATE "3 February 2023"
+#define VERSION "0.10.6"
+#define BUILT_DATE "6 February 2023"
// ------------------------------------------------------------------
@@ -2868,6 +2868,7 @@ void VMCode_puts(void **code, int n) {
#endif
} else if (code[i] == CodeAddr[OP_MKAGENT4]) {
+#if !defined(OPTIMISE_TWO_ADDRESS) || !defined(OPTIMISE_TWO_ADDRESS_MKAGENT4)
printf("mkagent4 id:%lu reg%lu reg%lu reg%lu reg%lu reg%lu\n",
(unsigned long)code[i+1],
(unsigned long)code[i+2],
@@ -2876,7 +2877,15 @@ void VMCode_puts(void **code, int n) {
(unsigned long)code[i+5],
(unsigned long)code[i+6]);
i+=6;
-
+#else
+ printf("mkagent4 id:%lu reg%lu reg%lu reg%lu reg%lu\n",
+ (unsigned long)code[i+1],
+ (unsigned long)code[i+2],
+ (unsigned long)code[i+3],
+ (unsigned long)code[i+4],
+ (unsigned long)code[i+5]);
+#endif
+
} else if (code[i] == CodeAddr[OP_MKAGENT5]) {
printf("mkagent5 id:%lu reg%lu reg%lu reg%lu reg%lu reg%lu reg%lu\n",
(unsigned long)code[i+1],
@@ -4133,6 +4142,11 @@ int CmEnv_Optimise_VMCode_CopyPropagation(int target_imcode_addr) {
return 1;
}
+ // ------------------------------------------------------------
+ // This part was commented out at v0.10.5
+ // Even if LOAD_META reg_n reg_n occurs, the varn could be preserved
+ // to another reg_n during the execusion, so it must not be DEAD_CODE here.
+ // ------------------------------------------------------------
/*
// When the given line is: LOAD_META src1 src1
if ((load_from == load_to) &&
@@ -4586,6 +4600,22 @@ int CmEnv_generate_VMCode(void **code) {
long dest = imcode->operand6;
#ifdef OPTIMISE_IMCODE
+ src4 = CmEnv_using_reg(src4);
+ if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num))
+ CmEnv_free_reg(src4);
+
+#if !defined(OPTIMISE_TWO_ADDRESS) || !defined(OPTIMISE_TWO_ADDRESS_MKAGENT4)
+ dest = CmEnv_get_newreg(dest);
+#else
+ int new_reg = CmEnv_assign_reg(dest, src4);
+ if (new_reg > 0) {
+ code[addr++] = CodeAddr[OP_LOAD];
+ code[addr++] = (void *)(unsigned long)src4;
+ code[addr++] = (void *)(unsigned long)new_reg;
+ }
+#endif
+
+
src1 = CmEnv_using_reg(src1);
if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand2, line_num))
&& (imcode->operand2 != imcode->operand3)
@@ -4603,12 +4633,6 @@ int CmEnv_generate_VMCode(void **code) {
if ((!CmEnv_Optimise_check_occurence_in_block(imcode->operand4, line_num))
&& (imcode->operand4 != imcode->operand5))
CmEnv_free_reg(src3);
-
- src4 = CmEnv_using_reg(src4);
- if (!CmEnv_Optimise_check_occurence_in_block(imcode->operand5, line_num))
- CmEnv_free_reg(src4);
-
- dest = CmEnv_get_newreg(dest);
#endif
@@ -4618,7 +4642,9 @@ int CmEnv_generate_VMCode(void **code) {
code[addr++] = (void *)(unsigned long)src2;
code[addr++] = (void *)(unsigned long)src3;
code[addr++] = (void *)(unsigned long)src4;
+#if !defined(OPTIMISE_TWO_ADDRESS) || !defined(OPTIMISE_TWO_ADDRESS_MKAGENT4)
code[addr++] = (void *)(unsigned long)dest;
+#endif
break;
}
case OP_MKAGENT5: {
@@ -8415,6 +8441,7 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) {
E_MKAGENT4:
+#if !defined(OPTIMISE_TWO_ADDRESS) || !defined(OPTIMISE_TWO_ADDRESS_MKAGENT4)
// puts("mkagent4 id src1 src2 src3 src4 dest");
a1 = make_Agent(vm, (unsigned long)code[++pc]);
{
@@ -8425,6 +8452,18 @@ void *exec_code(int mode, VirtualMachine * restrict vm, void * restrict *code) {
a1port[3] = reg[(unsigned long)code[++pc]];
}
reg[(unsigned long)code[++pc]] = a1;
+#else
+ // puts("mkagent4 id src1 src2 src3 src4 dest");
+ a1 = make_Agent(vm, (unsigned long)code[++pc]);
+ {
+ volatile VALUE *a1port = AGENT(a1)->port;
+ a1port[0] = reg[(unsigned long)code[++pc]];
+ a1port[1] = reg[(unsigned long)code[++pc]];
+ a1port[2] = reg[(unsigned long)code[++pc]];
+ a1port[3] = reg[(unsigned long)code[++pc]];
+ }
+ reg[(unsigned long)code[pc]] = a1;
+#endif
goto *code[++pc];
E_MKAGENT5:
@@ -10511,24 +10550,6 @@ loop_agent_a1_a2_this_order:
}
break; // end ID_PERCENT
- /*
- case ID_LAM:
- if (BASIC(a2)->id == ID_APP) {
- // Lam(x,t) ~ @(r,s) => r~t, x~s;
-
- COUNTUP_INTERACTION(vm);
-
- PUSH(vm, AGENT(a2)->port[0], AGENT(a1)->port[1]);
- VALUE a1p0 = AGENT(a1)->port[0];
- VALUE a2p1 = AGENT(a2)->port[1];
- free_Agent2(a1,a2);
- a1 = a1p0;
- a2 = a2p1;
- goto loop;
-
- }
- break; // end ID_LAM
- */
} // end switch(BASIC(a1)->id)
@@ -11021,7 +11042,8 @@ int exec(Ast *at) {
#else
-// CPU 数の設定用(sysconf(_SC_NPROSSEORS_CONF)) を使って求める)
+// For setting the number of CPUs.
+// it is calculated by using sysconf(_SC_NPROSSEORS_CONF) in tpool_init
static int CpuNum=1;
static pthread_cond_t ActiveThread_all_sleep = PTHREAD_COND_INITIALIZER;
@@ -11222,7 +11244,7 @@ int exec(Ast *at) {
IMCode_genCode2(OP_PUSH, p1, p2);
}
- eqsnum++; //分散用
+ eqsnum++; // for distrubution
at = ast_getTail(at);
}
IMCode_genCode0(OP_RET);