4 ms·

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.
  - ryao 2y ago
    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.
  - curiouscoding 2y ago
    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 :)
kccqzy 2y ago
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.
nostradumbasp 2y ago
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.

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.
- ryao 2y ago
  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.
- curiouscoding 2y ago
  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 :)

kccqzy 2y ago

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.

nostradumbasp 2y ago

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.