Rebased and fixed #347 #402

Shimuuar · 2021-08-11T09:19:57Z

This is rebased #347 updated to work with current master.

Makes indexM strict in vector by using basicIndexM
Word trick is used to make single comparison for range checks instead of two for all range checks

* Make `(!?)` extract a value from the vector eagerly. * Make the range check for `(!?)` use one comparison instead of two.

and use it for all checks

vector/src/Data/Vector/Generic.hs

vector/src/Data/Vector/Internal/Check.hs

Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

lehins

That's great that you were able to confirm that this trick works!

konsumlamm · 2021-08-11T18:33:35Z

Sorry for not mentioning this earlier, but wouldn't it be more efficient to directly index in the Maybe monad, like this (which was also done in #347)?

v !? i | i `inRange` length v = basicUnsafeIndexM v i
       | otherwise            = Nothing

It's possible that the allocation of the Box is optimized away, but we probably shouldn't rely on that.

gksato · 2021-08-11T19:00:19Z

@konsumlamm

Sorry for not mentioning this earlier, but wouldn't it be more efficient to directly index in the Maybe monad, like this (which was also done in #347)?
v !? i | i `inRange` length v = basicUnsafeIndexM v i
       | otherwise            = Nothing
It's possible that the allocation of the Box is optimized away, but we probably shouldn't rely on that.

Note that

class (MVector (Mutable v) a) => Vector v a where
  ...
  basicUnsafeIndexM :: v a -> Int -> Box a
  ...

and

-- | /O(1)/ Unsafe indexing without bounds checking.
unsafeIndex :: Vector v a => v a -> Int -> a
{-# INLINE_FUSED unsafeIndex #-}
unsafeIndex v i = checkIndex Unsafe i (length v) $ unBox (basicUnsafeIndexM v i)

in favor of GeneralizedNewtypeDeriving.

konsumlamm · 2021-08-11T19:12:08Z

Huh, apparently this was changed a while ago in #335. Ignore my comment, then.

gksato · 2021-08-11T19:31:02Z

And I should also apologize that I should've mentioned this earlier, but I was afraid a function like factorial in what follows may get a poor optimization with this:

factorial :: HasCallStack => Int -> Mod1097
factorial n
  | n < 0 = error "factorial: pole of Gamma function"
  | n >= VU.length factorials = error "factorial: out of desired range"
  | otherwise = factorials VU.! n

factorials :: VU.Vector Mod1097
factorials = VU.scanl' (*) (M1097 1) $ VU.generate 300000 (M1097 . fromIntegral . (+1))

-- | Remainder ring mod 10^9+7.
newtype Mod1097 = M1097 Word32
  deriving newtype (Eq, Show, VGM.MVector VUM.MVector, VG.Vector VU.Vector, VUM.Unbox) 
newtype instance VU.Vector Mod1097 = UnboxMod1097 (VU.Vector Word32)
newtype instance VUM.MVector s Mod1097 = UnboxMMod1097 (VUM.MVector s Word32)

instance Num Mod1097 where ...

Anyway, I'll try this and check how it goes. If it goes wrong, I'll inform you all in a separate issue.

Shimuuar · 2021-08-11T19:42:39Z

@konsumlamm Yes it has been changed in order to allow GND/DerivingVia since GHC cannot coerce between m A and m B for polymorphic m even if A and B are coercible.

@gksato I think GHC is rather good at cutting away such allocations. But please do report your findings

gksato · 2021-08-11T19:47:36Z

Allocations? I meant comparisons.
I was afraid that GHC possibly cannot infer
fromIntegral n < (fromIntegral len :: Word)
even if given
n >= 0 && n < len.

Shimuuar · 2021-08-11T19:54:42Z

Ah! I wonder if GHC is able to remove duplicate checks even without such trick

# Changes in version 0.13.0.0 * `mkType` from `Data.Vector.Generic` is deprecated in favor of `Data.Data.mkNoRepType` * The role signatures on several `Vector` types were too permissive, so they have been tightened up: * The role signature for `Data.Vector.Mutable.MVector` is now `type role MVector nominal representational` (previously, both arguments were `phantom`). [#224](haskell/vector#224) * The role signature for `Data.Vector.Primitive.Vector` is now `type role Vector nominal` (previously, it was `phantom`). The role signature for `Data.Vector.Primitive.Mutable.MVector` is now `type role MVector nominal nominal` (previously, both arguments were `phantom`). [#316](haskell/vector#316) * The role signature for `Data.Vector.Storable.Vector` is now `type role Vector nominal` (previous, it was `phantom`), and the signature for `Data.Vector.Storable.Mutable.MVector` is now `type role MVector nominal nominal` (previous, both arguments were `phantom`). [#235](haskell/vector#235) We pick `nominal` for the role of the last argument instead of `representational` since the internal structure of a `Storable` vector is determined by the `Storable` instance of the element type, and it is not guaranteed that the `Storable` instances between two representationally equal types will preserve this internal structure. One consequence of this choice is that it is no longer possible to `coerce` between `Storable.Vector a` and `Storable.Vector b` if `a` and `b` are nominally distinct but representationally equal types. We now provide `unsafeCoerce{M}Vector` and `unsafeCast` functions to allow this (the onus is on the user to ensure that no `Storable` invariants are broken when using these functions). * Methods of type classes `Data.Vector.Generic.Mutable.MVector` and `Data.Vector.Generic.Vector` use concrete monads (`ST`, etc) istead of being polymorphic (`PrimMonad`, etc). [#335](haskell/vector#335). This makes it possible to derive `Unbox` with: * `GeneralizedNewtypeDeriving` * via `UnboxViaPrim` and `Prim` instance * via `As` and `IsoUnbox` instance: [#378](haskell/vector#378) * Add `MonadFix` instance for boxed vectors: [#312](haskell/vector#312) * Re-export `PrimMonad` and `RealWorld` from mutable vectors: [#320](haskell/vector#320) * Add `maximumOn` and `minimumOn`: [#356](haskell/vector#356) * The functions `scanl1`, `scanl1'`, `scanr1`, and `scanr1'` for immutable vectors are now defined when given empty vectors as arguments, in which case they return empty vectors. This new behavior is consistent with the one of the corresponding functions in `Data.List`. Prior to this change, applying an empty vector to any of those functions resulted in an error. This change was introduced in: [#382](haskell/vector#382) * Change allocation strategy for `unfoldrN`: [#387](haskell/vector#387) * Remove `CPP` driven error reporting in favor of `HasCallStack`: [#397](haskell/vector#397) * Remove redundant `Storable` constraints on to/from `ForeignPtr` conversions: [#394](haskell/vector#394) * Add `unsafeCast` to `Primitive` vectors: [#401](haskell/vector#401) * Make `(!?)` operator strict: [#402](haskell/vector#402) * Add `readMaybe`: [#425](haskell/vector#425) * Add `groupBy` and `group` for `Data.Vector.Generic` and the specialized version in `Data.Vector`, `Data.Vector.Unboxed`, `Data.Vector.Storable` and `Data.Vector.Primitive`. [#427](haskell/vector#427) * Add `toArraySlice` and `unsafeFromArraySlice` functions for conversion to and from the underlying boxed `Array`: [#434](haskell/vector#434)

treeowl and others added 2 commits August 11, 2021 11:45

Use eager indexing for !?

5539ef7

* Make `(!?)` extract a value from the vector eagerly. * Make the range check for `(!?)` use one comparison instead of two.

Factor out Word trick into separate function

23f04f8

and use it for all checks

Shimuuar requested review from Bodigrim and lehins August 11, 2021 09:19

konsumlamm reviewed Aug 11, 2021

View reviewed changes

vector/src/Data/Vector/Generic.hs Outdated Show resolved Hide resolved

vector/src/Data/Vector/Internal/Check.hs Outdated Show resolved Hide resolved

Shimuuar and others added 2 commits August 11, 2021 14:29

Fix comment

9301ff3

Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

Formatting

cea3186

Co-authored-by: konsumlamm <44230978+konsumlamm@users.noreply.github.com>

lehins approved these changes Aug 11, 2021

View reviewed changes

Bodigrim approved these changes Aug 11, 2021

View reviewed changes

Bodigrim merged commit 8b4716b into haskell:master Aug 11, 2021

Shimuuar deleted the strict-index branch September 11, 2021 10:54

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Rebased and fixed #347 #402

Rebased and fixed #347 #402

Uh oh!

Shimuuar commented Aug 11, 2021

Uh oh!

Uh oh!

Uh oh!

lehins left a comment

Uh oh!

konsumlamm commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021 •

edited

Loading

Uh oh!

konsumlamm commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021

Uh oh!

Shimuuar commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021

Uh oh!

Shimuuar commented Aug 11, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Rebased and fixed #347 #402

Rebased and fixed #347 #402

Uh oh!

Conversation

Shimuuar commented Aug 11, 2021

Uh oh!

Uh oh!

Uh oh!

lehins left a comment

Choose a reason for hiding this comment

Uh oh!

konsumlamm commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

konsumlamm commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021

Uh oh!

Shimuuar commented Aug 11, 2021

Uh oh!

gksato commented Aug 11, 2021

Uh oh!

Shimuuar commented Aug 11, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

gksato commented Aug 11, 2021 •

edited

Loading