Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add NonEmpty containers, without imbalancing or massive code duplication #608

Open
Ericson2314 opened this issue Feb 27, 2019 · 19 comments

Comments

@Ericson2314
Copy link
Contributor

commented Feb 27, 2019

There's a number of packages on Hackage providing "non-empty" versions of containers, modeled after https://hackage.haskell.org/package/base/docs/Data-List-NonEmpty.html . There's a variety of use-cases, but perhaps my favorite is that they're needed to "curry" containers: for example, Map (k0, k1) v is isomorphic not to Map k0 (Map k1 v) but to Map k0 (NonEmptyMap k1 v). I like this use-case because it comes from the containers themselves.

Anyways, the problem with the existing implementations is that they tend to just prepend a minimal element to the container. This creates a less efficient, ill-balanced tree. But the alternative of copying the implementation creates a maintain burden. In https://github.com/mokus0/dependent-map/pull/31/files, I think I found an alternative which is the best of both worlds: mostly reused code and no degrade in balancing, namely making the types mutually recur.

For example, here are the types for DMap and NonEmptyDMap:

data DMap k f
  = Tip
  | Bin' {-# UNPACK #-} !(NonEmptyDMap k f)

pattern Bin s k v l r = Bin' (NonEmptyDMap s k v l r)

data NonEmptyDMap k f where
    NonEmptyDMap
         :: {- sz    -} !Int
         -> {- key   -} !(k v)
         -> {- value -} f v
         -> {- left  -} !(DMap k f)
         -> {- right -} !(DMap k f)
         -> NonEmptyDMap k f

DMap is like Maybe NonEmptyDMap but with the unboxed strict field.

Functions are then also written mutually recursively. (Take the exact weird worker wrapper style here with a grain of salt. This me trying to strike a balance between brevity and cargo culting the way the functions were written before.)

makeAdjustWithKey
  :: forall k f v
  .  GCompare k
  => (k v -> f v -> f v)
  -> k v
  -> ( DMap k f -> DMap k f
     , NonEmptyDMap k f -> NonEmptyDMap k f
     )
makeAdjustWithKey f k = (k `seq` go, k `seq` go')
  where
    go :: DMap k f -> DMap k f
    go Tip = Tip
    go (Bin' ne) = Bin' $! go' ne

    go' :: NonEmptyDMap k f -> NonEmptyDMap k f
    go' (NonEmptyDMap sx kx x l r) =
      case gcompare k kx of
        GLT -> NonEmptyDMap sx kx x (go l) r
        GGT -> NonEmptyDMap sx kx x l (go r)
        GEQ -> NonEmptyDMap sx kx (f kx x) l r
-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> DMap k f -> DMap k f
adjustWithKey f k = fst $ makeAdjustWithKey f k
-- | /O(log n)/. Adjust a value at a specific key. When the key is not
-- a member of the map, the original map is returned.
adjustWithKey :: GCompare k => (k v -> f v -> f v) -> k v -> NonEmptyDMap k f -> NonEmptyDMap k f
adjustWithKey f k = snd $ makeAdjustWithKey f k

One interesting side benefit is that rotations and other internal operations can be less partial. Take rotateL, for example:

rotateL :: k v -> f v -> DMap k f -> NonEmptyDMap k f -> NonEmptyDMap k f
rotateL k x l r@(NonEmptyDMap _ _ _ ly ry)
  | sizeE ly < ratio*sizeE ry = singleL k x l r
  | otherwise                 = doubleL k x l r

The non-empty argument proves that at least one left rotation is possible. (The double rotate is still partial.)

As my parenthetical above hints, I haven't yet investigated performance properly; rather my goal was to do just enough work to demonstrate that something like this might be possible. If this sort of refactor looks viable to you, maintainers, I'd be happy to take a stab at doing it for all of containers, along with hunting down any performance issues that arise.

@treeowl

This comment has been minimized.

Copy link
Member

commented Feb 27, 2019

It looks plausible, yes. It'll be a lot of work, though. Do you think you could implement some of the basic operations and get a sense of the performance?

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Feb 28, 2019

Glad to hear it! I'll start with something like the first commit of the DMap PR, mokus0/dependent-map@5985aad, to see just the performance impact of just the type change.

@treeowl

This comment has been minimized.

Copy link
Member

commented Feb 28, 2019

It would also be very nice to get a sense of the change in code size in one or two applications. I won't push too hard for that, but it'd be nice.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Mar 3, 2019

Are pattern synonyms OK (not too new) to use? I couldn't immediately tell.

@treeowl

This comment has been minimized.

Copy link
Member

commented Mar 3, 2019

We aim for more portability than that. But feel free to use them to get some quick benchmarks!

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Mar 9, 2019

Sorry for taking a bit; busy at work lately. Here's a branch with just the type change https://github.com/obsidiansystems/containers/tree/non-empty . Hope I'm not jinxing the optimizations being bullish, but know pattern synonyms so far.

@treeowl

This comment has been minimized.

Copy link
Member

commented Mar 9, 2019

So what do your benchmarks show so far?

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Mar 18, 2019

Sorry for the delays. It turns out that just as I opened this, I was heading into an especially busy period at work, so I haven't had much time for such open source things. Relatedly, I was being a bit daft and didn't realize you wanted me to run the benchmarks (should have read CONTRIBUTING.md and used common sense...).

Anyways, I did that now on GHC 8.6.3 with -O2, and the type change alone looks alright https://gist.github.com/Ericson2314/58709d0d99e0c0e83ad266701cd71841 . If anything, my type changes seems to have made it slightly faster (did not expect that!). Though I wouldn't also be surprised if there's nothing significant here; I ran them a few hours apart (while doing other things), so CPU temp differences or something might be distorting the results.

If the type change alone looks like a real and worthwhile performance benefit to you, I'd be happy to make the same change for all the containers, and only then sort out whether/how writing and exposing functions for the non-empty types makes sense.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Mar 30, 2019

@treeowl light ping :) --- I feel like a hypocrite after I taking a bit to respond my self, but have you had a chance to glance at those benchmarks? Just waiting for the signal to go do the same transformation on the other types.

@treeowl

This comment has been minimized.

Copy link
Member

commented Mar 30, 2019

I'm generally on board with this approach.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Apr 1, 2019

Sweet! I'll convert all the other types and make a PR.

@treeowl

This comment has been minimized.

Copy link
Member

commented Apr 1, 2019

You probably shouldn't bother with sequences, though. If it's possible to work a trick like that with sequences, it will be much more trouble than it's worth. It would make much more sense to fake non-empty sequences using smart constructors and such.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Apr 1, 2019

Right, let me roll back "all the other types" to just sticking to the family of Map, IntMap, Set, and IntSet`.

@treeowl

This comment has been minimized.

Copy link
Member

commented Apr 1, 2019

Er... Are you sure about those Int ones? Make sure they make sense, and make sure they're a separate PR, please. Also, did you ever see the WordMap stuff? It seems to have been abandoned, but it would be very interesting to see where it would go if picked up.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Apr 1, 2019

Oh oops completely forget that the Int ones are Patricia trees and also totally different. Nevermind then. The Nil constructor invariant begs for the more conventional newtype IntMap a = IntMap (UnpackingMaybe (NonEmptyIntMap a)), but until sums can be unpacked sadly that's not a pure win.

@treeowl

This comment has been minimized.

Copy link
Member

commented Apr 8, 2019

When do you expect to submit a proposal for non-empty Set and Map to the libraries list? It really shouldn't take long. Just get a good list of applications together.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Apr 8, 2019

Sorry I've also been hacking on GHC's build system a bit, spreading myself too thin again. It is indeed not too hard, and I can take a bunch of text from the original issue I opened.

@treeowl

This comment has been minimized.

Copy link
Member

commented Apr 15, 2019

Ping.

@Ericson2314

This comment has been minimized.

Copy link
Contributor Author

commented Apr 18, 2019

@Ericson2314 Ericson2314 referenced this issue Oct 8, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
2 participants
You can’t perform that action at this time.