Opened 2 years ago

Last modified 4 months ago

#7860 new feature request

Add more bit fiddling functions to 'integer-gmp'

Reported by: lebedev Owned by:
Priority: normal Milestone:
Component: Core Libraries Version: 7.6.3
Keywords: gmp Cc: hvr, core-libraries-committee@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: #3489, 9835 Differential Revisions:

Description

Current implementation of 'integer-gmp' uses only a subset of "bit fiddling" features, provided by the GMP library. The ones missing are:

* mpz_popcount
* mpz_setbit
* mpz_clrbit

I think it would be nice to add these functions in addition to 'testBitInteger'. Would you accept a patch?

Attachments (3)

integer-simple.patch (2.2 KB) - added by lebedev 2 years ago.
base.3.patch (2.6 KB) - added by lebedev 2 years ago.
integer-gmp.patch (10.1 KB) - added by lebedev 2 years ago.

Download all attachments as: .zip

Change History (18)

comment:1 Changed 2 years ago by lebedev

comment:2 Changed 2 years ago by igloo

  • Component changed from Compiler to libraries (other)
  • difficulty set to Unknown

We'd need an implementation for integer-simple too, but other than that it sounds OK.

comment:3 Changed 2 years ago by lebedev

I'm almost done with the patch, do I need to write some test cases as well?

Changed 2 years ago by lebedev

Changed 2 years ago by lebedev

comment:4 Changed 2 years ago by lebedev

The patches are attached. I wasn't able to test integer-simple implementation due to this linker error.

comment:5 Changed 2 years ago by igloo

  • Status changed from new to patch

Thanks, we'll take a look

Changed 2 years ago by lebedev

comment:6 Changed 22 months ago by igloo

  • Status changed from patch to new

Thanks for the patch. However, it's not clear to me that this won't actually cause performance regressions. For example, this:

clearBitInteger j@(S# _) i = clearBitInteger (toBig j) i

means that clearBit will always unnecessarily promote small integers to large integers.

comment:7 Changed 22 months ago by lebedev

Well, it looks like it's always safe to clear bit in a small-ish integer using operations on Int# and Word#:

clearBitInteger :: Integer -> Int# -> Integer
clearBitInteger (S# j) i   =
    -- We can always safely celear a bit of a _small_ integer.
    let !mask =
            int2Word# (1# `iShiftL#` i) `xor#` int2Word# (negateInt# 1#)
    in S# (word2Int# (int2Word# j `and#` mask))
clearBitInteger (J# s d) i =
    let !(# s', d' #) = clearBitInteger# s d i in J# s' d'

What do you think? I can modify setBitInteger in a similar way.

comment:8 Changed 22 months ago by lebedev

Actually, there should also be a case for negative bits, so the full version is:

clearBitInteger :: Integer -> Int# -> Integer
clearBitInteger (S# j) i
    | i <# 0# || i >=# (WORD_SIZE_IN_BITS# -# 1#) = S# j
    | otherwise =
        let !mask =
                int2Word# (1# `uncheckedIShiftL#` i) `xor#`
                int2Word# (negateInt# 1#)
        in S# (word2Int# (int2Word# j `and#` mask))
clearBitInteger (J# s d) i =
    let !(# s', d' #) = clearBitInteger# s d i in J# s' d'

comment:9 Changed 22 months ago by igloo

I suspect we'd want to refactor things so that

clearBitInteger (S# j) i = S# (clearBitInt j i)

(and similarly share code where possible for the other functions).

comment:10 Changed 22 months ago by lebedev

Yeah, this makes sense, where should I put this *Int functions?

comment:11 Changed 6 months ago by thoughtpolice

  • Component changed from libraries (other) to Core Libraries
  • Owner set to ekmett

Moving over to new owning component 'Core Libraries'.

comment:12 Changed 4 months ago by thomie

  • Cc hvr added
  • Component changed from Core Libraries to Driver

hvr: is this feature request still relevant after the integer-gmp rewrite (#9281)?

comment:13 Changed 4 months ago by thomie

  • Cc core-libraries-committee@… added
  • Component changed from Driver to Core Libraries
  • Owner ekmett deleted

comment:14 Changed 4 months ago by thomie

comment:15 Changed 4 months ago by hvr

integer-gmp2 does in fact already have a popcount primop (and it's used by Integer and Natural)

Fwiw, I'm planning to implement set/clearbit for integer-gmp2, at the latest for GHC 7.12

Note: See TracTickets for help on using tickets.