unsafeShift operations for Data.Bits
Hello libraries, fast shift operations that don't verify shift amount is rather popular demand. how about providing them in the Data.Bits? -- |Shifts its first operand left by the amount of bits specified in -- second operand. Result of shifting by negative/too large amount -- is not specified. Should be used only in situations when you may -- guarantee correct value of second operand or don't care about result :) unsafeShiftL :: Int -> Int -> Int unsafeShiftR :: Int -> Int -> Int #ifdef __GLASGOW_HASKELL__ unsafeShiftL (I# a) (I# b) = (I# (a `iShiftL#` b)) unsafeShiftR (I# a) (I# b) = (I# (a `uncheckedIShiftRL#` b)) #else /* ! __GLASGOW_HASKELL__ */ unsafeShiftL = shiftL unsafeShiftR = shiftR #endif /* ! __GLASGOW_HASKELL__ */ it may be even better to include them in Bits class with obvious default definition -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On 11/6/06, Bulat Ziganshin
Hello libraries,
fast shift operations that don't verify shift amount is rather popular demand. how about providing them in the Data.Bits?
-- |Shifts its first operand left by the amount of bits specified in -- second operand. Result of shifting by negative/too large amount -- is not specified. Should be used only in situations when you may -- guarantee correct value of second operand or don't care about result :) unsafeShiftL :: Int -> Int -> Int
unsafeShiftR :: Int -> Int -> Int
#ifdef __GLASGOW_HASKELL__ unsafeShiftL (I# a) (I# b) = (I# (a `iShiftL#` b)) unsafeShiftR (I# a) (I# b) = (I# (a `uncheckedIShiftRL#` b)) #else /* ! __GLASGOW_HASKELL__ */ unsafeShiftL = shiftL unsafeShiftR = shiftR #endif /* ! __GLASGOW_HASKELL__ */
it may be even better to include them in Bits class with obvious default definition
And use them for the default implementation of rotate, while we are at it.
On Mon, 6 Nov 2006, Samuel Bronson wrote:
And use them for the default implementation of rotate, while we are at it.
I thought you had a patch to GHC that worked really well? I think it is much beter idea to fix the inliner rather than exposing unsafe functionality. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''
On 11/6/06, roconnor@theorem.ca
On Mon, 6 Nov 2006, Samuel Bronson wrote:
And use them for the default implementation of rotate, while we are at it.
I thought you had a patch to GHC that worked really well? I think it is much beter idea to fix the inliner rather than exposing unsafe functionality.
It isn't really *unsafe*, exactly. But it might not be purely functional. However, it isn't imperative or anything like that. Also, for rotate, I needed to change the implementations in the *libraries* (it was only the GHC-specific implementations, though). (Also, nobody seems to have applied that patch yet for some reason.) And I needed to change them to use the raw, unchecked primops. Oh, that reminds me. Why call them "unsafe"? Why not "unchecked" as GHC's primops are called?
Hello Samuel, Monday, November 6, 2006, 10:09:18 PM, you wrote:
And use them for the default implementation of rotate, while we are at it.
I thought you had a patch to GHC that worked really well? I think it is much beter idea to fix the inliner rather than exposing unsafe functionality.
well, the whole story: ghc provides unchecked* low-level operations that does shifts without any checks. if shift is negative/too large, result value is not specified (and actually depends on concrete C/cpu implementation) haskell standard provides shiftL/R operation that had defined behavior for bad shift values. in order to implement this, ghc checks shift amount and only then performs actual shift there are high-performance algorithms that demands highest possible speed and at the same time make guarantees that shift amount will be "right". imagine, for example, a bit array implementation Samuel's patch improves inlining that allows to remove checks BUT only in the case where shift amount is compile-time known! so, while his patch is more general, it don't override need in unchecked shift operations
It isn't really *unsafe*, exactly. But it might not be purely functional. However, it isn't imperative or anything like that. Also, for rotate, I needed to change the implementations in the *libraries* (it was only the GHC-specific implementations, though). (Also, nobody seems to have applied that patch yet for some reason.) And I needed to change them to use the raw, unchecked primops.
these unsafe* operations will have the _same_ speed as unboxed unchecked* ones. so, it's a much better. all the ghc-specific code will be concentrated in a few simple lines instead of providing lot of haskell-specific implementations for rather complex rotate* functions
Oh, that reminds me. Why call them "unsafe"? Why not "unchecked" as GHC's primops are called?
it's tradition to call functions that should be used with caution as unsafe*. there is also unsafeChr, for example. i personally prefer >># and <<# names, but don't think that we can do such namespace pollution in widely used library -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com
On Mon, Nov 06, 2006 at 02:09:18PM -0500, Samuel Bronson wrote:
It isn't really *unsafe*, exactly. But it might not be purely functional. However, it isn't imperative or anything like that. Also, for rotate, I needed to change the implementations in the *libraries* (it was only the GHC-specific implementations, though). (Also, nobody seems to have applied that patch yet for some reason.) And I needed to change them to use the raw, unchecked primops.
Oh, that reminds me. Why call them "unsafe"? Why not "unchecked" as GHC's primops are called?
yes definitely. we should reserve 'unsafe' for when we really mean it. I see three levels of unsafeness, and try to use them appropriately. unsafeFoo - can break the static properties of the program. such as unsafePerformIO breaking typesafety, or the obvious unsafeCoerce unwiseFoo - can break dynamic properties of the program, the program will not go wrong or see any inconsistant results within a single run, but it might see different ones if run again or on a different machine. uncheckedFoo - under certain conditions that arn't checked for, this routine may produce well defined, but unspecified behavior. (as in, the behavior might depend on something compiler or architecture specific) John -- John Meacham - ⑆repetae.net⑆john⑈
john:
On Mon, Nov 06, 2006 at 02:09:18PM -0500, Samuel Bronson wrote:
It isn't really *unsafe*, exactly. But it might not be purely functional. However, it isn't imperative or anything like that. Also, for rotate, I needed to change the implementations in the *libraries* (it was only the GHC-specific implementations, though). (Also, nobody seems to have applied that patch yet for some reason.) And I needed to change them to use the raw, unchecked primops.
Oh, that reminds me. Why call them "unsafe"? Why not "unchecked" as GHC's primops are called?
yes definitely. we should reserve 'unsafe' for when we really mean it.
I see three levels of unsafeness, and try to use them appropriately.
unsafeFoo - can break the static properties of the program. such as unsafePerformIO breaking typesafety, or the obvious unsafeCoerce
Good idea: unsafePerformIO unsafeCoerce#
unwiseFoo - can break dynamic properties of the program, the program will not go wrong or see any inconsistant results within a single run, but it might see different ones if run again or on a different machine.
unwiseInterleaveIO :)
uncheckedFoo - under certain conditions that arn't checked for, this routine may produce well defined, but unspecified behavior. (as in, the behavior might depend on something compiler or architecture specific)
uncheckedShift uncheckedRead/Write -- Don
On Fri, 10 Nov 2006, Donald Bruce Stewart wrote:
uncheckedFoo - under certain conditions that arn't checked for, this routine may produce well defined, but unspecified behavior. (as in, the behavior might depend on something compiler or architecture specific)
uncheckedShift uncheckedRead/Write
Doesn't a uncheckedRead/Write potentially crash my machine and/or overwrite arbitrary points of memory? It seems like at least unwiseunsafeWrite could break the dynamic semantics by breaking the static semantics in a random and machine dependent way. And still a uncheckedRead can segfault my machine. I submit that any instruction that can segfault my machine is unsafe. -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''
roconnor:
On Fri, 10 Nov 2006, Donald Bruce Stewart wrote:
uncheckedFoo - under certain conditions that arn't checked for, this routine may produce well defined, but unspecified behavior. (as in, the behavior might depend on something compiler or architecture specific)
uncheckedShift uncheckedRead/Write
Doesn't a uncheckedRead/Write potentially crash my machine and/or overwrite arbitrary points of memory? It seems like at least unwiseunsafeWrite could break the dynamic semantics by breaking the static semantics in a random and machine dependent way. And still a uncheckedRead can segfault my machine. I submit that any instruction that can segfault my machine is unsafe.
:) -- Don
On 11/10/06, roconnor@theorem.ca
On Fri, 10 Nov 2006, Donald Bruce Stewart wrote:
uncheckedFoo - under certain conditions that arn't checked for, this routine may produce well defined, but unspecified behavior. (as in, the behavior might depend on something compiler or architecture specific)
uncheckedShift uncheckedRead/Write
Doesn't a uncheckedRead/Write potentially crash my machine and/or overwrite arbitrary points of memory? It seems like at least unwiseunsafeWrite could break the dynamic semantics by breaking the static semantics in a random and machine dependent way. And still a uncheckedRead can segfault my machine. I submit that any instruction that can segfault my machine is unsafe.
I was thinking the same thing. Also, note that unchecked shifts *don't* necessarily have well-defined behaviour. I mean, no nasal daemons or anything[1], but the values produced when out-of-range shift values are passed in could be anything (anything non-bottom, that is), couldn't they? In the back of K&R (section A7.8), it says "The result is undefined if the right operand is negative, or greater than or equal to the number of bits in the left expression's type." This sounds to me like it could give you random junk, but not crash your program unless your program does something stupid with the result value. So, it would violate referential transparency, maybe, but I don't think it matters that much... I mean, you aren't supposed to pass out-of-range shift amounts to uncheckedShift*. [1] That is, C's "undefined behaviour", where anything, including having daemons fly out your nose or cthulu being summoned, could happen according to the C standard.
participants (5)
-
Bulat Ziganshin -
dons＠cse.unsw.edu.au -
John Meacham -
roconnor＠theorem.ca -
Samuel Bronson