search

cuplv / iodyn.rust

Collections Library for Adapton, in Rust
13 stars 0 forks source link

Hash trie; for creating finite maps from sequences #19

Closed matthewhammer closed 7 years ago

matthewhammer commented 7 years ago

This PR implements the first of the two finite map representations described in https://github.com/cuplv/iodyn.rust/issues/20.

r @kyleheadley (following the Rust github conventions for requesting a review from @kyleheadley)

modules trie1 and trie2 are two variants of hash tries, for representing finite maps computed from sequences. The second variant is a bit simpler, with comparable performance to the first. In a later PR, I'll probably remove the first one and rename.

Performance

The image below shows that at 100k random usizes, constructing a Rust hashmap requires ~400ms to build (on my mac book air). Meanwhile, it only takes 10ms to change propagate the trie construction algorithm after we edit the initial sequence.

image

To reproduce this, go into branch dev-hammer, under eval and do cargo run --example unique_elms. I suspect that a more powerful computer may have similar, but slightly better results overall.

Commit history

I accidentally included a few commits (from master) of @kyleheadley below. There's probably a way of correcting this, but it's easier just to recommit this time. I know what I did, and how to avoid it next time (always do git pull --rebase origin/master before doing a PR, and don't pull without rebasing).

Update: I think I fixed this by rebasing the PR to target dev, not `master.

matthewhammer commented 7 years ago

@kyleheadley I've "rebased" this PR, targeting dev (instead of master).

I cleaned up the Cargo.toml file.

I've also added my latest key value log module, kvlog.rs.