Deserializing maps and sets

[sjakobi]

binary, cereal and store all deserialize Sets, IntSets, Maps and IntMaps via fromDistinctAscList <$> deserializeList or even fromList <$> deserializeList and I've been wondering if that's the best way to do it.

The problem seems to be that this will first completely build the intermediary list before the map or set is constructed from the list.

Instead, it seems to me that the set or map should be built by repeatedly inserting a single element.

Do you agree that this should save a lot of memory allocations?

What I think is missing from containers to support the alternative deserialization implementations is something like a insertDistinctMax function that can efficiently insert an element that is known to be strictly greater than all elements in the set/map.

[treeowl]

Nope; I don't agree. `fromDistinctAscList` (which is probably what they should all be using) is quite clever. It can reasonably be expected to be faster and to allocate less than building the set/map one element at a time, even taking the intermediate list into account. It might be possible to write a version of `fromDistinctAscList` that would accept one element at a time; that may be friendlier to the garbage collector. It would require restructuring it to use an explicit stack, I believe. Should definitely be doable.

…

On Wed, Feb 15, 2017 at 4:33 PM, Simon Jakobi ***@***.***> wrote: binary, cereal and store all deserialize Sets, IntSets, Maps and IntMaps via fromDistinctAscList <$> deserializeList or even fromList <$> deserializeList and I've been wondering if that's the best way to do it. The problem seems to be that this will first completely build the intermediary list before the map or set is constructed from the list. Instead, it seems to me that the set or map should be built by repeatedly inserting a single element. Do you agree that this should save a lot of memory allocations? What I think is missing from containers to support the alternative deserialization implementations is something like a insertDistinctMax function that can efficiently insert an element that is known to be strictly greater than all elements in the set/map. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#405>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_bENSSDZBGln_voX7KxH_sE7n-1Yks5rc29CgaJpZM4MCRmt> .

[treeowl]

Actually, it would be even better to use a version that takes the (recorded) size as an argument.

…

On Wed, Feb 15, 2017 at 6:12 PM, David Feuer ***@***.***> wrote: Nope; I don't agree. `fromDistinctAscList` (which is probably what they should all be using) is quite clever. It can reasonably be expected to be faster and to allocate less than building the set/map one element at a time, even taking the intermediate list into account. It might be possible to write a version of `fromDistinctAscList` that would accept one element at a time; that may be friendlier to the garbage collector. It would require restructuring it to use an explicit stack, I believe. Should definitely be doable. On Wed, Feb 15, 2017 at 4:33 PM, Simon Jakobi ***@***.***> wrote: > binary, cereal and store all deserialize Sets, IntSets, Maps and IntMaps > via fromDistinctAscList <$> deserializeList or even fromList <$> > deserializeList and I've been wondering if that's the best way to do it. > > The problem seems to be that this will first completely build the > intermediary list before the map or set is constructed from the list. > > Instead, it seems to me that the set or map should be built by repeatedly > inserting a single element. > > Do you agree that this should save a lot of memory allocations? > > What I think is missing from containers to support the alternative > deserialization implementations is something like a insertDistinctMax > function that can efficiently insert an element that is known to be > strictly greater than all elements in the set/map. > > — > You are receiving this because you are subscribed to this thread. > Reply to this email directly, view it on GitHub > <#405>, or mute the thread > <https://github.com/notifications/unsubscribe-auth/ABzi_bENSSDZBGln_voX7KxH_sE7n-1Yks5rc29CgaJpZM4MCRmt> > . >

[sjakobi]

Actually, it would be even better to use a version that takes the
(recorded) size as an argument.

Right, I had been thinking about that too, but thought it wasn't worthwhile. Now that you mention it, it seems to me that knowing the size of the container beforehand should make it possible to build the tree without any rebalancing.

I guess what I'm looking for is something like (Monad m, Ord a) => Int -> m a -> m (Set a)

[sjakobi]

I can definitely recommend fromDistinctAscList for now: mgsloan/store#96

[m-renaud]

At the minimum we should add this recommendation to the docs somewhere.

[sjakobi]

Actually, it would be even better to use a version that takes the
(recorded) size as an argument.

Here's a first implementation of such a function:

fromDistinctAscListOfSize :: Size -> [a] -> Set a
fromDistinctAscListOfSize n xs =
    case List.splitAt n' xs of
      (_, [] ) -> Tip
      (l, x:r) -> Bin n x (fromDistinctAscListOfSize n'           l)
                          (fromDistinctAscListOfSize (n - n' - 1) r)
  where n' = n `shiftR` 1

I haven't benchmarked it yet.

[treeowl]

The first split allocates n/2 conses. The next splits allocate n/4+n/4=n/2. This smells linearithmic, which is worse than the linear fromDistinctAscList. We can do better!

[sjakobi]

A new version that avoids the conses:

fromDistinctAscListOfSize :: Size -> [a] -> Set a
fromDistinctAscListOfSize sz xs =
    case go sz xs of
      (s, []) -> s
      _       -> error "Set.fromDistinctAscListOfSize: List is longer than expected"
  where
    go :: Size -> [a] -> (Set a, [a])
    go n xs0
      | n <= 0    = (Tip, xs0)
      | otherwise = case go n_half xs0 of
                      (l, x:xs1) ->
                        let (r, xs2) = go (n - n_half - 1) xs1
                        in (Bin n x l r, xs2)
                      _ -> error "Set.fromDistinctAscListOfSize: List is shorter than expected"
      where n_half = n `unsafeShiftR` 1

No benchmarks yet.

[treeowl]

Yes, better. We should probably have something like this. But let's also go back to the beginning. What you've written here is shaped an awful lot like a parser, isn't it? The list of remaining elements is the parser state. To get back to your original idea, we need to weave in the deserialization monad:

deserializeSet
  :: Monad m
  => Size
  -> m (Maybe a)
  -> m (Maybe (Set a))
deserializeSet size elem = ...

We don't depend on transformers, but we have our own copy of StateT and we can add one of MaybeT if that would be convenient.

[treeowl]

Roughly speaking, at least,

deserializeSet
  :: Monad m
  => Size
  -> m (Maybe a)
  -> m (Maybe (Set a))
deserializeSet sz = runMaybeT . go sz . MaybeT
  where
    go :: Size -> MaybeT m a -> MaybeT m (Set a)
    go n elem
      | n <= 0    = pure Tip
      | otherwise = do
           l <- go n_half elem
           x <- elem
           r <- go (n - n_half - 1) elem
           pure $! Bin n x l r
        where n_half = n `unsafeShiftR` 1

But we should probably pull out elem and inline everything.

[treeowl]

Oh, what am I thinking? Much better:

deserializeSet
  :: Monad m
  => Size
  -> m a
  -> m (Set a)
deserializeSet sz elem = go sz
  where
    -- go :: Size -> m (Set a)
    go n
      | n <= 0    = pure Tip
      | otherwise = do
           l <- go n_half
           x <- elem
           r <- go (n - n_half - 1)
           pure $! Bin n x l r
        where n_half = n `unsafeShiftR` 1

[treeowl]

Actually, I think we probably want to shift names and offer two versions:

deserialize
  :: Applicative m
  => Size
  -> m a
  -> m (Set a)
deserialize sz elem = go sz
  where
    -- go :: Size -> m (Set a)
    go n
      | n <= 0
      = pure Tip
      | otherwise
      = liftA3 (Bin n)
           (go n_half)
           elem
           (go (n - n_half - 1))
      where n_half = n `unsafeShiftR` 1

deserialize'
  :: Monad m
  => Size
  -> m a
  -> m (Set a)
deserialize' sz elem = go sz
  where
    -- go :: Size -> m (Set a)
    go n
      | n <= 0    = pure Tip
      | otherwise = do
           l <- go n_half
           x <- elem
           r <- go (n - n_half - 1)
           pure $! Bin n x l r
      where n_half = n `unsafeShiftR` 1

[sjakobi]

Nice! :) I hadn't realized that Applicative would be enough!

What's the point of offering an additional Monad version though?