DRAFT: Implement new integer-gmp2 from scratch (re #9281)
ClosedPublic

Authored by hvr on Jul 20 2014, 12:20 PM.

Details

Summary

(preliminary commit message)

This is done as a separate integer-gmp2 backend library because it
turned out to become a complete rewrite from scratch. This has been
tested only on Linux/x86_64 so far. The code has been written while
taking into account Linux/i386 and "64-bit" Windows, but will probably
need some tweaking to get right.

Also, we don't do any autoconf stuff anymore, and rely on Cabal's
"extra-libraries: gmp" to do the right thing (which probably won't work
everywhere)

Moreover, this is currently a big huge patch, which could easily be
split into 2 or 3 commits.

Test Plan

nofib & testsuite

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
There are a very large number of changes, so older changes are hidden. Show Older Changes
hvr added a comment.Aug 16 2014, 8:09 AM

@rwbarton thank you for taking such a close look!

I'll shortly upload a revised patch addressing most comments

libraries/integer-gmp2/integer-gmp2.cabal
3 ↗(On Diff #175)

This was actually a typo; integer-gmp2 started out as a natural-gmp which would only implement naturals. After some promising results I started refactoring it to become integer-gmp2

34 ↗(On Diff #175)

ack

38 ↗(On Diff #175)

ack

52 ↗(On Diff #175)

ack

libraries/integer-gmp2/src/GHC/Integer/Type.hs
66

I can't think of anything else than to emulate Foreign.C.Types define a boxed data-type (which would break symmetry for those FFI imports which would return a *-kinded result for an otherwise primitive integral value, and all other simply return word-sized #-kinded return values.

Alas we have only access to ghc-prim, so we have to reinvent the wheel for all sorts of convenience (see also the monadic helpers I had to hack up to be able to use the do notation to make the code slightly more readable)

209–214

I didn't write integerToWord64 (Jn# bn) = int64ToWord64# (integerToInt64 (Jn# bn)) as I was worried it might not get inlined due to {-# NOINLINE word64ToInteger #-}

247–251

If I write integerToWord (Jn# bn) = int2Word# (integerToInt (Jn# bn)) then I'm worried that it wouldn't be inlined since integerToInt is marked NOINLINE

270

I *think* they get reordered anyway already at the Core level. But @simonmar may know for sure...

284–286

Because I wrote a Haddock comment for that (as IMO neq looks a bit too much like neg which caused me a few typos in the past already)

369–370

Tbh, being able to do this shortcuts was one of my main motivations to change the Integer representation, as now there's only a unique representation for 0, i.e. S# 0# so the test is rather cheap. However, I remember that short-cutting operations with neutral elements had a measurable win in nofib wrt to allocations, as in real code, the probability of having 0 (or 1) as an operand is not *that* small. Moreover, since plusInteger can't be inlined, even for the plusInteger (S# 0#) (S# x) case we can avoid a redundant 16 byte allocation (on 64bit archs) this way.

394

I've tried that, but it looks ugly (with and w/o syntax highlighting). I've now simply added a

#define CONSTANT_FOLDED NOINLINE

which allows to write a properly syntax-highlighed pseudo-pragma

{-# CONSTANT_FOLDED plusInteger #-}
403–409

Yeah, I did measure reduced allocations in nofib

In integer-gmp, however, there's no unique representation of 0 and 1. That's why I didn't bother to do that there.

430

you're totally right. Those were copy'n'paste errors

474

good catch!

503

Actually, users are expected to access these operations via the Num and Bits classes. But I'll add a note nevertheless.

Btw, originally I wrote that function to have a Word# arguments, but in order to be compatible to the existing GHC.Integer interface and avoid a few word2Int# calls, I changed it back to Int#... :-/

598

those were an oversight; I went over everything and I hope it didn't miss any non-#-suffixed Int# var this time

715

ack

735

ack

798–801

It's due to the different kinds. But I'm still experimenting to see if I can get the do-notation working here as well.

824

I've removed the MAX_CONST_BIGNAT table in the newest revision as the additional complexity doesn't justify the rather small benefit at this point

957

That is supposed to be handled just like other 1-limb BigNats such as bn = 1

1140

In case of div-by-0, nullBigNat is more of a place-holder, as the code using quotRemBigNatWord is expected to avoid calling that function with 0## anyway (which is cheap to test against).

1222

any recommendation how to rename c_mpn_get_d? It was meant to be very close to the original mpn_get_d() operation, but more convenient for us to use.

1238–1268

ack

1240–1241

good catch!

1387

ack

1436–1456

not anymore; I've removed it now

1486–1501

Not easily, as normSizeofMutBigNat operates on a different type (requiring the stateful readWordArray# operation), and if I remember correctly, the pure indexWordArray# variant resulted in slightly better code generation.

1519

good catch!

1596

ack, a negateInt# was missing there

hvr updated this revision to Diff 373.Aug 16 2014, 9:22 AM
hvr edited edge metadata.

major revision, including 80-column reindentations

Known issue: This wouldn't validate yet with INTEGER_LIBRARY=integer-gmp2
due to Haddock getting confused because I cheated in
./compiler/prelude/TysWiredIn.lhs

hvr added a comment.Aug 16 2014, 9:27 AM

Note: the decodeDouble_Int64# commit is subject to D160 (I assumed arc diff wouldn't pick it up as it correctly recognized it belonging to a different revision, but well, here it is...)

hvr updated this revision to Diff 376.Aug 16 2014, 9:36 AM
hvr edited edge metadata.

Try to get rid of D160 patch

rwbarton added inline comments.Aug 20 2014, 3:39 PM
libraries/integer-gmp2/src/GHC/Integer/Type.hs
66

Oh right, you can't newtype an unboxed type, too bad.

209–214

What I mean is, why not just replace the whole definition of integerToWord64 with integerToWord64 n = int64ToWord64# (integerToInt64 n)? Isn't that the intent of integerToWord64? int64ToWord64# should just reinterpret a 64-bit value as another type so at the Cmm level it should already disappear.

If it's better to have two copies of the code rather than a jump (seems unlikely) then you should be able to use the inline magic function to override NOINLINE.

Anyways, there are a few spots like this that have what seems to me to be unnecessary code duplication, but landing the patch needn't wait on cleaning those up IMO.

957

I should have been more clear, seeing as it took me a while to remember what I meant by that question:

If bn = 0 then negative bn = ...00000 (unlike any bn > 0 in which case negative bn has an infinite leading string of 1s). Isn't that a problem for | isTrue# (li# >=# nx#) = True?

1222

Maybe some naming scheme like c_hs_mpn_get_d or c_igmp_mpn_get_d or something.

hvr planned changes to this revision.EditedSep 3 2014, 3:57 AM
hvr added a subscriber: simonpj.

There's a bigger issue at hand related to the wired-in types, and I plan to pursue what @simonpj suggested in a
ghc-devs@ posting, namely to "Stop having Integer as a wired-in type" in the hopes to avoid the issue and simplify code.

libraries/integer-gmp2/src/GHC/Integer/Type.hs
209–214

Btw, Is constructor-specialization guaranteed to kick in when I write integerToWord64 (Jn# bn) = int64ToWord64# (inline integerToInt64 (Jn# bn))?

957

Now I see what you mean, and you're right:

​We want testBitNegBigNat (0 :: BigNat) n == False to hold for all n, which currently isn't the case.

I'm tempted however to declare testBitNegBignat to require a non-zero BigNat (as there is no such thing as a negative 0 doesn't exist in the domain of integers) to avoid having to perform an additional test for a questionable edge-case.

In D82#45, @hvr wrote:

There's a bigger issue at hand related to the wired-in types, and I plan to pursue what @simonpj suggested in a
ghc-devs@ posting, namely to "Stop having Integer as a wired-in type" in the hopes to avoid the issue and simplify code.

Yes, please do try (3) in the message you point to. Ian replied to say "no particular reason", so I'm very optimistic that it'll be easy to make Integer non-wired-in, and that would make your life Much Easier.

Simon

ekmett added a subscriber: ekmett.Sep 20 2014, 4:29 PM
hvr updated this revision to Diff 965.Oct 23 2014, 6:06 AM

Rebased and updated to depend on D351

hvr updated this revision to Diff 974.Oct 24 2014, 3:36 PM

rebase to latest D351 patch

ezyang removed a subscriber: ezyang.Oct 27 2014, 2:06 PM
hvr updated this revision to Diff 1326.Nov 7 2014, 6:05 PM

Added support for in-tree GMP.
With this, integer-gmp2 is on par w/ integer-gmp (sans the mem allocation hooks).

I think in this state we can consider landing integer-gmp2 soon, even though it
doesn't yet implement some of the more ambitious features such as link-time
backend selection, it already provides a few benefits over integer-gmp.

ekmett added a comment.Nov 7 2014, 6:18 PM

I just want to say that I'm really looking forward to this patch landing.

hvr updated this revision to Diff 1338.Nov 8 2014, 2:20 AM

Set INTEGER_LIBRARY=integer-gmp2 by default, so ./validate actually runs against
integer-gmp2 in Harbormaster. Tweak testsuite to pass all tests.

hvr updated this revision to Diff 1339.Nov 8 2014, 2:50 AM

Minor fixup in libraries/integer-gmp2/integer-gmp2.buildinfo.in

hvr updated this revision to Diff 1340.Nov 8 2014, 4:27 AM

Fix bindist failure while installing HsIntegerGmp2.h

hvr added a comment.Nov 8 2014, 4:57 AM

Fyi, B1804 had only

Unexpected stat failures:
  perf/compiler T4801 [stat not good enough] (normal)
  perf/compiler T9675 [stat too good] (optasm)

Now I just need to find out by how much Phabricator's buildbot missed the thresholds (fwiw, those didn't fail for my local ./validate on Linux/amd64)

hvr updated this revision to Diff 1374.Nov 10 2014, 6:11 AM

TLDR:

  • make INTEGER_LIBRARY=integer-gmp2 result in integer-gmp-1.0.0.0
  • make INTEGER_LIBRARY=integer-gmp result in integer-gmp-0.5.1.0

So the old integer-gmp remains available in-tree

More details:

  • Minor fixup in libraries/integer-gmp2/integer-gmp2.buildinfo.in
  • Fix bindist failure while installing HsIntegerGmp2.h
  • Rename GHC.Integer.GMP2.Internals to *.GMP.*
  • Remove obsolete references to mkGmpDerivedConstants
  • Rename constructor SI# to S#
  • Disable T4801/peak_megabytes_allocated
  • Rename integer-gmp2's package name to integer-gmp. While the folder-name stays the same. This also bumps the version number to 1.0.0.0 (old integer-gmp is at 0.5.1.x)
austin accepted this revision.Nov 12 2014, 12:34 AM
austin edited edge metadata.

I looked at the changes after refactoring out your other patches, and overall it looks really good! And it seems to be almost 100% on par with what we had before (in features and performance it seems).

Therefore, I grant you a...

sealofapproval

IT IS DONE.

mk/config.mk.in
233

ronpaulomgyes

testsuite/tests/lib/integer/all.T
5

Why was this commented out? I haven't looked at the test but I assume it's probably a bit of work to fix.

Actually this does highlight a slightly annoying problem which is that we cannot test both versions of the library without disabling tests one way or another. Or rewriting them. Or having the test based on whether the integer-gmp version is >= 1.0 or not.

But I don't think this matters much because we're going to nuke the old one from orbit soon enough anyway.

testsuite/tests/perf/compiler/all.T
171 ↗(On Diff #1374)

s/to/too/

testsuite/tests/perf/space_leaks/all.T
18

Add the integer-gmp2 description here as to why this increased.

Actually this seems nice; while we're allocating a bit more (presumably due to doing less CMM hackery and a bit more Haskell) the peak megabyte usage actually seemed to drop. So I'm cool with that.

This revision is now accepted and ready to land.Nov 12 2014, 12:34 AM
This revision was automatically updated to reflect the committed changes.
hvr added a comment.Nov 12 2014, 6:09 AM

@austin, I think i have addressed all your comments

Moreover, latest benchmarks at P35, and see also landing announcement to ghc-devs@

testsuite/tests/lib/integer/all.T
5

The problem is, it tests a few internal GMP-specific optional primitives (like the import/export and exponentiation primitives) not yet provided by integer-gmp-1.*, and I'd need to say something like reqlib('integer-gmp-0.5.1.0') which I think doesn't work.

Some of the primitives I'm planning to re-implement after D82 lands. Then that test will be re-enabled

nomeata added a subscriber: nomeata.Dec 3 2014, 2:32 AM

JFTR: There is some minor fallout, reported at https://ghc.haskell.org/trac/ghc/ticket/9856#ticket