6 ms·

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

by ryao 2y ago

kubb 2y ago
Maybe, but should the author really cater to people who can’t overcome a language barrier? They probably won’t understand the concept anyway.
- ryao 2y ago
  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.
  - dxbydt 2y ago
    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.
  - kubb 2y ago
    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.
    - ryao 2y ago
      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?
  - mplanchard 2y ago
    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.
- mangamadaiyan 2y ago
  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.
  - kubb 2y ago
    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.
    - deleted 2y ago
      [deleted]
    - mangamadaiyan 2y ago
      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.
  - ryao 2y ago
    You are correct.
Rendello 2y ago
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.
barbegal 2y ago
Neither of those languages gives you portable SIMD. Rust is rapidly becoming the language of choice for high performance code.
- npalli 2y ago
  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 https://github.com/google/highway
  - ryao 2y ago
    You can do portable SIMD in GNU C/C++ using the vector extension: https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
    - swiftcoder 2y ago
      I'm not sure that "portable" and "only works on one specific compiler vendor" are very compatible concepts
      - bigpingo 2y ago
        gcc is available on and targets more platforms than rust. So if GNU C is not considered portable you can forget about 'portable rust'.
        swiftcoder 2y ago
        Portability in the C and C++ worlds generally means across standard-conforming compilers, not just across platforms
wolfgangK 2y ago
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.
- curiouscoding 2y ago
  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
  - ryao 2y ago
    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.
  - oguz-ismail 2y ago
    > this is also showing off what rust can do To people who already know Rust, yes. To others, not so much
- ryao 2y ago
  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/ https://en.algorithmica.org/hpc/data-structures/s-tree/
  - npalli 2y ago
    C++ not C. The author explains his choices elsewhere in the site.
pxmpxm 2y ago
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.
- curiouscoding 2y ago
  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.
  - jackschultz 2y ago
    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.
    - curiouscoding 2y ago
      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).
      - Andys 2y ago
        You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.
        ryao 2y ago
        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.
plasticeagle 2y ago
As a computer science article, it should have mostly been pseudocode. Concrete implementations can be given in an appendix, where they belong.
- curiouscoding 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - sigbottle 2y ago
    My former roommate works in a similar domain; https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 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.
quotemstr 2y ago
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.
- ryao 2y ago
  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/ 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.
  - quotemstr 2y ago
    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.
    - ryao 2y ago
      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.
deleted 2y ago
[deleted]
unrealhoang 2y ago
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.
- quotemstr 2y ago
  > 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.
- ryao 2y ago
  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.
  - quotemstr 2y ago
    > 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.
FridgeSeal 2y ago
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.
- ryao 2y ago
  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/ https://www.tiobe.com/tiobe-index/
  - coliveira 2y ago
    Yes, he is in a bubble.
bawolff 2y ago
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.
peutetre 2y ago
Well, you can do the C implementation then. Don't see it as a problem, see it as an opportunity.
tmtvl 2y ago
Oh no, it would've been better if it was written using the most readable language: Scheme.

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

by ryao 2y ago

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

kubb 2y ago

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

ryao 2y ago
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.
- dxbydt 2y ago
  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.
- kubb 2y ago
  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.
  - ryao 2y ago
    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?
- mplanchard 2y ago
  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.
mangamadaiyan 2y ago
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.
- kubb 2y ago
  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.
  - deleted 2y ago
    [deleted]
  - mangamadaiyan 2y ago
    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.
- ryao 2y ago
  You are correct.

Rendello 2y ago

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.

barbegal 2y ago

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

npalli 2y ago
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 https://github.com/google/highway
- ryao 2y ago
  You can do portable SIMD in GNU C/C++ using the vector extension: https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
  - swiftcoder 2y ago
    I'm not sure that "portable" and "only works on one specific compiler vendor" are very compatible concepts
    - bigpingo 2y ago
      gcc is available on and targets more platforms than rust. So if GNU C is not considered portable you can forget about 'portable rust'.
      - swiftcoder 2y ago
        Portability in the C and C++ worlds generally means across standard-conforming compilers, not just across platforms

wolfgangK 2y ago

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.

curiouscoding 2y ago
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
- ryao 2y ago
  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.
- oguz-ismail 2y ago
  > this is also showing off what rust can do To people who already know Rust, yes. To others, not so much
ryao 2y ago
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/ https://en.algorithmica.org/hpc/data-structures/s-tree/
- npalli 2y ago
  C++ not C. The author explains his choices elsewhere in the site.

pxmpxm 2y ago

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.

curiouscoding 2y ago
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.
- jackschultz 2y ago
  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.
  - curiouscoding 2y ago
    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).
    - Andys 2y ago
      You're really just exploiting hidden O(?) implementations inside the CPU, so it still applies, just less visibly.
      - ryao 2y ago
        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.

plasticeagle 2y ago

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

curiouscoding 2y ago
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.
- deleted 2y ago
  [deleted]
- sigbottle 2y ago
  My former roommate works in a similar domain; https://dl.acm.org/doi/pdf/10.1145/3448016.3452841 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.

quotemstr 2y ago

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.

ryao 2y ago
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/ 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.
- quotemstr 2y ago
  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.
  - ryao 2y ago
    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.

deleted 2y ago

[deleted]

unrealhoang 2y ago

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.

quotemstr 2y ago
> 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.
ryao 2y ago
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.
- quotemstr 2y ago
  > 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.

FridgeSeal 2y ago

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.

ryao 2y ago
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/ https://www.tiobe.com/tiobe-index/
- coliveira 2y ago
  Yes, he is in a bubble.

bawolff 2y ago

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.

peutetre 2y ago

Well, you can do the C implementation then. Don't see it as a problem, see it as an opportunity.

tmtvl 2y ago

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