Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,262
    • Issues 4,262
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 404
    • Merge Requests 404
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
  • Security & Compliance
    • Security & Compliance
    • Dependency List
    • License Compliance
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Collapse sidebar
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #14980

Closed
Open
Opened Mar 27, 2018 by ttylec@trac-ttylec

Runtime performance regression with binary operations on vectors

Let me briefly explain our use case: we have a machine learning tools created in Haskell. Basically it builds association rules for a database. In plain English: predicates on data rows. We need to score them, so we need to check how many rows are "matched" by the predicate.

In order to optimize performance, our code uses two main representations for data: one is a "human readable", where a values are real values. The second one is binarized representation for categorical data. The latter has is actually a family of representation, since we pack bits into tuples of Word64 and use bitwise operation to implement logic.

Simplified but representative code is attached.

In GHC 8.0.2 binary representation is faster by one order of magnitude than the "human readable" one:

➜  ghc-bug stack exec performance-bug-pair-1
"Generated"
benchmarking 256 columns/raw unbox vectors
time                 342.6 μs   (338.3 μs .. 348.0 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 339.3 μs   (337.5 μs .. 342.0 μs)
std dev              7.203 μs   (5.596 μs .. 10.07 μs)
variance introduced by outliers: 13% (moderately inflated)

benchmarking 256 columns/binary packed
time                 32.07 μs   (29.69 μs .. 34.14 μs)
                     0.982 R²   (0.976 R² .. 0.997 R²)
mean                 29.97 μs   (29.41 μs .. 31.03 μs)
std dev              2.428 μs   (1.526 μs .. 3.750 μs)
variance introduced by outliers: 78% (severely inflated)

In GHC 8.2.2 (and later) binary representation performance is similar to "human readable", so no performance gain:

➜  ghc-bug stack exec performance-bug-pair-1
"Generated"
benchmarking 256 columns/raw unbox vectors
time                 442.4 μs   (406.7 μs .. 474.5 μs)
                     0.978 R²   (0.969 R² .. 0.993 R²)
mean                 399.3 μs   (391.3 μs .. 415.1 μs)
std dev              34.73 μs   (20.36 μs .. 53.29 μs)
variance introduced by outliers: 71% (severely inflated)

benchmarking 256 columns/binary packed
time                 378.6 μs   (295.8 μs .. 488.0 μs)
                     0.637 R²   (0.492 R² .. 0.780 R²)
mean                 568.1 μs   (437.1 μs .. 747.6 μs)
std dev              308.7 μs   (233.6 μs .. 386.1 μs)
variance introduced by outliers: 98% (severely inflated)

However, for certain compilation paths, we still can get similar speedup as with GHC 8.0.2. In the above examples we used 4-tuple of Word64 as binary representation. In the following code we run two tests: one on just Word64 and one of 4-tuple of Word64. The difference is that we just add the Word64 case:

➜  ghc-bug stack exec performance-bug-pair-2
"Generated"
benchmarking 64 columns/raw unbox vectors
time                 337.6 μs   (336.1 μs .. 339.3 μs)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 349.6 μs   (344.4 μs .. 359.7 μs)
std dev              23.22 μs   (15.39 μs .. 38.22 μs)
variance introduced by outliers: 60% (severely inflated)

benchmarking 64 columns/binary packed
time                 21.66 μs   (21.53 μs .. 21.79 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 21.68 μs   (21.53 μs .. 21.89 μs)
std dev              613.2 ns   (466.0 ns .. 806.0 ns)
variance introduced by outliers: 30% (moderately inflated)

benchmarking 256 columns/raw unbox vectors
time                 344.5 μs   (341.6 μs .. 348.2 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 345.1 μs   (342.5 μs .. 349.3 μs)
std dev              10.66 μs   (7.997 μs .. 16.34 μs)
variance introduced by outliers: 25% (moderately inflated)

benchmarking 256 columns/binary packed
time                 28.04 μs   (27.70 μs .. 28.46 μs)
                     0.999 R²   (0.999 R² .. 1.000 R²)
mean                 28.05 μs   (27.85 μs .. 28.30 μs)
std dev              758.2 ns   (628.2 ns .. 907.6 ns)
variance introduced by outliers: 27% (moderately inflated)

I made a variant of code with simpler accumulating function (in our code we accumulate pair of integers, simplified accumulator work on one integer). GHC 8.2.2 in that case losses speed-up with 4-tuples:

➜  ghc-bug stack exec performance-bug-2
"Generated"
benchmarking 64 columns/raw unbox vectors
time                 333.8 μs   (333.0 μs .. 335.1 μs)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 333.6 μs   (332.4 μs .. 335.8 μs)
std dev              5.651 μs   (3.233 μs .. 9.582 μs)

benchmarking 64 columns/binary packed
time                 39.06 μs   (38.98 μs .. 39.14 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 38.94 μs   (38.83 μs .. 39.14 μs)
std dev              495.0 ns   (310.2 ns .. 782.1 ns)

benchmarking 256 columns/raw unbox vectors
time                 336.9 μs   (336.2 μs .. 337.9 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 337.5 μs   (336.2 μs .. 339.8 μs)
std dev              5.757 μs   (2.946 μs .. 8.979 μs)

benchmarking 256 columns/binary packed
time                 239.8 μs   (237.6 μs .. 243.0 μs)
                     0.998 R²   (0.996 R² .. 0.999 R²)
mean                 251.4 μs   (247.9 μs .. 259.8 μs)
std dev              11.50 μs   (5.662 μs .. 19.79 μs)
variance introduced by outliers: 37% (moderately inflated)

In GHC 8.0.2 we have speed-up in both cases.

What may be related: using random-fu to generate random numbers seems to produce broken code on GHC 8.2.2 (the performance-bug-rfu.hs source).

Short description of attached sources:

  • performance-bug-pair-2.hs: using two binary representations
  • performance-bug-pair-1.hs: using one binary representation (one case commented)
  • performance-bug-1.hs: using one binary representation with simplified accumulator
  • performance-bug-2.hs: using two binary representation with simplified accumulator
  • performance-bug-rfu.hs: using random-fu to generate data (optional)
  • stack-8.0.yaml: stack file for GHC-8.0.2
  • stack-8.2.yaml: stack file for GHC-8.2.2
  • stack-nightly.yaml: stack file for GHC-8.4
  • performance-bug.cabal: to be able to stack build everything.
Trac metadata
Trac field Value
Version 8.2.2
Type Bug
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component Compiler
Test case
Differential revisions
BlockedBy
Related
Blocking
CC
Operating system
Architecture
Assignee
Assign to
9.0.1
Milestone
9.0.1 (Past due)
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#14980