search

ekmett / ersatz

A monad for interfacing with external SAT solvers
Other
62 stars 15 forks source link

StableName performance #30

Closed jwaldmann closed 7 years ago

jwaldmann commented 7 years ago

Should we be worried by this ( https://ghc.haskell.org/trac/ghc/ticket/13165 )

The RTS hash table is rather slow. .. the RTS hash table wasn't used for anything particularly performance critical other than StablePtr operations.

Now ersatz uses StableNames heavily (each node of a Bit expression DAG gets stable-named, https://hackage.haskell.org/package/ersatz-0.3.1/docs/src/Ersatz.Problem.html#generateLiteral ) , and we easily have a million of those.

The doc https://hackage.haskell.org/package/base-4.9.1.0/docs/System-Mem-StableName.html says that "Stable Names are similar to Stable Pointers". Does this also imply we are hit by this issue?

jwaldmann commented 7 years ago

Here is some profiling data, obtained with

stack build --profile --executable-profiling --library-profiling
stack exec -- ersatz-dominatingset +RTS -p -h -RTS sumBits 100 10000

This is at the top:

        total time  =        1.25 secs   (1245 ticks @ 1000 us, 1 processor)
        total alloc = 1,124,574,056 bytes  (excludes profiling overheads)

COST CENTRE        MODULE                      %time %alloc

runBit.\           Ersatz.Bit                   30.9   35.6
bClause.\          Ersatz.Problem                6.3   10.5
bClause            Ersatz.Problem                5.6    3.3
runBit             Ersatz.Bit                    5.4    7.4
makeStableName'    Ersatz.Internal.StableName    4.6    0.6

runBit https://hackage.haskell.org/package/ersatz-0.3.1/docs/src/Ersatz.Bit.html#runBit contains an inlined call to generateLiteral (which calls makeStableName)

I am reading this as:

more detail from the profile:

       runBit.\                                            Ersatz.Bit                   6116      69945   23.3   24.1    43.1   41.3
        negateLiteral                                      Ersatz.Internal.Literal      6361          0    0.2    0.0     0.2    0.0
         literalId                                         Ersatz.Internal.Literal      6362      34973    0.0    0.0     0.0    0.0
        literalId                                          Ersatz.Internal.Literal      6360      89958    0.0    0.0     0.0    0.0
        fromClause                                         Ersatz.Internal.Formula      6169     249828    0.0    0.0     0.0    0.0
        mappend                                            Ersatz.Internal.Formula      6167     249828    0.7    1.1     0.7    1.1
        formula                                            Ersatz.Problem               6162      69945    0.2    0.1     0.2    0.1
        #.                                                 Data.Profunctor.Unsafe       6138     209833    0.1    0.0     0.5    0.0
         #..\                                              Data.Profunctor.Unsafe       6139     209833    0.4    0.0     0.4    0.0
        stableMap                                          Ersatz.Problem               6137      69943    0.1    0.1     0.1    0.1
        modify                                             Control.Monad.State.Class    6134     139888    0.3    0.7    11.1   11.2
jwaldmann commented 7 years ago

https://mail.haskell.org/pipermail/ghc-devs/2017-January/013648.html