Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Use bulk IntMap operations for efficiency #39

Closed
treeowl opened this issue Aug 30, 2016 · 4 comments
Closed

Use bulk IntMap operations for efficiency #39

treeowl opened this issue Aug 30, 2016 · 4 comments
Milestone
5.6.0.0

Comments

@treeowl
Copy link
Contributor

treeowl commented Aug 30, 2016

Insertion, for example, should be able to use the ill-named differenceWithKey function. First, form a map consisting of operations to perform on predecessor/successor nodes; then use differenceWithKey to perform them. When inserting nodes with many predecessors/successors, this should be faster than modifying them all sequentially. The mergeWithKey function would probably be more appropriate, but I hope to deprecate that eventually in favor of a safer variation on the theme.
@ivan-m
Copy link
Contributor

ivan-m commented Aug 30, 2016

I think this depends on #38 being implemented first (or else more ugly RULE usage).

@ivan-m ivan-m added this to the 5.6.0.0 milestone Aug 30, 2016
@treeowl
Copy link
Contributor Author

treeowl commented Aug 30, 2016

This is entirely orthogonal. I'll submit a PR shortly to explain what I
mean.

On Mon, Aug 29, 2016 at 11:59 PM, Ivan Lazar Miljenovic <
notifications@github.com> wrote:

I think this depends on #38 #38
being implemented first (or else more ugly RULE usage).

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#39 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ABzi_bH_9opsR77A4xDdl7lugTEDN7Xyks5qk6qngaJpZM4JwF8Q
.

@ivan-m
Copy link
Contributor

ivan-m commented Aug 30, 2016

Oh, for the & operator in general rather than for insNodes, etc.?

@treeowl
Copy link
Contributor Author

treeowl commented Aug 30, 2016

Yes, my first change is to the (&) operator for the PatriciaTree
implementation. I haven't looked beyond that yet.

On Tue, Aug 30, 2016 at 12:04 AM, Ivan Lazar Miljenovic <
notifications@github.com> wrote:

Oh, for the & operator in general rather than for insNodes, etc.?

—
You are receiving this because you authored the thread.
Reply to this email directly, view it on GitHub
#39 (comment), or mute
the thread
https://github.com/notifications/unsubscribe-auth/ABzi_bkqtJPqLfXVcj9a5A9XCPefWCI8ks5qk6vbgaJpZM4JwF8Q
.

treeowl added a commit to treeowl/fgl that referenced this issue Aug 30, 2016
@treeowl
Use bulk IntMap operations
4a78b91 
Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

Fixes haskell#39
@treeowl treeowl mentioned this issue Aug 30, 2016
Closed
treeowl added a commit to treeowl/fgl that referenced this issue Aug 30, 2016
@treeowl
Use bulk IntMap operations
294dc3d 
Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 30, 2016
@treeowl
Use bulk IntMap operations
c5d1e4f 
* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Use bulk IntMap operations
9f4c81c 
* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Use bulk IntMap operations
587fdca 
Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Add cabal benchmark integration
64a0152 
* Add the benchmarks to `fgl.cabal`.

* Disable AVL benchmarks that result in errors. Surely something
  needs to be fixed!

* Add benchmark for building a full graph with `&`.

* Enable GHC optimizations. Otherwise, none of the `RULES` or
  inlining the source code talks about can ever happen.

Add cabal benchmark integration

* Add the benchmarks to `fgl.cabal`.

* Disable AVL benchmarks that result in errors. Surely something
  needs to be fixed!

* Add benchmark for building a full graph with `&`.

Use bulk IntMap operations

* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39

Use bulk IntMap operations

Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Use bulk IntMap operations
bf699be 
* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Use bulk IntMap operations
64d3c6b 
* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39
treeowl added a commit to treeowl/fgl that referenced this issue Aug 31, 2016
@treeowl
Add cabal benchmark integration
4f9fcd3 
* Add the benchmarks to `fgl.cabal`.

* Disable AVL benchmarks that result in errors. Surely something
  needs to be fixed!

* Add benchmark for building a full graph with `&`.

* Enable GHC optimizations. Otherwise, none of the `RULES` or
  inlining the source code talks about can ever happen.

Add cabal benchmark integration

* Add the benchmarks to `fgl.cabal`.

* Disable AVL benchmarks that result in errors. Surely something
  needs to be fixed!

* Add benchmark for building a full graph with `&`.

Use bulk IntMap operations

* Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

* Require `containers >= 0.5.0`. Since that came out in 2012,
  and works with `base` going all the way back to 4.2 (which
  came out in 2009) it seems a reasonable dependency. I want it
  for `Data.IntMap.Strict`.

Fixes haskell#39

Use bulk IntMap operations

Use `Data.IntMap.differenceWith` to implement `(&)` and `match`
for `Data.Graph.Inductive.PatriciaTree`. Instead of modifying
the graph manually, one key at a time, `differenceWith` will
efficiently partition the set of keys to be modified along the
structure of the graph. This should be considerably more efficient
when inserting or matching on well-connected nodes.

Fixes haskell#39
@ivan-m ivan-m closed this as completed in bb65f5c Mar 3, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
5.6.0.0
Development

No branches or pull requests
2 participants
@ivan-m @treeowl