[m-rev.] for review: version array reimplementation
Peter Wang
novalazy at gmail.com
Mon Jul 27 17:09:13 AEST 2009
On 2009-07-27, Ralph Becket <rafe at csse.unimelb.edu.au> wrote:
> Peter Wang, Monday, 27 July 2009:
> >
> > I'm going to see if I can make ML_va_set handle this case more
> > gracefully and then compare mmc --make again.
>
> That would actually be very handy. One of the things that has put me
> off using version arrays more is the need to make copies every now and
> then. If this behaviour was automatic based on usage then that would
> make them much more attractive.
I made ML_va_set copy the array if it notices that it's not updating the
latest version of the array. This makes it faster than my representation
for mmc --make. Here are the times for mmc --make to figure out that
a particular program is up to date.
Old representation with fix:
6.31s user 13.50s system 106% cpu 18.655 total
6.38s user 13.39s system 106% cpu 18.634 total
6.59s user 13.33s system 106% cpu 18.635 total
New representation:
8.07s user 14.81s system 107% cpu 21.322 total
8.10s user 14.95s system 108% cpu 21.317 total
8.33s user 15.06s system 107% cpu 21.659 total
Branches: main
Make version_array.set make a new array if it's not updating the latest version
of an array. This avoids unexpected bad performance, where the version array
essentially turns into a linked list with an array at the end, if the user
happens to go back to an older version of an array without an explicit
rewind/copy.
library/version_array.m:
As above.
compiler/make.dependencies.m:
Use size doubling when resizing version arrays.
diff --git a/compiler/make.dependencies.m b/compiler/make.dependencies.m
index 6191138..d9f97d9 100644
--- a/compiler/make.dependencies.m
+++ b/compiler/make.dependencies.m
@@ -210,12 +210,22 @@ module_name_to_index(ModuleName, Index, !Info) :-
Map0 = module_index_map(Forward0, Reverse0, Size0),
Index = module_index(Size0),
Size = Size0 + 1,
- Forward = version_hash_table.det_insert(Forward0, ModuleName, Index),
- version_array.resize(Size, ModuleName, Reverse0, Reverse),
+ version_hash_table.det_insert(ModuleName, Index, Forward0, Forward),
+ TrueSize = version_array.size(Reverse0),
+ ( Size > TrueSize ->
+ NewSize = increase_array_size(TrueSize),
+ version_array.resize(NewSize, ModuleName, Reverse0, Reverse)
+ ;
+ version_array.set(Size0, ModuleName, Reverse0, Reverse)
+ ),
Map = module_index_map(Forward, Reverse, Size),
!Info ^ module_index_map := Map
).
+:- func increase_array_size(int) = int.
+
+increase_array_size(N) = (if N = 0 then 1 else N * 2).
+
:- pred module_index_to_name(make_info::in, module_index::in, module_name::out)
is det.
@@ -259,7 +269,13 @@ dependency_file_to_index(DepFile, Index, !Info) :-
Index = dependency_file_index(Size0),
Size = Size0 + 1,
version_hash_table.det_insert(DepFile, Index, Forward0, Forward),
- version_array.resize(Size, DepFile, Reverse0, Reverse),
+ TrueSize = version_array.size(Reverse0),
+ ( Size > TrueSize ->
+ NewSize = increase_array_size(TrueSize),
+ version_array.resize(NewSize, DepFile, Reverse0, Reverse)
+ ;
+ version_array.set(Size0, DepFile, Reverse0, Reverse)
+ ),
Map = dependency_file_index_map(Forward, Reverse, Size),
!Info ^ dep_file_index_map := Map
).
diff --git a/library/version_array.m b/library/version_array.m
index e2fc02f..e1cdf79 100644
--- a/library/version_array.m
+++ b/library/version_array.m
@@ -357,11 +357,14 @@ cmp_version_array_2(I, Size, VAa, VAb, R) :-
[will_not_call_mercury, promise_pure, will_not_modify_trail,
does_not_affect_liveness, may_not_duplicate],
"
+ ML_va_ptr latest;
MR_Integer i;
MR_Integer size_VA0;
MR_Integer min;
- size_VA0 = ML_va_size(VA0);
+ latest = ML_va_get_latest(VA0);
+
+ size_VA0 = ML_va_size(latest);
min = (N <= size_VA0 ? N : size_VA0);
VA = MR_GC_NEW(struct ML_va);
@@ -371,9 +374,11 @@ cmp_version_array_2(I, Size, VAa, VAb, R) :-
VA->rest.array->size = N;
for (i = 0; i < min; i++) {
- (void) ML_va_get(VA0, i, &VA->rest.array->elements[i]);
+ VA->rest.array->elements[i] = latest->rest.array->elements[i];
}
+ ML_va_rewind_into(VA, VA0);
+
for (i = min; i < N; i++) {
VA->rest.array->elements[i] = X;
}
@@ -439,6 +444,11 @@ struct ML_va {
};
/*
+ ** Returns a pointer to the latest version of the array.
+ */
+extern ML_va_ptr ML_va_get_latest(ML_va_ptr VA);
+
+ /*
** Returns the number of items in a version array.
*/
extern MR_Integer ML_va_size(ML_va_ptr);
@@ -458,6 +468,17 @@ extern int ML_va_get(ML_va_ptr, MR_Integer, MR_Word *);
extern int ML_va_set(ML_va_ptr, MR_Integer, MR_Word, ML_va_ptr *);
/*
+ ** Create a copy of VA0 as a new array.
+ */
+static ML_va_ptr ML_va_flat_copy(const ML_va_ptr VA0);
+
+ /*
+ ** Update the array VA using the override values in VA0
+ ** i.e. recreate the state of the version array as captured in VA0.
+ */
+static void ML_va_rewind_into(ML_va_ptr VA, const ML_va_ptr VA0);
+
+ /*
** `Rewinds' a version array, invalidating all extant successors
** including the argument.
*/
@@ -469,13 +490,21 @@ extern ML_va_ptr ML_va_rewind(ML_va_ptr);
#define ML_va_latest_version(VA) ((VA)->index == -1)
-MR_Integer
-ML_va_size(ML_va_ptr VA)
+ML_va_ptr
+ML_va_get_latest(ML_va_ptr VA)
{
while (!ML_va_latest_version(VA)) {
VA = VA->rest.next;
}
+ return VA;
+}
+
+MR_Integer
+ML_va_size(ML_va_ptr VA)
+{
+ VA = ML_va_get_latest(VA);
+
return VA->rest.array->size;
}
@@ -502,13 +531,14 @@ ML_va_get(ML_va_ptr VA, MR_Integer I, MR_Word *Xptr)
int
ML_va_set(ML_va_ptr VA0, MR_Integer I, MR_Word X, ML_va_ptr *VAptr)
{
- ML_va_ptr VA1 = MR_GC_NEW(struct ML_va);
+ ML_va_ptr VA1;
if (ML_va_latest_version(VA0)) {
if (I < 0 || I >= VA0->rest.array->size) {
return MR_FALSE;
}
+ VA1 = MR_GC_NEW(struct ML_va);
VA1->index = -1;
VA1->value = (MR_Word) NULL;
VA1->rest.array = VA0->rest.array;
@@ -519,19 +549,64 @@ ML_va_set(ML_va_ptr VA0, MR_Integer I, MR_Word X, ML_va_ptr *VAptr)
VA1->rest.array->elements[I] = X;
} else {
- if (I < 0 || I >= ML_va_size(VA0)) {
+ VA1 = ML_va_flat_copy(VA0);
+
+ if (I < 0 || I >= VA1->rest.array->size) {
return MR_FALSE;
}
- VA1->index = I;
- VA1->value = X;
- VA1->rest.next = VA0;
+ VA1->rest.array->elements[I] = X;
}
*VAptr = VA1;
return MR_TRUE;
}
+static ML_va_ptr
+ML_va_flat_copy(const ML_va_ptr VA0)
+{
+ ML_va_ptr latest;
+ ML_va_ptr VA;
+ MR_Integer N;
+ MR_Integer i;
+
+ latest = ML_va_get_latest(VA0);
+ N = latest->rest.array->size;
+
+ 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] = latest->rest.array->elements[i];
+ }
+
+ ML_va_rewind_into(VA, VA0);
+
+ return VA;
+}
+
+static void
+ML_va_rewind_into(ML_va_ptr VA, const ML_va_ptr VA0)
+{
+ MR_Integer I;
+ MR_Word X;
+
+ if (ML_va_latest_version(VA0)) {
+ return;
+ }
+
+ ML_va_rewind_into(VA, VA0->rest.next);
+
+ I = VA0->index;
+ X = VA0->value;
+ if (I < VA->rest.array->size) {
+ VA->rest.array->elements[I] = X;
+ }
+}
+
ML_va_ptr
ML_va_rewind(ML_va_ptr 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