[mercury-users] version_array vs. field update performance

[Ralph Becket]

I've just run some tests on version arrays (see vatest.m attached) and I
get the following results which scale as I'd expect, rather than as you
report in your tests:

./vatest 1000 10 100
0 ms
./vatest 10000 10 100
4 ms
./vatest 100000 10 100
47 ms
./vatest 1000000 10 100
490 ms

./vatest 1000 100 100
0 ms
./vatest 10000 100 100
5 ms
./vatest 100000 100 100
47 ms
./vatest 1000000 100 100
490 ms

./vatest 1000 1000 100
0 ms
./vatest 10000 1000 100
5 ms
./vatest 100000 1000 100
47 ms
./vatest 1000000 1000 100
489 ms

Ondrej Bojar, Wednesday,  7 February 2007:
> :- pred varr(int::in,
>            version_array(float)::in,
>            version_array(float)::out) is det.
> varr(Iters, V, OutV) :-
>   fold_up(
>     (pred(I::in, IV::in, OV::out) is det :-
>       Pos = I mod 8,
>       PrePos = (-I) mod 8,
>       OV = IV^elem(Pos) := IV^elem(PrePos)+1.0
>     ), 0, Iters, V, OutV).
> % dummily increase value from a field and put it to a different
> % field, repeat Iters times.

My guess is that you are not calling varr with a new version array each
time, but rather are reusing the same one on different iterations.  That
would explain the quadratic behaviour you observed.

-- Ralph
-------------- next part --------------
%-----------------------------------------------------------------------------%
% vatest.m
% Ralph Becket <rafe at csse.unimelb.edu.au>
% Wed Feb  7 12:26:04 EST 2007
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
% Test "latest version" performance of version arrays, in response to
% what appears to be a performance bug reported by Ondrej Bojar.
%
%-----------------------------------------------------------------------------%

:- module vatest.

:- interface.

:- import_module io.



:- pred main(io :: di, io :: uo) is cc_multi.

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%

:- implementation.

:- import_module benchmarking, int, list, string, version_array.

%-----------------------------------------------------------------------------%

main(!IO) :-
    io.command_line_arguments(Args, !IO),
    ( if
        Args = [CountStr, ArraySizeStr, RepeatsStr],
        string.to_int(CountStr, Count),
        string.to_int(ArraySizeStr, ArraySize),
        string.to_int(RepeatsStr, Repeats)
      then
        benchmarking.benchmark_det(run_test(Count), ArraySize, _, Repeats,
            TotalTime),
        io.format("%d ms\n", [i(TotalTime / Repeats)], !IO)
      else
        io.format("usage: vatest loop_count array_size num_repeats\n", [],
            !IO),
        io.set_exit_status(1, !IO)
    ).

%-----------------------------------------------------------------------------%

:- pred run_test(int::in, int::in, version_array(int)::out) is det.

run_test(N, ArraySize, VersionArray) :-
    VersionArray0 = version_array.new(ArraySize, 0),
    run_test_2(N, ArraySize, VersionArray0, VersionArray).


:- pred run_test_2(int::in, int::in,
        version_array(int)::in, version_array(int)::out) is det.

run_test_2(N, ArraySize, !VersionArray) :-
    ( if N =< 0 then
        true
      else
        !:VersionArray =
            !.VersionArray ^ elem(N mod ArraySize) :=
                !.VersionArray ^ elem(-N mod ArraySize) + 1,
        run_test_2(N - 1, ArraySize, !VersionArray)
    ).

%-----------------------------------------------------------------------------%
%-----------------------------------------------------------------------------%