Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
43 messages Options
123
Reply | Threaded
Open this post in threaded view
|

Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
If there's not an existing way to do this, I suppose this is a minor proposal.

When writing monadic code that consumes a container (Set, Map) etc, I often find that I just want what iterators in imperative languages provide:  that is, to iterate over the contents of a large container, performing monadic effects along the way, but without allocating.

The Foldable instance for Data.Map almost gives you what you want, but it only exposes the values, not their keys.  The "traverseWithKey" function is close too, but it builds a new Map as output:

traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)

So in practice what I do, and what I assume others do is this:

mapM_ f (toList myMap)

And I don't see any fusion rules that would ameliorate this (they seem limited to pure code), so I'm betting I always pay the cost of conversion to a list.

In the case of Data.Map the proposal is simply a "traverseWithKey_" that returns "t ()".  This follows the suffixing convention of mapM/mapM_ etc.

More generally, it would be nice to do an audit of all popular containers with the assumption of very large collections that cant' be frivolously copied.

   -Ryan

P.S. Actually, there are a number of places where the standard libraries could do with a more complete set of "_" functions -- e.g. it always chafes to not have "atomicModifyIORef_", which would apply a (a->a) function like a regular modifyIORef.


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Shachaf Ben-Kiki
On Tue, Jul 2, 2013 at 6:58 AM, Ryan Newton <[hidden email]> wrote:

> If there's not an existing way to do this, I suppose this is a minor
> proposal.
>
> When writing monadic code that consumes a container (Set, Map) etc, I often
> find that I just want what iterators in imperative languages provide:  that
> is, to iterate over the contents of a large container, performing monadic
> effects along the way, but without allocating.
>
> The Foldable instance for Data.Map almost gives you what you want, but it
> only exposes the values, not their keys.  The "traverseWithKey" function is
> close too, but it builds a new Map as output:
>
> traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k
> b)
>
> So in practice what I do, and what I assume others do is this:
>
> mapM_ f (toList myMap)
>
> And I don't see any fusion rules that would ameliorate this (they seem
> limited to pure code), so I'm betting I always pay the cost of conversion to
> a list.
>
> In the case of Data.Map the proposal is simply a "traverseWithKey_" that
> returns "t ()".  This follows the suffixing convention of mapM/mapM_ etc.
>
> More generally, it would be nice to do an audit of all popular containers
> with the assumption of very large collections that cant' be frivolously
> copied.
>
>    -Ryan
>
> P.S. Actually, there are a number of places where the standard libraries
> could do with a more complete set of "_" functions -- e.g. it always chafes
> to not have "atomicModifyIORef_", which would apply a (a->a) function like a
> regular modifyIORef.
>
>

Is there a reason you couldn't implement this just as well using
traverseWithKey, à la
http://hackage.haskell.org/packages/archive/lens/3.9.0.2/doc/html/Control-Lens-Fold.html#v:traverseOf_
? traverse-style functions let you choose your own Applicative, so
with the right choice of Applicative you can accumulate effects
without building up a new structure.

Of course, if you think this should be added for convenience, that's a
different matter, but the API already seems to provide the ability.

(Note: The implementation in lens uses undefined internally in one
place, but that's not necessary in general. See
https://github.com/ekmett/lens/issues/177 .)

    Shachaf

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Henning Thielemann
In reply to this post by Ryan Newton

On Tue, 2 Jul 2013, Ryan Newton wrote:

> If there's not an existing way to do this, I suppose this is a minor proposal.
> When writing monadic code that consumes a container (Set, Map) etc, I often find that I just want what
> iterators in imperative languages provide:  that is, to iterate over the contents of a large container,
> performing monadic effects along the way, but without allocating.
>
> The Foldable instance for Data.Map almost gives you what you want, but it only exposes the values, not their
> keys.  The "traverseWithKey" function is close too, but it builds a new Map as output:
>
> traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
>
> So in practice what I do, and what I assume others do is this:
>
> mapM_ f (toList myMap)
You could also do

   Map.foldrWithKey (\k a -> f k a >>) (return ())

which does not need an interim Map, or

   Foldable.sequence_ . Map.mapWithKey f

which looks more elegant.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Edward Kmett-2
In reply to this post by Ryan Newton
This could be implemented very easily with an appropriate Monoid with foldMapWithKey. I put in a proposal for adding it (and a ticket on containers) that received a couple of +1s, but I confess I never followed up on it with Milan and Johan after the proposal period ended.

A simpler construction that works today for this case would be to just use foldrWithKey or foldlWithKey.

-Edward

On Tue, Jul 2, 2013 at 9:58 AM, Ryan Newton <[hidden email]> wrote:
If there's not an existing way to do this, I suppose this is a minor proposal.

When writing monadic code that consumes a container (Set, Map) etc, I often find that I just want what iterators in imperative languages provide:  that is, to iterate over the contents of a large container, performing monadic effects along the way, but without allocating.

The Foldable instance for Data.Map almost gives you what you want, but it only exposes the values, not their keys.  The "traverseWithKey" function is close too, but it builds a new Map as output:

traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)

So in practice what I do, and what I assume others do is this:

mapM_ f (toList myMap)

And I don't see any fusion rules that would ameliorate this (they seem limited to pure code), so I'm betting I always pay the cost of conversion to a list.

In the case of Data.Map the proposal is simply a "traverseWithKey_" that returns "t ()".  This follows the suffixing convention of mapM/mapM_ etc.

More generally, it would be nice to do an audit of all popular containers with the assumption of very large collections that cant' be frivolously copied.

   -Ryan

P.S. Actually, there are a number of places where the standard libraries could do with a more complete set of "_" functions -- e.g. it always chafes to not have "atomicModifyIORef_", which would apply a (a->a) function like a regular modifyIORef.


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Edward Kmett-2
In reply to this post by Henning Thielemann
On Tue, Jul 2, 2013 at 2:45 PM, Henning Thielemann <[hidden email]> wrote:
  Foldable.sequence_ . Map.mapWithKey f 
 
which looks more elegant.
 
This has the unfortunate consequence that it builds an entire new map strictly before sequencing it, due to the fact that Data.Map is spine-strict. =(

-Edward

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Milan Straka
In reply to this post by Edward Kmett-2
Hi Edward,

> -----Original message-----
> From: Edward Kmett <[hidden email]>
> Sent: 2 Jul 2013, 14:51
>
> This could be implemented very easily with an appropriate Monoid with
> foldMapWithKey. I put in a proposal for adding it (and a ticket on
> containers) that received a couple of +1s, but I confess I never followed
> up on it with Milan and Johan after the proposal period ended.

Oh, I completely forgot. I went through the last year's mailboxes and
found it. Merging now :)

Cheers,
Milan

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
In reply to this post by Edward Kmett-2
Hi all,

Thanks for the responses.  I want to go through and make sure I understand these.

--------------------------------------------------------
First, Henning, won't both of these allocate in proportion to the size of the map?

    Map.foldrWithKey (\k a -> f k a >>) (return ())
    Foldable.sequence_ . Map.mapWithKey f

In particular, will the compiler be able to avoid allocating when building up that large monadic computation in the foldrWithKey?

--------------------------------------------------------
Edward said to use foldMapWithKey, which hasn't been released yet, but it sounds like it will be.


Even then, I might argue it is somewhat non-obvious to the programmers how to use this to do a non-allocating "for-each".  For example, I am not totally clear on what will happen with that tree of mappend calls -- will it allocate thunks?  Further, IO is not a monoid, so am I to create an instance of "Monoid (IO ())" in order to use foldMapWithKey to iterate over the Map?

--------------------------------------------------------
On Tue, Jul 2, 2013 at 10:29 AM, Shachaf Ben-Kiki <[hidden email]> wrote:
> Is there a reason you couldn't implement this just as well using traverseWithKey, à la
http://hackage.haskell.org/packages/archive/lens/3.9.0.2/doc/html/Control-Lens-Fold.html#v:traverseOf_

That function looks more overloaded than the traverse in Data.Map that I'm referring to, e.g. here:

I'm afraid I don't understand the proposal then -- is it to use lens somehow?  For the traversal I need to do over a Data.Map.Map, I need to fix 't' to be IO or Par or whatever I'm working with, so that the (k -> a -> t b) function I'm passing in can do the effects I need.  

To be specific I'm proposing providing these variants:

   traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
   traverseWithKey_ :: Applicative t => (k -> a -> t ()) -> Map k a -> t ()

And without exposing the latter natively, I still don't understand how to trick the former into not allocating, if that's the proposal.

   -Ryan


On Tue, Jul 2, 2013 at 2:54 PM, Edward Kmett <[hidden email]> wrote:
On Tue, Jul 2, 2013 at 2:45 PM, Henning Thielemann <[hidden email]> wrote:
  Foldable.sequence_ . Map.mapWithKey f 
 
which looks more elegant.
 
This has the unfortunate consequence that it builds an entire new map strictly before sequencing it, due to the fact that Data.Map is spine-strict. =(

-Edward


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Henning Thielemann

On Tue, 2 Jul 2013, Ryan Newton wrote:

> Hi all,
> Thanks for the responses.  I want to go through and make sure I understand these.
>
> --------------------------------------------------------
> First, Henning, won't both of these allocate in proportion to the size of the map?
>
>     Map.foldrWithKey (\k a -> f k a >>) (return ())
>     Foldable.sequence_ . Map.mapWithKey f
>
> In particular, will the compiler be able to avoid allocating when building up that large monadic computation
> in the foldrWithKey?
Since it is a foldr, the first action can be run without knowing the
following ones. That is, at no time all actions must be allocated.

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
In reply to this post by Ryan Newton
Ok, here's a little test to confirm what happens when you try to use foldrWithKey for this.

--------------------------------------------------------
import Control.DeepSeq
import GHC.Stats
import qualified Data.Map.Strict as M
import Data.Time.Clock
import Control.Exception
import System.Mem

main :: IO ()
main = do
  t0 <- getCurrentTime
  let m0 = M.fromList (map (\i -> (i,i)) [1..1000000::Int])
  evaluate$ rnf m0 
  t1 <- getCurrentTime
  performGC
  s1 <- getGCStats  
  putStrLn$"Constructed map in "++show (diffUTCTime t1 t0)++"\n "++ show s1++"\n"
  let fn 500000 v = putStrLn "Got it!"
      fn _      _ = return ()
  
  M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0
  t2 <- getCurrentTime
  performGC
  s2 <- getGCStats 
  putStrLn$"Consumed map in "++show (diffUTCTime t2 t0)++"\n "++ show s2++"\n"
  putStrLn$"Bytes allocated during consume:  "++show (bytesAllocated s2 - bytesAllocated s1)
  return ()
--------------------------------------------------------  


And here is the loop ("go10") generated "fn":

Ok, empirically, in -O2, the consumption phase allocates 32MB additional data (for a 1 million element map), and in -O0 it allocates 200MB.  Here's the recursive case of the loop:


((\ (eta_B1 :: GHC.Prim.State# GHC.Prim.RealWorld) ->
case x1_s2rr of _ {
__DEFAULT ->
((go10_r2uL z'_a10K r_a10S)
`cast` (<GHC.Types.NTCo:IO <()>>
~#
(GHC.Prim.State# GHC.Prim.RealWorld
-> (# GHC.Prim.State# GHC.Prim.RealWorld, () #))))
eta_B1;

Ok, so I didn't yet look at the STG where there's a clear allocation story.  So, actually, I'm not sure if this recursive case forces GHC to build some O(1M) first class representation of the IO action here, since eta is abstract?  At least, I'm assuming that's what the 32Mb-200Mb allocated is (though 32MB is actually rather skimpy for such a thing... it would have to spend only 4 words per closure...)




On Tue, Jul 2, 2013 at 3:32 PM, Ryan Newton <[hidden email]> wrote:
Hi all,

Thanks for the responses.  I want to go through and make sure I understand these.

--------------------------------------------------------
First, Henning, won't both of these allocate in proportion to the size of the map?

    Map.foldrWithKey (\k a -> f k a >>) (return ())
    Foldable.sequence_ . Map.mapWithKey f

In particular, will the compiler be able to avoid allocating when building up that large monadic computation in the foldrWithKey?

--------------------------------------------------------
Edward said to use foldMapWithKey, which hasn't been released yet, but it sounds like it will be.


Even then, I might argue it is somewhat non-obvious to the programmers how to use this to do a non-allocating "for-each".  For example, I am not totally clear on what will happen with that tree of mappend calls -- will it allocate thunks?  Further, IO is not a monoid, so am I to create an instance of "Monoid (IO ())" in order to use foldMapWithKey to iterate over the Map?

--------------------------------------------------------
On Tue, Jul 2, 2013 at 10:29 AM, Shachaf Ben-Kiki <[hidden email]> wrote:
> Is there a reason you couldn't implement this just as well using traverseWithKey, à la
http://hackage.haskell.org/packages/archive/lens/3.9.0.2/doc/html/Control-Lens-Fold.html#v:traverseOf_

That function looks more overloaded than the traverse in Data.Map that I'm referring to, e.g. here:

I'm afraid I don't understand the proposal then -- is it to use lens somehow?  For the traversal I need to do over a Data.Map.Map, I need to fix 't' to be IO or Par or whatever I'm working with, so that the (k -> a -> t b) function I'm passing in can do the effects I need.  

To be specific I'm proposing providing these variants:

   traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map k b)
   traverseWithKey_ :: Applicative t => (k -> a -> t ()) -> Map k a -> t ()

And without exposing the latter natively, I still don't understand how to trick the former into not allocating, if that's the proposal.

   -Ryan


On Tue, Jul 2, 2013 at 2:54 PM, Edward Kmett <[hidden email]> wrote:
On Tue, Jul 2, 2013 at 2:45 PM, Henning Thielemann <[hidden email]> wrote:
  Foldable.sequence_ . Map.mapWithKey f 
 
which looks more elegant.
 
This has the unfortunate consequence that it builds an entire new map strictly before sequencing it, due to the fact that Data.Map is spine-strict. =(

-Edward



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Shachaf Ben-Kiki
In reply to this post by Ryan Newton
On Tue, Jul 2, 2013 at 12:32 PM, Ryan Newton <[hidden email]> wrote:

> On Tue, Jul 2, 2013 at 10:29 AM, Shachaf Ben-Kiki <[hidden email]> wrote:
>> Is there a reason you couldn't implement this just as well using
>> traverseWithKey, à la
>>
>> http://hackage.haskell.org/packages/archive/lens/3.9.0.2/doc/html/Control-Lens-Fold.html#v:traverseOf_
>
> That function looks more overloaded than the traverse in Data.Map that I'm
> referring to, e.g. here:
>
> http://www.haskell.org/ghc/docs/latest/html/libraries/containers/Data-Map-Strict.html#g:13
>
> I'm afraid I don't understand the proposal then -- is it to use lens
> somehow?  For the traversal I need to do over a Data.Map.Map, I need to fix
> 't' to be IO or Par or whatever I'm working with, so that the (k -> a -> t
> b) function I'm passing in can do the effects I need.
>
> To be specific I'm proposing providing these variants:
>
>    traverseWithKey :: Applicative t => (k -> a -> t b) -> Map k a -> t (Map
> k b)
>    traverseWithKey_ :: Applicative t => (k -> a -> t ()) -> Map k a -> t ()
>
> And without exposing the latter natively, I still don't understand how to
> trick the former into not allocating, if that's the proposal.
>
>    -Ryan
>

The suggestion is that

(a) You can derive a balanced foldMapWithKey from traverseWithKey, as follows:

    foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
    foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k x))

Since the Applicative used is Const (newtype Const m a = Const m), the
structure is never built up.

(b) You can derive traverseWithKey_ from foldMapWithKey, e.g. as follows:

    newtype Traverse_ f = Traverse_ { runTraverse_ :: f () }

    instance Applicative f => Monoid (Traverse_ f) where
      mempty = Traverse_ (pure ())
      Traverse_ a `mappend` Traverse_ b = Traverse_ (a *> b)

    traverseWithKey_ :: Applicative f => (k -> a -> f ()) -> M.Map k a -> f ()
    traverseWithKey_ f = runTraverse_ . foldMapWithKey (\k x ->
Traverse_ (void (f k x)))

As Henning and Edward pointed out, though, foldrWithKey/foldlWithKey
are already exported by Data.Map (and they give you right/left
associativity, so they're possibly better... Of course, you can derive
them from traverseWithKey too!).

    Shachaf

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
In reply to this post by Henning Thielemann

In particular, will the compiler be able to avoid allocating when building up that large monadic computation
in the foldrWithKey?

Since it is a foldr, the first action can be run without knowing the following ones. That is, at no time all actions must be allocated.

Hi all,

Well, to test it out I went ahead and made a patch to containers, here:


Henning, while I agree with you that GHC shouldn't truly *need* to generate a first class representation of that 10M-step monadic action... it remains the case that the updated test (attached to the end of this email), shows the traverseWithKey_ version allocating only 200K, whereas the foldrWithKey allocates 32M.

Further, I argue that the traverseWithKey_ version is clearer to programmers that don't yet grok the first class nature of monadic actions (e.g. a fold to build up one big monadic action).  And again, if we are not sure of the performance implications of that in this thread, I imagine many Haskell programmers would not be.

So unless there's a strong counterargument, I propose the above patch for acceptance.

   -Ryan

P.S. Using the HEAD version of cabal the allocation for -O0 foldrWithKey actually went up from 200M to 300M.

Appendix: updated code below and at this URL:
--------------------------------------------
import Control.DeepSeq
import GHC.Stats
import qualified Data.Map.Strict as M
import Data.Time.Clock
import Control.Exception
import System.Mem

main :: IO ()
main = do
  t0 <- getCurrentTime
  let m0 = M.fromList (map (\i -> (i,i)) [1..1000000::Int])
  evaluate$ rnf m0 
  t1 <- getCurrentTime
  performGC
  s1 <- getGCStats  
  putStrLn$"Constructed map in "++show (diffUTCTime t1 t0)++"\n "++ show s1++"\n"
  let fn 500000 v = putStrLn "Got it!"
      fn _      _ = return ()

  -- Regular traverseWithKey uses 48MB
  -- traverseWithKey_ usse 200K of allocation:
  M.traverseWithKey_ fn m0
  t2 <- getCurrentTime
  performGC
  s2 <- getGCStats 
  putStrLn$"[traverseWithKey_] Consumed map in "++show (diffUTCTime t2 t1)++"\n "++ show s2++"\n"
  putStrLn$"Bytes allocated during consume:  "++show (bytesAllocated s2 - bytesAllocated s1)

  -- foldrWithKey uses 32MB allocation:
  M.foldrWithKey (\k a -> (fn k a >>)) (return ()) m0
  t3 <- getCurrentTime
  performGC
  s3 <- getGCStats 
  putStrLn$"[foldrWithKey] Consumed map in "++show (diffUTCTime t3 t2)++"\n "++ show s3++"\n"
  putStrLn$"Bytes allocated during consume:  "++show (bytesAllocated s3 - bytesAllocated s2)
  return ()



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
In reply to this post by Shachaf Ben-Kiki

    foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
    foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k x))

Shachaf, thanks for fleshing it out.  I updated the test with your version as well:


In short, it performs exactly the same as the foldrWithKey version, as you pointed out (32M allocation).  

In both cases, using first class monadic/applicative values seems to foil GHC.

And btw, these do show the scaling you would expect, on 2M elements, it allocates 64MB, 4M -> 128MB, and so on, whereas the traverseWithKey_ version allocates a constant amount.

  -Ryan


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Roman Cheplyaka-2
In reply to this post by Henning Thielemann
* Henning Thielemann <[hidden email]> [2013-07-02 21:57:58+0200]

>
> On Tue, 2 Jul 2013, Ryan Newton wrote:
>
> >Hi all,
> >Thanks for the responses.  I want to go through and make sure I understand these.
> >
> >--------------------------------------------------------
> >First, Henning, won't both of these allocate in proportion to the size of the map?
> >
> >    Map.foldrWithKey (\k a -> f k a >>) (return ())
> >    Foldable.sequence_ . Map.mapWithKey f
> >
> >In particular, will the compiler be able to avoid allocating when building up that large monadic computation
> >in the foldrWithKey?
>
> Since it is a foldr, the first action can be run without knowing the
> following ones. That is, at no time all actions must be allocated.

It's not a foldr you would expect.
Here's the code:

  foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
  foldrWithKey f z = go z
    where
      go z' Tip             = z'
      go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l

You can see that 'go' is (partially) driven by the tree structure.

A more foldr-y foldr would look like

  foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
  foldrWithKey f z = go z
    where
      go z' Tip             = z'
      go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)

Perhaps this should be fixed? (Note that I haven't done any testing.)

Another note: I guess "non-allocating" in the title means that we're not
allocating anything of the order of map size. Some stack-like allocation
is inevitable since we're working with a tree, but it will be
logarithmic in the map size.

But then, it seems to me that the current version of foldrWithKey
should satsify that criterion, only with a big(ger) constant factor.
It always traverses the left branch accumulating z, then yields control
to f.

Roman

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton
In my case, I'm trying to avoid heap allocation, because in parallel haskell it is death to performance.

My claim is that:
  • current version of foldrWithKey heap allocates in proportion to the input size
  • my proposed traverseWithKey_ doesn't 
  • traverseWithKey_ may be a more obvious an idiom to some programmers than folding to compose an IO action (requires understanding the detailed interaction of laziness, optimizations, and first class IO actions)
It sounds like Roman's alternate foldrWithKey will be an improvement as well, so I'll test it.

   -Ryan


On Thu, Jul 4, 2013 at 12:41 PM, Roman Cheplyaka <[hidden email]> wrote:
* Henning Thielemann <[hidden email]> [2013-07-02 21:57:58+0200]
>
> On Tue, 2 Jul 2013, Ryan Newton wrote:
>
> >Hi all,
> >Thanks for the responses.  I want to go through and make sure I understand these.
> >
> >--------------------------------------------------------
> >First, Henning, won't both of these allocate in proportion to the size of the map?
> >
> >    Map.foldrWithKey (\k a -> f k a >>) (return ())
> >    Foldable.sequence_ . Map.mapWithKey f
> >
> >In particular, will the compiler be able to avoid allocating when building up that large monadic computation
> >in the foldrWithKey?
>
> Since it is a foldr, the first action can be run without knowing the
> following ones. That is, at no time all actions must be allocated.

It's not a foldr you would expect.
Here's the code:

  foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
  foldrWithKey f z = go z
    where
      go z' Tip             = z'
      go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l

You can see that 'go' is (partially) driven by the tree structure.

A more foldr-y foldr would look like

  foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
  foldrWithKey f z = go z
    where
      go z' Tip             = z'
      go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)

Perhaps this should be fixed? (Note that I haven't done any testing.)

Another note: I guess "non-allocating" in the title means that we're not
allocating anything of the order of map size. Some stack-like allocation
is inevitable since we're working with a tree, but it will be
logarithmic in the map size.

But then, it seems to me that the current version of foldrWithKey
should satsify that criterion, only with a big(ger) constant factor.
It always traverses the left branch accumulating z, then yields control
to f.

Roman


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Andreas Abel
In reply to this post by Roman Cheplyaka-2
Hello Roman,

On 04.07.2013 19:41, Roman Cheplyaka wrote:

> It's not a foldr you would expect.
> Here's the code:
>
>    foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>    foldrWithKey f z = go z
>      where
>        go z' Tip             = z'
>        go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l
>
> You can see that 'go' is (partially) driven by the tree structure.

This called an in-order traversal of the tree.  (The node is handled
in-between the sub trees.)

   foldrWithKey f z = foldr (uncurry f) z . toAscList

> A more foldr-y foldr would look like
>
>    foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>    foldrWithKey f z = go z
>      where
>        go z' Tip             = z'
>        go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)

This is a post-order traversal. (The node is handled after the
subtrees.)  This is a different thing.

> Perhaps this should be fixed?

I don't think so.  You would change the semantics.  (Try to convert a
Map into an ascending key-value list with your new definition.)

Cheers,
Andreas

--
Andreas Abel  <><      Du bist der geliebte Mensch.

Theoretical Computer Science, University of Munich
Oettingenstr. 67, D-80538 Munich, GERMANY

[hidden email]
http://www2.tcs.ifi.lmu.de/~abel/

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Roman Cheplyaka-2
* Andreas Abel <[hidden email]> [2013-07-04 23:41:45+0300]

> Hello Roman,
>
> On 04.07.2013 19:41, Roman Cheplyaka wrote:
> >It's not a foldr you would expect.
> >Here's the code:
> >
> >   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
> >   foldrWithKey f z = go z
> >     where
> >       go z' Tip             = z'
> >       go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l
> >
> >You can see that 'go' is (partially) driven by the tree structure.
>
> This called an in-order traversal of the tree.  (The node is handled
> in-between the sub trees.)
>
>   foldrWithKey f z = foldr (uncurry f) z . toAscList
>
> >A more foldr-y foldr would look like
> >
> >   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
> >   foldrWithKey f z = go z
> >     where
> >       go z' Tip             = z'
> >       go z' (Bin _ kx x l r) = f kx x (go (go z' r) l)
>
> This is a post-order traversal. (The node is handled after the
> subtrees.)  This is a different thing.
>
> >Perhaps this should be fixed?
>
> I don't think so.  You would change the semantics.  (Try to convert a
> Map into an ascending key-value list with your new definition.)

Thanks Andreas, I missed the fact that this transformation changes the
traversal order. (Although I believe my version is pre-order, not
post-order.)

The same applies to the Ryan's traverseWithKey_, by the way — in his
patch he also handles the node before the subtrees. But that's easily
fixable.

After playing a bit with Ryan's benchmark, I no longer think that the
order matters much for the total number of allocations. Nor do I believe
in first-class vs non-first-class IO actions. All that should matter is
how many allocations we can move to the stack. But I haven't yet figured
out why exactly different versions differ so drastically in this regard.

Roman

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Ryan Newton

After playing a bit with Ryan's benchmark, I no longer think that the
order matters much for the total number of allocations. Nor do I believe
in first-class vs non-first-class IO actions. All that should matter is
how many allocations we can move to the stack. But I haven't yet figured
out why exactly different versions differ so drastically in this regard.

Yeah, it's all rather different to predict in advance, isn't it?

I tried your alternate foldrWithKey and I saw it heap allocating as well.

Further, -O0 vs. -O2 can make a big difference.  It's a little frustrating because for dealing efficiently with big data sets, especially in parallel.  It would be nice to have big-O numbers in the docs for heap allocation as well as time cost -- and ones you could trust irrespective of optimize level.

By the way, is traverse/traverseWithKey supposed to guarantee a specific order?  The doc uses this code in the definition:

    traverse ((k, v) -> (,) k $ f k v) (toList m)

And I thought "toList" didn't guarantee anything (as opposed to toAscList)...


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

John Lato-2
Slightly off-topic, but why do you care about the performance of code compiled with -O0?  I can think of at least one valid reason for doing so, but even for that particular instance I doubt that changing the code is the proper solution.

Aside from that, I definitely agree that most packages could do a better job documenting the heap usage of functions.


On Fri, Jul 5, 2013 at 8:41 AM, Ryan Newton <[hidden email]> wrote:

After playing a bit with Ryan's benchmark, I no longer think that the
order matters much for the total number of allocations. Nor do I believe
in first-class vs non-first-class IO actions. All that should matter is
how many allocations we can move to the stack. But I haven't yet figured
out why exactly different versions differ so drastically in this regard.

Yeah, it's all rather different to predict in advance, isn't it?

I tried your alternate foldrWithKey and I saw it heap allocating as well.

Further, -O0 vs. -O2 can make a big difference.  It's a little frustrating because for dealing efficiently with big data sets, especially in parallel.  It would be nice to have big-O numbers in the docs for heap allocation as well as time cost -- and ones you could trust irrespective of optimize level.

By the way, is traverse/traverseWithKey supposed to guarantee a specific order?  The doc uses this code in the definition:

    traverse ((k, v) -> (,) k $ f k v) (toList m)

And I thought "toList" didn't guarantee anything (as opposed to toAscList)...


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

John Lato-2
Upon re-reading, this was much more terse than I intended, mostly because I didn't want to get bogged down in an off-topic tangent.  What I mean is that I think it's quite rare indeed to be in a situation where you care about performance, code with -O2 performs acceptably well, but being performance-bound at -O0 is a serious hindrance.

But that's my own experience, and I'm sure that others have had different experiences.  And this issue in particular comes up often enough that I'm sure there's something I'm missing.  Hence my question.


On Fri, Jul 5, 2013 at 10:48 AM, John Lato <[hidden email]> wrote:
Slightly off-topic, but why do you care about the performance of code compiled with -O0?  I can think of at least one valid reason for doing so, but even for that particular instance I doubt that changing the code is the proper solution.

Aside from that, I definitely agree that most packages could do a better job documenting the heap usage of functions.


On Fri, Jul 5, 2013 at 8:41 AM, Ryan Newton <[hidden email]> wrote:

After playing a bit with Ryan's benchmark, I no longer think that the
order matters much for the total number of allocations. Nor do I believe
in first-class vs non-first-class IO actions. All that should matter is
how many allocations we can move to the stack. But I haven't yet figured
out why exactly different versions differ so drastically in this regard.

Yeah, it's all rather different to predict in advance, isn't it?

I tried your alternate foldrWithKey and I saw it heap allocating as well.

Further, -O0 vs. -O2 can make a big difference.  It's a little frustrating because for dealing efficiently with big data sets, especially in parallel.  It would be nice to have big-O numbers in the docs for heap allocation as well as time cost -- and ones you could trust irrespective of optimize level.

By the way, is traverse/traverseWithKey supposed to guarantee a specific order?  The doc uses this code in the definition:

    traverse ((k, v) -> (,) k $ f k v) (toList m)

And I thought "toList" didn't guarantee anything (as opposed to toAscList)...


_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries




_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

Shachaf Ben-Kiki
In reply to this post by Ryan Newton
On Tue, Jul 2, 2013 at 1:46 PM, Ryan Newton <[hidden email]> wrote:

>
>>     foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
>>     foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k
>> x))
>
>
> Shachaf, thanks for fleshing it out.  I updated the test with your version
> as well:
>
>    https://gist.github.com/rrnewton/5912908
>
> In short, it performs exactly the same as the foldrWithKey version, as you
> pointed out (32M allocation).
>
> In both cases, using first class monadic/applicative values seems to foil
> GHC.
>
> And btw, these do show the scaling you would expect, on 2M elements, it
> allocates 64MB, 4M -> 128MB, and so on, whereas the traverseWithKey_ version
> allocates a constant amount.
>
>   -Ryan
>

If you're actually benchmarking it, you should note a few things:

* As I mentioned, lens's actual implementation of this function is
slightly different:

    -- The argument 'a' of the result should not be used!
    newtype Traversed a f = Traversed { getTraversed :: f a }
    instance Applicative f => Monoid (Traversed a f) where
      mempty = Traversed (pure (error "Traversed: value used"))
      Traversed ma `mappend` Traversed mb = Traversed (ma *> mb)

with one "void" applied at the very end of the fold, instead of one in
each step. This may or may not be better; it should probably be
measured.

* Following a discussion with Milan off-list, he implemented a simple
optimization in traverseWithKey which might have a significant impact.
See https://github.com/haskell/containers/commit/4d24ff5d08f0bb27ca73a9888286d6426149515b
. It should probably be considered in these benchmarks.

* I haven't thought it through, but it's possible that using a
"difference monoid" -- i.e. folding with Endo, the way
Data.Foldable.foldr is implemented by default -- would also be useful
to measure, to compare with the existing foldrWithKey.

    Shachaf

_______________________________________________
Libraries mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/libraries
123