[NEWBIE] is there an in-place map?

[NEWBIE] is there an in-place map?

[Kuba Ober]

I need functionality of map, but done in such a way that the output array
is given as the argument, not as a return value. The closest I could get was

let inplace_map f a b = Array.blit (map f a) 0 b 0 (Array.length a)

Arrays a and b are of the same size.
This seems very inelegant.

One could use an adapter function and iteri, but that adds very noticeable 
overhead, and doesn't seem too elegant either.

let inplace_map f a b = Array.iteri (fun i src -> b.(i) <- f src; ()) a

There must be a better way of doing it, right? The given here is that the 
arrays a and b are there to stay, so we have to use them in-place.

Cheers, Kuba

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Jean-Christophe Filliâtre]

Kuba Ober a écrit :
> I need functionality of map, but done in such a way that the output array
> is given as the argument, not as a return value. The closest I could get was
> 
> let inplace_map f a b = Array.blit (map f a) 0 b 0 (Array.length a)
> 
> Arrays a and b are of the same size.
> This seems very inelegant.

I guess you mean Array.map. Indeed, this is not optimal because
Array.map allocates a new array, whose contents is immediately copied
into b.

> One could use an adapter function and iteri, but that adds very noticeable 
> overhead, and doesn't seem too elegant either.
> 
> let inplace_map f a b = Array.iteri (fun i src -> b.(i) <- f src; ()) a

You may find this inelegant too, but it is clearly more efficient than
your previous version using map. Note that "; ()" can be omitted, since
the assignment <- already has type unit.

Equivalently, you could use a for loop instead of Array.iteri.

-- 
Jean-Christophe Filliâtre
http://www.lri.fr/~filliatr/

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Brian Hurt]

[-- Attachment #1: Type: text/plain, Size: 1345 bytes --]

Jean-Christophe Filliâtre wrote:

>Kuba Ober a écrit :
>  
>
>>I need functionality of map, but done in such a way that the output array
>>is given as the argument, not as a return value. The closest I could get was
>>
>>let inplace_map f a b = Array.blit (map f a) 0 b 0 (Array.length a)
>>
>>Arrays a and b are of the same size.
>>This seems very inelegant.
>>    
>>
>
>I guess you mean Array.map. Indeed, this is not optimal because
>Array.map allocates a new array, whose contents is immediately copied
>into b.
>
>  
>
There's a reason for that...

>>One could use an adapter function and iteri, but that adds very noticeable 
>>overhead, and doesn't seem too elegant either.
>>
>>let inplace_map f a b = Array.iteri (fun i src -> b.(i) <- f src; ()) a
>>    
>>
>
>You may find this inelegant too, but it is clearly more efficient than
>your previous version using map. Note that "; ()" can be omitted, since
>the assignment <- already has type unit.
>
>Equivalently, you could use a for loop instead of Array.iteri.
>
>  
>

Both of these maps have the type ('a -> 'a) -> 'a array -> 'a array, as 
opposed to the normal map, which has the type ('a -> 'b) -> 'a array -> 
'b array.  Once you allocate an array, you can't change the type it 
holds.  So I'd probably give the function some other name, maybe 
"modify" or similiar.

Brian



[-- Attachment #2: Type: text/html, Size: 1978 bytes --]

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Edgar Friendly]

Kuba Ober wrote:
> I need functionality of map, but done in such a way that the output array
> is given as the argument, not as a return value. The closest I could get was
> 
> let inplace_map f a b = Array.blit (map f a) 0 b 0 (Array.length a)
> 
> Arrays a and b are of the same size.
> This seems very inelegant.
> 
> One could use an adapter function and iteri, but that adds very noticeable 
> overhead, and doesn't seem too elegant either.
> 
> let inplace_map f a b = Array.iteri (fun i src -> b.(i) <- f src; ()) a
> 
> There must be a better way of doing it, right? The given here is that the 
> arrays a and b are there to stay, so we have to use them in-place.
> 
> Cheers, Kuba
> 

let blit_map f a b =
	for i = 0 to (min (Array.length b) (Array.length a)) - 1 do
		b.(i) <- f a.(i);
	done

I don't see any better way to do this.  I can't see any overhead to
using a for loop like this.  I guess the recursive solution should also
work fast:

let blit_map f a b =
	let rec loop i =
		if i < 0 then ()
		else b.(i) <- f a.(i); loop (i-1)
	in
	let max_i = min (Array.length a) (Array.length b) in
	loop (max_i - 1)

But as I've been finding out in trying to performance tune for the
Shootout, 'for' loops seem faster than even tail-recursion.  I'd say
something about function call overhead, but tail recursion shouldn't
have such.  Maybe the work of updating the loop counter in the recursive
case makes the difference...

E.

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Brian Hurt]

[-- Attachment #1: Type: text/plain, Size: 1678 bytes --]

Edgar Friendly wrote:

>Kuba Ober wrote:
>  
>
>>I need functionality of map, but done in such a way that the output array
>>is given as the argument, not as a return value. The closest I could get was
>>
>>let inplace_map f a b = Array.blit (map f a) 0 b 0 (Array.length a)
>>
>>Arrays a and b are of the same size.
>>This seems very inelegant.
>>
>>One could use an adapter function and iteri, but that adds very noticeable 
>>overhead, and doesn't seem too elegant either.
>>
>>let inplace_map f a b = Array.iteri (fun i src -> b.(i) <- f src; ()) a
>>
>>There must be a better way of doing it, right? The given here is that the 
>>arrays a and b are there to stay, so we have to use them in-place.
>>
>>Cheers, Kuba
>>
>>    
>>
>
>let blit_map f a b =
>	for i = 0 to (min (Array.length b) (Array.length a)) - 1 do
>		b.(i) <- f a.(i);
>	done
>  
>
I was thinking more like:

let modify f a =
    for i = 0 to (Array.length a) - 1 do
       a.(i) <- f a.(i)
    done;
    a
;;

The OP did say "in place modification.

>But as I've been finding out in trying to performance tune for the
>Shootout, 'for' loops seem faster than even tail-recursion.  I'd say
>something about function call overhead, but tail recursion shouldn't
>have such.  Maybe the work of updating the loop counter in the recursive
>case makes the difference...
>
>  
>
It depends.  If you have to use multiple references to make the for-loop 
work, then I've seen tail recursion be faster (and clearer).  Also, if 
you recalculate the ending requirement every recursive call, recursion 
can be slower (in the above for loop above, for example, Array.length is 
gaurenteed to be called only once).

Brian


[-- Attachment #2: Type: text/html, Size: 2284 bytes --]

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Edgar Friendly]

Brian Hurt wrote:
> The OP did say "in place modification.
> 
Kuba also said "the output array is given as the argument, not as a
return value."

> It depends.  If you have to use multiple references to make the for-loop
> work, then I've seen tail recursion be faster (and clearer).  

Any example of a faster tail recursion?

> Also, if
> you recalculate the ending requirement every recursive call, recursion
> can be slower (in the above for loop above, for example, Array.length is
> gaurenteed to be called only once).

I have no problems precalculating the Array.length value, or recursing
down to 0.
> 
> Brian
> 

A little testing results in some data: for arrays of 1024 ints and
simple arithmetic operations, I get a 9% speed increase in using a for
loop over recursion.

E.

Re: [Caml-list] [NEWBIE] is there an in-place map?

[Kuba Ober]

On Wednesday 02 January 2008, you wrote:
> Brian Hurt wrote:
> > The OP did say "in place modification.
>
> Kuba also said "the output array is given as the argument, not as a
> return value."
>
> > It depends.  If you have to use multiple references to make the for-loop
> > work, then I've seen tail recursion be faster (and clearer).
>
> Any example of a faster tail recursion?
>
> > Also, if
> > you recalculate the ending requirement every recursive call, recursion
> > can be slower (in the above for loop above, for example, Array.length is
> > gaurenteed to be called only once).
>
> I have no problems precalculating the Array.length value, or recursing
> down to 0.
>
> > Brian
>
> A little testing results in some data: for arrays of 1024 ints and
> simple arithmetic operations, I get a 9% speed increase in using a for
> loop over recursion.

It seems to be such a basic operation, I was thinking that it must be there. 
Array.map is fine and dandy, but it is a premature pessimization if used 
repeatedly unless the compiler would be very smart about it. It's one of the 
common Java pessimizations too: generating lots of garbage at the same spot 
in a tight loop.

Cheers, Kuba