<html><head><style>
body {
font-family: "Helvetica Neue", Helvetica, Arial, sans-serif;
padding:1em;
margin:auto;
background:#fefefe;
}
h1, h2, h3, h4, h5, h6 {
font-weight: bold;
}
h1 {
color: #000000;
font-size: 28pt;
}
h2 {
border-bottom: 1px solid #CCCCCC;
color: #000000;
font-size: 24px;
}
h3 {
font-size: 18px;
}
h4 {
font-size: 16px;
}
h5 {
font-size: 14px;
}
h6 {
color: #777777;
background-color: inherit;
font-size: 14px;
}
hr {
height: 0.2em;
border: 0;
color: #CCCCCC;
background-color: #CCCCCC;
display: inherit;
}
p, blockquote, ul, ol, dl, li, table, pre {
margin: 15px 0;
}
a, a:visited {
color: #4183C4;
background-color: inherit;
text-decoration: none;
}
#message {
border-radius: 6px;
border: 1px solid #ccc;
display:block;
width:100%;
height:60px;
margin:6px 0px;
}
button, #ws {
font-size: 12 pt;
padding: 4px 6px;
border-radius: 5px;
border: 1px solid #bbb;
background-color: #eee;
}
code, pre, #ws, #message {
font-family: Monaco;
font-size: 10pt;
border-radius: 3px;
background-color: #F8F8F8;
color: inherit;
}
code {
border: 1px solid #EAEAEA;
margin: 0 2px;
padding: 0 5px;
}
pre {
border: 1px solid #CCCCCC;
overflow: auto;
padding: 4px 8px;
}
pre > code {
border: 0;
margin: 0;
padding: 0;
}
#ws { background-color: #f8f8f8; }
.bloop_markdown table {
border-collapse: collapse;
font-family: Helvetica, arial, freesans, clean, sans-serif;
color: rgb(51, 51, 51);
font-size: 15px; line-height: 25px;
padding: 0; }
.bloop_markdown table tr {
border-top: 1px solid #cccccc;
background-color: white;
margin: 0;
padding: 0; }
.bloop_markdown table tr:nth-child(2n) {
background-color: #f8f8f8; }
.bloop_markdown table tr th {
font-weight: bold;
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px; }
.bloop_markdown table tr td {
border: 1px solid #cccccc;
margin: 0;
padding: 6px 13px; }
.bloop_markdown table tr th :first-child, table tr td :first-child {
margin-top: 0; }
.bloop_markdown table tr th :last-child, table tr td :last-child {
margin-bottom: 0; }
.bloop_markdown blockquote{
border-left: 4px solid #dddddd;
padding: 0 15px;
color: #777777; }
blockquote > :first-child {
margin-top: 0; }
blockquote > :last-child {
margin-bottom: 0; }
code, pre, #ws, #message {
word-break: normal;
word-wrap: normal;
}
hr {
display: inherit;
}
.bloop_markdown :first-child {
-webkit-margin-before: 0;
}
code, pre, #ws, #message {
font-family: Menlo, Consolas, Liberation Mono, Courier, monospace;
}
.send { color:#77bb77; }
.server { color:#7799bb; }
.error { color:#AA0000; }</style></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;"><div class="bloop_markdown"><p></p></div><div class="bloop_original_html"><style>body{font-family:Helvetica,Arial;font-size:13px}</style><div id="bloop_customfont" style="font-family:Helvetica,Arial;font-size:13px; color: rgba(0,0,0,1.0); margin: 0px; line-height: auto;">On August 3, 2015 at 8:28:02 AM, Jake McArthur (<a href="mailto:jake.mcarthur@gmail.com">jake.mcarthur@gmail.com</a>) wrote:</div> <div><blockquote type="cite" class="clean_bq" style="color: rgb(0, 0, 0); font-family: Helvetica, Arial; font-size: 13px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><span><div><div></div><div><p dir="ltr">Vector also does something like what your are describing. I think the phrase to google for is "array recycling".</p><br><div class="gmail_quote"><div dir="ltr">On 11:56PM, Fri, Jul 31, 2015 William Yager <<a href="mailto:will.yager@gmail.com">will.yager@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin: 0px 0px 0px 0.8ex; border-left-width: 1px; border-left-color: rgb(204, 204, 204); border-left-style: solid; padding-left: 1ex;"><div dir="ltr">Has anyone done any research into fusing operations that involve thawing some data, mutating it, and then freezing it again?<div><br></div><div>Data.Vector does something similar; it turns vectors into streams, operates on the streams, and then turns them back into vectors. It can fuse these operations by removing intermediate However, I've done a bit of preliminary work on a fusion system that works on operations of the form </div><div><br></div><div> runST $ do </div><div> x' <- thaw x</div><div> foo x'</div><div> freeze x'</div><div><br></div><div>and yields promising results in some cases. This could be useful for data structures that aren't stream-able, but suffer from lots of unnecessary freezing and unfreezing. </div><div><br></div><div>This seems like the sort of thing that someone would have already done, so I wanted to check if anyone knew of any previous work on this.</div><div><br></div><div>Cheers,</div><div>Will</div></div>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org" target="_blank">Haskell-Cafe@haskell.org</a><br><a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br></blockquote></div>_______________________________________________<span class="Apple-converted-space"> </span><br>Haskell-Cafe mailing list<span class="Apple-converted-space"> </span><br>Haskell-Cafe@haskell.org<span class="Apple-converted-space"> </span><br>http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe<span class="Apple-converted-space"> </span></div></div></span></blockquote></div><p><br></p><p><br></p></div><div class="bloop_markdown"><p></p>
<p>I’d be interested in knowing about the preliminary work you’re doing here. I’ve got a port of Clojure’s persistent vectors (pvector for short) in development right now, and I’m working on figuring out how to batch consecutive pure modifications of a pvector into doing cheaper operations on the mutable version before converting it into the immutable version again.
Here are the operations scenarios that I’m especially interested in optimizing this way:</p>
<pre><code>{- each of these requires cloning a 32-element array.
optimizing consecutive snocs is important because
fromList is defined as (foldl' snoc empty)
-}
update1 :: Vector a -> Int -> a -> Vector a
snoc :: Vector a -> a -> Vector a
unsnoc :: Vector a -> Maybe (a, Vector a)
{- requires cloning <= N/32 arrays, where N is length of update batch -}
update :: Vector a -> Vector (Int, a) -> Vector a
{- would be nice to preallocate a fully-sized pvector for consecutive concats.
for example (\vs -> foldr concat empty vs)
-}
concat :: Vector a -> Vector a -> Vector a
</code></pre>
<p>I only just started working on freeze/thaw fusion myself, so I haven’t gotten far at all. One trick that I’ve got in place in the transient structure to make this cheaper though is how I track modifications of the persistent vector. The immutable version is represented like so:</p>
<pre><code class="haskell">data Node a
= Leaf !(Array a) {- Array here from primitive package -}
| Branch !(Array (Node a))
| EmptyNode
data Vector a = Vector
{ vCount :: !Int
, vShift :: !Int
, vRoot :: !(Node a)
, vTail :: !(Array a)
, vTailCount :: !Int
}
And then here’s the transient version:
data TransientNode s a
= UneditedLeaf !(Array a)
| UneditedBranch !(Array (Node a))
| EditedLeaf !(MutableArray s a)
| EditedBranch !(MutableArray s (TransientNode s a))
| EmptyTransientNode
data TransientVector s a = TransientVector
{ tvCount :: !Int
, tvShift :: !Int
, tvRoot :: !(TransientNode s a)
, tvTail :: !(MutableArray s a)
, tvTailEdited :: !Bool
, tvTailCount :: !Int
}
</code></pre>
<p>When the persistent version is converted to the transient version, the data structure tracks which children have been modified over the course of operations on the transient structure. So, when the mutable version is converted back into the persistent version, any of the underlying arrays which haven’t been touched are still shared with any of the other live pvectors that are referencing them. That’s not specifically relevant to fusion, but it does make it quite cheap to go roundtrip from persistent->transient->persistent again.</p></div></body></html>