Opened 12 months ago

Last modified 10 months ago

#7860 new feature request

Add more bit fiddling functions to 'integer-gmp'

Reported by: lebedev Owned by:
Priority: normal Milestone:
Component: libraries (other) Version: 7.6.3
Keywords: gmp Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Unknown
Test Case: Blocked By:
Blocking: Related Tickets: #3489

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 12 months ago.
base.3.patch (2.6 KB) - added by lebedev 12 months ago.
integer-gmp.patch (10.1 KB) - added by lebedev 12 months ago.

Download all attachments as: .zip

Change History (13)

comment:1 Changed 12 months ago by lebedev

comment:2 Changed 12 months 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 12 months ago by lebedev

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

Changed 12 months ago by lebedev

Changed 12 months ago by lebedev

comment:4 Changed 12 months ago by lebedev

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

comment:5 Changed 12 months ago by igloo

  • Status changed from new to patch

Thanks, we'll take a look

Changed 12 months ago by lebedev

comment:6 Changed 10 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 10 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 10 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 10 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 10 months ago by lebedev

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

Note: See TracTickets for help on using tickets.