{"action":"created","issue":{"url":"https://api.github.com/repos/haskell/containers/issues/340","repository_url":"https://api.github.com/repos/haskell/containers","labels_url":"https://api.github.com/repos/haskell/containers/issues/340/labels{/name}","comments_url":"https://api.github.com/repos/haskell/containers/issues/340/comments","events_url":"https://api.github.com/repos/haskell/containers/issues/340/events","html_url":"https://github.com/haskell/containers/pull/340","id":176542801,"number":340,"title":"Rewrite Data.IntMap to be faster and use less memory","user":{"login":"gereeter","id":2328242,"avatar_url":"https://avatars.githubusercontent.com/u/2328242?v=3","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":39,"created_at":"2016-09-13T03:57:06Z","updated_at":"2016-09-25T19:47:22Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/haskell/containers/pulls/340","html_url":"https://github.com/haskell/containers/pull/340","diff_url":"https://github.com/haskell/containers/pull/340.diff","patch_url":"https://github.com/haskell/containers/pull/340.patch"},"body":"I still sort of think of this as a work in progress, but I've been sitting for over 2 years now on this code, and all the tests pass with significant improvements on many benchmarks. The general approach is detailed at [gereeter/bounded-intmap](https://github.com/gereeter/bounded-intmap) - the README is a bit outdated and I really should incorporate it into comments, but it is the best reference for how the structure works. As for compatibility, I think I'm missing some instances, some Safe Haskell stuff, and anything required to get things working on compilers that aren't the latest GHC.\r\n\r\nIf this is a large enough change, I wouldn't mind sending mail to the libraries mailing list, but it should be entirely backwards compatible.\r\n\r\ncc @ekmett - This is a (heavily modified) version of an idea you came up with.\r\n\r\n## Memory usage\r\nThe old implementation had `6n-5` words of overhead (i.e. discounting storage of the keys and the pointers to values). The new implementation has only `3n-1` words of overhead.\r\n\r\n## Large runtime regressions\r\n- ~~`fromAscList` and `fromDistinctAscList` are currently just aliases for `fromList`~~\r\n- I have no clue about `foldlWithKey'`\r\n- `keysSet`, `fromSet`, `restrictKeys`, and `withoutKeys` are currently implemented naively and are probably much slower\r\n\r\n## Benchmarks\r\n```\r\nBenchmark                     Runtime change  Original runtime\r\nlookup                         -19.25%        4.38e-04\r\ninsert                         -22.57%        9.17e-04\r\n\"insertWith empty\"             -10.20%        8.85e-04\r\n\"insertWith update\"             -7.32%        1.96e-03\r\n\"insertWith' empty\"             -9.92%        8.84e-04\r\n\"insertWith' update\"           -11.00%        1.67e-03\r\n\"insertWithKey empty\"          -10.23%        8.76e-04\r\n\"insertWithKey update\"          +6.64%        1.96e-03\r\n\"insertWithKey' empty\"         -10.47%        8.84e-04\r\n\"insertWithKey' update\"        -11.29%        1.68e-03\r\n\"insertLookupWithKey empty\"    -46.46%        1.74e-03\r\n\"insertLookupWithKey update\"   -41.50%        3.94e-03\r\nmap                            -17.13%        1.81e-04\r\nmapWithKey                     -24.97%        2.19e-04\r\nfoldlWithKey                   -19.19%        1.50e-03\r\nfoldlWithKey'                 +112.26%        4.29e-05\r\nfoldrWithKey                   -79.82%        1.02e-07\r\ndelete                          +9.36%        3.42e-04\r\nupdate                         -12.59%        1.50e-03\r\nupdateLookupWithKey             +1.39%        2.44e-03\r\nalter                           +5.04%        1.53e-03\r\nmapMaybe                       -15.58%        2.25e-04\r\nmapMaybeWithKey                -15.88%        2.24e-04\r\nfromList                       -15.42%        8.96e-04\r\nfromAscList                    -81.50%        6.83e-04\r\nfromDistinctAscList            -43.34%        2.24e-04\r\n```\r\n\r\n### Merges\r\n```\r\nBenchmark               Runtime change  Original runtime\r\nunion-disj_nn             +8.53%        2.08e-07\r\nunion-disj_nn             +9.74%        2.09e-07\r\nunion-disj_ns            +11.66%        1.85e-07\r\nunion-disj_ns             +7.15%        1.85e-07\r\nunion-disj_sn             +7.00%        1.94e-07\r\nunion-disj_sn             +5.67%        1.94e-07\r\nunion-disj_nt             +7.22%        1.55e-07\r\nunion-disj_nt             +5.51%        1.55e-07\r\nunion-disj_tn             +5.88%        1.61e-07\r\nunion-disj_tn             +5.91%        1.61e-07\r\nunion-common_nn          -15.58%        1.12e-02\r\nunion-common_nn          -15.30%        1.10e-02\r\nunion-common_ns          -11.65%        4.69e-03\r\nunion-common_ns          -11.57%        4.67e-03\r\nunion-common_sn          -10.49%        4.67e-03\r\nunion-common_sn          -10.23%        4.67e-03\r\nunion-common_nt          -26.05%        9.11e-05\r\nunion-common_nt          -28.51%        9.43e-05\r\nunion-common_tn          -21.01%        8.89e-05\r\nunion-common_tn          -19.67%        8.80e-05\r\nunion-mix_nn             +12.20%        2.06e-02\r\nunion-mix_nn             +11.70%        2.06e-02\r\nunion-mix_ns              +5.05%        5.10e-03\r\nunion-mix_ns              +5.84%        5.10e-03\r\nunion-mix_sn              +6.15%        5.11e-03\r\nunion-mix_sn              +7.16%        5.08e-03\r\nunion-mix_nt              -4.19%        8.05e-05\r\nunion-mix_nt              -4.29%        8.03e-05\r\nunion-mix_tn              -6.17%        8.58e-05\r\nunion-mix_tn              -6.81%        8.61e-05\r\nunion-block_nn           +38.23%        1.03e-04\r\nunion-block_nn           +39.21%        1.03e-04\r\nunion-block_ns           +30.53%        6.79e-06\r\nunion-block_ns           +31.57%        6.78e-06\r\nunion-block_sn           +29.41%        6.92e-06\r\nunion-block_sn           +30.39%        6.88e-06\r\ndifference-disj_nn       -78.96%        1.72e-07\r\ndifference-disj_nn       -78.95%        1.72e-07\r\ndifference-disj_ns       -73.77%        1.60e-07\r\ndifference-disj_ns       -77.32%        1.60e-07\r\ndifference-disj_sn       -82.64%        1.91e-07\r\ndifference-disj_sn       -82.02%        1.91e-07\r\ndifference-disj_nt       -74.05%        1.40e-07\r\ndifference-disj_nt       -74.09%        1.40e-07\r\ndifference-disj_tn       -77.35%        1.47e-07\r\ndifference-disj_tn       -77.28%        1.47e-07\r\ndifference-common_nn      +4.10%        7.50e-03\r\ndifference-common_nn      +4.25%        7.50e-03\r\ndifference-common_ns      -0.97%        4.27e-03\r\ndifference-common_ns      -1.31%        4.28e-03\r\ndifference-common_sn     -30.13%        8.64e-04\r\ndifference-common_sn     -34.10%        8.55e-04\r\ndifference-common_nt     -20.80%        1.00e-04\r\ndifference-common_nt     -18.82%        1.01e-04\r\ndifference-common_tn     -37.75%        5.91e-05\r\ndifference-common_tn     -32.56%        5.92e-05\r\ndifference-mix_nn        -18.42%        1.78e-02\r\ndifference-mix_nn        -18.95%        1.78e-02\r\ndifference-mix_ns        -21.13%        4.36e-03\r\ndifference-mix_ns        -21.18%        4.35e-03\r\ndifference-mix_sn        +19.57%        1.49e-03\r\ndifference-mix_sn        +19.49%        1.49e-03\r\ndifference-mix_nt        -29.75%        8.57e-05\r\ndifference-mix_nt        -29.13%        8.52e-05\r\ndifference-mix_tn        -27.97%        5.37e-05\r\ndifference-mix_tn        -29.38%        5.45e-05\r\ndifference-block_nn      -69.85%        7.37e-05\r\ndifference-block_nn      -70.66%        7.57e-05\r\ndifference-block_ns      -64.67%        6.55e-06\r\ndifference-block_ns      -64.53%        6.54e-06\r\ndifference-block_sn      -40.12%        5.43e-06\r\ndifference-block_sn      -40.19%        5.44e-06\r\nintersection-disj_nn     -70.09%        1.24e-07\r\nintersection-disj_nn     -69.98%        1.24e-07\r\nintersection-disj_ns     -67.57%        1.12e-07\r\nintersection-disj_ns     -66.18%        1.12e-07\r\nintersection-disj_sn     -66.65%        1.12e-07\r\nintersection-disj_sn     -66.92%        1.12e-07\r\nintersection-disj_nt     -60.91%        9.38e-08\r\nintersection-disj_nt     -61.18%        9.38e-08\r\nintersection-disj_tn     -60.17%        9.28e-08\r\nintersection-disj_tn     -60.32%        9.27e-08\r\nintersection-common_nn    +6.06%        7.08e-03\r\nintersection-common_nn    +5.82%        7.07e-03\r\nintersection-common_ns   -25.00%        1.04e-03\r\nintersection-common_ns   -25.84%        1.05e-03\r\nintersection-common_sn   -20.87%        1.07e-03\r\nintersection-common_sn   -15.66%        1.05e-03\r\nintersection-common_nt   -31.67%        5.48e-05\r\nintersection-common_nt   -31.14%        5.45e-05\r\nintersection-common_tn   -28.09%        5.97e-05\r\nintersection-common_tn   -28.55%        5.98e-05\r\nintersection-mix_nn       +0.71%        3.01e-03\r\nintersection-mix_nn       -6.14%        3.14e-03\r\nintersection-mix_ns      -29.39%        6.40e-04\r\nintersection-mix_ns      -30.65%        6.39e-04\r\nintersection-mix_sn      -23.04%        6.64e-04\r\nintersection-mix_sn      -22.10%        6.58e-04\r\nintersection-mix_nt      -17.51%        3.90e-05\r\nintersection-mix_nt      -19.35%        3.91e-05\r\nintersection-mix_tn      -21.05%        4.63e-05\r\nintersection-mix_tn      -17.28%        4.59e-05\r\nintersection-block_nn    -62.01%        4.88e-05\r\nintersection-block_nn    -62.37%        4.88e-05\r\nintersection-block_ns    -45.10%        3.52e-06\r\nintersection-block_ns    -45.39%        3.54e-06\r\nintersection-block_sn    -27.86%        3.43e-06\r\nintersection-block_sn    -27.83%        3.43e-06\r\n```"},"comment":{"url":"https://api.github.com/repos/haskell/containers/issues/comments/249442360","html_url":"https://github.com/haskell/containers/pull/340#issuecomment-249442360","issue_url":"https://api.github.com/repos/haskell/containers/issues/340","id":249442360,"user":{"login":"gereeter","id":2328242,"avatar_url":"https://avatars.githubusercontent.com/u/2328242?v=3","gravatar_id":"","url":"https://api.github.com/users/gereeter","html_url":"https://github.com/gereeter","followers_url":"https://api.github.com/users/gereeter/followers","following_url":"https://api.github.com/users/gereeter/following{/other_user}","gists_url":"https://api.github.com/users/gereeter/gists{/gist_id}","starred_url":"https://api.github.com/users/gereeter/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/gereeter/subscriptions","organizations_url":"https://api.github.com/users/gereeter/orgs","repos_url":"https://api.github.com/users/gereeter/repos","events_url":"https://api.github.com/users/gereeter/events{/privacy}","received_events_url":"https://api.github.com/users/gereeter/received_events","type":"User","site_admin":false},"created_at":"2016-09-25T19:47:22Z","updated_at":"2016-09-25T19:47:22Z","body":"> It doesn't look like there's all that much code shared between Node L and Node R. It strikes me as cleaner to use\r\n>\r\n> ```haskell\r\n> data NodeL a = BinL !(NodeL a) !(NodeR a) !Key a | TipL\r\n> data NodeR a = BinR !Key a !(NodeL a) !(NodeR a) | TipR\r\n> ```\r\n\r\nSo, I thought this too (as it would also avoid the type families nastiness when tagging keys and values), but I just tried it and hit a pretty fundamental wall. Specifically, it required splitting `IntMap_` into `IntMap` and `IntMapR`. This is a first much nicer, since it avoids the wrapper newtype, but I ran into problems implementing `intersection`. The `goLookup` functions return either a singleton map or an empty map, and therefore return something that is generic on `L/R`. There isn't a good, consistent choice of which type to return. Additionally, since `goLookupL` and `goLookupR` call each other, there is no way to make a choice based on whether it is an `L` or `R` function without adding overhead and losing the tail recursive property. I could use some third representation that was generic, but that would require an extra conversion step at the end. I could duplicate all the `goLookup` functions, but that is really ugly and might result in slowdowns due to different code paths being taken. The one solution I see that preserves performance would be to fully commit to `SketchyIntMap t a`, leaving that generic, and add a generic `sketchySingleton :: Key -> a -> SketchyIntMap t a` function. However, you indicated that you didn't want to keep `SketchyIntMap`."}}
{"actor":{"display_login":"gereeter"}}