#4342: Review containers changes
----------------------------------+-----------------------------------------
Reporter: igloo | Owner:
Type: bug | Status: new
Priority: high | Milestone: 7.2.1
Component: libraries (other) | Version: 7.1
Keywords: | Testcase:
Blockedby: | Difficulty:
Os: Unknown/Multiple | Blocking:
Architecture: Unknown/Multiple | Failure: None/Unknown
----------------------------------+-----------------------------------------
Comment(by milan):
> T1969 and T3294 are passing now, and T3064 is better: was:
> {{{
> bytes allocated 316528584 is more than maximum allowed 280000000
> }}}
> now:
> {{{
> bytes allocated 299224968 is more than maximum allowed 280000000
> }}}
Ah, according to the 280000000 limit, it is a 64-bit GHC. On 32-bit
machine T3064 passes.
>
> This patch causes a lot of warnings.
>
> I started fixing them, but in some cases I was fixing shadowed variable
warnings by SATing functions, and I'm not sure if you deliberately left
them unSATed; certainly in some cases functions seem to have been
deliberately unSATed, e.g. (diffing relative to the 7.0 branch's
containers):
> {{{
> lookup :: Ord k => k -> Map k a -> Maybe a
> -lookup k = k `seq` go
> +lookup = go
> where
> - go Tip = Nothing
> - go (Bin _ kx x l r) =
> + STRICT12(go)
> + go k Tip = Nothing
> + go k (Bin _ kx x l r) =
> case compare k kx of
> - LT -> go l
> - GT -> go r
> + LT -> go k l
> + GT -> go k r
> EQ -> Just x
> }}}
>
> We need it to be `-Wall` clean before we can apply it, though.
I am sorry, I did not think of that. Do you want me to correct it? I will
gladly do it, but I do not want to do the work twice :)
> Incidentally, I don't like these names:
> {{{
> +-- Use macros to define strictness of functions.
> +-- STRICTxy denotes an y-ary function strict in the x-th parameter.
> +#define STRICT12(fn) fn arg _ | arg `seq` False = undefined
> +#define STRICT13(fn) fn arg _ _ | arg `seq` False = undefined
> +#define STRICT23(fn) fn _ arg _ | arg `seq` False = undefined
> +#define STRICT24(fn) fn _ arg _ _ | arg `seq` False = undefined
> }}}
> I would prefer `STRICT_1_OF_2`, but personally I think we should just
use bang patterns.
Bang patterns are not in any standards, so this would rule out other
compilers not supporting them. Your rename seems reasonable, I would go
with that.
> This comment:
> {{{
> +-- The balance function is equivalent to the following:
> ...
> +-- It is only written in such a way that every node is pattern-matched
only once.
> }}}
> makes me wonder if !SpecConstr should be generating the more efficient
code automatically?
Well, it is just an invariant of the structure that allows to do the
pattern-matching only once. As the code was written previously, it would
be incorrect to use just one pattern-matching.
> In `Data.IntSet`, I don't understand the `natFromInt` stuff, and the
change in `lookup`.
The natFromInt && friends are the same, just with explicit INLINEs (at
some point it did not get inlined and that caused a lot of problems).
> I am suspicious about the extra
> {{{
> | nomatch x p m = False
> }}}
> clause in `member`, as compared to `lookup`.
This is as it was in 0.3. It is semantically correct both ways. The only
think is time complexity. The member is a bit faster if the key looked for
is _not_ in the set, but it does slightly more work if the key is present.
We can decide both ways and make it consistent.
> There are some things I'll leave to the containers experts to review:
>
> I haven't checked the `balance`/`balanceL`/`balanceR` changes at all
(neither the definitions, nor the calls).
>
> I haven't checked the change of `delta` from 4 to 3.
>
> I haven't checked the `<=` to `<` change in `join`.
Also in merge.
>
> I haven't checked the changes of case into let, e.g. in
`Data.IntMap.insertLookupWithKey`.
The current version is from 0.3.
>
> I haven't checked the `trim` changes.
>
> I haven't checked the `union*`/`diff*`/`hedge*` changes.
Thanks for your work,
Cheers,
Milan
--
Ticket URL: <http://hackage.haskell.org/trac/ghc/ticket/4342#comment:13>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler
_______________________________________________
Glasgow-haskell-bugs mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/glasgow-haskell-bugs
