haskell-unordered-containers / hashable Goto Github PK

Hi,

I’m having trouble building hashable on powerpc and likely other architectures, as reported at http://bugs.debian.org/783772:

Test suite tests: RUNNING...
properties:
  bernstein: [OK, passed 100 tests]
  text:
    text/strict: [OK, passed 100 tests]
    text/lazy: [OK, passed 100 tests]
    text/rechunk: [OK, passed 100 tests]
    text/rechunked: [OK, passed 100 tests]
  bytestring:
    bytestring/strict: [OK, passed 100 tests]
    bytestring/lazy: [OK, passed 100 tests]
    bytestring/short: [OK, passed 100 tests]
    bytestring/rechunk: [OK, passed 100 tests]
    bytestring/rechunked: [OK, passed 100 tests]
  generics:
    sum2_differ: [OK, passed 100 tests]
    sum3_differ: [OK, passed 100 tests]
regressions:
  hashNearPageBoundary: [Failed]
ERROR: mmap: invalid argument (Invalid argument)

         Properties   Test Cases  Total       
 Passed  12           0           12          
 Failed  0            1           1           
 Total   12           1           13          
Test suite tests: FAIL
Test suite logged to: dist-ghc/test/hashable-1.2.3.2-tests.log
0 of 1 test suites (0 of 1 test cases) passed.

Full log at https://buildd.debian.org/status/fetch.php?pkg=haskell-hashable&arch=powerpc&ver=1.2.3.2-2&stamp=1430199777

Do you have any idea what this could mean?

When compiled with -msse4.1, SSE 4.1 instructions are generated even for siphash-sse2.c (at least with gcc 4.6.3 on Linux). Can be verified by searching for pinsrd in the generated assembly or running this function on an older processor.

GDB session log:

(gdb) run
Starting program: server 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
[New Thread 0x1100b40 (LWP 28445)]
[New Thread 0x1901b40 (LWP 28446)]
no port specified, defaulting to port 8000
Listening on http://0.0.0.0:8000/
[New Thread 0x2102b40 (LWP 28448)]

Program received signal SIGILL, Illegal instruction.
[Switching to Thread 0x1901b40 (LWP 28446)]
0x08155f2e in hashable_siphash24_sse2 ()
(gdb) bt
#0  0x08155f2e in hashable_siphash24_sse2 ()
#1  0x0815375c in hashablezm1zi2zi0zi2_DataziHashableziClass_zdwzdchashWithSalt1_info ()
#2  0xaee1721a in ?? ()
#3  0x56e2b8a0 in ?? ()
#4  0xed74dd7a in ?? ()
#5  0x89ab6abd in ?? ()
#6  0x008f1f80 in ?? ()
Backtrace stopped: previous frame inner to this frame (corrupt stack?)
(gdb) display/i $pc
1: x/i $pc
=> 0x8155f2e <hashable_siphash24_sse2+270>: pinsrd $0x1,%esi,%xmm5

SipHash is a new hash function by Bernstein et. al. the promises both good performance on short strings and cryptographic properties. The latter is useful to avoid denial of service attacks when the attacker can chose the keys that go into some hash table.

http://131002.net/siphash/siphash.pdf

Two things need to happen if we are to switch to SipHash:

1. Evaluate its performance relative to the current implementation.
2. Create an incremental version such that the hash of a strict and lazy bytestring with the same content (but with different chunk boundaries) are the same.

the size field of the J# constructor is a signed size, so all negative numbers with the J# constructor get hashed to the same number.

The most recent entry seems to be about 3 years old, and it's shown on hackage via the changelog link

It's no big deal, but it would be useful for users to get an overview about what changed between 1.1 and 1.2

Can you please limit SSE usage in hashable?

Reasons:

1. It hurts people with older gccs, like OpenBSD people (-msse4.1 is not supported by gcc 4.2.1)
2. It hurts people with older cpus. I managed to build it with clang 3.1 using --ghc-options="-pgmc clang -pgml clang -pgma clang" and get "Illegal instruction" when trying to run code using hashable.
   My cpu is Genuine Intel(R) CPU T2400 @ 1.83GHz ("GenuineIntel" 686-class).
   I'm running OpenBSD/i386.
   hashable 1.2.0.2, ghc 7.4.2

Hashable has become the defacto way to hash in Haskell.

However, there is no way to get a hash that is consistent across platforms with different sizes for Int at this time.

This means incurring a constraint for another class, when users have frankly grown used to using and supplying instances for this one.

I'm mostly posting this to note that there is an issue, not necessarily crying out for an immediate resolution.

This is just an idea, I'd like to propose and discuss:

Sometimes the hash operation might be a bit more expensive, so maybe a wrapper in the style of (untested):

data HashCached a = HashCached !Int a   deriving (Eq)

-- smart-constructor
mkHashCached :: Hashable a => a -> HashCached a
mkHashCached v = HashCached (hash v) v

instance HashCached a where
   hash (HashCached i _) = i

...would allow to be able store data with a precomputed hash-value; before I waste more time with investigating idea: what do you think of it?

> hash (0, 1) == hash (1, 0)
True
> hash (7, 5, 5) == hash (5, 7, 5)
True
> hash (8, 9, 4, 9) == hash (8, 9, 9, 4)
True

It is very fatal when creating containers wherein the keys are tuples.

See Data.Unique

I have noticed huge performance regression in latest hashable library.

For example, this program (http://hpaste.org/81663) runs almost 3 times slower with hashable 1.2.0.5 - 190 seconds on my pc vs 70 seconds with hashable 1.2.0.4.

This was tested on windows x86, ghc 7.6.2

foreign import ccall unsafe "djb_hash_offset" c_hashByteArray
:: ByteArray# -> CLong -> CLong -> CLong -> CLong

This is outside of the GHC ifdef. I can take care of the change - this is just here in case I forget.

Using version 1.2.0.2 of hashable from Hackage, the following program reliably segfaults (whether compiled or interpreted):

import Data.Text (empty)
import Data.Hashable (hash)

main = print $ hash empty

The next commit in the history (8a416d0) fixes the problem. Given that that commit seems to just deal with architecture issues, this might be a CPU-specific bug instead of an OS-specific bug. Either way, I think a new version of hashable should be released ASAP.

Based on a git bisect, I believe the bug was introduced in: 2e3ebc1

The title says it all.

Here's the gist of what's missing:

import Data.Hashable
import qualified Data.ByteString.Short.Internal as BI

instance Hashable BI.ShortByteString where
    hashWithSalt salt sbs@(BI.SBS ba) 
        = hashByteArrayWithSalt ba 0 (BI.length sbs) salt

Building hashable-1.2.0.6...
Preprocessing library hashable-1.2.0.6...
[1 of 4] Compiling Data.Hashable.RandomSource ( Data/Hashable/RandomSource.hs, dist/build/Data/Hashable/RandomSource.o )
[2 of 4] Compiling Data.Hashable.Class ( Data/Hashable/Class.hs, dist/build/Data/Hashable/Class.o )
[3 of 4] Compiling Data.Hashable.Generic ( Data/Hashable/Generic.hs, dist/build/Data/Hashable/Generic.o )
[4 of 4] Compiling Data.Hashable ( Data/Hashable.hs, dist/build/Data/Hashable.o )
In-place registering hashable-1.2.0.6...
Preprocessing test suite 'tests' for hashable-1.2.0.6...

tests/Regress.hs:8:18:
Could not find module `Regress.Mmap'
Use -v to see a list of the files searched for.

I've once managed to make the test suite fail with:

"\NUL"
""

  text/lazy: [Failed]
Falsifiable with seed -776323391, after 24 tests. Reason: Falsifiable

This was on OS X 10.6.4 on a Intel Core 2 Duo.

Hi,

Is there the slightest chance that Hashable will ever get PowerPC support ?

Thanks in advance,

Gaël Deest

There are numerous hash collisions for relatively short sequences of ASCII characters (this is for the String instance, but tuples of Char etc. have essentially the same problem):

let eqhash a b = hash a == hash b
let sameHashes xs = filter (\xs -> not (null xs) && not (null (tail xs))) . groupBy eqhash . sortBy (comparing hash) $ xs
let readable = [' '..'~']
let mcons a b = liftM2 (:) a b
sameHashes $ mcons readable $ mcons readable [""]

Note that there are 3-way hash collisions for simple two-character strings. It seems like a better combine function would be a good idea; a teensy bit more computation would be offset by reduced collisions and thus fewer string equality tests. The best test here is probably benchmarking on 0-4 character strings using Data.HashMap.Strict. My concern here is as much with data structures containing multiple integer fields whose value is usually small as much as with strings, though.

A user has been been trying to install uniplate via Cygwin on Windows 7x64 running ghc 7.6.1, with Cabal 1.16.0.2. The compilation of Uniplate is failing related to " __imp_CryptAcquireContextA", with the error:

ghc.exe: unable to load package `hashable-1.2.0.2'
ghc.exe: C:\Program Files\Haskell\hashable-1.2.0.2\ghc-7.6.1\HShashable-1.2.0.2.o: unknown symbol `__imp_CryptAcquireContextA'

I advised the user downgrade to hashable-1.1 which worked.

Compiling with GHC 7.8, I get the following warning:

Data/Hashable/Class.hs:193:11: Warning:
    In the use of ‘bitSize’ (imported from Data.Bits):
    Deprecated: "Use 'bitSizeMaybe' or 'finiteBitSize' instead"

Data/Hashable/Class.hs:216:11: Warning:
    In the use of ‘bitSize’ (imported from Data.Bits):
    Deprecated: "Use 'bitSizeMaybe' or 'finiteBitSize' instead"

Data/Hashable/Class.hs:100:15: Warning:
    Literal 15868100553162883236 is out of the Int range -9223372036854775808..9223372036854775807

I don't know if this is intended, but I think it would be clearer to write the actual value instead of some value that will overflow.

I assume nobody tries to compile Hashable without GHC, but anyway: the Hashable instance of Text uses hashByteArrayWithSalt, which is provided conditionally if defined(__GLASGOW_HASKELL__). To be consistent, we should either

• remove the conditional compilation of hashByteArrayWithSalt. The ByteArray# is mentioned from the Text package, which we depend on unconditionally.
• provide instances for Text only for GHC (and also depending on Text only when using GHC).
• theoretically we could provide two Text instances, one GHC and other non-GHC. But currently Text does not compile without GHC, so I think it has no sense doing it.

Cabal doesn't pass cpp-options when compiling c-sources. Thus, #ifdefs introduced in 2fc2e2d effectively disable SSE2 in all cases.

IMHO, Data.Hashable should provide a type synonym to avoid having to hard-code Ints (although client code is still free to use Ints) and help make type-signatures more self explanatory, e.g.

type Hash = Int

Then type signatures would read as

hash :: Hashable a => a -> Hash
hashWithSalt :: Hashable a => Int -> a -> Hash
combine :: Hash -> Hash -> Hash

PS: This could pave the way to take it a step further, by making hash-values a newtype Hash to enforce type-safety (e.g. to help avoid mixing up opaque hash-values with integers denoting quantities or other real-world properties)

Hi.

When I try to run this program, with the input json that is a parameter in the program, sometimes I get an error, and sometimes I the json is parsed correctly. The provided Json is correct, and the problem is not the UTF-8 encoding issues.

Source: http://hpaste.org/87328

To get more than one result, the program must be executed from GHCi, calling main, several times. It should fail about 4 of 5 tries, returning Nothing instead of the correct parse. With hashable-1.1.2.5 it works.

I get a segfault with GHCi 7.6.1 on Windows XP with the following interactions:

C:\spacework>ghci
GHCi, version 7.6.1: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> import Data.Hashable
Prelude Data.Hashable> import Data.ByteString.Char8
Prelude Data.Hashable Data.ByteString.Char8> hash $ pack ""
Loading package array-0.4.0.1 ... linking ... done.
Loading package deepseq-1.3.0.1 ... linking ... done.
Loading package bytestring-0.10.0.0 ... linking ... done.
Loading package text-0.11.2.3 ... linking ... done.
Loading package hashable-1.2.0.2.1 ... linking ... done.
<segfault>

Note that 1.2.0.2.1 is hashable repo at f649428. This segfault occured in previous versions of hashable, then went away, and has now come back.

with ghc-7.6.1, hashable-1.1.2.5, on linux, amd64, the following program can be compiled, but gives Stack space overflow at runtime.

{-# language DeriveGeneric #-}

import Data.Hashable
import GHC.Generics

data Foo a = Foo a deriving (Show, Generic)

instance Hashable a => Hashable (Foo a)

main = print $ hash $ Foo (42 :: Int)

On 32bit Linux, hashing ByteString causes segfault:

% ghci -XOverloadedStrings

:m Data.Hashable
:m +Data.ByteString.Char8
hash ("/" :: ByteString)
zsh: segmentation fault ghci -XOverloadedStrings

This bug introduced some between 1.1.2.5 and 1.2.0.0. This bug does not exist on 64bit Linux.

It is my understanding that the Bernstein hash used in hashable has poor performance on binary (non-ASCII) data and has bad dispersion for short sequences.

I propose using FNV-1a hash instead (it is public domain, information draft is at http://tools.ietf.org/html/draft-eastlake-fnv-03). It has better dispersion qualities, is usable on binary data, but is very simple and structurally similar to Bernstein hash.

The C implementation would change from

  while (len--) {
    hash = (hash * 33) ^ *str++;
  }

to

  while (len--) {
    hash = (hash ^ *str++) * 16777619;
  }

and the Haskell implementation from

combine h1 h2 = (h1 + h1 `shiftL` 5) `xor` h2

to

combine h1 h2 = (h1 `xor` h2) * 16777619;

I will create a pull request if we decide to proceed.

Build of hashable-1.2.3.2 fails in integer-simple configuration (i.e. with -f-integer-gmp) with the following error:

Data\Hashable\Class.hs:269:0:
     error: missing binary operator before token "("

Looks like the problem is that MIN_VERSION_integer_gmp macro is not defined. Reverting changes from 6a4437d fixes the problem.

Hi, I'm getting:

(gdb) run
Starting program: /home/tycho/playground/hq/dist/build/AttributeTests/AttributeTests 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".

Program received signal SIGILL, Illegal instruction.
0x0818cf6e in hashable_siphash24_sse2 ()
(gdb) display/i $pc
3: x/i $pc
=> 0x818cf6e <hashable_siphash24_sse2+270>:     pinsrd $0x1,%esi,%xmm5

when I'm on an atom CPU. My /proc/cpuinfo says I've got sse2 support, though not sse4. A bit of googling seems to indicate that pinsrd is an sse4 instruction.

There are some bad instances of Hashable that use small integers as hash results.

This is a bad idea, as it makes it trivially easy to exploit arithmetic properties to cause collisions.

Witness the definition of combine:

combine h1 h2 = (h1 * 16777619) `xor` h2

It's common for people combining hashes to write definitions like this. In this case, it is obvious that if you can fix the first hash to be zero, the result will be exactly the second hash.

Worse, if someone chains together a series of multiplications in an instance of their own, they can accidentally end up with hashes always being zero.

I propose two ways to address this problem:

1. Document it. In the Hashable class, tell people to use large random numbers, and why,
2. Fix the current vulnerable instances by replacing small random numbers with large.

Because the preprocessor does not understand negation, so this test in Data/Hashable/Class.hs is always false, and Data.ByteString.Lazy.Internal does not get imported:

#if !MIN_VERSION_bytestring(0,10,0)
import qualified Data.ByteString.Lazy.Internal as BL -- foldlChunks
#endif

I recommend using

#if MIN_VERSION_bytestring(0,10,0)
#else
import qualified Data.ByteString.Lazy.Internal as BL -- foldlChunks
#endif

instead.

It would be nice if hash could fold constants at compile time, so that writing things like

 Data.HashMap.Strict.lookup "fieldName"  x

wouldn't repeatedly recompute the the hash for fieldName. I'm not sure how to accomplish this at the moment though.

When I attempt to cabal install hashable from a clean install with GHC 7.8.2, I get

[3 of 3] Compiling Data.Hashable    ( Data/Hashable.hs, dist/build/Data/Hashable.o )
/usr/bin/ld: cannot find -lHStext-1.1.0.1-ghc7.8.2
collect2: error: ld returned 1 exit status
Failed to install hashable-1.2.1.0
cabal: Error: some packages failed to install:
hashable-1.2.1.0 failed during the building phase. The exception was:
ExitFailure 1

.

The installation proceeded smoothly after a cabal install text.

As mentioned in Issue #30 Integral types do now hash to themselves. This leads to several problems.

Generally this behaviour would be okay if the combining function would take care of this. In the current implementation it is using a simple xor which has the following property:

xor 0 a = a
xor a 0 = a

Which makes the following hashes to be the same:
hash [] == hash [0,0,0,0] == hash [1,0,0] == hash [0,1,0] == hash [1]

As mentioned in the old issue, languages like Python also hash Ints to themselves. But they got the chaining right. In Python:
hash ((0)) = 0
hash ((0,0)) = 3713080549408328131

Further the usage of xor loads to miserable avalanche behavior for chains of Ints, For example:

hash [1,2] == hash 3
hash [1,2,3] == hash 0

This leads to a ton of hash collisions and all kind of funky errors.

This property naturally expands to generic instances which will affect a wide range of applications. For Example
data Salary = Salary { month :: Int, salary :: Int }
hash (Salary 1 2) == hash (Salary 0 3)
hash (Salary 0 1) == hash (Salard 1 0)

A long-running application of me seems to segfault every once in a long while. I ran it using GDB last time and got the backtrace -- it seems to fail on ByteString hashing in some particular case.

GDB gives me a segfault on 0x088ed28a in hashable_siphash_24_sse2. The disassembly of this method can be found here: https://gist.github.com/jaspervdj/4986452

I think I'm going to recompile hashable with debugging flags enabled and try to reproduce it. However, the issue only appears after running for a few days so it might take a while.

Johannes Weiß reports:

I just compiled a program and crashes "Illegal Instruction" and it's probably related to your new hashable implementation, I think.

gdb tells me

Program received signal SIGILL, Illegal instruction.
0x081daf9e in hashable_siphash24_sse2 ()

(The failing instruction is "=> pinsrd $0x1,%esi,%xmm5")

I used cabal-dev to build, hashable-1.2.0.2 installed and currently I am testing against the standard GHC on my Debian (version 7.4.1). My computer runs Linux 3.1.7 (vanilla) and a Intel Core Duo T2400 @ 1.83GHz (32bit). cat /proc/cpuinfo lists the following flags:

fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx constant_tsc arch_perfmon bts aperfmperf pni monitor vmx est tm2 xtpr pdcm dts

The Void type was moved from void to base-4.8, but by doing that it had to lose its (trivial) Hashable instance.

Here's the basic gist of what needs to be added to hashable:

#if MIN_VERSION_base(4,8,0)
import Data.Void (Void, absurd)

instance Hashable Void where
  hashWithSalt _ = absurd
#endif

/cc @ekmett

The builds fails with the message:

tests/Regress.hs:8:18:
    Could not find module `Regress.Mmap'
    Use -v to see a list of the files searched for.

I guess that file is missing from the Cabal file and thus the release tarball?

Citing from http://hydra.cryp.to/build/723359/nixlog/1/raw:

Data/Hashable/Class.hs:458:40: Not in scope: ‘typeRepFingerprint’

This simple benchmark, which uses the hashtables package, gets about 22x slower if you compile it with hashable-1.2.0.5 instead of hashable-1.1.2.5:

{-# LANGUAGE BangPatterns #-}

import qualified Data.HashTable.IO as H

main :: IO ()
main = do
  h <- H.fromList [(x,x) | x <- [1..n]] :: IO (H.BasicHashTable Int Int)
  print =<< H.lookup h 100
  where
    n = 10^(7 :: Int)

Using ghc-7.4.2, 32 bit and cabal 1.16.0.2 on MacOS X 10.8.

Installing hashable with cabal works, but using the library with persistent gives this error:

Configuring persistent-1.1.4...
Building persistent-1.1.4...
Preprocessing library persistent-1.1.4...
[ 1 of 15] Compiling Database.Persist.Util ( Database/Persist/Util.hs, dist/build/Database/Persist/Util.o )
[ 2 of 15] Compiling Database.Persist.TH.Library ( Database/Persist/TH/Library.hs, dist/build/Database/Persist/TH/Library.o )
[ 3 of 15] Compiling Database.Persist.EntityDef ( Database/Persist/EntityDef.hs, dist/build/Database/Persist/EntityDef.o )
[ 4 of 15] Compiling Database.Persist.Quasi ( Database/Persist/Quasi.hs, dist/build/Database/Persist/Quasi.o )
[ 5 of 15] Compiling Database.Persist.Store ( Database/Persist/Store.hs, dist/build/Database/Persist/Store.o )
[ 6 of 15] Compiling Database.Persist.GenericSql.Internal ( Database/Persist/GenericSql/Internal.hs, dist/build/Database/Persist/GenericSql/Internal.o )
[ 7 of 15] Compiling Database.Persist.GenericSql.Raw ( Database/Persist/GenericSql/Raw.hs, dist/build/Database/Persist/GenericSql/Raw.o )
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Loading package array-0.4.0.0 ... linking ... done.
Loading package deepseq-1.3.0.0 ... linking ... done.
Loading package filepath-1.3.0.0 ... linking ... done.
Loading package old-locale-1.0.0.4 ... linking ... done.
Loading package old-time-1.1.0.0 ... linking ... done.
Loading package bytestring-0.9.2.1 ... linking ... done.
Loading package unix-2.5.1.1 ... linking ... done.
Loading package directory-1.1.0.2 ... linking ... done.
Loading package silently-1.2.4.1 ... linking ... done.
Loading package text-0.11.2.3 ... linking ... done.
Loading package hashable-1.2.0.4 ... linking ... ghc:
lookupSymbol failed in resolveImports
/Users/mb/Library/Haskell/ghc-7.4.2/lib/hashable-1.2.0.4/lib/HShashable-1.2.0.4.o: unknown symbol _hashable_siphash24_sse2' ghc: unable to load packagehashable-1.2.0.4'
Failed to install persistent-1.1.4

Please consider adding

#if defined(__GLASGOW_HASKELL__) && __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif

to the top of Data.Hashable.

As it is, no package that depends transitively on hashable 1.2 can be Safe-Inferred. They all have to explicitly claim to be Trustworthy. This greatly expands the required trusted core, and the number of places that a distrustful user needs to inspect for safety.

This flag simply enables users to trust the package. Without it they have no recourse.

The current configuration of hashable assumes that at least SSE2 is available for all x86 builds. In practice, some x86 installations don't have working SSE support (sometimes due to compiler problems, sometimes because of old processors). Would it be possible to add a flag to disable SSE entirely?

Hi,

I am using GHC, Version 7.0.3. Tried failed to install via cabal:

Resolving dependencies...
cabal: hashable.cabal:74: The 'type' field is required for test suites. The
available test types are: exitcode-stdio-1.0
cabal: Error: some packages failed to install:
hashable-1.2.0.5 failed during the configure step. The exception was:
ExitFailure 1

Is this a problem with the package or I am doing something wrong?

Thank you,
Radu

Currently structures containing lists are treated as if they were all concatenated: hash ["abc"] == hash ["a","bc"] == hash ("ab", "c") == hash "abc". That is, hashable completely ignores the structure. Is it deliberate?

I think that in some cituations it might be a serious flaw — for instance, storing all partitions of a list (they would all have one hash).

the subject says it all :-)

See Data.Version

Given the @hvr PPA as used in Travis buildbot testing, I get the error:

Data/Hashable/Class.hs:456:14:
    Constructor ‘TypeRep’ should have 4 arguments, but has been given 3
    In the pattern: TypeRep (Fingerprint x _) _ _
    In an equation for ‘hashTypeRep’:
        hashTypeRep (TypeRep (Fingerprint x _) _ _) = fromIntegral x

This is either an error with the @hvr PPA, or a real error that is going to start occurring with GHC 7.10.1.