mcschroeder/ttrie

A contention-free STM hash map for Haskell

A contention-free STM hash map for Haskell.

"Contention-free" means that the map will never cause spurious conflicts. A transaction operating on the map will only ever have to retry if another transaction is operating on the same key at the same time.

This is an implementation of the transactional trie, which is basically a lock-free concurrent hash trie lifted into STM. For a detailed discussion, including an evaluation of its performance, see Chapter 3 of my master's thesis.

ttrie's Issues

What would appropriate caution be when using unsafeDelete?

Docs for unsafeDelete state:

This is not an atomic operation, however. Use with caution!

What would be an appropriate level of caution? External synchronization?

Is the risk that another operation would get a stale read, or could this potentially corrupt the data structure?

Thanks!

Put ttrie on stackage

Hello,

as this package is quite interesting and to gain more traction you should consider adding it to Stackage!

Questions about the future

Hey, great project! I'm wondering about a few things:

• Is the API going to change? Any new operations planned, or does it have to stay similar to keep those nice properties?
• Is it a problem, in practice, that keys stay in memory after deletion? Is the memory requirement large there?

Have you posted it on reddit or somewhere? I'm sure the community would appreciate it.

Compilation failure against primitive 0.7.3.0

/var/stackage/work/unpack-dir/unpacked/ttrie-0.1.2.1-6fd7d840f6d22ff83ebd4cdc2cebda36bb56ba8a9665557e9ca203b0cd0e0475/src/Data/SparseArray.hs:8:7: error:
    Ambiguous occurrence ‘emptyArray’
    It could refer to
       either ‘Data.Primitive.Array.emptyArray’,
              imported from ‘Data.Primitive.Array’ at src/Data/SparseArray.hs:17:1-27
           or ‘Data.SparseArray.emptyArray’,
              defined at src/Data/SparseArray.hs:32:1
  |
8 |     , emptyArray, mkSingleton, mkPair
  |       ^^^^^^^^^^
curator: Received ExitFailure 1 when running

c.f. commercialhaskell/stackage#6259