[m-rev.] diff: implement concat_string_list for .NET

[Ralph Becket]

Michael Day, Monday, 17 February 2003:
> 
> > null-terminated strings. (In that case, you may have to scan a
> > string with an explicit length to search for nulls before the end of
> > the string, and even if that scan is negative, you may have to copy
> > the string to buffer that has room for the final null to be
> > inserted.)
> 
> Ouch, that's a nasty example of paying for stuff you don't use,
> considering that very few strings are going to be stuffed with nulls, and
> if they are then you won't have much luck passing them to C libraries or
> the operating system anyway.

There is a much more serious problem which is not related to the C/OS
interface.  Neither the Mercury compiler or GCC seems able to optimize
away redundant calls to string.length in a loop iterating over the chars
in a string.  This causes an O(n) algorithm to become O(n^2).

I've just written a small benchmark (see attached file a.m) which sums
the char codes over the length of a string, comparing the cost of
string.elem with string.unsafe_elem (clearly, using the former would be
preferable were it not so inefficient to do so.)

Using `mmc --make a -O5' I get the following times (obtained via
benchmark_func) on ceres (I got bored waiting for the `safe' results on
longer strings):

100 iterations over 2^13 char strings:
TSafe   =    17869 ms
TUnsafe =       10 ms

100 iterations over 2^12 char strings:
TSafe   =     4470 ms
TUnsafe =       10 ms

100 iterations over 2^11 char strings:
TSafe   =     1149 ms
TUnsafe =        0 ms

100 iterations over 2^10 char strings:
TSafe   =      305 ms
TUnsafe =        0 ms

100 iterations over 2^9 char strings:
TSafe   =       79 ms
TUnsafe =        0 ms

We can clearly see the O(n) --> O(n^2) effect.  The results are
unaffected if I turn on --transitive-intermodule-optimization.

So I'd argue there is either a problem with the optimizer or there is a
strong case for changing the representation of strings to support O(1)
calls to string.length.

	Ralph


p.s.  I get the following whinge from the compiler if I use -O6:

Making a.int3
Making a.opt
Making a.c
Making a.o
In file included from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/gc_inl.h:17,
                 from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/mercury.h:46,
                 from Mercury/mihs/a.mih:26,
                 from Mercury/cs/a.c:19:
/home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/private/gc_priv.h:57: warning: `TRUE' redefined
/home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/mercury_bootstrap.h:46: warning: this is the location of the previous definition
/home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/private/gc_priv.h:58: warning: `FALSE' redefined
/home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/mercury_bootstrap.h:49: warning: this is the location of the previous definition
In file included from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/private/gc_priv.h:70,
                 from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/gc_inl.h:17,
                 from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/mercury.h:47,
                 from Mercury/mihs/a.mih:26,
                 from Mercury/cs/a.c:19:
/home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/private/gcconfig.h:1978: warning: function declaration isn't a prototype
In file included from /home/ceres/public/mercury-latest/i686-pc-linux-gnu/lib/mercury/inc/gc_inl.h:17,
Making a

-------------- next part --------------
%-----------------------------------------------------------------------------%
% a.m
% Ralph Becket <rafe at cs.mu.oz.au>
% Tue Feb 18 10:03:54 EST 2003
% vim: ft=mercury ts=4 sw=4 et wm=0 tw=0
%
%-----------------------------------------------------------------------------%

:- module a.

:- interface.

:- import_module io.



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

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

:- implementation.

:- import_module std_util, string, char, int, list, benchmarking.

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

main(!IO) :-

    S = pow(func(S0) = S0 ++ S0, 13, "x"),
    N = 100,

    io.format("Starting (safe) elem benchmark...\n", [], !IO),
    benchmark_func(loop(S, safe),   0, _, N, TSafe  ),

    io.format("Starting unsafe_elem benchmark...\n", [], !IO),
    benchmark_func(loop(S, unsafe), 0, _, N, TUnsafe),

    io.format("TSafe   = %8d ms\nTUnsafe = %8d ms\n",
        [i(TSafe), i(TUnsafe)], !IO).

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

:- func loop(string, func(string, int, int, T) = T, T) = T.

loop(S, F, A) = F(S, 0, length(S), A).

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

:- func safe(string, int, int, int) = int.

safe(S, I, N, A) =
    ( if I < N then safe(S, I + 1, N, A + to_int(S ^ elem(I)))
               else A ).

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

:- func unsafe(string, int, int, int) = int.

unsafe(S, I, N, A) =
    ( if I < N then unsafe(S, I + 1, N, A + to_int(S ^ unsafe_elem(I)))
               else A ).

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