[m-rev.] for review: Make version_array's rewind code use constant stack space.
Paul Bone
paul at bone.id.au
Thu Apr 10 18:08:01 AEST 2014
For review by anyone, especially someone who knows C#. I have tested the C#
version and didn't find a problem but I don't actually know C#. Thanks.
Branches: version-14.01-branch, master
---
Make version_array's rewind code use constant stack space.
Although rewinding version arrays should be rare it is better if this code
uses constant stack space to avoid crashes. Currently the list of updates
made in a version array is kept in a singly linked list. This list needs to
be walked backwards to unwind updates, such as when updating an old version
of an array (to fork into two separate arrays). The stack is used to
perform this backwards work and can overflow for long histories.
This patch makes these lists doubly-linked so that they can be traversed in
either direction. I'm willing to bet that this unwind code is also faster.
library/version_array.m:
As above; I developed this algorithm in the C implementation first and
then replicated the changes in the Java and C# implementations.
tests/hard_coded/version_array_test.m:
tests/hard_coded/version_array_test.exp:
Extend the test case to exercise implicitly unwinding a version array by
updating an old version of an array. Note that the implicit and
explicit unwind codepaths are different as they are out-of-place and
in-place respectively.
---
library/version_array.m | 271 +++++++++++++++++++++++++++-----
tests/hard_coded/version_array_test.exp | 1 +
tests/hard_coded/version_array_test.m | 16 +-
3 files changed, 246 insertions(+), 42 deletions(-)
diff --git a/library/version_array.m b/library/version_array.m
index 4208206..ea097e2 100644
--- a/library/version_array.m
+++ b/library/version_array.m
@@ -922,6 +922,7 @@ struct ML_va {
MR_ArrayPtr array; /* Valid if index == -1 */
ML_va_ptr next; /* Valid if index >= 0 */
} rest;
+ ML_va_ptr prev; /* NULL if this is the oldest update */
#ifdef MR_THREAD_SAFE
MercuryLock *lock; /* NULL or lock */
#endif
@@ -1154,6 +1155,7 @@ ML_va_set(ML_va_ptr VA0, MR_Integer I, MR_Word X, ML_va_ptr *VAptr,
VA1->index = -1;
VA1->value = (MR_Word) NULL;
VA1->rest.array = VA0->rest.array;
+ VA1->prev = VA0;
#ifdef MR_THREAD_SAFE
VA1->lock = VA0->lock;
#endif
@@ -1194,10 +1196,11 @@ ML_va_flat_copy(ML_const_va_ptr VA0, MR_AllocSiteInfoPtr alloc_id)
MR_incr_hp_msg(array, N + 1,
alloc_id, ""version_array.version_array/1"");
- VA->index = -1;
- VA->value = (MR_Word) NULL;
- VA->rest.array = (MR_ArrayPtr) array;
- VA->rest.array->size = N;
+ VA->index = -1;
+ VA->value = (MR_Word) NULL;
+ VA->rest.array = (MR_ArrayPtr) array;
+ VA->rest.array->size = N;
+ VA->prev = NULL;
for (i = 0; i < N; i++) {
VA->rest.array->elements[i] = latest->rest.array->elements[i];
@@ -1218,22 +1221,40 @@ ML_va_flat_copy(ML_const_va_ptr VA0, MR_AllocSiteInfoPtr alloc_id)
}
static void
-ML_va_rewind_into(ML_va_ptr VA, ML_const_va_ptr VA0)
+ML_va_rewind_into(ML_va_ptr VA_dest, ML_const_va_ptr VA_src)
{
- MR_Integer I;
- MR_Word X;
+ MR_Integer I;
+ MR_Word X;
+ ML_va_ptr cur;
- if (ML_va_latest_version(VA0)) {
+ if (ML_va_latest_version(VA_src)) {
+ /* Shortcut */
return;
}
- ML_va_rewind_into(VA, VA0->rest.next);
+ /*
+ ** Copy elements in the reverse order that they were updated into the
+ ** latest array, then return the latest array.
+ */
+ cur = ML_va_get_latest(VA_src);
+ cur = cur->prev; /* start from first 'update' record */
+ while (cur != VA_src) {
+ I = cur->index;
+ X = cur->value;
+ if (I < VA_dest->rest.array->size) {
+ VA_dest->rest.array->elements[I] = X;
+ }
- I = VA0->index;
- X = VA0->value;
- if (I < VA->rest.array->size) {
- VA->rest.array->elements[I] = X;
+ cur = cur->prev;
}
+
+ /*
+ * This loop must be inclusive of the update in VA.
+ */
+ I = cur->index;
+ X = cur->value;
+
+ VA_dest->rest.array->elements[I] = X;
}
ML_va_ptr
@@ -1254,18 +1275,59 @@ ML_va_rewind_dolock(ML_va_ptr VA)
static ML_va_ptr
ML_va_rewind(ML_va_ptr VA)
{
- MR_Integer I;
- MR_Word X;
+ MR_Integer I;
+ MR_Word X;
+ ML_va_ptr cur;
+ ML_va_ptr last_visited;
if (ML_va_latest_version(VA)) {
+ /* Shortcut */
return VA;
}
- I = VA->index;
- X = VA->value;
- VA = ML_va_rewind(VA->rest.next);
+ /*
+ ** last_visited is the last element we interated through, we remember it
+ ** because we update it's prev pointer after the loop. This isn't
+ ** strictly required as we're already destroying that list.
+ */
+ last_visited = NULL;
+
+ /*
+ ** Copy elements in the reverse order that they were updated into the
+ ** latest array, then return the latest array.
+ */
+ cur = ML_va_get_latest(VA);
+ VA->rest.array = cur->rest.array;
+ cur = cur->prev; /* start from first 'update' record */
+ while (cur != VA) {
+ I = cur->index;
+ X = cur->value;
+
+ VA->rest.array->elements[I] = X;
+
+ last_visited = cur;
+ cur = cur->prev;
+ }
+ /*
+ * This loop must be inclusive of the update in VA.
+ */
+ I = cur->index;
+ X = cur->value;
+
VA->rest.array->elements[I] = X;
+ /*
+ * Clear the prev pointer since we've broken the chain.
+ */
+ if (NULL != last_visited) {
+ last_visited->prev = NULL;
+ }
+
+ /*
+ * This element is no-longer an update element.
+ */
+ VA->index = -1;
+ VA->value = 0;
return VA;
}
@@ -1307,10 +1369,11 @@ ML_va_resize(ML_va_ptr VA0, MR_Integer N, MR_Word X,
MR_incr_hp_msg(array, N + 1,
alloc_id, ""version_array.version_array/1"");
- VA->index = -1;
- VA->value = (MR_Word) NULL;
- VA->rest.array = (MR_ArrayPtr) array;
- VA->rest.array->size = N;
+ VA->index = -1;
+ VA->value = (MR_Word) NULL;
+ VA->rest.array = (MR_ArrayPtr) array;
+ VA->rest.array->size = N;
+ VA->prev = NULL;
for (i = 0; i < min; i++) {
VA->rest.array->elements[i] = latest->rest.array->elements[i];
@@ -1421,7 +1484,9 @@ public class ML_uva : ML_va {
private object value; /* Valid if index >= 0 */
private object rest; /* array if index == -1 */
/* next if index >= 0 */
+ private ML_uva prev; /* previous array update */
+ /* True if this is a fresh clone of another ML_uva */
private bool clone = false;
public ML_uva() {}
@@ -1431,6 +1496,7 @@ public class ML_uva : ML_va {
va.index = -1;
va.value = null;
va.rest = new object[0];
+ va.prev = null;
return va;
}
@@ -1439,6 +1505,7 @@ public class ML_uva : ML_va {
va.index = -1;
va.value = null;
va.rest = new object[N];
+ va.prev = null;
for (int i = 0; i < N; i++) {
va.array()[i] = X;
}
@@ -1464,6 +1531,7 @@ public class ML_uva : ML_va {
VA.index = -1;
VA.value = null;
VA.rest = new object[N];
+ VA.prev = null;
System.Array.Copy(latest.array(), 0, VA.array(), 0, min);
@@ -1534,6 +1602,7 @@ public class ML_uva : ML_va {
VA1.index = -1;
VA1.value = null;
VA1.rest = VA0.array();
+ VA1.prev = VA0;
VA0.index = I;
VA0.value = VA0.array()[I];
@@ -1562,6 +1631,7 @@ public class ML_uva : ML_va {
VA.value = null;
VA.rest = latest.array().Clone();
VA.clone = true;
+ VA.prev = null;
VA0.rewind_into(VA);
@@ -1580,18 +1650,36 @@ public class ML_uva : ML_va {
{
int I;
object X;
+ ML_uva cur;
if (this.is_latest()) {
+ /* Shortcut */
return;
}
- this.next().rewind_into(VA);
+ /*
+ ** Copy elements in the reverse order that they were updated into the
+ ** latest array, then return the latest array.
+ */
+ cur = this.latest();
+ cur = cur.prev; /* start from first 'update' record */
+ while (cur != this) {
+ I = cur.index;
+ X = cur.value;
+ if (I < VA.size()) {
+ VA.array()[I] = X;
+ }
- I = this.index;
- X = this.value;
- if (I < VA.size()) {
- VA.array()[I] = X;
+ cur = cur.prev;
}
+
+ /*
+ * This loop must be inclusive of the update in VA.
+ */
+ I = cur.index;
+ X = cur.value;
+
+ VA.array()[I] = X;
}
public ML_va rewind()
@@ -1601,19 +1689,59 @@ public class ML_uva : ML_va {
public ML_uva rewind_uva()
{
- ML_uva VA = this;
int I;
object X;
+ ML_uva VA = this;
+ ML_uva cur;
+ ML_uva last_visited;
if (VA.is_latest()) {
return VA;
}
- I = VA.index;
- X = VA.value;
- VA = VA.next().rewind_uva();
+ /*
+ ** last_visited is the last element we interated through, we
+ ** remember it because we update it's prev pointer after the
+ ** loop.
+ */
+ last_visited = null;
+
+ /*
+ ** Copy elements in the reverse order that they were updated into
+ ** the latest array, then return the latest array.
+ */
+ cur = VA.latest();
+ VA.rest = cur.array();
+ cur = cur.prev; /* start from first 'update' record */
+ while (cur != VA) {
+ I = cur.index;
+ X = cur.value;
+
+ VA.array()[I] = X;
+
+ last_visited = cur;
+ cur = cur.prev;
+ }
+ /*
+ ** This loop must be inclusive of the update in VA.
+ */
+ I = cur.index;
+ X = cur.value;
+
VA.array()[I] = X;
+ /*
+ ** Clear the prev pointer since we've broken the chain.
+ */
+ if (null != last_visited) {
+ last_visited.prev = null;
+ }
+
+ /*
+ ** This element is no-longer an update element.
+ */
+ VA.index = -1;
+ VA.value = 0;
return VA;
}
}
@@ -1707,6 +1835,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
private Object value; /* Valid if index >= 0 */
private Object rest; /* array if index == -1 */
/* next if index >= 0 */
+ private ML_uva prev; /* previous array update */
private boolean clone = false;
@@ -1717,6 +1846,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
va.index = -1;
va.value = null;
va.rest = new Object[0];
+ va.prev = null;
return va;
}
@@ -1725,6 +1855,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
va.index = -1;
va.value = null;
va.rest = new Object[N];
+ va.prev = null;
java.util.Arrays.fill(va.array(), X);
return va;
}
@@ -1744,6 +1875,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA.index = -1;
VA.value = null;
VA.rest = new Object[N];
+ VA.prev = null;
System.arraycopy(latest.array(), 0, VA.array(), 0, min);
@@ -1808,6 +1940,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA1.index = -1;
VA1.value = null;
VA1.rest = VA0.array();
+ VA1.prev = VA0;
VA0.index = I;
VA0.value = VA0.array()[I];
@@ -1835,6 +1968,7 @@ public static class ML_uva implements ML_va, java.io.Serializable {
VA.index = -1;
VA.value = null;
VA.rest = latest.array().clone();
+ VA.prev = null;
VA.clone = true;
VA0.rewind_into(VA);
@@ -1854,35 +1988,92 @@ public static class ML_uva implements ML_va, java.io.Serializable {
{
int I;
Object X;
+ ML_uva cur;
if (this.is_latest()) {
return;
}
- this.next().rewind_into(VA);
+ /*
+ ** Copy elements in the reverse order that they were updated into the
+ ** latest array, then return the latest array.
+ */
+ cur = latest();
+ cur = cur.prev; /* start from first 'update' record */
+ while (cur != this) {
+ I = cur.index;
+ X = cur.value;
+ if (I < VA.size()) {
+ VA.array()[I] = X;
+ }
- I = this.index;
- X = this.value;
- if (I < VA.size()) {
- VA.array()[I] = X;
+ cur = cur.prev;
}
+
+ /*
+ * This loop must be inclusive of the update in VA.
+ */
+ I = cur.index;
+ X = cur.value;
+
+ VA.array()[I] = X;
}
public ML_uva rewind()
{
- ML_uva VA = this;
+ ML_uva VA = this;
int I;
Object X;
+ ML_uva cur;
+ ML_uva last_visited;
if (VA.is_latest()) {
return VA;
}
- I = VA.index;
- X = VA.value;
- VA = VA.next().rewind();
+ /*
+ ** last_visited is the last element we interated through, we remember it
+ ** because we update it's prev pointer after the loop. This isn't
+ ** strictly required as we're already destroying that list.
+ */
+ last_visited = null;
+
+ /*
+ ** Copy elements in the reverse order that they were updated into the
+ ** latest array, then return the latest array.
+ */
+ cur = VA.latest();
+ VA.rest = cur.array();
+ cur = cur.prev; /* start from first 'update' record */
+ while (cur != VA) {
+ I = cur.index;
+ X = cur.value;
+
+ VA.array()[I] = X;
+
+ last_visited = cur;
+ cur = cur.prev;
+ }
+ /*
+ * This loop must be inclusive of the update in VA.
+ */
+ I = cur.index;
+ X = cur.value;
+
VA.array()[I] = X;
+ /*
+ * Clear the prev pointer since we've broken the chain.
+ */
+ if (null != last_visited) {
+ last_visited.prev = null;
+ }
+
+ /*
+ * This element is no-longer an update element.
+ */
+ VA.index = -1;
+ VA.value = 0;
return VA;
}
}
diff --git a/tests/hard_coded/version_array_test.exp b/tests/hard_coded/version_array_test.exp
index 00ca036..2a7172d 100644
--- a/tests/hard_coded/version_array_test.exp
+++ b/tests/hard_coded/version_array_test.exp
@@ -5,6 +5,7 @@ ordering(A2, A1) = '>'
(size 0)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (size 10)
9, 8, 7, 6, 5, 4, 3, 2, 1, 0 (size 10)
+0, 1, 6, 3, 12, 5, 18, 7, 24, 9 (size 10)
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 (size 10)
7, 7, 7, 7, 7, 7, 7 (size 7)
(sum 49)
diff --git a/tests/hard_coded/version_array_test.m b/tests/hard_coded/version_array_test.m
index 30c2d23..d45c324 100644
--- a/tests/hard_coded/version_array_test.m
+++ b/tests/hard_coded/version_array_test.m
@@ -12,8 +12,6 @@
:- import_module io.
-
-
:- pred main(io :: di, io :: uo) is cc_multi.
%-----------------------------------------------------------------------------%
@@ -29,6 +27,8 @@ main(!IO) :-
A0 = version_array.empty,
A1 = version_array(0`..`9),
A2 = int.fold_up(func(I, A) = ( A ^ elem(I) := 9 - I ), 0, 9, A1),
+ % A21 forces an implicit rollback:
+ A21 = int.fold_up(make_a21, 0, 9, A1),
io.write_string("ordering(A1, A0) = ", !IO),
io.write(ordering(A1, A0), !IO),
io.nl(!IO),
@@ -47,6 +47,8 @@ main(!IO) :-
io.format(" (size %d)\n", [i(size(A1))], !IO),
io.write_list(to_list(A2), ", ", io.write_int, !IO),
io.format(" (size %d)\n", [i(size(A2))], !IO),
+ io.write_list(to_list(A21), ", ", io.write_int, !IO),
+ io.format(" (size %d)\n", [i(size(A21))], !IO),
A3 = unsafe_rewind(A1),
io.write_list(to_list(A3), ", ", io.write_int, !IO),
io.format(" (size %d)\n", [i(size(A3))], !IO),
@@ -146,5 +148,15 @@ test_exception(Pred, !IO) :-
io.nl(!IO)
).
+:- func make_a21(int, version_array(int)) = version_array(int).
+
+make_a21(I, A0) = A :-
+ X = A0 ^ elem(I),
+ ( X `mod` 2 = 0 ->
+ A = A0 ^ elem(I) := X * 3
+ ;
+ A = A0
+ ).
+
%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%
--
1.9.1
More information about the reviews
mailing list