search

haskell / vector

An efficient implementation of Int-indexed arrays (both mutable and immutable), with a powerful loop optimisation framework .
Other
366 stars 139 forks source link

The Bundle datatype seemingly doesn't need the field sVector #269

Open gksato opened 4 years ago

gksato commented 4 years ago

In the module Data.Vector.Fusion.Bundle.Monadic, the datatype Bundle m v a has the field sVector :: Maybe (v a), whose value is currently used by no consumer, apparently (by which I mean I didn't find any usage when I scanned through the code). I am just curious how come it's there. For what (practical or historical) reason does the field exist? Is it even OK to make a pull request in favor of its removal?

cartazio commented 4 years ago

Good question! I’m not sure offhand, I’ll take a look, and we should definitely look at the history and applicable design writings.

Also do any producers generate a Just v ?!

There’s absolutely a lot of ways we can improve vector and I welcome meticulous experimentation

On Sun, Jan 26, 2020 at 12:20 AM Genki Sato notifications@github.com wrote:

In the package Data.Vector.Fusion.Bundle.Monadic, the datatype Bundle m v a has the field sVector :: Maybe (v a), whose value is currently used by no consumer. I am just curious how come it's there. Is there any practical or historical reason? Is it even OK to make a pull request in favor of the removal of that field?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/haskell/vector/issues/269?email_source=notifications&email_token=AAABBQVR4GKNRQXNDQ3CTSDQ7UMTLA5CNFSM4KLU5R72YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4IIXL54A, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAABBQRHEEOWZVUAYS6C54DQ7UMTLANCNFSM4KLU5R7Q .

gksato commented 4 years ago

At least one generator does generate Just v: Data.Vector.Fusion.Bundle.Monadic.fromVector (and hence so do Data.Vector.Generic.stream and Data.Vector.Fusion.Bundle.fromVector). Also, Data.Vector.Fusion.Bundle.Monadic.trans preserves the value of the field. If I've read through and searched within the code correctly, they are the only functions that can give Bundle having Just in sVector.

gksato commented 4 years ago

Oops. There's Data.Vector.Generic.stream', of course! ;)

cartazio commented 4 years ago

all good :)

gksato commented 4 years ago

I don't understand why this has got closed. Could you explain why? My point is that someone assigns it, but nobody uses it. Maybe for use from other package?

cartazio commented 4 years ago

You indicated that you misread the code as dead? Or Did I misinterpret your remark ? I’ve been juggling a lot today so could totally be a mistake

On Thu, Jan 30, 2020 at 10:45 PM Genki Sato notifications@github.com wrote:

I don't understand why this get closed. Could you explain why?

— You are receiving this because you modified the open/close state.

Reply to this email directly, view it on GitHub https://github.com/haskell/vector/issues/269?email_source=notifications&email_token=AAABBQWANR23G6NDBJ5WN6DRAONFZA5CNFSM4KLU5R72YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKNMLVY#issuecomment-580568535, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAABBQRPBWAVMSODSCOU7KTRAONFZANCNFSM4KLU5R7Q .

gksato commented 4 years ago

My point is: some agents (Generic.stream, Generic.stream', Bundle.Monadic.fromVector and Bundle.fromVector) give a value to it, other (Bundle.Monadic.trans and Bundle.lift) leave the value in it as it is, but if I eye-grepped right, nobody takes a value out of it.

cartazio commented 4 years ago

Ohhhh ok.

There’s certainly some room for improvement

On Thu, Jan 30, 2020 at 11:20 PM Genki Sato notifications@github.com wrote:

My point is: some agents (Generic.stream, Generic.stream', Bundle.Monadic.fromVector and Bundle.fromVector) give a value to it, other (Bundle.Monadic.trans and Bundle.lift) leave the value in it as it is, but if I eye-grepped right, nobody takes a value out of it.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/haskell/vector/issues/269?email_source=notifications&email_token=AAABBQXGGLXZDWFPDXSTKDLRAORHPA5CNFSM4KLU5R72YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEKNNY7Y#issuecomment-580574335, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAABBQXHHKJOKAXHLZTZVETRAORHPANCNFSM4KLU5R7Q .

gksato commented 4 years ago

There are some options I can think of: 1: We could add some consumption: unstreaming operation, slicing operation, and indexing may take the vector out of sVector. There may or may not be performance penalty. I'm pretty doubtful there will be performance benefit. (I say "doubtful"; I didn't test.) 2: We could entirely remove sVector. May get a slight performance benefit? 3: Leave it as it is. I don't say this is a very good choice. However it's not an utterly bad option, if you think of Data.Vector.Fusion as non-internal. In fact, I found this issue when I was writing Stream Fusion code outside of vector. 4: I am wrong. My eye-grep is buggy and there's an usage I didn't find, or the field is some mysterious magic getting the whole thing blazing fast ;)

lehins commented 3 years ago

The whole reason why Bundle was created is to utilize SIMD instructions. It is described in this paper: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/07/haskell-beats-C.pdf At some point, I think, there was a fork of vector that worked with some fork of GHC that was actually able to utilize CPU vectorization, but currently this is not the case and I believe sVector isn't used for anything constructive

So, what do we do about it?

I am leaning towards the latter.

CC @Shimuuar This is my opinion on this issue, since it came up in the release plan.

Linking #251 as related ticket on the subject.

gksato commented 3 years ago

@lehins Oh, as an author of this issue, let me mention #330! (Sorry I'm so lazy).

lehins commented 3 years ago

Oh, yeah, I forgot that we found a use for sVector :wink:

So, let's keep this issue open, but without any rush of removing sVector and Bundle restructure, who knows what other uses we can find for it.

Bodigrim commented 3 years ago

Let's keep sVector then.

cartazio commented 3 years ago

I remember @dolio found that the bundle fusion layer actually helped more things fuse. But I don’t remember the specific examples.

On Sun, Jan 17, 2021 at 12:32 PM Bodigrim notifications@github.com wrote:

Let's keep sVector then.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/haskell/vector/issues/269#issuecomment-761848605, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAABBQQIUSGESSSEK5XRGCTS2MNKPANCNFSM4KLU5R7Q .