[Haskell-cafe] vector to uvector and back again

[Roman Leshchinskiy]

On 12/02/2010, at 23:28, Dan Doel wrote:

> On Thursday 11 February 2010 8:54:15 pm Dan Doel wrote:
>> On Thursday 11 February 2010 12:43:10 pm stefan kersten wrote:
>>> On 10.02.10 19:03, Bryan O'Sullivan wrote:
>>>> I'm thinking of switching the statistics library over to using vector.
>>> 
>>> that would be even better of course! an O(0) solution, at least for me ;)
>>> let me know if i can be of any help (e.g. in testing). i suppose
>>> uvector-algorithms would also need to be ported to vector, then.
>> 
>> I could do this.
> 
> To this end, I've done a preliminary port of the library, such that all the 
> modules compile. I've just used safe operations so far, so it's probably a 
> significant decrease in performance over the 0.2 uvector-algorithms (unless 
> perhaps you turn off the bounds checking flag), but it's a start. It can be 
> gotten with:
> 
>  darcs get http://code.haskell.org/~dolio/vector-algorithms

That's great, thanks! FWIW, vector has two kinds of bounds checks: "real" ones which catch invalid indices supplied by the user (on by default) and internal ones which catch bugs in the library (off by default since the library is, of course, bug-free ;-). I guess you'd eventually want to use the latter but not the former; that's exactly what unsafe operations provide.

> I only encountered a couple snags during the porting so far:
> 
>  * swap isn't exported from D.V.Generic.Mutable, so I'm using my own.

Ah, I'll export it. Also, I gladly accept patches :-)

>  * I use a copy with an offset into the from and to arrays, and with a
>    length (this is necessary for merge sort). However, I only saw a whole
>    array copy (and only with identical sizes) in vector (so I wrote my own
>    again).

That's actually a conscious decision. Since vectors support O(1) slicing, you can simply copy a slice of the source vector into a slice of the target vector.

>  * Some kind of thawing of immutable vectors into mutable vectors, or other
>    way to copy the former into the latter would be useful. Right now I'm
>    using unstream . stream, but I'm not sure that's the best way to do it.

At the moment, it is (although it ought to be wrapped in a nicer interface). Something like memcpy doesn't work for Data.Vector.Unboxed because the ByteArrays aren't pinned. I don't really want to provide thawing until someone convinces me that it is actually useful.

BTW, vector also supports array recycling so you could implement true in-place sorting for fused pipelines. Something like

  map (+1) . sort . update xs

wouldn't allocate any temporary arrays in that case.

Roman