Skip to content

Implement mutable vectors using arrays#146

Closed
utdemir wants to merge 2 commits intotweag:masterfrom
utdemir:vector-refactor
Closed

Implement mutable vectors using arrays#146
utdemir wants to merge 2 commits intotweag:masterfrom
utdemir:vector-refactor

Conversation

@utdemir
Copy link
Copy Markdown
Contributor

@utdemir utdemir commented Sep 2, 2020 •
edited
Loading

This PR refactors Data.Vector.Mutable.Linear to use Data.Array.Mutable.Linear instead of Unsafe.MutableArray. I also did a few refactors around the Array code.

In summary:

  • I exposed unsafeRead and unsafeWrite functions from vectors and array to reduce unnecessary bounds-checking in vector code.
  • I changed the type signatures so that the linear collection is the last parameter as opposed to the first. This might be controversial , but IMO it makes it nicer to compose the functions, eg:
Vector.fromList l
  $ \vec ->
    vec
      Linear.& Vector.length
      Linear.& \(vec, Unrestricted oldLength) -> Vector.snoc 42 vec
      Linear.& Vector.length
      Linear.& getSnd
      Linear.& \(Unrestricted newLength) -> Unrestricted $ newLength === oldLength + 1
  • Array had a few resize functions with counter-intutive semantics. I replaced them with three functions: allocBeside, growBy and shrinkTo. Let me know if you prefer something else.
  • MutableArray, Array and Vector used to require at least one element inside. I removed this constraint. It seems like MutableArray can have 0 length, and therefore there is no reason Array and Vector to have that restriction.

So I'm sorry if this PR is a bit all around the place. I suggest you review the modules in this order:

  • Unsafe.MutableArray
  • Data.Array.Mutable.Linear
  • Data.Vector.Mutable.Linear.
  • tests
  • Data.HashMap.Linear (only contains changes because of the parameter order change)

utdemir
utdemir commented Sep 2, 2020
View reviewed changes
src/Data/Array/Mutable/Linear.hs
allocBeside :: Int -> a -> Array b #-> (Array b, Array a)
allocBeside size val orig
| size >= 0 = (orig, Array (Unsafe.newMutArr size val))
| otherwise = orig `lseq` error ("Trying to allocate an array of size " ++ show size)
Copy link
Copy Markdown
Contributor Author

@utdemir utdemir Sep 2, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I find this function interesting. It is required since when implementing HashMap's, insertions can cause a new, bigger array to be created. However, we can not use alloc function there since it requires a continuation; and making HashMap insertions take a continuation would be unwieldy.

I wanted to replace it with something more generic, but couldn't figure out how to do it nicely. I think this connects to @aspiwack 's suggestion on #130.

utdemir
utdemir commented Sep 2, 2020
View reviewed changes
src/Data/Vector/Mutable/Linear.hs
where
unsafeLength :: Vector a -> (Vector a, Int)
unsafeLength v@(Vec (len, _) _) = (v, len)
length :: Vector a #-> (Vector a, Unrestricted Int)
Copy link
Copy Markdown
Contributor Author

@utdemir utdemir Sep 2, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I replaced this function to return an Unrestricted Int instead of Int, to be more consistent with other functions like read.

utdemir
utdemir commented Sep 2, 2020
View reviewed changes
src/Data/Vector/Mutable/Linear.hs

-- | Read from a vector, with an in-range index and error for an index that is
-- out of range (with the usual range @0..length-1@).
read :: HasCallStack => Vector a #-> Int -> (Vector a, a)
Copy link
Copy Markdown
Contributor Author

@utdemir utdemir Sep 2, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The new version of this function returns a Unrestricted a instead. Since the vector does not contain its values linearly, I think it was overly restrictive.

utdemir
utdemir commented Sep 2, 2020
View reviewed changes
src/Data/Array/Mutable/Linear.hs

data Array a where
Array :: Int -> (MutableArray# RealWorld a) -> Array a
Array :: MutableArray# RealWorld a -> Array a
Copy link
Copy Markdown
Contributor Author

@utdemir utdemir Sep 2, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Now the Array does not have an extra size parameter, since MutableArray# already comes with a sizeof method.

@aspiwack
Copy link
Copy Markdown
Member

aspiwack commented Sep 2, 2020 •
edited
Loading

  • I changed the type signatures so that the linear collection is the last parameter as opposed to the first. This might be controversial , but IMO it makes it nicer to compose the functions

Whatever I think of this change. It didn't belong to this PR. Additionally, this is not the sort of change that you should make without talking about it first. We've all got better things to do than revert this in the course of this PR, though I do hope this sort of conflation won't happen again. But please open an issue to discuss the order of arguments in these functions. (under the bikeshedding label, I assume)

@aspiwack
Copy link
Copy Markdown
Member

aspiwack commented Sep 2, 2020

Array had a few resize functions with counter-intutive semantics. I replaced them with three functions: allocBeside, growBy and shrinkTo. Let me know if you prefer something else.

This should have been another PR.

@utdemir
Copy link
Copy Markdown
Contributor Author

utdemir commented Sep 2, 2020

I'm happy to spend some time sending separate PR's for each. Sorry about this.

@utdemir utdemir closed this Sep 2, 2020
This was referenced Sep 2, 2020
Closed
Closed
Closed
@utdemir
Copy link
Copy Markdown
Contributor Author

utdemir commented Sep 2, 2020 •
edited
Loading

I split this up to #147, #148 and #149. Alongside with the original #144, they should cover all of the changes here.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@Divesh-Otwani Divesh-Otwani Awaiting requested review from Divesh-Otwani

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

2 participants

@utdemir @aspiwack