[Haskell-cafe] library for set of heterogeneous values?
Anthony Clayden
David Feuer
should look (at least for inspiration) at both vinyl and
dependent-map.
> _______________________________________________
> Haskell-Cafe mailing list
> To (un)subscribe, modify options or view archives go to:
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
> Only members subscribed via the mailman list are allowed to post.
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Яшин Сергей
Anthony Clayden
> but you should look (at least for inspiration) at both
> vinyl and dependent-map.
vinyl is a record 'solution', not a set-of-records
repository
Really there's now too many bewildering choices for records;
representing the records is not the difficult part.
dependent-map, and
vault [Heinrich Apfelmus,thank you Sergei for the
suggestion]
seem to be (key, value) stores
so I'm not seeing how I 'query'/filter the values (the whole
records)
if I don't already know the keys for those records.
Contrast that with Data.Set [*],
you could stream the contents to a list and filter.
(Which would be horribly inefficient for my purposes.)
[*] Data.Set seems to have been swallowed into the new
collections library,
which is not currently maintained :-(
Doug Burke
Anthony Clayden
Set is a purely functional data structure, no in-situ updating of nodes, no pointer semantics
Would it save construction/destruction/access overhead to have three extra constructors?
David Feuer
I don't really think we need to bring *two* mailing lists into this. I'm treeowl. The hedge algorithms were usually slower on benchmarks and never much faster. Their theoretical performance has never been understood well. Divide and conquer is fast, and its theoretical performance bound is now understood to be good. The new code is not on Hackage because I haven't made a release yet. containers doesn't usually release a major version more than once a year. This year it may get two, but there's no need to rush.
The Tip constructor is not allocated over and over. Nullary constructors of any given type are shared. So there's just one Tip somewhere. GHC's pointer tagging means that the pointers to Tip are almost never followed. Pattern matching on a Tip value ends up just inspecting the two (32-bit) or three (64-bit) tag bits on the pointer to it.
Yes, constructor order makes a difference, weird as that seems. When GHC desugars a pattern match, it always reorders the case branches into constructor order. Sometimes this is obviously good; certain large case expressions are turned into jump tables. Sometimes this is not so good. One of my predecessors (probably Milan Straka, but I'm not sure) ran a lot of benchmarks and picked the constructor order that was usually best.
Milan Straka wrote a paper that, among other things, recommended adding an additional singleton constructor. I don't actually know why he didn't do that; I can try to ask him. It's possible that it made some things better and others worse.
Anthony Clayden
> Yes, constructor order makes a difference, weird as that seems. When GHC desugars a pattern match, it always reorders the case branches into constructor order. Sometimes this is obviously good; certain large case expressions are turned into jump tables. Sometimes this is not so good. One of my predecessors (probably Milan Straka, but I'm not sure) ran a lot of benchmarks and picked the constructor order that was usually best.
Yes it was Milan [1], [2] refers to [3], which has the explanation. (And yes it seems weird.)
"indirect jumps are particularly expensive on a modern processor architecture, because they fox the branch prediction hardware, leading to a stall of 10 or more cycles depending on the length of the pipeline." [Introduction. The paper goes on to estimate a penalty around 7 to 9 % in general GHC code.]
Milan benchmarked a penalty around 10% for Data.Set. The prediction hardware doesn't seem very clever: it "predicts" any test-and-jump will not jump but will barrel on through the straight-line code. GHC's test is for the constructor not being the first in the decl. So the optimal straight-line code comes from declaring first your most likely constructor.
That seems to me worrying for case/constructor branching code in general. Do we pay that cost for every pattern-match on a list or a Maybe, for example? Their definitions in the Prelude put the constructors in the 'wrong' order. (Although presumably those two get optimised to smithereens.)
> Milan Straka wrote a paper [that's 2] that, among other things, recommended adding an additional singleton constructor. I don't actually know why he didn't do that; I can try to ask him. It's possible that it made some things better and others worse.
Performance seemed somewhat better for certain functions. (And none were worse.) OTOH you would pay a penalty of another indirect jump. So perhaps the extra code complexity just wasn't worth it. Perhaps the combination of pointer tagging and inlining the recursive call wrung the best performance out of it. (Inlining works, despite recursion, because every 'visible' function has a helper `go` that isn't inlined.)
Anthony Clayden
> top of vinyl and provides one way to access data either as
> an array of structures or a structures of arrays.
Thanks Doug,
Nice ability to define column types on the fly,
and interpret them from incoming CSV.
Yes and treat as structure of arrays.
AFAICT Frames keeps each set of records distinct;
and wants each set to be same type/same columns and types.
So there's no heterogeneous repository.
> whether it allows the kind of filtering you were asking
for.
There's standard filtering features you'd get with Set or
List.
I'm not seeing any ability to match/join across different
datasets.
That is, you'd have to write your own code.
wren romano
<anthony...@clear.net.nz> wrote:
> "indirect jumps are particularly expensive on a modern processor
> architecture, because they fox the branch prediction hardware, leading to a
> stall of 10 or more cycles depending on the length of the pipeline."
> [Introduction. The paper goes on to estimate a penalty around 7 to 9 % in
> general GHC code.]
Indeed, this is the point I was about to bring up (but I've been AWOL
the last few weeks).
The cost model here makes sense if you think about a recursive
function over something like lists. To compile down to a tight C-like
loop we'll chose the conditional statement to be "is this nil" and
assume it's always false, so that code falls through straightline to
do whatever loop body, and then does an unconditional jump back up to
the top of the loop. "Almost always" our assumption that the condition
fails will be correct, as it's correct in the recursive case and only
fails in the basis case. (This notion of "almost always" is assuming
we don't have most of our input arguments be the empty list; with
felicity degrading as nil inputs begin to dominate.)
Regardless of how GHC does things, those basics of branch prediction
and primop ordering will remain the same. The question is just about
how we get there, how we go from english descriptions like "the
recursive case" and "the basis case" (or the "common" and "uncommon"
cases) and get to the actual byte code.
In practice GHC does the naive thing of ordering branches to be in
order of declaration in the data type definition. This is good in as
much as it doesn't matter how users textually order their case
analyses, since GHC will reorder them. But it's bad in that the
assumed ordering is not always very smart— especially when the order
of data constructors in a data type's definition is also used for
other magic, like deriving Ord. Really, we'd like to make GHC smarter
here about how it orders things; but that gets complicated very
quickly.
> That seems to me worrying for case/constructor branching code in general. Do
> we pay that cost for every pattern-match on a list or a Maybe, for example?
In principle, yes. In practice, not so much. Because it's not
recursive, you gotta figure you're just going to be wrong half the
time— but you don't know which half. The only stable solutions here
are (a) use dynamic instrumentation to determine which is the hot path
and then recompile, or (b) distinguish the (Nothing | Some a) type
from the (Just a | Everything) type— which we often want anyways for
other things like Ord and Monoid instances, but noone other than me
seems to care very much. In addition to these, there are also various
unstable solutions: (c) assume the user-provided case-analysis order
gives the most likely constructor first (but do we treat Maybe as a
special case? do we over-serialize everything?), (d) add a new pragma
to specify for each case analysis which constructor should be
considered hot (but how much should we actually trust the user to get
that right?), etc...
--
Live well,
~wren
Anthony Clayden
> > "indirect jumps are particularly expensive on a modern
> > processor architecture, because they fox the branch
> > prediction hardware, leading to a stall of 10 or more
> > cycles depending on the length of the pipeline."
> [Introduction. The paper goes on to estimate a penalty
> > around 7 to 9 % in general GHC code.]
Thanks Wren. Is that 7 to 9 % figure unduly alarmist?
(It is consistent with Milan's benchmarking.)
For example would strictifying or inlining
have much greater benefits than worrying about constructors?
And it only affects processor-intensive applications(?)
> ...
> Regardless of how GHC does things, those basics of branch
> prediction and primop ordering will remain the same. ...
> In practice GHC does the naive thing of ordering branches
> to be in order of declaration in the data type definition.
> This is good in as much as it doesn't matter how users
> textually order their case analyses, since GHC will
> reorder them. ...
> ...the order of data constructors in a data type's
definition
> is also used for other magic, like deriving Ord. ...
Hmm, I'd hardly describe derivng Ord as "magic".
It's what the language report says [Chapter 11].
> Really, we'd like to make GHC smarter here about
> how it orders [case branchng code];
> but that gets complicated very quickly.
I can see that. I gave some possible rules of thumb
in an earlier message.
(In particular, recursive constructors are more likely.)
> ... noone other than me seems to care very much. ...
I guess not many know. We kinda expect GHC will be much
smarter
than we could achieve by hand-crafting the object code.
Those who could write assembler code must be dying out ;-)
Judging by the 2006 paper,
part of the difficulty seems to be that the C code GHC
generates
is none too idiomatic for what a C optimiser is tuned for.
AntC