Hacker News Reader

Comment by ryao | Hacker News Reader

This would have been easier for a larger number of people to read if it had been in C or Python.

What a weird thing to complain about. The Rust code in TFA are purely arithmetic and imperative function calls. Any C developer that is good enough to care about the algorithm mentioned will have no issue reading such Rust code, heck, they could even throw the code to chatgpt to translate for them no problem.

Such a good and detailed article that packed with techniques that are applicable everywhere yet the complaints are: “but rust”.

Regarding Python, how could such optimizations be implemented in Python? Generating LLVM bytecodes directly aside.

Fluent in C and C++ among others, know nothing about Rust. It's mostly easy to follow, but I'm having trouble with notation like `&[u32]` and `&[u32; P]`. Arrays that hold unsigned 32 bit integers? But there's `Vec<u32>` which also seems like an array type? Is it like the difference between C++ primitive arrays and std::vector?

`&[u32]` is essentially `std::span<const uint32_t>`.

`&[u32; P]` is similarly something like `std::span<const uint32_t, P>`.

`[u32; P]` (no `&`) is essentially `std::array<uint32_t, P>`.

`Vec<u32>` is essentially `std::vector<uint32_t>`, yes.

Thanks

For `&[u32]` and `&[u32; P]`, those are both references to an array of unsigned 32 but integers, however the former is to an array of any size (and carries its size at runtime), whereas the latter is to an array with an explicitly known size at compile time. It's unusual in C, I think you can express it as `int[24] *` (or possibly some other permutation, I'm away from a compiler).

Vec<u32> is pretty much like std::vector compared to them, yeah.

I have not studied Rust and find its syntax alien. It looks like a cross between a functional language and C++. Trying to read it is like forcing myself to read Italian. I don’t know Italian, but have studied Spanish and Latin. I can sort of figure things out if I put in effort, but there is always uncertainty when I do. That is the problem with reading Rust.

This could be addressed if I just learned Rust (much like my difficulty with Italian could be addressed by studying Italian). However, I already know at least 10 programming languages. I am unwilling to learn the latest fashionable language unless it can promise me that the language will not change and there will never be another fashionable language for me to learn. Given that Rust rejected the standardization process that C and C++ embraced, and Zig is expected to replace Rust one day, I doubt Rust can make such assurances.

As for Python, it is often used for teaching CS and everything except the assembly code is doable in it. Using low level assembly from Python would require using the FFI. Also, Python has nothing to do with LLVM.

Suck to be you, I guess? If you don’t care enough then you don’t care. You wouldn’t bitch when there’s an article written in Italian with good knowledge inside: “but Italian”. You either trying to read using translation tool or ignore it entirely.

I didn’t say python has anything to do with LLVM, it’s just a technique, read about it, or not.

> Zig is expected to replace Rust one day

That's a bold prediction considering that Zig is unsafe and Rust is safe.

If Zig's idioms make it safe, then modern C++ is safe too.

Zig replacing Rust is not my prediction. It is what I am hearing from the Zig enthusiast I know. I have also seen others express the sentiment that the next fashionable language after Rust will be Zig. Regardless of whether it is Zig, there will be another. Rust is just one part of a never ending cycle of people trying to reinvent programming.

There's approximately a 0% chance of Zig seeing non-trivial adoption anywhere other than maybe the embedded world.

It otherwise solves basically nobodies problems in the real world and is just a love letter to C. It's cute, kinda, but that's about it.

Zig is like the Vulcan Centaur next to Starship.

> Rust is just one part of a never ending cycle of people trying to reinvent programming.

This is true of every single programming language.

That is my complaint against the next fashionable language. Once you have some level of proficiency in around 10 languages, adding more to the list is a chore. It lacks the enjoyment that came from the first few. At least, that is my experience. That is why I am resistant to learning new languages unless software I want to modify is already written in it. Then, I am forced to learn and time spent on it is time that actually needed to be spent, unlike my brief time spent teaching myself FORTRAN in college, which was largely a waste of time.

> Zig enthusiasts

Yeah, don’t you think they might be perhaps just slightly biased? I have some news for you about your average technology enthusiast…

Anyone who claims Zig is going to replace Rust knows nothing about either Zig, Rust, or both. Zig is designed to solve none of the problems that Rust solves. Trillion-dollar corporations are rewriting things in Rust because it solves problems that really matter to them.

The US government strongly recommends writing all new mission-critical code in memory-safe languages. Guess which one of Rust and Zig is memory-safe?

I have nothing against Zig, it looks like a very nice better C, and the comptime stuff is both cool and useful. But its priorities are not Rust’s priorities.

Of course, Rust evangelists are also more than slightly biased.

Of course.

> Rust is just one part of a never ending cycle of people trying to reinvent programming.

Which is good. Programming is an open field, ideas are constantly popping in and out and you sometimes need to reinvent things to prove that they are worth it. More languages is a good thing, the bizarre tribalism around them is dangerous, but it is not possible to prevent it, people gotta be people.

Both are unsafe, just zig is usually safer than rust.

And also so more readable, ie. maintainable

That’s one crazy claim to make.

> Regarding Python, how could such optimizations be implemented in Python? Generating LLVM bytecodes directly aside.

You don't. You instead use your favorite Python extension system (regular Python modules, Cython, Numba, whatever) to implement this tree algorithm and expose it to Python already shaped into a container.

I don't think that Python would be the right language for such low-level performance maxxing endeavor. I would have picked C++ but t was eye opening for me to see how rust enabled such low level optimization, so I'm grateful for the choice.

C would be useful to the broadest audience. C++ programmers can read C while C programmers cannot always read C++, especially when the newer language constructs are used. I mentioned Python because of its popularity.

Interesting, the Algorithmica article the author cited is in C:

https://en.algorithmica.org/hpc/data-structures/s-tree/

C++ not C. The author explains his choices elsewhere in the site.

The code snippets should be accepted by a C compiler and therefore are valid C code.

If you want to be pedantic, there is a constexpr in the snippets, wont be accepted by the C compiler. More broadly though it is a C++ tutorial. I insisted on it because the author of algorithmica actually explains he chose C++ and perhaps sometime later C/Rust or something might be better. Should respect his POV.

I had not seen the use of constexpr. You are correct that those are in C++.

C23 has constexpr, albeit only for objects, not functions. The code also uses namespaces, as in `std::aligned_alloc(P, T)`.

You have to be 1/3 down the page to see any of this in the code examples. By that point, you would already have seen a number of examples that are valid C code and it is reasonable to expect the rest to be. At least, that was my experience.

Yeah, I don't think python is the right tool here. C++ definitely would be an option though.

Anyway very happy that this is also showing off what rust can do

As far as I can tell, the community is largely divided into three major groups. Those that can read C, those that can read Python and those that can read both. Using either of them would have dodged criticism that your code examples are not accessible to much of the community.

That said, you are right that Python is not the best language to use when you need to use intrinsics, as you would be writing it in another language and using the Python FFI to access it.

> this is also showing off what rust can do

To people who already know Rust, yes. To others, not so much

I have a far easier time reading Rust than C. Probably because it’s been years since I’ve had to do C, and I find some of the syntax and patterns quite C-specific and confusing. Python also does not express some of the important implementation details well enough in its standard syntax IMO: there’s no obvious delineation between references and pass by value in Python, borrowing, etc.

So realistically, this is just the other half of the coin for all the articles where the code examples were written in C and everyone who didn’t really read C just had to put up with it.

The TIOBE index suggests that you are in a much smaller group than those who have difficulty reading Rust:

https://www.tiobe.com/tiobe-index/

Yes, he is in a bubble.

Rust is now common enough in the industry that everyone should be expected to at least read it, just like every programmer should be able to fizzbuzz in Python and JavaScript just as a matter of general technical literacy. There's no advanced Rust here and no concepts specific to the language.

It's a good article.

If Heinlein were in our industry, he might write this:

A programmer should be able to write a shell, parse binary data, design a protocol (and reverse engineer one too), authenticate a password, not fumble multi-code-point graphemes, wrangle semaphores, plug memory leaks, compress data, migrate databases, automate builds, git rebase a tree, profile tail latency, write a simple design doc for a complex system, draw a triangle, multiply tensors, and do fizzbuzz in every popular language on GitHub. Specialization is for insects.

Here is a list of languages people can be generally expected to be able to read:

  * C
  * C++
  * Java
  * JavaScript
  * Python

It is the top 6 of the TIOBE index, minus C#:

https://www.tiobe.com/tiobe-index/

Rust is not very high on the TIOBE index. It has rank 14 with a 1.29% rating. That is not much higher than COBOL.

You forgot the part where no one cares about TIOBE though.

As the TIOBE index says “The ratings are based on the number of skilled engineers world-wide, courses and third party vendors”. Very many people do care about that. Is there any reason I should think your remark is from some legitimate issue rather than you not liking the index results?

I would argue most people working software jobs either haven't heard of TIOBE or don't care about it. I only occasionally hear about it from strange internet comments that are far too focused on language particulars.

That is surprising. I heard about the TIOBE index often about 15 years ago, but now that I think about it, I have not heard about it lately. I wonder if the rise of Python and ML has caused people to stop asking “what language should I learn”. That is the question the TIOBE index often was cited to answer.

Rust is where the action is though. It's not just about cumulative SLOC weight, but about mindshare among the "movers and shakers" of the industry. Think of it as a prestige language, an acrolect, you should at least vaguely know so that you can participate in the most challenging conversations in the field.

That is an interesting perspective. Here is my perspective. There are no popular projects that use Rust as a primary language. The current fashionable area of computers is machine learning. As far as high level languages go, you will see a mix of Python, C++ and perhaps a tiny bit of C there. Rust is nowhere to be seen.

Your description would be better applied to C, C++ and Python. That is what the majority of popular software uses and people having challenging conversations are often using one of those languages.

> There are no popular projects that use Rust as a primary language.

Servo is pretty notable and visible. ripgrep, influxdb, wasmer, deno. uv and ruff in the python ecosystem are written in rust.

AWS, Cloudflare, Discord (iirc), and Microsoft have all adopted Rust extensively.

As of late 2023 there are committed drivers in the Linux kernel written in rust. (Linux is pretty popular.) prior to those, only C and assembly were allowed.

None of this contradicts what I said.

Don't forget Pydantic

> There are no popular projects that use Rust as a primary language

You may be surprised to learn, Python's `cryptography` project is written (EDIT: maybe not primarily, it's hard to compare given dependencies) in Rust, and saw around 8.1 million downloads from PyPI yesterday. That puts it close to the top 20 (the 20th project comes in at 8.5m).

I would like to also point out that rust is boring as hell. Lots of otherwise ordinary people write super simple non-fancy programs using it too :)

If you know C/C++ you could have learned to read Rust in the time you spent commenting in this thread. The number of new syntaxes you need to learn is quite minimal.

As an aside: why is Java winning out over C# these days? When I first experienced C# I didn't want to go back.

>Rust is now common enough in the industry

Source?

Maybe, but should the author really cater to people who can’t overcome a language barrier? They probably won’t understand the concept anyway.

The ACM for a time only accepted code examples in ALGOL because it was felt that there should be a standard language that everyone understood. ALGOL eventually gave way to C and others, but there is definite value in ensuring things are accessible to the largest possible audience.

You're free to use ALGOL in your posts if you want. It reads like pseudocode used in algorithmic books, and should be familiar to anyone who used the Pascal family.

ALGOL gave way to C, and C is now giving way to Rust, Zig and others. You're playing the role of the people who wanted to keep the example snippets in ALGOL.

The point was that examples should be in widely understood languages. The niche languages you list do not qualify as widely understood.

Estne melius scribere exempla latine?

usaco explicitly nudges you towards C++ on the first page itself. problems are graded on running time, even with moderately large datasets, Python simply doesn’t make the cut. So most high schoolers end up using C++ for usaco, and Java for AP Comp Science.

This is someone’s blog, not an ACM publication. Why hold it to the same standard? They can write in whatever they like. I have a hard time reading Haskell, but I don’t sit and kvetch about it anytime someone wants to use it in a blog post.

Erm, the concepts that you're referring to are independent of the language being used. The author is free to use whatever language they want. The GP (I think) was merely trying to make a point about making the article accessible to a wider audience that is capable of appreciating the concepts involved.

If you can't understand the code snippets in this post, the concepts will most likely be lost on you, no matter what other language would be used for the code.

Isn't that precisely the point that the GP was trying to make, about the accessibility of the article?

Edit: Eytzinger layout, Cache lines, SIMD, et cetera are independent of the particular language used in the article. They're just as valid in C, for example. I don't understand your point about them being tied to Rust.

You are correct.

I wonder what percentage of Rust users have significant experience with C. The difficulty curve of Rust was too high for me when I was coming from Python, but after doing HolyC and Zig, I find it fairly straightforward to conceptualize, though still difficult.

I've been working with real C today and have been having fun, but it's very different for me to step back into the C world again after working with more modern tools.

Neither of those languages gives you portable SIMD. Rust is rapidly becoming the language of choice for high performance code.

google has a mature C++ library for portable SIMD. The original article seems to be a translation of the excellent algorithmica site which had it in C++.

https://github.com/google/highway

You can do portable SIMD in GNU C/C++ using the vector extension:

https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html

I'm not sure that "portable" and "only works on one specific compiler vendor" are very compatible concepts

gcc is available on and targets more platforms than rust. So if GNU C is not considered portable you can forget about 'portable rust'.

Portability in the C and C++ worlds generally means across standard-conforming compilers, not just across platforms

Oh no, it would've been better if it was written using the most readable language: Scheme.

I've never programmed in rust and i can understand find.

At the end of the day rust is just another imperative programming language. You shouldn't need to know the language at all to understand the very simple examples written in rust.

As a computer science article, it should have mostly been pseudocode. Concrete implementations can be given in an appendix, where they belong.

The problem with pseudocode is that it's completely underspecified. And how would I ever write intrinsics in pseudocode? Much easier to do a proper language directly so people can actually Google things and read their official documentation.

My former roommate works in a similar domain; https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 is an example of a paper implementing intrinsics in pseudocode. They "unroll" the intrinsics with a comment saying that this is implemented with an intrinsic. Of course though, your blog isn't a paper, don't know why people are getting up in arms about it.

Also the other comment saying that "psuedocode is not concerned with intrinsics" is false. You can get "great" theoretical speedups (the shaveoffs are tiny but hey, they're better) with "simple" intrinsic operations - that's my roommate's entire research lol. The external memory model, for example, formalizes caching and allows all these low level optimizations to flourish. I'm not sure how intrinsics tied into it, but he's published so I'm not gonna question it :)

---

Speaking of which, I noticed that you did competitive programming. How does CP compare to research? I loved data structure manipulation problems in CP when they were clever - often because they involved noticing that you can take a "common" model, but then optimize it significantly because you only needed to support a subset of the operations through a clever mathematical proof based on the structure of the problem - but as I got to the higher levels it felt more and more that a lot of them became really obscure "support 413 operations on a tree, and yes, you really need to support all 413 operations on a tree" and that's kind of my opinion of data structure research unfortunately as well :( I guess because solving broad general instances is more important. I'd love to hear your perspective though.

Pseudo code can be whatever you want it to be. You can do SIMD pseudo code, but most generally don’t as that is often an implementation detail.

Yeah exactly, pseudocode just doesn't cut it if what matters is exactly the implementation itself.

Indeed I did a bunch of competitive programming! But actually there my favourite topics are combinatorics, graph theory, and number theory. I'd usually leave the datastructure (read segtree) problems to my teammates.

I super enjoyed that, and indeed was looking for a PhD where I could do similar things (because my time at Google was boring in comparison -- mostly just software engineering), on the intersection of new theory and practical fast code. I decided on bioinformatics, because this is exactly a field that has a lot of data, and the amount of data is growing fast, so that fast algorithms&code are needed, both in theory (big-O) and practice. Generally I've been super excited working on various problems in this domain, and I'd say it quite closely matches my compprog experience :)

That's unrealistic given that the author is not just doing computer science but also engineering using SIMD. The kind of available SIMD instructions actually affects code choice.

I strongly prefer actual implementations and adore the way this was written. Maybe its all of the "to get this to run in O(N) time we will leave the trick for the reader to discover" I've bumped into. Or the classic "use this esoteric pay-walled reference for instructions for this important subalgorithm" then when you get that reference you realize its doing the same sort of thing. Super cool for quizzing masters students, pretty ridiculous for people in industry or hobbyists who learn by playing with code. Unfortunately when that happens there is almost never an OSS implementation with the "trick" either.

Well, you can do the C implementation then.

Don't see it as a problem, see it as an opportunity.

I suspect like 9/10 of these type of articles are really just meant to be PR for rust. Like someone that wants to write Bart Simpsonensque "rust is great" over and over, but have to hide it into something more interesting.

Rust is great :")

But no, this is actually part of my PhD research. The next step will be to use this in a fast suffix-array search algorithm.

Great stuff. We get told O notation is what matters for data structures / algorithms, but improvements low level with memory and storage with things like rust is much more where improves can be made. These types of tricks for anctual run times are so valuable, and interesting to follow.

Ohh yeah, don't get me started in big-O...

It was great while computers were not really a thing yet, but these days it's often so meaningless. We see papers with 2x speedup with a lot of novel algorithmic stuff that sell better than 10x speedup just by exploiting CPUs to the fullest.

Even myself I kinda think theoretical contributions are cooler, and we really need to get rid of that (slightly exaggerating).

Your article led me to wonder if our b-trees would be faster if I switched the intra node operations to use Eytzinger ordered arrays:

https://github.com/openzfs/zfs/commit/677c6f8457943fe5b56d7a...

There are two ways to look at this Big O wise. One is that insertions and deletions would be asymptomatically faster since memmove() is a linear operation while bubble up/down are logarithmic operations. Look ups would not be any different asymptotically, but the constant factor might improve from being able to do prefetch. The other way is that the N is bounded, such that it is all O(1) and the difference is how big the constant factor is.

I imagine I could implement it and benchmark it. However, my intuition is that the end result have lookups be marginally faster to the point of splitting hairs while insertions and deletions would be slower. While memmove() is a technically a linear time operation, it is a sequential operation that has a very low constant factor. The bubble up and bubble down operations needed to do insertions and deletions in a Eytzinger ordered array are technically random access, which has a higher constant factor. At some point, the Eytzinger ordered array operations should win, but that point is likely well beyond the size of a b-tree node.

My reason for saying this is to say that Big O notation still matters, but understanding when the constant factor is significant is important.

Same with async and throwing threads at a problem. People love do those and think it's the right answer, but you can do a ton with smarter memory management and actually looking at what the code is doing lower level rather than abstractions.

Video about this that was very interesting to follow and somewhat related to what you're doing: https://www.youtube.com/watch?v=5rb0vvJ7NCY

You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.

He is improving the constant factor in big O notation. University algorithm classes tend to ignore cases where the constant factor difference is significant enough to favor a asymptomatically slower algorithm. Matrix multiplication is the quintessential example of this, since a good implementation of the O(n^3) algorithm will outperform asymptotically faster algorithms, such as the famous O(n^2 * log(n) * log(log(n))) one that uses the FFT. At least, it outperforms it on matrix multiplications people actually do in practice.

Rust is... okay. I still prefer C++'s template system to Rust generics, in part because Rust doesn't have specialization and won't for a while. Memory safety by default is a big enough win to make me overlook these nits. Really, though, most people most of the time should be writing managed code.

Do you think this article was written specifically as just PR for Rust?

Who do you think is behind this? The government?

Clearly it is Big Compiler propaganda! </bazinga>

The people likely to wear programming socks.

You suspect wrong. People are interested in things you're not. Get over it.

Reply on news.ycombinator.com