[m-rev.] for review: threadsafe version_arrays in Java
Peter Ross
pro at missioncriticalit.com
Wed Apr 14 16:22:15 AEST 2010
Hi,
Peter Wang is probably the best person to review this.
Ralph might want to make version_arrays thread safe on the C backend,
however at least now the user will get an error when they try and use
the non-safe version_array in a context where it might have to support
concurrent access.
===================================================================
Estimated hours taken: 12
Branches: main, 10.04
Make the version_array(T) type thread safe in the Java grade.
Abort the program if the user attempts to use a non thread safe version_array
when threading is available on the C backends.
Supply a unsafe version_array initialization functions so that users can use
version_arrays on grades supporting threading with the proviso that they don't
concurrently access the version_array.
The synchronized version dramatically slows down version_array.lookup (100x slower).
However the test case MC uses which is to replace a map being used as a memo table
with a version_hash_table for the memo_table it is still approximately 40% faster
than the map even with the synchronization overhead.
library/version_array.m:
Make ML_va be an interface.
Provide two implementations of the ML_va interface: ML_uva (formerly
ML_va) which provides an unsynchronized version_array, and ML_sva which
provides a synchronized version_array.
ML_sva just wraps a ML_uva but locks itself so that only one thread can
access the version array at a time, making the ML_uva safe.
Add to ML_uva the method isClone() so that the ML_sva knows when the
underlying array has been cloned, so then we can use a different lock
object as we are protecting access to a different underlying array.
Index: library/version_array.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/version_array.m,v
retrieving revision 1.21
diff -u -r1.21 version_array.m
--- library/version_array.m 5 Aug 2009 07:34:12 -0000 1.21
+++ library/version_array.m 14 Apr 2010 05:58:14 -0000
@@ -51,6 +51,22 @@
%
:- func init(int, T) = version_array(T).
+ % Same as empty/0 except the resulting version_array is not thread safe.
+ %
+ % That is your program can segfault if you attempt to concurrently access
+ % the version_array, however this version is much quicker if you guarantee
+ % that you never concurrently access the version_array.
+ %
+:- func unsafe_empty = version_array(T).
+
+ % Same as new(N, X) except the resulting version_array is not thread safe.
+ %
+ % That is your program can segfault if you attempt to concurrently access
+ % the version_array, however this version is much quicker if you guarantee
+ % that you never concurrently access the version_array.
+ %
+:- func unsafe_new(int, T) = version_array(T).
+
% version_array(Xs) returns an array constructed from the items in the list
% Xs.
%
@@ -332,12 +348,20 @@
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness],
"
+#ifdef MR_THREAD_SAFE
+ MR_fatal_error(""thread safe version_array not yet implemented"");
+#else
+ /*
+ ** If we are not in an environment which uses threads
+ ** then it is safe to use the unsynchronized version_array.
+ */
VA = MR_GC_NEW(struct ML_va);
VA->index = -1;
VA->value = (MR_Word) NULL;
VA->rest.array = (MR_ArrayPtr) MR_GC_NEW_ARRAY(MR_Word, 1);
VA->rest.array->size = 0;
+#endif
").
:- pragma foreign_proc("Java",
@@ -345,11 +369,28 @@
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness],
"
- VA = new version_array.ML_va();
+ VA = new ML_sva(ML_uva.empty());
+").
- VA.index = -1;
- VA.value = null;
- VA.rest = new Object[0];
+:- pragma foreign_proc("C",
+ version_array.unsafe_empty = (VA::out),
+ [will_not_call_mercury, promise_pure, will_not_modify_trail,
+ does_not_affect_liveness],
+"
+ VA = MR_GC_NEW(struct ML_va);
+
+ VA->index = -1;
+ VA->value = (MR_Word) NULL;
+ VA->rest.array = (MR_ArrayPtr) MR_GC_NEW_ARRAY(MR_Word, 1);
+ VA->rest.array->size = 0;
+").
+
+:- pragma foreign_proc("Java",
+ version_array.unsafe_empty = (VA::out),
+ [will_not_call_mercury, promise_pure, will_not_modify_trail,
+ does_not_affect_liveness],
+"
+ VA = ML_uva.empty();
").
:- pragma foreign_proc("C",
@@ -357,6 +398,9 @@
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness, may_not_duplicate],
"
+#ifdef MR_THREAD_SAFE
+ MR_fatal_error(""thread safe version_array not yet implemented"");
+#else
MR_Integer i;
VA = MR_GC_NEW(struct ML_va);
@@ -368,6 +412,7 @@
for (i = 0; i < N; i++) {
VA->rest.array->elements[i] = X;
}
+#endif
").
:- pragma foreign_proc("Java",
@@ -375,12 +420,33 @@
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness, may_not_duplicate],
"
- VA = new version_array.ML_va();
- VA.index = -1;
- VA.value = null;
- VA.rest = new Object[N];
+ VA = new ML_sva(ML_uva.init(N, X));
+").
+
+:- pragma foreign_proc("C",
+ version_array.unsafe_new(N::in, X::in) = (VA::out),
+ [will_not_call_mercury, promise_pure, will_not_modify_trail,
+ does_not_affect_liveness, may_not_duplicate],
+"
+ MR_Integer i;
- java.util.Arrays.fill(VA.array(), X);
+ VA = MR_GC_NEW(struct ML_va);
+ VA->index = -1;
+ VA->value = (MR_Word) NULL;
+ VA->rest.array = (MR_ArrayPtr) MR_GC_NEW_ARRAY(MR_Word, N + 1);
+ VA->rest.array->size = N;
+
+ for (i = 0; i < N; i++) {
+ VA->rest.array->elements[i] = X;
+ }
+").
+
+:- pragma foreign_proc("Java",
+ version_array.unsafe_new(N::in, X::in) = (VA::out),
+ [will_not_call_mercury, promise_pure, will_not_modify_trail,
+ does_not_affect_liveness, may_not_duplicate],
+"
+ VA = ML_uva.init(N, X);
").
:- pragma foreign_proc("C",
@@ -420,25 +486,7 @@
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness, may_not_duplicate],
"
- ML_va latest;
- int size_VA0;
- int min;
-
- latest = VA0.latest();
-
- size_VA0 = latest.size();
- VA = new ML_va();
-
- VA.index = -1;
- VA.value = null;
- VA.rest = new Object[N];
-
- System.arraycopy(latest.array(), 0, VA.array(), 0, min);
-
- VA0.rewind_into(VA);
-
- java.util.Arrays.fill(VA.array(), min, N, X);
+ VA = VA0.resize(N, X);
").
resize(N, X, VA, resize(VA, N, X)).
@@ -730,45 +778,167 @@
:- pragma foreign_code("Java", "
-static class ML_va {
- int index; /* -1 for latest, >= 0 for older */
- Object value; /* Valid if index >= 0 */
- Object rest; /* array if index == -1 */
- /* next if index >= 0 */
+public interface ML_va {
+ public Object get(int I) throws ArrayIndexOutOfBoundsException;
+ public ML_va set(int I, Object X);
+ public ML_va resize(int N, Object X);
+ public ML_va rewind();
+ public int size();
+}
+
+// An implementation of version arrays that is safe when used in multiple
+// threads.
+//
+// It just wraps the unsafe version is some synchronization logic so
+// that only one thread can be accessing the array at one instant.
+public static class ML_sva implements ML_va {
+ private ML_uva version_array;
+ private Object lock;
+
+ public ML_sva(ML_uva va) {
+ version_array = va;
+ lock = new Object();
+ }
+
+ private ML_sva() {};
+
+ public Object get(int I) throws ArrayIndexOutOfBoundsException {
+ synchronized (lock) {
+ return version_array.get(I);
+ }
+ }
+
+ public ML_sva set(int I, Object X) {
+ synchronized (lock) {
+ ML_sva result = new ML_sva();
+
+ result.version_array = version_array.set(I, X);
+
+ if (result.version_array.isClone()) {
+ result.version_array.resetIsClone();
+ result.lock = new Object();
+ } else {
+ result.lock = this.lock;
+ }
+
+ return result;
+ }
+ }
+
+ public ML_sva resize(int N, Object X) {
+ synchronized (lock) {
+ ML_sva result = new ML_sva();
+ result.version_array = version_array.resize(N, X);
+ result.lock = new Object();
+ return result;
+ }
+ }
+
+ public ML_sva rewind()
+ {
+ synchronized (lock) {
+ ML_sva result = new ML_sva();
+ result.version_array = version_array.rewind();
+ result.lock = this.lock;
+ return result;
+ }
+ }
+
+ public int size()
+ {
+ synchronized (lock) {
+ return version_array.size();
+ }
+ }
+}
+
+// An implementation of version arrays that is only safe when used from
+// a single thread, but *much* faster than the synchronized version.
+public static class ML_uva implements ML_va {
+ private int index; /* -1 for latest, >= 0 for older */
+ private Object value; /* Valid if index >= 0 */
+ private Object rest; /* array if index == -1 */
+ /* next if index >= 0 */
+
+ private boolean clone = false;
+
+ public ML_uva() {}
+
+ public static ML_uva empty() {
+ ML_uva va = new ML_uva();
+ va.index = -1;
+ va.value = null;
+ va.rest = new Object[0];
+ return va;
+
+ }
+
+ public static ML_uva init(int N, Object X) {
+ ML_uva va = new ML_uva();
+ va.index = -1;
+ va.value = null;
+ va.rest = new Object[N];
+ java.util.Arrays.fill(va.array(), X);
+ return va;
+ }
+
+ public ML_uva resize(int N, Object X) {
+ ML_uva VA0 = this;
+ ML_uva latest;
+ int size_VA0;
+ int min;
+
+ latest = VA0.latest();
+
+ size_VA0 = latest.size();
+ ML_uva VA = new ML_uva();
+
+ VA.index = -1;
+ VA.value = null;
+ VA.rest = new Object[N];
- boolean is_latest()
+ System.arraycopy(latest.array(), 0, VA.array(), 0, min);
+
+ VA0.rewind_into(VA);
+
+ java.util.Arrays.fill(VA.array(), min, N, X);
+ return VA;
+ }
+
+ private boolean is_latest()
{
return index == -1;
}
- ML_va latest()
+ private ML_uva latest()
{
- ML_va VA = this;
+ ML_uva VA = this;
while (!VA.is_latest()) {
VA = VA.next();
}
return VA;
}
- Object[] array()
+ private Object[] array()
{
return (Object[]) rest;
}
- ML_va next()
+ private ML_uva next()
{
- return (ML_va) rest;
+ return (ML_uva) rest;
}
- int size()
+ public int size()
{
return latest().array().length;
}
- Object get(int I)
+ public Object get(int I)
throws ArrayIndexOutOfBoundsException
{
- ML_va VA = this;
+ ML_uva VA = this;
while (!VA.is_latest()) {
if (I == VA.index) {
@@ -781,13 +951,13 @@
return VA.array()[I];
}
- ML_va set(int I, Object X)
+ public ML_uva set(int I, Object X)
{
- ML_va VA0 = this;
- ML_va VA1;
+ ML_uva VA0 = this;
+ ML_uva VA1;
if (VA0.is_latest()) {
- VA1 = new ML_va();
+ VA1 = new ML_uva();
VA1.index = -1;
VA1.value = null;
VA1.rest = VA0.array();
@@ -806,27 +976,36 @@
return VA1;
}
- ML_va flat_copy()
+ private ML_uva flat_copy()
{
- ML_va VA0 = this;
- ML_va latest;
- ML_va VA;
+ ML_uva VA0 = this;
+ ML_uva latest;
+ ML_uva VA;
int N;
latest = VA0.latest();
N = latest.size();
- VA = new ML_va();
+ VA = new ML_uva();
VA.index = -1;
VA.value = null;
VA.rest = latest.array().clone();
+ VA.clone = true;
VA0.rewind_into(VA);
return VA;
}
- void rewind_into(ML_va VA)
+ public boolean isClone() {
+ return clone;
+ }
+
+ public void resetIsClone() {
+ this.clone = false;
+ }
+
+ private void rewind_into(ML_uva VA)
{
int I;
Object X;
@@ -844,9 +1023,9 @@
}
}
- ML_va rewind()
+ public ML_uva rewind()
{
- ML_va VA = this;
+ ML_uva VA = this;
int I;
Object X;
@@ -862,6 +1041,7 @@
return VA;
}
}
+
").
%-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to: mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions: mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------
More information about the reviews
mailing list