How to learn std from source code more efficiently?

I recently got the idea that iterators are not really fast, as stated in the book. I spent a very long time reading the source code manually through the site, and I got tired of it. I installed rust-analyser and neovim, I thought rust-analyser would help me read the source code. From my code, going to the standard library code, I couldn't use gd ([g]o to [d]efinition) on private types. And when opening the source code from the rustup folder, my lsp was blocked because it did not support the feature from nightly. I donโ€™t know how else I can quickly get to definitions, and especially expand macros. So what tools will help me examine source code?

โ”‚ยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทยทโ”‚
\/ This is mistake \/
PS:as I later found out from this forum, iterator is indeed slow, because the implementation of nth() calls next() many times, as I expected.
(I was wrong)

If it were me having the idea that iterators, or anything else, were slow the first thing I would do is measure it. Benchmark against whatever one thinks should be faster, perhaps even in a different language. Then do the research if it turns out to actually be slow. Unless one just wants to get familiar with the code anyway.

So is the case then that it's not iterator that you found slow but nth(). Seems to me that rather depends what one is finding nth(). Surely one has to call next() on a linked list and such where one cannot just index into an array.

8 Likes

Eh, the conclusion that "iterator is slow because nth is called multiple times" is completely unfounded. In simple cases, the compiler can "see through" the abstraction and just use normal indexing: Compiler Explorer

6 Likes

slice::Iter and Copied have custom implementations that speed up nth. This time it was not compiler magic.

1 Like

Okay, my mistake was that I was looking at the default implementation of Iterator. I looked at the specific implementation of Vec and realized that advance_by() is overridden so that it does not call next() many times. And I still think that nth() calls next() many times by default, because this approach will work with all structures, and not because it is often implemented on linkedList. To summarize, what conclusion should I draw? Is it better not to read the source code of the rust standard library at all?

So what tools will help me examine source code?

If you want to investigate the standard library specifically you could try using a nightly toolchain and rust-analyzer setup.

Alternatively you could build the docs with --generate-link-to-definition --document-hidden-items --document-private-items which should document everything and make all the types in rustdoc source code view linked.

2 Likes

My point is that it completely depends on what you are looking at. Iterator is a generally applicable trait that doesn't require a linear buffer in memory like an array. The conservative implementation is to call next repeatedly. But when there is a linear buffer, it can be implemented differently.

3 Likes

I only meant linked list as an example of a container where finding the nth() is not as trivial as indexing an array.

I'm all for studying the std source code if you are interested and have the time.

But when it comes to performance for some job you need to do I think the first step should always be to measure what is happening. Rather than disappearing down a rabbit hole of research.

Or take a look at the assembler language that is produced for by the compiler. Godbolt is a great tool for that: Compiler Explorer. With a bit of experience one can get a feel for how it would perform.

1 Like

I was just wondering why iterators are faster, I already believed in it, because it was written in the book and because I already know the proofs, I was interested in the code itself, how iterators are implemented in principle, because for me they seemed like an obvious overhead. And this interest filled me with experience, so itโ€™s not so useless, I think, because rust is the first language in which I was able to dive deeper into iterators without fear (I gave up learning other languages and didnโ€™t go deeper into iterators, so this experience useful to me).

Having dived into iterators, I discovered that supposedly nth is slow. It turned out that I simply forgot about the existence of default implementation. This is the very useful experience I was talking about. If I had simply measured performance, I might have made mistakes in the future due to misunderstandings of default implementations. Now I probably won't do it

1 Like

That sounds very good to me. I will never knock understanding what is going on under the hood.

1 Like

I tried this: rustdoc +nightly --document-private-items --document-hidden-items --generate-link-to-definition --out-dir $HOME/home/doctmp -Z unstable-options std/src/lib.rs

And got a bunch of errors... 169 to be exact

And rust-analyser is officially supported only in stable, but rustup +nightly component list shows the presence of rust-analyser

Edited:
Used another command: cargo +nightly rustdoc --open -- --document-private-items --document-hidden-items --generate-link-to-definition -Z unstable-options -v

I used it on an existing crate, where a module from std is used as a dependency. When navigating through the std module, when you go to the definition of a private item, it reports that there is no such page

If you're interested in things like that, you might enjoy reading Implementing Vec - The Rustonomicon, which has a bunch of sub-chapters about how Vec (and its IntoIter) work internally.

As for slice iterators (which Vec also uses for the non-owned thing), the implementation has a whole bunch of micro-optimization because it's so perf-critical: https://github.com/rust-lang/rust/blob/1a47f5b448f1e023e7ffd2eb57d473d619d2c04d/library/core/src/slice/iter/macros.rs#L151-L387. (It does a bunch of things that are not a good idea in most places, but because slice::Iter is so important for inner loops in all kinds of things, it has had lots of extra effort put into it.)

3 Likes

Did you also install the submodule sources? If you clone the rust repository (github.com/rust-lang/rust) as is, the submodule source will not be fetched, so language server will not work properly.

Actually, I didn't download this repository. I simply pressed gd on mentions of items from std in my code. Everything worked with public items.

Can you tell me what exactly needs to be downloaded from the repository? Wouldn't it be enough to download the library folder? (I just donโ€™t have much space left on my computer (actually my phone, I use Termux))

I decided like this:
git clone --depth 1 https://github.com/rust-lang/rust
git submodule update --init library/*

I hope this is enough

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.