Stream: t-compiler/wg-incr-comp

Topic: Lazy DefPathTable decoding


view this post on Zulip mw (Jan 25 2021 at 13:33):

Hey @Aaron Hilland @Tyson Nottingham, since you've both been doing work in this area I wanted to give you a heads up that I'm experimenting with an alternative implementation of lazy DefPathTable decoding along the lines this description: https://github.com/rust-lang/rust/pull/80177#issuecomment-749484088

I have a promising implementation of a hashtable that can be used directly in its binary format (i.e. without any upfront decoding) and making DefPaths "structured" turned out to be pretty simple. Overall this seems to simplify things quite a bit. The on-disk hashtable adds some complexity -- but it is a generic data structure that might come in handy for other use cases too.

Let me know if you'd like to get a ping when things have progressed far enough for a performance testing PR.

view this post on Zulip Tyson Nottingham (Jan 25 2021 at 19:03):

Sure! Sounds neat. :)

view this post on Zulip mw (Jan 26 2021 at 20:12):

I just created a public repo for the hash table implementation at https://github.com/michaelwoerister/odht.

view this post on Zulip mw (Jan 26 2021 at 20:13):

It uses robin hood hashing (i.e. what libstd used before HashBrown) and seems to perform pretty well (although HashBrown can be up to 2x faster)

view this post on Zulip mw (Jan 26 2021 at 20:14):

It should not be too hard to change the underlying implementation in the future, if needed

view this post on Zulip Tyson Nottingham (Jan 26 2021 at 20:25):

Nice. I'll try to check it out sometime this week and let you know if I run into any problems.

view this post on Zulip mw (Jan 27 2021 at 09:56):

Great. I'm interested in any kind of feedback, especially concerning the public API.

view this post on Zulip mw (Feb 01 2021 at 17:39):

I just opened https://github.com/rust-lang/rust/pull/81635, which implements the "structured DefPathHash" pre-requisite.

view this post on Zulip Tyson Nottingham (Feb 02 2021 at 23:59):

@mw, I haven't read the whole implementation, but I can give a little feedback on the ODHT API. By the way, is your intent for it to be general purpose and possibly release it on crates.io, or for it to be purpose-built for DefPathTable decoding? I might be less inclined to nitpick if it's the latter.

Now to feedback:

Overall, seems good!

view this post on Zulip mw (Feb 03 2021 at 11:03):

Awesome, thank you for the feedback, @Tyson Nottingham!

view this post on Zulip simulacrum (Feb 03 2021 at 11:18):

min_const_generics are stable on nightly right now so should be possible to use, but maybe not for this use case


Last updated: Oct 21 2021 at 22:01 UTC