Stream: wg-traits

Topic: Q: union find data structures


Eh2406 (Jan 07 2019 at 14:57, on Zulip):

I have a question about chalk/polonius implomatation.

For Cargo's resolver, I have been looking into persistent union find data structures. The papers I am reading have had 2 examples of where these are useful: for type resolution and for Prolog implementations. So my question is does chalk/polonius already have an implementation if not would a crate be useful for chalk/polonius?

lqd (Jan 07 2019 at 15:12, on Zulip):

(deleted)

nikomatsakis (Jan 07 2019 at 15:41, on Zulip):

@Eh2406 in fact, ena supports a persistent union-find, though I've not played with it much to measure performance or anything

nikomatsakis (Jan 07 2019 at 15:41, on Zulip):

er, sorry, to answer your question, we are using https://crates.io/crates/ena

nikomatsakis (Jan 07 2019 at 15:41, on Zulip):

(polonius doens't need that)

Eh2406 (Jan 07 2019 at 15:43, on Zulip):

Where can I find the persistent veriton, is it on master?

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

@Eh2406 in some sense, it's always persistent -- you just clone the table whenever you want

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

that said, the persistent feature enables one that uses a persistent vector under the hood

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

this makes cloning O(1) instead of O(n)

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

note that this does not mean it is faster

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

I've usually found the opposite

nikomatsakis (Jan 07 2019 at 15:55, on Zulip):

https://github.com/nikomatsakis/ena/blob/49d9270d95910e303061128938dafce0ae79a45e/Cargo.toml#L15

nikomatsakis (Jan 07 2019 at 15:56, on Zulip):

if you enable that feature, you can create a UnificationTable<Persistent> I think

nikomatsakis (Jan 07 2019 at 15:56, on Zulip):

where the Persistent type is defined here

nikomatsakis (Jan 07 2019 at 15:57, on Zulip):

here are some tests: link

nikomatsakis (Jan 07 2019 at 15:57, on Zulip):

it might be interesting to make a version based on im.rs or something, should be possible

nikomatsakis (Jan 07 2019 at 15:58, on Zulip):

there is a trait that controls the backing store, here is the implementation for persistent vectors

nikomatsakis (Jan 07 2019 at 15:58, on Zulip):

(as an aside, I've been thinking it would make sense to revamp ena for some time but anyway.... the basics are right)

Eh2406 (Jan 07 2019 at 16:01, on Zulip):

Thanks for all the links!

Eh2406 (Jan 07 2019 at 16:01, on Zulip):

Let me see if I can say it back.

Eh2406 (Jan 07 2019 at 16:03, on Zulip):

rustc and chalk use a ena. A persistent version is available there, but is largely not used as it is slower.

Eh2406 (Jan 07 2019 at 16:03, on Zulip):

Work to make it faster would be interesting to its manteners.

nikomatsakis (Jan 07 2019 at 16:04, on Zulip):

sounds roughly right. Chalk in particular might benefit from a persistent setup, as it does some cloning

nikomatsakis (Jan 07 2019 at 16:04, on Zulip):

tbh I've just not benmarked it much

nikomatsakis (Jan 07 2019 at 16:05, on Zulip):

there are also alternative strategies for impl'ing union find, though I think they're not much different

nikomatsakis (Jan 07 2019 at 16:05, on Zulip):

e.g. minikanren's impl is intended to be persistent

Eh2406 (Jan 07 2019 at 16:07, on Zulip):

The papers I am reading say that "just swapping out the backing sore for a persistent version, is to slow in practice", I can find the exact quote if you'd like.

nikomatsakis (Jan 07 2019 at 16:07, on Zulip):

seems plausible

Eh2406 (Jan 07 2019 at 16:09, on Zulip):

They have a page describing exactly why that destroys the Big O of the normal version.

Eh2406 (Jan 07 2019 at 16:12, on Zulip):

Thanks for the info! I will continue researching, and try to report back to ena!

simulacrum (Jan 07 2019 at 17:22, on Zulip):

@Eh2406 FWIW I know petgraph has a UnionFind data structure as well but I don't think it's persistent -- might be worth looking at though.

Eh2406 (Jan 07 2019 at 17:24, on Zulip):

Do you have a link for minikanren's impl?

nikomatsakis (Jan 07 2019 at 18:45, on Zulip):

not really

Eh2406 (Jan 07 2019 at 21:02, on Zulip):

Ba humbug. I miss read the abstract. The paper was about the "ask the same object for what is value used to be" type of persistent not the "fast clone" " type of persistent. (they are related, but not the same) It is not faster for the case we care about.

blitzerr (Jan 07 2019 at 22:30, on Zulip):

The papers I am reading say that "just swapping out the backing sore for a persistent version, is to slow in practice", I can find the exact quote if you'd like.

@Eh2406 , can you paste a link to the papers you are hinting towards ?

Eh2406 (Jan 07 2019 at 22:58, on Zulip):

The one that turned out to be about the wrong problem is
https://link.springer.com/chapter/10.1007/BFb0028283

Eh2406 (Jan 07 2019 at 23:01, on Zulip):

The quote I had in mind is from
https://www.lri.fr/~filliatr/ftp/publis/puf-wml07.pdf

But it goes on to suggest a somost automatic version of the snapshot idea that is already in ena

blitzerr (Jan 08 2019 at 01:29, on Zulip):

thanks a lot @Eh2406

Last update: Nov 18 2019 at 01:50UTC