Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Nov 24 12:57
    lehins commented #97
  • Nov 23 20:36
    lehins closed #101
  • Nov 23 20:36
    lehins commented #101
  • Oct 31 22:23
    lehins edited #94
  • Jul 30 13:26
    adamConnerSax commented #50
  • Jul 28 23:25
    lehins edited #106
  • Jul 28 23:22
    lehins milestoned #106
  • Jul 28 23:21
    lehins opened #106
  • Jul 28 14:39
    adamConnerSax closed #105
  • Jul 28 14:39
    adamConnerSax commented #105
  • Jul 28 13:52
    lehins commented #105
  • Jul 28 13:40
    lehins commented #105
  • Jul 28 13:38
    lehins commented #105
  • Jul 28 13:30
    adamConnerSax commented #105
  • Jul 28 13:26
    adamConnerSax commented #105
  • Jul 28 13:24
    adamConnerSax commented #105
  • Jul 28 12:59
    adamConnerSax commented #105
  • Jul 28 12:56
    lehins commented #105
  • Jul 28 12:33
    adamConnerSax commented #105
  • Jul 28 10:48
    lehins commented #105
Alexey Kuleshevich
@lehins
@ocramz Do you mean you want an actual size of the array at the type level or just the dimension 3D, 4D etc.
If you are talking about the latter then Dimensions ix :: Nat is exactly that, but I get a feeling that you want the former. I contemplated on adding array size to the type level, but that would complicate the library significantly. So I decided if I ever get time I will create a wrapper library that has the ability to reason about array sizes at compile time, but for now it is pretty far away on the list of things I'd like to do. Here is one library that augments a massiv matrix with type level size: mapalgebra (eg. [Raster`](https://hackage.haskell.org/package/mapalgebra-0.2.1/docs/Geography-MapAlgebra.html#t:Raster))
Marco Z
@ocramz
thank you @lehins ; I only ask about this since I started blending massiv with backprop: trying to write array functions that can be automatically differentiated. backprop requires you to write combinators using pure function and typeclass instances, at the cost of approximating the problem (e.g. padding mismatching arrays with zeros) or losing safety (crashing on mismatching dimensions):
inner :: (Backprop a, Num a, Reifies s W) => BVar s (Vector D a) -> BVar s (Vector D a) -> BVar s a
inner = liftOp2 . op2 $ \ u v ->
                          ( sum $ unsafeLiftArray2 (*) u v
                          , \dzdy -> (dzdy *. v, u .* dzdy)
                          )

-- | this instance only exists for Delayed arrays
instance (Index ix, Backprop e) => Backprop (Array D ix e) where
  zero = fmap zero
  one = fmap one
  add = zipWith add
Alexey Kuleshevich
@lehins
@ocramz Yeah it looks like you need to know array size at the type level. It is the same issue with Num instance for D. The only thing I can recommend is creating a newtype wrapper with phantom type variable around Array that would carry the size at the type level and create a Backprop instance for that type instead. It is currently not possible to add this functionality to massiv without major breaking and I don't think I would want to do that either. Not all people care about types that much. But I do see a future where we have a library that implements this functionality on top of massiv.
Paul Chiusano
@pchiusano
Just saying hello, Massiv seems like a great project. I'm investigating using it for some numeric computing support for the Unison language
Paul Chiusano
@pchiusano
@lehins is there any special handling for unboxed arrays of booleans? wondering if I can do efficient bit-vector-y stuff with Massiv
Paul Chiusano
@pchiusano
@lehins also, any support for scans (prefix sums, etc), I couldn't find anything
Alexey Kuleshevich
@lehins

Hi @pchiusano This is pretty awesome that you are considering massiv for Unison language, hope it works out for you.
Current handling of Bool type depends on the representation, but the only ones that do unboxing are U and S. The former is the same as unboxing of Bool from Data.Vector.Unboxed, the latter is the Storable instance. Neither one of them will do any tight packing, for Unbox it will use a Word8, while for Storable it is even worse and each element will take 4 bytes since it is stored as Int32. This is a bit unfortunate, but it will still be faster than if Bool is treated as boxed.

That being said, there is a way to get support for tightly packed Bools with massiv by using https://github.com/Bodigrim/bitvec The Bit type has Unbox instance and it will work with U representation.

With regards to scans I simply haven't gotten to them yet, but it would be fairly easy to add them, since all the stream stuff (DS representation) in massiv is a wrapper around the vector streams.

Paul Chiusano
@pchiusano
gotcha
I have some questions about the performance when massiv computations are being created dynamically - like, if I have foo * x + y then I'm guessing that can get optimized really well with sufficient inlining... but now suppose that expression is being created dynamically, like in the front end of a programming language. Now static inlining doesn't do anything. Is it going to end up with everything being boxed and/or with intermediate vectors being created? @lehins
Alexey Kuleshevich
@lehins

Devil is in the details. First of all what do you mean by "computations are being created dynamically"? Second of all what are the types of foo, x and y

Intermediate vectors in massiv are not being created on its own. Unlike vector package or lists in Haskell, massiv is structured in such a way that the user is in control of fusion of computation, in other words functions like compute do allocations and computation, while + and * create delayed computation. With respect to inlining it is a crucial optimization and if the code fails to inline because a program was not compiled with optimizations then performance will be terrible, no matter which numeric library you use in Haskell.
Boxed and Unboxed is also known statically thanks to representations B/N vs U/P/S respectively

Paul Chiusano
@pchiusano
right, so using D/DS allows you to control fusion
Alexey Kuleshevich
@lehins
Correct!
Paul Chiusano
@pchiusano
but I'm still uncertain on the boxing stuff
let's simplify a little - suppose I write map (1+) . map (2*) . fromList Seq [1,2,3]
and then computeAs U of that
er compute?
If I write that expression computeAs U . map (1+) . map (2*) . fromList Seq [1,2,3] as Haskell code, I can expect a lot of it to get inlined and performance to be good, right?
Alexey Kuleshevich
@lehins
fromList will require you to provide a manifest type too. So fromList Seq [1,2,3] :: Vector U Int will allocate an unboxed vector with contents [1,2,3], then both maps will create delayed arrays (so no allocations), then computeAs U will allocate another vector and load elements [3,5,7] into the contents of that vector. And yes, performance of that will be great.
Paul Chiusano
@pchiusano
but in Unison, we'd be parsing a program which starts out as text, and then dynamically generating massiv expressions... so inlining at compile time is not going to happen
(understood re: manifest type - still learning the API :))
but do you see what I'm asking re: the dynamically generated expressions?
Alexey Kuleshevich
@lehins
So you are essentially doing something like JIT in Unison?
all the inlining and all of the other optimizations that massiv relies on heavily comes from ghc.
Paul Chiusano
@pchiusano
I mean, right now it is an interpreted language, but yeah - we are producing these expressions dynamically
well, suppose nothing got inlined in computeAs U . map (1+) . map (2*) . fromList Seq [1,2,3] :: Vector U Int, what would it end up doing?
it's still not going to materialize the intermediate arrays, right
Alexey Kuleshevich
@lehins
Which means if you are not using ghc -O performance will not be great at all. But I am sure you know that any more or less complicated piece of code in Haskell will have poor performance with out inlining

it's still not going to materialize the intermediate arrays, right

That is correct. materialization is controlled manually

Paul Chiusano
@pchiusano
will it be doing more boxing than it would if it did inlining?
or will it be fine, just with more function call overhead
Alexey Kuleshevich
@lehins
No boxing or surprising allocations will occur if the code is not inlined. All of this stuff is known at compile time with array representations and inliner plays no role in this decision making
Paul Chiusano
@pchiusano
hmm... what about the map (1+) ... could that end up calling a boxed Int -> Int function... maybe this is more of a vector streams question
Alexey Kuleshevich
@lehins
That being said, I suspect function call overhead will be pretty significant, nevertheless overall performance should be better than with libraries such as vector that rely heavily on inlining for fusion or lists that also do not fuse and thus also do not get unboxed without optimizations

what about the map (1+) ... could that end up calling a boxed Int -> Int function

in case of map (1+) in massiv it is essentially just function composition. But, considering that Int in ghc is a boxed value around Int#, compiling without optimizations probably will cause all the intermediate boxing/unboxing, but that is the cost of interpreting Haskell vs compiling it, regardless of a library you use.

Alexey Kuleshevich
@lehins
By the way, there are two different maps in massiv: map and smap. Latter can be only processed sequentially and can only deal with flat vectors because it operates on streams, while the former can work on multidimensional arrays and can be parallelized. This is pretty much the difference between the D and DSrepresentations.
Paul Chiusano
@pchiusano
I mean, if you have a call site in the interpreter which always calls the same map (1+) operation, that won't be boxed I'd imagine... but if you are like taking a function Int -> Int dynamically, and then passing that to map, then that probably will end up boxed
understood re: D vs DS
DS might not have known size
Alexey Kuleshevich
@lehins
yep
Paul Chiusano
@pchiusano
okay other idea - could you get a "chunked" view of an array? like suppose < 32 element chunks, and then each stage of the composition is given the whole chunk to work with
Alexey Kuleshevich
@lehins
There are functions for slicing, extracting etc. which all produce delayed arrays as well. I think that is your question, right? Just as with map, they are all constant time index manipulations and fuse just like map would.
Paul Chiusano
@pchiusano
right... okay let me play with it some more. Thanks for your help! also great library :)
Alexey Kuleshevich
@lehins
Thank you, appreciate it. Good luck with Unison. Shoot questions here if you get stuck with massiv on something.
Paul Chiusano
@pchiusano
:thumbsup:
Marco Z
@ocramz
something that's been bugging me for a while: why can only D arrays be Numeric? https://hackage.haskell.org/package/massiv-0.5.4.0/docs/Data-Massiv-Core-Operations.html#t:Numeric
Marco Z
@ocramz
In my case, I have a few conduit combinators that do numerical operations on streams of massiv D arrays, most often Vector D Double. Most of them are based on folds or scanlM(https://hackage.haskell.org/package/conduit-1.3.2.1/docs/Data-Conduit-Combinators.html#v:scanlM). Either way, running these operations gets progressively slower, which I think is an indication of a space leak. I tried both strict and lazy consumers, like closing the conduit with a printC or sinking the results into a list and printing that, with similar behaviours
I don't have a clear path forward on this, but I thought that making arrays strict could be one possible solution
Marco Z
@ocramz
I'll try by sprinkling some seq here and there
Alexey Kuleshevich
@lehins

something that's been bugging me for a while: why can only D arrays be Numeric?

In short, numeric interface is still going through design and Numeric class was created to add more efficient numeric implementation, hopefully with some SIMD support, but that is still quite far away in the future, so for now it is only D that works with Numeric

Why is only D, because if you write something like compute (x + y * z) you want the numeric operations to fuse. If representations like U would have an instance then every numeric operation would cause an allocation of a completely new array, which would quickly become very slow.

There is no point to use D array with conduit. Delayed array do not take up any memory, so constant memory processing approach doesn't make sense. On the other hand, if you producer is actually allocating new arrays, then you really want to call compute for each scan operation in your pipeline, however this will cause allocation of a whole new array as well for each iteration. So you might want to look into computeInto, in order to reuse the same region of memory at each step. Of course, devil is in the details.

@ocramz Anyways, as I I've mentioned before, I am not that big on discussing code abstractly, so if you have some snippets I can point you in the right direction. Also seq will be of no use with delayed arrays, since D doesn't rely on Haskell laziness. Think of compute as being a seq for massiv.

Marco Z
@ocramz
Thanks @lehins , indeed I didn't have a good mental model of delayed arrays. In this case I believe the progressive slowdown can be observed by summing streams of D arrays. In my case it's a few arrays that keep state for an on-line optimization algorithm. I'll try compute-ing them and will report back!