Use native operations for `Enum Int64` and `Enum Word64` on 32-bit platforms

[noughtmare]

Situation

Currently, the instances Enum Int64 and Enum Word64 conditionally compile like this:

#if WORD_SIZE_IN_BITS < 64
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFrom #-}
    enumFrom            = integralEnumFrom
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFromThen #-}
    enumFromThen        = integralEnumFromThen
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFromTo #-}
    enumFromTo          = integralEnumFromTo
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFromThenTo #-}
    enumFromThenTo      = integralEnumFromThenTo
#else
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFrom #-}
    enumFrom            = boundedEnumFrom
    -- See Note [Stable Unfolding for list producers] in GHC.Enum
    {-# INLINE enumFromThen #-}
    enumFromThen        = boundedEnumFromThen
#endif

So, it uses a slow Integer-based fallback on 32-bit platforms.

Motivation

Now two things have happened that might make use reevaluate this decision:

• GHC is getting a JavaScript back end which uses 32-bit words.
• I have recently implemented code generation for 64-bit operations in the i386 back end (!10771).

So 32-bit platforms will become more common and there is now more performance to gain on i386.

Concrete Changes

I propose to write custom Enum Int64 and Enum Word64 instances that use native operations instead of falling back to Integer-based operations. Essentially, this means copying the implementation of Enum Int and Enum Word and replacing all occurrences of Int with Int64 and the same for Word.

Implementation

I've already implemented the required changes in !10825.

Impact

This is purely a performance change. I expect it will almost always have a positive impact on performance, but it might cause things to inline differently. I have done benchmarks for i386 which shows a 1.5x performance improvement and also for JS which shows a 5.6x performance improvement.

One other impact is that this adds a bit of maintenance burden on the GHC developers. But this part of the code has been very stable, so we don't expect this to be a problem.

Alternatives

1. Keep status quo. This means bad performance.

2. Reduce duplication using CPP trickery. This makes it harder to navigate the source code.

[hasufell]

I have done no benchmarks yet.

Please do. It sounds exciting.

One other impact is that this adds maintenance burden on the GHC developers.

Do GHC devs have concerns?

[noughtmare]

Please do. It sounds exciting.

@hsyl20 can you run some benchmarks with the JS back end? I can run benchmarks for i386. I think something like your example will do:

import Data.Word

main :: IO ()
main = print (sum [0..123456 :: Word64])

Do GHC devs have concerns?

I'll ask.

[bgamari]

Do GHC devs have concerns?

No, these instances are extremely stable. The maintenance burden should be negligible. In my opinion this change is long overdue.

[noughtmare]

Rough benchmark results on i386:

-- Bench.hs
import Data.Word

main = print (sum [1..123456789 :: Word64])

Compiled with:

$ _build/stage1/bin/ghc -O2 Bench.hs

Before:

$ ./Bench +RTS -s
7620789436823655
     987,701,620 bytes allocated in the heap
          11,780 bytes copied during GC
          42,704 bytes maximum residency (2 sample(s))
          31,024 bytes maximum slop
               6 MiB total memory in use (0 MiB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0       234 colls,     0 par    0.000s   0.000s     0.0000s    0.0000s
  Gen  1         2 colls,     0 par    0.000s   0.000s     0.0000s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.515s  (  0.514s elapsed)
  GC      time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.515s  (  0.515s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    1,918,939,977 bytes per MUT second

  Productivity  99.9% of total user, 99.8% of total elapsed

After:

$ ./Bench +RTS -s
7620789436823655
          47,300 bytes allocated in the heap
           1,656 bytes copied during GC
          42,704 bytes maximum residency (1 sample(s))
          26,928 bytes maximum slop
               6 MiB total memory in use (0 MiB lost due to fragmentation)

                                     Tot time (elapsed)  Avg pause  Max pause
  Gen  0         0 colls,     0 par    0.000s   0.000s     0.0000s    0.0000s
  Gen  1         1 colls,     0 par    0.000s   0.000s     0.0001s    0.0001s

  INIT    time    0.000s  (  0.000s elapsed)
  MUT     time    0.347s  (  0.346s elapsed)
  GC      time    0.000s  (  0.000s elapsed)
  EXIT    time    0.000s  (  0.000s elapsed)
  Total   time    0.347s  (  0.346s elapsed)

  %GC     time       0.0%  (0.0% elapsed)

  Alloc rate    136,491 bytes per MUT second

  Productivity  99.9% of total user, 99.9% of total elapsed

So about 1.5x faster, or 33% less running time if you prefer. If not for the blazing fast copying GC, it would be a lot worse because it also lowers total allocations by a factor of 20,000.

[noughtmare]

I've tried benchmarking the JS backend myself, but I'm actually seeing a regression:

-- Bench.hs
import Data.Word

main = print (sum [1..12345678 :: Word64])

Before:

$ hyperfine ./Bench_before
Benchmark 1: ./Bench_before
  Time (mean ± σ):      4.809 s ±  0.038 s    [User: 4.819 s, System: 0.019 s]
  Range (min … max):    4.738 s …  4.854 s    10 runs

After:

$ hyperfine ./Bench
Benchmark 1: ./Bench
  Time (mean ± σ):      5.651 s ±  0.031 s    [User: 5.665 s, System: 0.020 s]
  Range (min … max):    5.615 s …  5.727 s    10 runs

@hsyl20 can you help figuring out what's going on here?

[noughtmare]

@hsyl20 has written an MR for improved code generation for 64 bit addition and with that we get much better times:

$ hyperfine ./Bench
Benchmark 1: ./Bench
  Time (mean ± σ):     243.9 ms ±   0.7 ms    [User: 231.9 ms, System: 18.8 ms]
  Range (min … max):   243.0 ms … 245.3 ms    12 runs

So almost 20x faster (or 95% less running time)!

Edit: perhaps this is not entirely fair because the bignum implementation might also benefit from Silvain's 64 bit addition MR. I will run another test with Silvain's changes but without this Enum Int/Word64 change.

As I thought, Silvain's changes also affect the old implementation:

$ hyperfine ./Bench_before
Benchmark 1: ./Bench_before
  Time (mean ± σ):      1.369 s ±  0.025 s    [User: 1.365 s, System: 0.020 s]
  Range (min … max):    1.311 s …  1.405 s    10 runs

So it's "only" 5.6x faster (82% less run time).

[hsyl20]

Thanks for the benchmarks (and the patch!) @noughtmare!

[noughtmare]

@hasufell I think this is ready for review by the committee.

[Bodigrim]

@noughtmare is the new code sufficiently covered with tests?
I'm AFK and somewhat lazy to review it for correctness myself, it would be better just to trust a test suite ;)

[noughtmare]

@Bodigrim I don't know actually; I'll check. However, the code in my MR is a pretty direct copy of the Enum instance of Word [1] and Int respectively. Diffing against that would make the review easier.

[1] https://gitlab.haskell.org/ghc/ghc/-/blob/a7349217fb9a992ad1c0e0d6ce1ab78e29dbe144/libraries/base/GHC/Enum.hs#L736

[noughtmare]

@Bodigrim I think there is sufficient test coverage:

• Int64: https://gitlab.haskell.org/ghc/ghc/-/blob/master/libraries/base/tests/enum02.hs#L194
• Word64: https://gitlab.haskell.org/ghc/ghc/-/blob/master/libraries/base/tests/enum03.hs#L197

In fact, I just remembered these test caught an issue with the Enum Int64 instance, which I have now fixed.

[Bodigrim]

Dear CLC members, let's vote on the proposal to implement instance Enum Int64 and instance Enum Word64 that use native operations on all platforms instead of falling back to Integer-based ones. This has positive performance impact: 1.5x faster for i386 backend and 5.6x faster for JavaScript backend. The MR is available at https://gitlab.haskell.org/ghc/ghc/-/merge_requests/10825. The change is somewhat technically involved, but is closely derived from existing instance Enum {Int,Word} and covered with tests.

@tomjaguarpaw @chshersh @hasufell @angerman @parsonsmatt @mixphix

---

+1 from me.

[tomjaguarpaw]

+1

[mixphix]

+1

[chshersh]

+1

---

Always happy to see performance improvements!