A brief tale of faster equality

Posted in haskell, open source
8 comments on “A brief tale of faster equality
  1. Stefan Wehr says:

    Hi Bryan,

    those numbers look very good! Thanks a lot!!

    Stefan

  2. Johan Tibell says:

    This is great. Did you make similar changes to the Ord instance? It would matter a great deal in the common case of Map Text .

  3. sfvisser says:

    Great news! Your library becomes faster without writing any code, my programs become faster without writing any code. Thanks a lot for this library.

  4. Roman Leshchinskiy says:

    Did you find out what the performance problem in the stream fusion code was? I could bet it was mostly carrying two array indices instead of one. Also, did something like toUpper xs == toUpper ys get slower because of the change?

  5. Johan, I did Ord tonight, and it made a correspondingly large change to performance.

  6. Roman, I didn’t look for the source of the performance problem, but I doubt that it was caused by carrying two indices around. That’s what the compare implementation has to do, and it’s fast.

    As for your toUpper xs == toUpper ys question, that gets slower under GHC 7, but not 6. I’ve tried adding rewrite rules to catch these cases, but they’re not firing and I don’t know why.

    I have code that looks more or less like this:

    toLower :: Text -> Text
    toLower t = unstream (S.toLower (stream t))
    {-# INLINE toLower #-}

    oldCompare :: Text -> Text -> Ordering
    oldCompare a b = Stream.compare (stream a) (stream b)

    instance Ord Text where compare = oldCompare

    {-# RULES “TEXT compare fused” forall s1 s2.
    compare (unstream s1) (unstream s2) = Stream.compare s1 s2
    #-}

    That RULE doesn’t fire, and I don’t know why.

  7. Roman Leshchinskiy says:

    Does adding {-# INLINE [1] compare #-} to the Ord instance help? Otherwise, compare could be inlined immediately, before the rule has had a chance to fire.

  8. gwern says:

    This would have been more interesting with the code shown and differences explained. *What* 5-line change and why is it faster?

1 Pings/Trackbacks for "A brief tale of faster equality"
  1. [...] Eq and Ord instances are also now very fast, up to 5x faster than before. They're now faster than the bytestring [...]

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>