v0.11.0

10 files changed, 67 insertions, 41 deletions

diff --git a/Changelog.md b/Changelog.md
index bb6f5fa..7a8ebc0 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -1,5 +1,20 @@
 # Change log
 
+### v0.11.0 (released on 13 May 2023)
+#### Polished
+- **The expansion size of the Flexibly expandable ring buffer for agents and names**: The ring buffer contains several small ring buffers. A new one is added to the ring buffer when each node in these buffers is used up. The size of the new buffer was based on the size of the last buffer searched, but this was found to be inefficient, especially for the reuse optimisation. So, it is now based on the size of the buffer where the last node was placed. It improves the reuse optimisation. The annotations for the optimisation were selected heuristically. Now they are placed systematically based on an algorithm. The execution times are shown in the table below. We can get more or less almost the same ones. This will be the basis for the automatic placement of the annotations.
+
+|              |                    v0.10.8-1                     |                                                        | -> | v0.11.0 |         |
+| ------------ | :----------------------------------------------: | :----------------------------------------------------: | :-----:: | :-------: | :-------: |
+|              |                      Inpla8                      |                        Inpla8r                         |  | Inpla8 | Inpra8r |
+| n-queens 12  |    0.54     |    0.36     |  | 0.55 | 0.40 |
+| ack(3,11)    | 0.90  | 0.73  |  | 0.91 | **0.68** |
+| fib 38       |      0.43      |      0.45      |  | **0.43** | **0.45** |
+| bsort 20000  |   2.38    | 1.48  |  | **2.31** | **1.45** |
+| isort 20000  | 0.32  | 0.32  |  | **0.32** | 0.33 |
+| qsort 260000 |   0.15   | 0.12 |  | **0.15** | **0.12** |
+| msort 260000 | 0.14 |   0.16   |  | **0.14** | 0.17 |
+
 ### v0.10.8-1 minor update (released on 7 May 2023)
 #### Bug fix
 - **Segmentation faults in rule definitions**: This was caused by a lack of linearity checking, which had been omitted for some experiments. Also, the compilation environment was updated for incomplete rule definitions. These are now fixed. Previously, the segmentation fault error was caused as follows:
diff --git a/README.md b/README.md
index 5d5a715..0cbbf46 100644
--- a/README.md
+++ b/README.md
@@ -6,7 +6,7 @@
 
 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.8-1, released on **7 May 2023**. (See [Changelog.md](Changelog.md) for details.) 
+* The current version is 0.11.0, released on **13 May 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.7.png)
diff --git a/comparison/Inpla/src/ack-stream_3-11-reuse.in b/comparison/Inpla/src/ack-stream_3-11-reuse.in
index 4a05f82..dc1a0fd 100644
--- a/comparison/Inpla/src/ack-stream_3-11-reuse.in
+++ b/comparison/Inpla/src/ack-stream_3-11-reuse.in
@@ -28,13 +28,13 @@ Ackm(ret, int m) >< (int n)
 | _ => (*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);
+=> (*R)Ack(cnt,n)~m, (*L)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) => (*R)Ack(cnt,n)~m, (*L)Sumup(ret,0)~cnt;
 //AckMain(ret)><(int m, int n) => Ack(cnt,n)~m, Sumup(ret,0)~cnt;
 
 AckMain(ret)~(3,11);
diff --git a/comparison/Inpla/src/bsort-20000-reuse.in b/comparison/Inpla/src/bsort-20000-reuse.in
index 0b7e551..f7348d5 100644
--- a/comparison/Inpla/src/bsort-20000-reuse.in
+++ b/comparison/Inpla/src/bsort-20000-reuse.in
@@ -22,8 +22,8 @@ bs_Cons(r, int n)>< x:xs => (*L)bs_ConsCons(r, n, x) ~ xs;
 bs_Cons(r, int n)>< [] => r~(*R)[];
 
 bs_ConsCons(r, int n, int x) >< (int y):ys
-| x < y => r~x:cnt, (*L)bs(cnt, (*R)(y:ys)) ~(n-1)
-| _ => r~y:cnt, (*L)bs(cnt, (*R)(x:ys))~(n-1);
+| x < y => r~(*R)(x:cnt), (*L)bs(cnt, y:ys) ~(n-1)
+| _ => r~(*R)(y:cnt), (*L)bs(cnt, x:ys)~(n-1);
 bs_ConsCons(r, int n, int x) >< [] => r~(*R)[x];
 
 go(r,xs) >< (int n)
@@ -45,13 +45,13 @@ make_RandList(ret) >< (int n)
 
 
 // validation checks
-valid(ret) >< [] => ret~True;
+valid(ret) >< [] => ret~(*L)True;
 valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs;
 
 valid_Cons(ret, int x) >< [] => ret~True;
 valid_Cons(ret, int x) >< (int y):ys
 | x<=y => (*L)valid_Cons(ret,y)~ys
-| _ => ret~False, Eraser~ys;
+| _ => ret~(*L)False, (*R)Eraser~ys;
 
 // The `Eraser' is a built-in agent defined for any agents as follows:
 //Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5;
diff --git a/comparison/Inpla/src/isort-20000-reuse.in b/comparison/Inpla/src/isort-20000-reuse.in
index aa63652..76bc4ff 100644
--- a/comparison/Inpla/src/isort-20000-reuse.in
+++ b/comparison/Inpla/src/isort-20000-reuse.in
@@ -2,7 +2,7 @@
 isort(ret) >< [] => ret~(*R)[];
 isort(ret) >< x:xs => (*R)I(ret, x)~cnt, (*L)isort(cnt)~xs;
 
-I(ret, int x) >< [] => ret~[x];
+I(ret, int x) >< [] => ret~(*R)[x];
 I(ret, int x) >< (int y):ys
 | x<=y => ret~(*L)(x:(*R)(y:ys))
 | _    => (*L)I(cnt, x)~ys, ret~(*R)(y:cnt);
@@ -16,13 +16,13 @@ make_RandList(ret) >< (int n)
 
 
 // validation checks
-valid(ret) >< [] => ret~True;
+valid(ret) >< [] => ret~(*L)True;
 valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs;
 
 valid_Cons(ret, int x) >< [] => ret~True;
 valid_Cons(ret, int x) >< (int y):ys
 | x<=y => (*L)valid_Cons(ret,y)~ys
-| _ => ret~False, Eraser~ys;
+| _ => ret~(*L)False, (*R)Eraser~ys;
 
 // The `Eraser' is a built-in agent defined for any agents as follows:
 //Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5;
diff --git a/comparison/Inpla/src/msort-260000-reuse.in b/comparison/Inpla/src/msort-260000-reuse.in
index 14aa4a3..075fa7b 100644
--- a/comparison/Inpla/src/msort-260000-reuse.in
+++ b/comparison/Inpla/src/msort-260000-reuse.in
@@ -12,10 +12,10 @@ 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;
+| x <= y => ret~(*R)(x:cnt), (*L)mergeCC(cnt, y, ys) ~ xs
+| _      => ret~(*R)(y:cnt), (*L)mergeCC(cnt, x, xs) ~ ys;
 
-split(right,left) >< [] => right~[], left~[];
+split(right,left) >< [] => right~(*L)[], left~(*R)[];
 split(right,left) >< x:xs =>
 	right~(*R)(x:cntl), left~cntr, (*L)split(cntr,cntl)~xs;
 
@@ -28,13 +28,13 @@ make_RandList(ret) >< (int n)
 
 
 // validation checks
-valid(ret) >< [] => ret~True;
+valid(ret) >< [] => ret~(*L)True;
 valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs;
 
 valid_Cons(ret, int x) >< [] => ret~True;
 valid_Cons(ret, int x) >< (int y):ys
 | x<=y => (*L)valid_Cons(ret,y)~ys
-| _ => ret~False, Eraser~ys;
+| _ => ret~(*L)False, (*R)Eraser~ys;
 
 // The `Eraser' is a built-in agent defined for any agents as follows:
 //Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5;
diff --git a/comparison/Inpla/src/msort-800000-reuse.in b/comparison/Inpla/src/msort-800000-reuse.in
index f50f359..e1aa31d 100644
--- a/comparison/Inpla/src/msort-800000-reuse.in
+++ b/comparison/Inpla/src/msort-800000-reuse.in
@@ -12,10 +12,10 @@ 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;
+| x <= y => ret~(*R)(x:cnt), (*L)mergeCC(cnt, y, ys) ~ xs
+| _      => ret~(*R)(y:cnt), (*L)mergeCC(cnt, x, xs) ~ ys;
 
-split(right,left) >< [] => right~[], left~[];
+split(right,left) >< [] => right~(*L)[], left~(*R)[];
 split(right,left) >< x:xs =>
 	right~(*R)(x:cntl), left~cntr, (*L)split(cntr,cntl)~xs;
 
@@ -28,13 +28,13 @@ make_RandList(ret) >< (int n)
 
 
 // validation checks
-valid(ret) >< [] => ret~True;
+valid(ret) >< [] => ret~(*L)True;
 valid(ret) >< x:xs => (*L)valid_Cons(ret,x)~xs;
 
 valid_Cons(ret, int x) >< [] => ret~True;
 valid_Cons(ret, int x) >< (int y):ys
 | x<=y => (*L)valid_Cons(ret,y)~ys
-| _ => ret~False, Eraser~ys;
+| _ => ret~(*L)False, (*R)Eraser~ys;
 
 // The `Eraser' is a built-in agent defined for any agents as follows:
 //Eraser >< Alpha(a1, ..., a5) => Eraser~a1, ..., Eraser~a5;
diff --git a/comparison/Inpla/src/nqueen-12-reuse.in b/comparison/Inpla/src/nqueen-12-reuse.in
index 4e5a6b6..c7b06b8 100644
--- a/comparison/Inpla/src/nqueen-12-reuse.in
+++ b/comparison/Inpla/src/nqueen-12-reuse.in
@@ -20,7 +20,7 @@ member(r, list, int x) >< (int y):ys
 | x==y =>
         r~1, list~(*R)(y:ys)
 | _ =>
-        list~(*R)(y:cnt), member(r, cnt, x)~ys;
+        list~(*R)(y:cnt), (*L)member(r, cnt, x)~ys;
 
 
 /** 
@@ -35,13 +35,13 @@ len_list(len, done) >< [] =>
         len~0, done~(*R)[];
 len_list(len, done) >< x:xs => 
         done~(*R)(x:cnt), 
-        len_list_(len, cnt, 1)~xs;
+        (*L)len_list_(len, cnt, 1)~xs;
 
 len_list_(len, done, int ct) >< [] =>
         len~ct, done~(*R)[];
 len_list_(len, done, int ct) >< x:xs => 
         done~(*R)(x:cnt), 
-        len_list_(len, cnt, ct+1) ~ xs; 
+        (*L)len_list_(len, cnt, ct+1) ~ xs; 
 
 /** 
  * len (non-stream version)
@@ -53,7 +53,7 @@ len_list_(len, done, int ct) >< x:xs =>
 len(ret) >< [] =>
         ret~0;
 len(ret) >< x:xs =>
-        len_list(ret, Eraser)~(*R)(x:xs);
+        (*L)len_list(ret, Eraser)~(*R)(x:xs);
 
 
 
@@ -88,7 +88,7 @@ threat(r, done, int k, int q)><(int x):xs
 | (k == x-q) or (k == q-x) =>
         r~1, done~(*R)(x:xs)
 | _ =>
-        done~(*R)(x:cnt), threat(r, cnt, k+1, q)~xs;
+        done~(*R)(x:cnt), (*L)threat(r, cnt, k+1, q)~xs;
 
 
 
@@ -99,14 +99,14 @@ threat(r, done, int k, int q)><(int x):xs
 //         else (queen1 (m::b) n n) @ (queen1 b n (m-1));
 // fun queen n = queen1 n [] n;
 
-queen(ret) >< (int n) => queen_(ret, [], n)~n;
+queen(ret) >< (int n) => (*L)queen_(ret, [], n)~n;
 
 queen_(r, b, int n) >< (int m)
 | m==0 =>
-        r~[], (*L)Eraser~b
+        r~(*L)[], Eraser~b
 | _ =>
         mem_ret, done_b << member(m,b), 
-        queen__chk_m_in_b(r, done_b, n, m)~mem_ret;
+        (*L)queen__chk_m_in_b(r, done_b, n, m)~mem_ret;
 
 queen__chk_m_in_b(r, b, int n, int m) >< (int mem_ret)
 | mem_ret == 1 =>
diff --git a/src/config.h b/src/config.h
index ed6c624..cc8bb44 100644
--- a/src/config.h
+++ b/src/config.h
@@ -14,14 +14,14 @@
 // Heaps 
 // ------------------------------------------------
 // There are three methods for agents and names heaps:
-//   - Fixed-size ring buffers (default)
+//   - Fixed-size ring buffers
 //       The size is specified by an execution option -c
 //
 //   - Expandable ring buffers
 //       Automatically new buffers are inserted when all are run up.
 //
 //   - Ring buffers whose Initial size and newly inserted size
-//     are flexibly changed.
+//     are flexibly changed. (DEFAULT)
 //       The initial size and the expansion magnification are
 //       specified by execution options -Xms, -Xmt, respectively.
 //
diff --git a/src/inpla.y b/src/inpla.y
index c15640d..430c5cc 100644
--- a/src/inpla.y
+++ b/src/inpla.y
@@ -22,8 +22,8 @@
 
 // ----------------------------------------------
   
-#define VERSION "0.10.8-1"
-#define BUILT_DATE  "7 May 2023"
+#define VERSION "0.11.0"
+#define BUILT_DATE  "13 May 2023"
 
 // ------------------------------------------------------------------
 
@@ -942,7 +942,7 @@ typedef struct HoopList_tag {
 
 typedef struct Heap_tag {
   HoopList *last_alloc_list;
-  int last_alloc_idx;
+  unsigned int last_alloc_idx;
 } Heap;  
 
 
@@ -963,7 +963,7 @@ HoopList *HoopList_new_forName(unsigned int size) {
       printf("[HoopList->Hoop (name)]Malloc error\n");
       exit(-1);
   }  
-  for (int i=0; i<size; i++) {
+  for (unsigned int i=0; i<size; i++) {
     RESET_HOOPFLAG_READYFORUSE_NAME(((Name *)(hp_list->hoop))[i].basic.id);
   }
   hp_list->size = size;
@@ -999,7 +999,7 @@ HoopList *HoopList_new_forAgent(unsigned int size) {
       printf("[HoopList->Hoop]Malloc error\n");
       exit(-1);
   }
-  for (int i=0; i<size; i++) {
+  for (unsigned int i=0; i<size; i++) {
     RESET_HOOPFLAG_READYFORUSE_AGENT(((Agent *)(hp_list->hoop))[i].basic.id);
   }
   hp_list->size = size;
@@ -1032,7 +1032,7 @@ unsigned long Heap_GetNum_Usage_forAgent(Heap *hp) {
   do {
     
     hoop = (Agent *)(hoop_list->hoop);
-    for (int i = 0; i < hoop_list->size; i++) {
+    for (unsigned int i = 0; i < hoop_list->size; i++) {
       if (!IS_READYFORUSE(hoop[i].basic.id)) {
 	count++;
       }
@@ -1054,7 +1054,7 @@ unsigned long Heap_GetNum_Usage_forName(Heap *hp) {
   do {
     
     hoop = (Name *)(hoop_list->hoop);
-    for (int i = 0; i < hoop_list->size; i++) {
+    for (unsigned int i = 0; i < hoop_list->size; i++) {
       if (!IS_READYFORUSE(hoop[i].basic.id)) {
 	count++;
       }
@@ -1072,7 +1072,7 @@ unsigned long Heap_GetNum_Usage_forName(Heap *hp) {
 //static inline
 VALUE myalloc_Agent(Heap *hp) {
 
-  int idx;  
+  unsigned int idx;  
   HoopList *hoop_list;
   Agent *hoop;
   
@@ -1126,7 +1126,8 @@ VALUE myalloc_Agent(Heap *hp) {
 #endif
       
       HoopList *new_hoop_list;
-      unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude;
+      //unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude;
+      unsigned int new_size_p2 = (hp->last_alloc_list->size) * Hoop_increasing_magnitude;
       new_hoop_list = HoopList_new_forAgent(new_size_p2);
 
       HoopList *last_alloc = hoop_list->next;
@@ -1154,7 +1155,7 @@ VALUE myalloc_Agent(Heap *hp) {
 //static inline
 VALUE myalloc_Name(Heap *hp) {
 
-  int idx;
+  unsigned int idx;
   HoopList *hoop_list;
   Name *hoop;
 
@@ -1207,7 +1208,9 @@ VALUE myalloc_Name(Heap *hp) {
 #endif
       
       HoopList *new_hoop_list;
-      unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude;
+      //unsigned int new_size_p2 = hoop_list->size * Hoop_increasing_magnitude;
+      unsigned int new_size_p2 = (hp->last_alloc_list->size) * Hoop_increasing_magnitude;      
+
       new_hoop_list = HoopList_new_forName(new_size_p2);
 
       HoopList *last_alloc = hoop_list->next;
@@ -1867,6 +1870,14 @@ void VM_Buffer_Init(VirtualMachine * restrict vm) {
   vm->agentHeap.last_alloc_list->next = vm->agentHeap.last_alloc_list;
   vm->agentHeap.last_alloc_idx = 0;
   */
+
+  // Agent and Name heaps start from two hoops:
+  //     +-----------------------+
+  //     |    new        new     |
+  //     v    hoop       hoop    |
+  // init-->|......|-->|......|--+
+  //        last_alloc  next
+  //        idx=0
   
   vm->agentHeap.last_alloc_list = HoopList_new_forAgent(Hoop_init_size);
   vm->agentHeap.last_alloc_list->next = HoopList_new_forAgent(Hoop_init_size);