[GHC] #7860: Add more bit fiddling functions to 'integer-gmp'
#7860: Add more bit fiddling functions to 'integer-gmp' -----------------------------+---------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Component: Compiler Version: 7.6.3 | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Blockedby: Blocking: | Related: 3489 -----------------------------+---------------------------------------------- Current implementation of 'integer-gmp' uses only a subset of "bit fiddling" features, [http://gmplib.org/manual/Integer-Logic-and-Bit- Fiddling.html 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? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' -----------------------------+---------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Component: Compiler Version: 7.6.3 | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Blockedby: Blocking: | Related: #3489 -----------------------------+---------------------------------------------- Changes (by lebedev): * related: 3489 => #3489 -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' ----------------------------------+----------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Keywords: gmp | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: #3489 | ----------------------------------+----------------------------------------- Changes (by igloo): * difficulty: => Unknown * component: Compiler => libraries (other) Comment: We'd need an implementation for `integer-simple` too, but other than that it sounds OK. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' ----------------------------------+----------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Keywords: gmp | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: #3489 | ----------------------------------+----------------------------------------- Comment(by lebedev): I'm almost done with the patch, do I need to write some test cases as well? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' ----------------------------------+----------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Keywords: gmp | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: #3489 | ----------------------------------+----------------------------------------- Comment(by lebedev): The patches are attached. I wasn't able to test integer-simple implementation due to [http://www.haskell.org/pipermail/ghc- devs/2013-April/000996.html this] linker error. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' ----------------------------------+----------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: patch Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Keywords: gmp | Os: Unknown/Multiple Architecture: Unknown/Multiple | Failure: None/Unknown Difficulty: Unknown | Testcase: Blockedby: | Blocking: Related: #3489 | ----------------------------------+----------------------------------------- Changes (by igloo): * status: new => patch Comment: Thanks, we'll take a look -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:5 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' --------------------------------+------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: #3489 --------------------------------+------------------------------------------- Changes (by igloo): * status: patch => new Comment: 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. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' --------------------------------+------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: #3489 --------------------------------+------------------------------------------- Comment(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. -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' --------------------------------+------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: #3489 --------------------------------+------------------------------------------- Comment(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' }}} -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' --------------------------------+------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: #3489 --------------------------------+------------------------------------------- Comment(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). -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
#7860: Add more bit fiddling functions to 'integer-gmp' --------------------------------+------------------------------------------- Reporter: lebedev | Owner: Type: feature request | Status: new Priority: normal | Milestone: Component: libraries (other) | Version: 7.6.3 Resolution: | Keywords: gmp Os: Unknown/Multiple | Architecture: Unknown/Multiple Failure: None/Unknown | Difficulty: Unknown Testcase: | Blockedby: Blocking: | Related: #3489 --------------------------------+------------------------------------------- Comment(by lebedev): Yeah, this makes sense, where should I put this *Int functions? -- Ticket URL: http://hackage.haskell.org/trac/ghc/ticket/7860#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler
participants (2)
-
GHC -
GHC