nikita-volkov / stm-hamt Goto Github PK
View Code? Open in Web Editor NEWSTM-specialised Hash Array Mapped Trie
Home Page: https://hackage.haskell.org/package/stm-hamt
License: MIT License
STM-specialised Hash Array Mapped Trie
Home Page: https://hackage.haskell.org/package/stm-hamt
License: MIT License
I migrated some code using unordered-containers Strict HashMap.
https://github.com/YellowOnion/1brc/blob/14842cd63b6f85892f4b9b315be205fa7c2b1eaf/app/Main.hs#L116
I use one map per-thread and then merge them at the end, this should blow-out my L3 (64MB) and create substantially slower code than using one shared Map.
This implementation takes 12s and uses about 450% CPU load.
Migrating my code to stm-containers, it takes 16s and consumes 950% CPU, and spends 50% of it's time inside onBranchElement
.
The core loop looks like this:
stmInsertEntry :: BS.ByteString -> Entry -> HMap -> STM ()
stmInsertEntry !k !v = Map.focus (Focus.insertOrMerge (<>) v) k
calcThread :: (OutChan (Maybe BS.ByteString), Int)
-> HMap
-> IO ()
calcThread (oc, id) m = runInBoundThread go
where go = do
mbs <- readChan oc
case mbs of
Just bs -> do
let (k, v) = parseEntry bs
in atomically $ stmInsertEntry k v m
go
Nothing -> return ()
Here's a profile:
While trying to build the latest haskell-language-server for Fedora 37 (ghc-8.10.7) using cabal-install, I hit:
Building library for stm-hamt-1.2.0.10..
[1 of 9] Compiling StmHamt.Prelude ( library/StmHamt/Prelude.hs, dist/build/StmHamt/Prelude.o, dist/build/StmHamt/Prelude.dyn_o )
[2 of 9] Compiling StmHamt.IntOps ( library/StmHamt/IntOps.hs, dist/build/StmHamt/IntOps.o, dist/build/StmHamt/IntOps.dyn_o )
[3 of 9] Compiling StmHamt.Types ( library/StmHamt/Types.hs, dist/build/StmHamt/Types.o, dist/build/StmHamt/Types.dyn_o )
[4 of 9] Compiling StmHamt.ListT ( library/StmHamt/ListT.hs, dist/build/StmHamt/ListT.o, dist/build/StmHamt/ListT.dyn_o )
[5 of 9] Compiling StmHamt.Constructors.Branch ( library/StmHamt/Constructors/Branch.hs, dist/build/StmHamt/Constructors/Branch.o, dist/build/StmHamt/Constructors/Branch.dyn_o )
[6 of 9] Compiling StmHamt.Focuses ( library/StmHamt/Focuses.hs, dist/build/StmHamt/Focuses.o, dist/build/StmHamt/Focuses.dyn_o )
[7 of 9] Compiling StmHamt.UnfoldlM ( library/StmHamt/UnfoldlM.hs, dist/build/StmHamt/UnfoldlM.o, dist/build/StmHamt/UnfoldlM.dyn_o )
[8 of 9] Compiling StmHamt.Hamt ( library/StmHamt/Hamt.hs, dist/build/StmHamt/Hamt.o, dist/build/StmHamt/Hamt.dyn_o )
library/StmHamt/Hamt.hs:34:66: error:
* Could not deduce (Eq key) arising from a use of `=='
from the context: Hashable key
bound by the type signature for:
focus :: forall key element result.
Hashable key =>
Focus element STM result
-> (element -> key) -> key -> Hamt element -> STM result
at library/StmHamt/Hamt.hs:33:1-108
Possible fix:
add (Eq key) to the context of
the type signature for:
focus :: forall key element result.
Hashable key =>
Focus element STM result
-> (element -> key) -> key -> Hamt element -> STM result
* In the first argument of `(.)', namely `(==) key'
In the third argument of `focusExplicitly', namely
`((==) key . elementToKey)'
In the expression:
focusExplicitly focus (hash key) ((==) key . elementToKey)
|
34 | focus focus elementToKey key = focusExplicitly focus (hash key) ((==) key . elementToKey)
| ^^^^^^^^
library/StmHamt/Hamt.hs:47:36: error:
* Could not deduce (Eq key) arising from a use of `=='
from the context: Hashable key
bound by the type signature for:
insert :: forall key element.
Hashable key =>
(element -> key) -> element -> Hamt element -> STM Bool
at library/StmHamt/Hamt.hs:44:1-83
Possible fix:
add (Eq key) to the context of
the type signature for:
insert :: forall key element.
Hashable key =>
(element -> key) -> element -> Hamt element -> STM Bool
* In the first argument of `(.)', namely `(==) key'
In the second argument of `insertExplicitly', namely
`((==) key . elementToKey)'
In the expression:
insertExplicitly (hash key) ((==) key . elementToKey) element
|
47 | in insertExplicitly (hash key) ((==) key . elementToKey) element
| ^^^^^^^^
library/StmHamt/Hamt.hs:100:56: error:
* Could not deduce (Eq key) arising from a use of `=='
from the context: Hashable key
bound by the type signature for:
lookup :: forall key element.
Hashable key =>
(element -> key) -> key -> Hamt element -> STM (Maybe element)
at library/StmHamt/Hamt.hs:99:1-90
Possible fix:
add (Eq key) to the context of
the type signature for:
lookup :: forall key element.
Hashable key =>
(element -> key) -> key -> Hamt element -> STM (Maybe element)
* In the first argument of `(.)', namely `(==) key'
In the second argument of `lookupExplicitly', namely
`((==) key . elementToKey)'
In the expression:
lookupExplicitly (hash key) ((==) key . elementToKey)
|
100 | lookup elementToKey key = lookupExplicitly (hash key) ((==) key . elementToKey)
| ^^^^^^^^
Error: cabal: Failed to build stm-hamt-1.2.0.10 (which is required by
exe:haskell-language-server-wrapper from haskell-language-server-1.10.0.0 and
exe:haskell-language-server from haskell-language-server-1.10.0.0). See the
build log above for details.
Thanks to nikita-volkov/stm-containers#30, there's a version of stm-containers
which supports transformers
0.6. However, given the dependency on stm-hamt
, which doesn't support transformers
0.6 (yet), things don't really work out.
related to nikita-volkov/primitive-extras#4, a higher upper bound is required for ghc 9 support
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.