Migrate from array to vector

[Bodigrim]

Older parts of arithmoi tend to use Data.Array instead of Data.Vector, as newer modules do. It would be nice to migrate to vectors completely. The migration should be pretty straightforward, so it is a nice first issue.

[tau3]

Hello!

I'd like to try and implement this feature if nobody is currently working on it. Could you give me a hint on castSTUArray - what is the similar function for STVector?

[Bodigrim]

castSTUArray is basically return . unsafeCoerce, no more no less. But in fact we should get rid of castSTUArray :: STUArray s Int Bool -> ST s (STUArray s Int Word)) at all.

The thing is that this code in arithmoi is based upon a assumption that Array a Bool is a tightly-packed bit sequence, 8 Bool per byte, 32/64 Bool per machine word. This assumption is not guaranteed in general and, what is more important, is wrong for vectors: Vector Bool stores one Bool per byte, 4/8 Bool per machine word.

That said, one should replace

data PrimeSieve = PS !Integer {-# UNPACK #-} !(UArray Int Bool)

by

data PrimeSieve = PS !Integer {-# UNPACK #-} !(UArray Int Word)

and take care of correct indexing of individual bits. This is better to be done in a separate small PR, before taking a stab to current issue.

---

I believe @rockbmb had plans to fix this issue. @rockbmb are you interested to do it yourself or @tau3 may take over?

[tau3]

@Bodigrim
Thanks for explanation!

@rockbmb
I have already refactored MoebiusInversion and Cubes, please take it if you need 😄

[rockbmb]

@tau3 I have some code that may be useful to the issue, I'll push it to a branch in my fork and you can see if it helps you.

[rockbmb]

@tau3 Here you go, hope it helps! https://github.com/rockbmb/arithmoi/tree/arrays-to-vectors 👍
(Does not currently compile)

[Bodigrim]

I picked some low-hanging fruits in 9c90153 and b6e1145. See #157 for discussion about vectors for sieves.

[rockbmb]

@Bodigrim did this change introduce any changes in benchmarks? I've always been curious as to which is generally faster, Array or Vector, although this example might be too simple to give correct answers.

[Bodigrim]

We do not have benchmarks for these parts of the project.

In M.NT.Powers.* we use arrays to construct lookup tables. Once they are constructed, lookups should take pretty much the same time both for array and for vector.

There are might be some differences for M.NT.MoebiusInversion, but I doubt it. We do not use any advanced features from either package which may differ in inlining, fusion or memory alignment, just plain element-wise read and write.

---

AFAIU there are not many reasons to stick to array, except that it is a part of Haskell 2010 report and therefore must be available on any platform and any Haskell compiler.