Re: [Caml-list] Gripes with array

[Jon Harrop <jon@jdh30.plus.com>]

On Saturday 11 September 2004 21:53, Damien Doligez wrote:
> ... Frankly,
> I find it hard to imagine that it would give a noticeable run-time
> improvement on any program.  Most likely, it would make them all a
> fraction
> of a percent slower, except for the most synthetic of benchmarks.

If it let you do extensible arrays safely then it could be used to reduce the 
asymptotic complexity of array append- or prepend-element from O(n) to 
amortized O(1) and "i"th insert from O(n) to amortized O(min{i, n-i}).

> > No, I don't think the performance improvement would justify your time
> > or the
> > loss of safety.
>
> No loss of safety if we don't export that primitive and use it only in
> Array.init.  After all, it only breaks type safety, and only if you use
> it wrong.

I was assuming that you would export it. My discrete wavelet transform (DWT) 
code, for example, is easily proven to fill all array elements but it fills 
them out of order (I've considered ways to make it fill in-order but they all 
incur significant performance penalties elsewhere, e.g. lots of swapping). So 
I was thinking of using unsafe_make for that. Still, I don't think it would 
be worth your writing it.

Having said that, it might be possible to abstract the array lookup and 
replace it with a clever function to work out where the "i"th element really 
is. Then you could give Array.init a continuation. Hmm...

> >  Could you add a memset to String.create though? :-)
>
> String.make

I meant for safety reasons - either don't export String.create or make it 
safe, e.g. "let create n = make n '\000'".

> > An array_init2 function which specialises the array type but uses an
> > external
> > "f" function betters the time taken by Array.init by ~36% (perhaps not
> > significantly different):
>
> That's from getting rid of the float/non-float test.  Nothing to do with
> the cost of initializing twice.

Yes. Optimising that would be much more productive. Am I right in thinking 
that ocamlopt doesn't hoist the test out of the loop?

Such optimisations would be best done at run-time, e.g. by Basile's JIT. Where 
is he? ;-)

Cheers,
Jon.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners