google-research / google-research/dex-lang

Demo idea: Hashable interface with parallelizable associative hash function

Open
#591 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
Haskell
Stars
1.7k
Forks
116
PR merge metrics
No merged PRs in 30d

Description

It's useful to be able to hash any data structure, and it should be straightforward to allow this using Dex's typeclass system. Haskell has a comprehensive [Hashable typeclass](https://hackage.haskell.org/package/hashable), for example.

But rather than just copying Haskell's implementation, there's a potential for Dex's implementation to take advantage of parallelism and the `Accum` effect. The only catch is that we'd have to find an associative hashing operation.

Luckily, one was recently developed: [Hashing with SL2](https://www.rocq.inria.fr/secret/Jean-Pierre.Tillich/publications/HashingSL2.pdf)

Here's a [Haskell implementation](https://hackage.haskell.org/package/hwsl2), which wraps [C code](https://hackage.haskell.org/package/hwsl2-0.4.0.1/src/src/core/gf2p127-inl.h) and uses lots of `unsafePerformIO`. I expect that a Dex version could be much shorter, more portable and GPU friendly, and probably also allow more parallelism within chunks.

To get started, below is the beginning of an interface. The main idea is that an associative hash would allow the sequential `fold` for the table instance could be replaced with a parallel `reduce`.

```
interface Hashable a
hash : Key -> a -> Key

instance Hashable Int32
hash = \key y.
y64 = IToW64 y
threeFry2x32 key y64

instance Hashable Float32
hash = \key y.
y64 = IToW64 $ FToI y
threeFry2x32 key y64

instance Hashable (Fin n)
-- Todo: This should be the instance for the Idx typeclass.
hash = \key y.
y64 = IToW64 (ordinal y)
threeFry2x32 key y64

instance [Hashable a] Hashable (Maybe a)
hash = \key x. case x of
Nothing -> hash (IToW64 0) 0
Just x -> hash (IToW64 1) x

instance [Hashable a] Hashable (n=>a)
hash = \key table.
fold key \i k. hash k table.i

instance [Hashable a, Hashable b] Hashable (a & b)
hash = \key (left, right).
hash (hash key left) right

instance [Hashable a, Hashable b] Hashable (a | b)
hash = \key lor. case lor of
Left lor -> hash (IToW64 0) lor
Right lor -> hash (IToW64 1) lor
```

This [blog post](https://alexknvl.com/posts/monoidal-hashing.html) also gives a bit more background on the problem, and an alternative approach.

Contributor guide

Open the contributing guide

Research direction

Start by reviewing the proposed Hashable interface and its examples for Int32, Float32, Fin, Maybe, tables, products, and sums. Then investigate how Dex currently implements typeclasses, fold, reduce, and the Accum effect. Done would require a decided associative hashing design and a complete, tested Dex implementation, but the issue does not identify relevant files or tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.