I got started in rust recently and these live sessions are so helpful! I get to see and understand implementations and learn from code style and functionality from you. Great video!
I love how fast and efficient your workflow is. I'm currently learning Vim and soon I'm switching to Linux completely. Is that i3-wm + tmux you're using? I'm thinking of using arch + i3-wm. I hope I won't get lost :P Thanks for this video! ♥
Glad you enjoyed watching it! I'm sure you'll do fine. There's a bit of a learning curve, but once you get used to it, it's quite efficient. I'm using xmonad as my window manager, though basically any tiling wm would do. The bar at the bottom is polybar. My terminal is alacritty + tmux + fish, with neovim as the editor. I also have a bunch of plugins that make things easier, most importantly a good file-opener through fzf. My full vim config is here if it's helpful: github.com/jonhoo/configs/blob/master/.vimrc
40:34 - why are those "CPU instructions unnecessary"? I'm pretty sure some sort of iteration needs to happen anyway, even if you could create the vector using the `vec![]` macro. It somehow has to fill _all_ of the elements of the vector with (a clone of) the provided value, after all… It might be less convenient to type up, but I highly doubt it performs any worse (in the sense of "performs iteration/doesn't perform iteration") than the macro.
Well, an empty vector is all zeros. If the memory allocator can give you pre-zeroed memory (or better yet, memory that is zeroed the first time it is accessed), then you do not need to iterate over all of the buckets at all. They are already initialized to the right (empty) value :)
In the current implementation of Vec, the buffer pointer is non-null, instead it's 0x1, so an empty vector is actually not all zeros. Therefore, pre-zeroed memory doesn't help much in this case. See it in action: play.rust-lang.org/?gist=072deddd43205d21fef383f6de16c8d4&version=stable&mode=debug
Ah, yes, that's a good point. I think I was mostly lamenting the fact that I feel like this shouldn't *need* iterating over all the buckets, but you're right that it wouldn't be trivial to achieve!
Can someone define buckets and entries in easy terms? From what I understand, bucket is just an array index that can have one or more than one value (entries). The way an index or a bucket is chosen is typically done in the hash function, which takes a key, uses some mathematical functions and returns a hash value, which is then modded with the size of the hash table and then inserted in the bucket. Is my understanding correct?
Ah, yes, so that turned out to really be an issue with the Rust borrow checker as I suspected! See the response from one of the compiler developers here: twitter.com/nikomatsakis/status/1003238711881076739. Someone also submitted a pull request that fixed this here: github.com/jonhoo/rust-basic-hashmap/pull/1
Hi. Rust noob here. If I pause the video at 1:58:18, then I see that from the POV of the compiler - the "if" statement that checks entry.0 == key might never pass right? And in that case Entry::Occupied is never returned so the mutable borrow is still in play? Ownership / borrowing is confusing.
I recently found your channel and love what you have been doing! It's a bit under the rust knowledge required as what you've been porting over, but do you think you'd ever do something like javas arraylist or a generic BST?
Glad you like it! I've gotten a decent number of questions about building more "basic" things for people who are newer to Rust, and while it would be interesting and useful, I feel like that space is already covered decently well by other resources out there. The "advanced programming" space though is lacking, which is why I started this channel. But maybe one day I'll at least do one :p
With a lot of previously recorded live-coding sessions I have to pump up the playback speed to 1.25. With Jon, I have to slow him down to 0.75. I tried coding along with this stream about a year ago and it was futile. Now I can keep up... at .75. Jon's videos are great for testing your progress with Rust by coming back and seeing if you can keep up AND comprehend. Also, even if you are an experienced programmer but have never touched Rust, good idea to read the NoStarch book and/or the O'Reilly book before attempting to code along with Jon. For me, I think you start with the 'Cancellable Services' video, then move on to this one and then go on to the longer and multi-part videos. Just my opinion in hindsight.
Great video! Is there a data structures and algorithms text/resource that you can recommend that gave you a solid foundation/good understanding for doing a video such as this one? Thanks again for the great content!
Glad you enjoyed it! I have heard very good things about www.algorist.com/, but have not (yet) read it myself. I also came across porgionesanke.wordpress.com/2016/07/11/a-comparison-of-four-algorithms-textbooks/ a while back, which seems to point in the same direction. Apart from that there area lot of good resources online, and even reading the documented source code for some of them (like the ones in the Rust standard library), can be extremely instructive! Ultimately though, trying to implement them yourself is usually the best way to get to know them :) One thing you could consider doing for a challenge is to find well-established algorithm from older research papers like the Michael-Scott concurrent queue or the Treiber stack, and then try implementing those!
i just watched this, and i find it interesting that this is a "simple" hashmap... i did not find this simple especially when it came to the entry api... a lot of generics, and lifetimes etc. Coming from java, i still find Rust syntax very hard to remember, especially where to declare generics, and lifetimes. When to use &, ref, when to consume the values (self, and when to &self)
At 1:32:50 the Python snippet could use docs.python.org/3.9/library/collections.html#collections.defaultdict Therefore you don't need the if block either.
Hey Jon, I gotta ask because I couldn't find it despite some digging - what's your environment look like? I saw some pretty awesome shortcuts and it looks pretty slick. Firefox and Fedora?
I'm on Arch Linux using xmonad as my (very bare-bones) window manager, kupfer as my launcher, and polybar as my system tray. Most of my configuration scripts and such are at github.com/jonhoo/configs. Browser is Firefox w/ dark theme and modified to have the tabs on the bottom using a userChrome.css like this: gist.github.com/jonhoo/21ede33321c38352de8f9e478d0221ee
No, since our number of buckets is a power of two. Even if this wasn't the case, the additional probability of hitting bucket zero compared to say the last bucket is up to just 2^(-32) up from 2^(-64). Huge increase, but still tiny
I don't think not requiring the Eq and Hash bounds on K in the struct makes sense. The hash map is kind of unusable at that point. You can retrieve the pairs with an enumerator, but you cannot insert any, making it totally useless. Even if you could could insert key-value pairs, you would still be better of using a Vec if all you want is to store pairs and later retrieve them all.
Mostly the first, but the actual answer is neither, technically: find, map and most other methods on Iterator simply return a new wrapping iterator type around the source Iterator you call them on, and they work by requesting values from their source when they have values requested from them. This means the source is only iterated once. In practice, since the complier can see all the code, inlining means that equivalent code to the manual loop with the current and end pointers and if statements gets generated.
I got started in rust recently and these live sessions are so helpful! I get to see and understand implementations and learn from code style and functionality from you. Great video!
Can't wait for more Live-coding. Thanks for sharing your knowledge!
Audio suddenly fixes itself at 1:08:35
I love how fast and efficient your workflow is. I'm currently learning Vim and soon I'm switching to Linux completely. Is that i3-wm + tmux you're using? I'm thinking of using arch + i3-wm. I hope I won't get lost :P Thanks for this video! ♥
Glad you enjoyed watching it! I'm sure you'll do fine. There's a bit of a learning curve, but once you get used to it, it's quite efficient. I'm using xmonad as my window manager, though basically any tiling wm would do. The bar at the bottom is polybar. My terminal is alacritty + tmux + fish, with neovim as the editor. I also have a bunch of plugins that make things easier, most importantly a good file-opener through fzf. My full vim config is here if it's helpful: github.com/jonhoo/configs/blob/master/.vimrc
Jon Gjengset thank you!! 😘
Did the link to you vim config get removed?
How can you move the cursor so fast in vim? What kind of commands are you using?
At 1:48:30 you talk about borrows being in the scope of blocks. With the now-merged non lexical lifetimes does this code now compile?
Ah, you mentioned this just after that
40:34 - why are those "CPU instructions unnecessary"? I'm pretty sure some sort of iteration needs to happen anyway, even if you could create the vector using the `vec![]` macro. It somehow has to fill _all_ of the elements of the vector with (a clone of) the provided value, after all… It might be less convenient to type up, but I highly doubt it performs any worse (in the sense of "performs iteration/doesn't perform iteration") than the macro.
Well, an empty vector is all zeros. If the memory allocator can give you pre-zeroed memory (or better yet, memory that is zeroed the first time it is accessed), then you do not need to iterate over all of the buckets at all. They are already initialized to the right (empty) value :)
In the current implementation of Vec, the buffer pointer is non-null, instead it's 0x1, so an empty vector is actually not all zeros. Therefore, pre-zeroed memory doesn't help much in this case. See it in action: play.rust-lang.org/?gist=072deddd43205d21fef383f6de16c8d4&version=stable&mode=debug
Ah, yes, that's a good point. I think I was mostly lamenting the fact that I feel like this shouldn't *need* iterating over all the buckets, but you're right that it wouldn't be trivial to achieve!
Sure, it would definitely be nice if cases like this would be somehow optimized!
50:40 Why &x.0? x is reference type, so shouldn't we instead dereference it(ie using * operator) to access the value? Or is it actually like &(x.0)?
Can someone define buckets and entries in easy terms? From what I understand, bucket is just an array index that can have one or more than one value (entries). The way an index or a bucket is chosen is typically done in the hash function, which takes a key, uses some mathematical functions and returns a hash value, which is then modded with the size of the hash table and then inserted in the bucket. Is my understanding correct?
Did you figured out the issue with mutable borrow in some way?
Ah, yes, so that turned out to really be an issue with the Rust borrow checker as I suspected! See the response from one of the compiler developers here: twitter.com/nikomatsakis/status/1003238711881076739. Someone also submitted a pull request that fixed this here: github.com/jonhoo/rust-basic-hashmap/pull/1
Thank you
Hi. Rust noob here. If I pause the video at 1:58:18, then I see that from the POV of the compiler - the "if" statement that checks entry.0 == key might never pass right? And in that case Entry::Occupied is never returned so the mutable borrow is still in play?
Ownership / borrowing is confusing.
I recently found your channel and love what you have been doing! It's a bit under the rust knowledge required as what you've been porting over, but do you think you'd ever do something like javas arraylist or a generic BST?
Glad you like it! I've gotten a decent number of questions about building more "basic" things for people who are newer to Rust, and while it would be interesting and useful, I feel like that space is already covered decently well by other resources out there. The "advanced programming" space though is lacking, which is why I started this channel. But maybe one day I'll at least do one :p
Interesting screencast 👍 How is about vimium for firefox 🤓 have the same env, its quite great!
thanks for the sharings
With a lot of previously recorded live-coding sessions I have to pump up the playback speed to 1.25. With Jon, I have to slow him down to 0.75. I tried coding along with this stream about a year ago and it was futile. Now I can keep up... at .75. Jon's videos are great for testing your progress with Rust by coming back and seeing if you can keep up AND comprehend.
Also, even if you are an experienced programmer but have never touched Rust, good idea to read the NoStarch book and/or the O'Reilly book before attempting to code along with Jon. For me, I think you start with the 'Cancellable Services' video, then move on to this one and then go on to the longer and multi-part videos. Just my opinion in hindsight.
Hahaha, I appreciate this comment so much :) Maybe I should keep a "suggested reading lists" somewhere...
1:53:45 *screams internally*
pro tip : watch movies on flixzone. Me and my gf have been using them for watching a lot of movies these days.
@Yosef Hezekiah Definitely, I have been watching on flixzone for since december myself :)
Python dicts have the setdefault() method with kind of does the same thing or_insert, but Entry is more powerful in general.
Great video! Is there a data structures and algorithms text/resource that you can recommend that gave you a solid foundation/good understanding for doing a video such as this one? Thanks again for the great content!
Glad you enjoyed it! I have heard very good things about www.algorist.com/, but have not (yet) read it myself. I also came across porgionesanke.wordpress.com/2016/07/11/a-comparison-of-four-algorithms-textbooks/ a while back, which seems to point in the same direction. Apart from that there area lot of good resources online, and even reading the documented source code for some of them (like the ones in the Rust standard library), can be extremely instructive! Ultimately though, trying to implement them yourself is usually the best way to get to know them :) One thing you could consider doing for a challenge is to find well-established algorithm from older research papers like the Michael-Scott concurrent queue or the Treiber stack, and then try implementing those!
This is a good primer for this vid as well ruclips.net/video/zg9ih6SVACc/видео.html
When I code in rust and the borrow checker complains, I'm wrong. When Jon codes in rust and the borrow checker complains, the borrow checker is wrong.
i just watched this, and i find it interesting that this is a "simple" hashmap... i did not find this simple especially when it came to the entry api... a lot of generics, and lifetimes etc. Coming from java, i still find Rust syntax very hard to remember, especially where to declare generics, and lifetimes. When to use &, ref, when to consume the values (self, and when to &self)
This is a simple hashmap, when reaches the load factor threshold, we simply double the buckets and rehash everything
At 1:32:50 the Python snippet could use docs.python.org/3.9/library/collections.html#collections.defaultdict
Therefore you don't need the if block either.
Hey Jon, I gotta ask because I couldn't find it despite some digging - what's your environment look like? I saw some pretty awesome shortcuts and it looks pretty slick. Firefox and Fedora?
I'm on Arch Linux using xmonad as my (very bare-bones) window manager, kupfer as my launcher, and polybar as my system tray. Most of my configuration scripts and such are at github.com/jonhoo/configs. Browser is Firefox w/ dark theme and modified to have the tabs on the bottom using a userChrome.css like this: gist.github.com/jonhoo/21ede33321c38352de8f9e478d0221ee
Would wrapping the output of hasher.finish to a u32 cause bucket distribution skew?
No, since our number of buckets is a power of two. Even if this wasn't the case, the additional probability of hitting bucket zero compared to say the last bucket is up to just 2^(-32) up from 2^(-64). Huge increase, but still tiny
I don't think not requiring the Eq and Hash bounds on K in the struct makes sense. The hash map is kind of unusable at that point. You can retrieve the pairs with an enumerator, but you cannot insert any, making it totally useless.
Even if you could could insert key-value pairs, you would still be better of using a Vec if all you want is to store pairs and later retrieve them all.
When you use like find and map together in Rust are they mixed together? Or they iterate twice
I believe they are, I'm not sure at which layer of optimization this happens, whether it's the Rust compiler or LLVM, but I think it does.
Mostly the first, but the actual answer is neither, technically: find, map and most other methods on Iterator simply return a new wrapping iterator type around the source Iterator you call them on, and they work by requesting values from their source when they have values requested from them. This means the source is only iterated once.
In practice, since the complier can see all the code, inlining means that equivalent code to the manual loop with the current and end pointers and if statements gets generated.
1:41:29 holy fuck, naming a lifetime `'static` is *nasty*. Thank god it doesn't work in the current version.
What vim theme is that?
It's called gruvbox, and I'm specifically using the "hard" dark version :)
> do you work for Facepunch?
Facepunch is the company that develops the Rust video game lol
Nope, this is not related to the Rust video game at all :)
40:25 I simply cannot come wrap my head around wasting CPU runtime "to make the compiler happy". There must be another way.