search

sebastian-philipp / StringMap

Haskell Project to convert the PrefixTree of the Holumbus into it's own Hackage Packet
MIT License
1 stars 5 forks source link

Ghc9x #9

Open mantkiew opened 1 year ago

mantkiew commented 1 year ago

Make the code compatible with GHC 9.x.

  1. fix strictness syntax
  2. make values strict in strict StringMap (port of https://github.com/alexbiehl/StringMap/commit/abdc99c2f11f39dbb0c6c69f1e934d4844ff91bd)
  3. fix for MonadFail required to use fail

Code now also builds with

sebastian-philipp commented 1 year ago

Curious. What is your use case for this?

mantkiew commented 1 year ago

Hi,

thanks for contacting me. We have this project https://www.clafer.org/ which is a modeling language and a compiler. It has been dormant for years, but people still keep using it and I am now modernizing it to work with the current GHC.

https://github.com/gsdlab/clafer/commits/develop

I tried migrating to Data.HashMap but they don't have the "prefixFind" function (https://hackage.haskell.org/package/data-stringmap-1.0.1.1/docs/Data-StringMap-Strict.html#v:prefixFind), which we use. Do you know of an alternative package that would provide that?

Thanks a lot for your package.

Best,

Michał Antkiewicz, MSc., PhD Research Engineer Waterloo Intelligent Systems Engineering (WISE) Lab University of Waterloo https://uwaterloo.ca/wise-lab/ E7-5418

From: Sebastian Wagner @.> Sent: August 24, 2023 10:23 AM To: sebastian-philipp/StringMap @.> Cc: Michal Antkiewicz @.>; Author @.> Subject: Re: [sebastian-philipp/StringMap] Ghc9x (PR #9)

Curious. What is your use case for this?

— Reply to this email directly, view it on GitHubhttps://github.com/sebastian-philipp/StringMap/pull/9#issuecomment-1691784335, or unsubscribehttps://github.com/notifications/unsubscribe-auth/AADLKSOL7KI23YV25KYZNUTXW5PW7ANCNFSM6AAAAAA35BIYXQ. You are receiving this because you authored the thread.Message ID: @.***>

sebastian-philipp commented 1 year ago

Yeah, right this is probably the only reason to use this package at all. There is just one problem: I have no easy way to verify your PR. Let me think.

mantkiew commented 1 year ago

I tried to get benchmarking working. Added benchmark section to the cabal file and information into README. Here are my results:

$ cabal bench
...
Running 1 benchmarks...
Benchmark bench-all: RUNNING...
benchmarking lookup
time                 27.78 ms   (25.56 ms .. 29.25 ms)
                     0.981 R²   (0.955 R² .. 0.995 R²)
mean                 31.97 ms   (30.56 ms .. 33.15 ms)
std dev              2.811 ms   (2.310 ms .. 3.555 ms)
variance introduced by outliers: 34% (moderately inflated)

benchmarking insert
time                 57.58 ms   (55.47 ms .. 59.29 ms)
                     0.997 R²   (0.994 R² .. 1.000 R²)
mean                 56.74 ms   (55.23 ms .. 58.51 ms)
std dev              3.083 ms   (2.058 ms .. 4.828 ms)
variance introduced by outliers: 15% (moderately inflated)

benchmarking insertWith empty
time                 53.65 ms   (50.41 ms .. 56.14 ms)
                     0.994 R²   (0.989 R² .. 0.998 R²)
mean                 57.23 ms   (55.88 ms .. 59.32 ms)
std dev              3.092 ms   (2.019 ms .. 4.642 ms)
variance introduced by outliers: 15% (moderately inflated)

benchmarking insertWith update
time                 69.83 ms   (66.27 ms .. 73.74 ms)
                     0.995 R²   (0.990 R² .. 0.999 R²)
mean                 69.64 ms   (68.08 ms .. 71.80 ms)
std dev              3.080 ms   (1.720 ms .. 4.731 ms)

benchmarking insertWithKey empty
time                 56.16 ms   (52.34 ms .. 61.42 ms)
                     0.989 R²   (0.978 R² .. 0.998 R²)
mean                 59.75 ms   (58.14 ms .. 61.31 ms)
std dev              2.904 ms   (1.959 ms .. 4.279 ms)
variance introduced by outliers: 15% (moderately inflated)

benchmarking insertWithKey update
time                 75.52 ms   (68.96 ms .. 79.26 ms)
                     0.991 R²   (0.979 R² .. 0.998 R²)
mean                 75.18 ms   (72.73 ms .. 77.82 ms)
std dev              4.626 ms   (3.500 ms .. 6.090 ms)
variance introduced by outliers: 17% (moderately inflated)

benchmarking map
time                 12.30 ms   (11.86 ms .. 12.76 ms)
                     0.992 R²   (0.988 R² .. 0.996 R²)
mean                 11.82 ms   (11.31 ms .. 12.18 ms)
std dev              1.054 ms   (558.4 μs .. 1.572 ms)
variance introduced by outliers: 46% (moderately inflated)

benchmarking foldlWithKey
time                 70.95 ms   (68.80 ms .. 72.98 ms)
                     0.998 R²   (0.995 R² .. 1.000 R²)
mean                 68.78 ms   (66.80 ms .. 70.74 ms)
std dev              3.448 ms   (2.296 ms .. 5.339 ms)
variance introduced by outliers: 16% (moderately inflated)

benchmarking delete
time                 23.47 ms   (22.81 ms .. 24.52 ms)
                     0.994 R²   (0.987 R² .. 0.999 R²)
mean                 23.99 ms   (23.70 ms .. 24.39 ms)
std dev              786.6 μs   (513.6 μs .. 1.067 ms)

benchmarking update
time                 64.72 ms   (62.57 ms .. 66.63 ms)
                     0.998 R²   (0.994 R² .. 0.999 R²)
mean                 66.86 ms   (65.47 ms .. 69.01 ms)
std dev              3.019 ms   (1.828 ms .. 3.988 ms)

benchmarking fromList
time                 57.85 ms   (55.39 ms .. 60.17 ms)
                     0.996 R²   (0.991 R² .. 0.999 R²)
mean                 58.82 ms   (57.88 ms .. 60.33 ms)
std dev              2.166 ms   (1.678 ms .. 2.999 ms)

benchmarking lookupRange
time                 91.89 ns   (91.69 ns .. 92.06 ns)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 92.24 ns   (92.00 ns .. 92.43 ns)
std dev              718.0 ps   (593.7 ps .. 872.4 ps)

Benchmark bench-all: FINISH
mantkiew commented 1 year ago

Also, here are the results of the tests:

$ cabal test
Build profile: -w ghc-9.4.6 -O1
In order, the following will be built (use -v for more details):
 - HUnit-1.6.2.0 (lib) (requires download & build)
 - ghc-heap-view-0.6.4 (lib:ghc-heap-view) (requires download & build)
 - hostname-1.0 (lib:hostname) (requires download & build)
 - prettyprinter-compat-ansi-wl-pprint-1.0.2 (lib) (requires download & build)
 - ansi-wl-pprint-1.0.2 (lib) (requires download & build)
 - test-framework-0.8.2.0 (lib) (requires download & build)
 - test-framework-quickcheck2-0.3.0.5 (lib) (requires download & build)
 - test-framework-hunit-0.3.0.2 (lib:test-framework-hunit) (requires download & build)
 - data-stringmap-1.0.2 (test:properties) (first run)
...
Test suite properties: RUNNING...
Test suite properties: PASS
BurningWitness commented 11 months ago

Do you know of an alternative package that would provide that?

I think the only maintained package that qualifies right now is bytestring-trie, submap is its prefix slicer function. It should be more than enough if all you're looking for are spine-strict radix trees, with the slight inconvenience of having to convert from UTF-8 to bytes (encodeUtf8 is O(1) anyway).

I am in the process of writing a highly similar package to that, with the goals of higher generality (NonEmpty Word8 as keys) and implementing a proper lazy interface (radix trees can do that), when I'm done I'll try to push it over the abandoned radix-tree library.