6 ms·
Speaking as someone who has read about 40 years of papers in compiler optimization, it's very interesting. In the early days, there were fairly exact algorithm
by DannyBee 7y ago
Speaking as someone who has read about 40 years of papers in compiler optimization, it's very interesting.
In the early days, there were fairly exact algorithms that worked as described, and were implemented as described, but were pseudocoded in papers. Where the pseudocode differed from implementation, differences were described in great detail (IE they may say an array can be shared but isn't to make the pseudocode easier to describe).
Then, over time, things start to get further away from that. You start to see papers published with algorithms that either don't work as described, or are so inefficient as to be unusable. Like literally cannot work. Where you can get source code, later looking at the source code shows that's not what they did at all.
One infamous example of this is SSAPRE - to this day, people have a lot of trouble understanding the paper (and it has significant errors that make the algorithm incorrect as written). The concept sure, but the exact algorithm - less so.
Reading the source code to it in Open64 - it is just wildly different than the paper (and often requires a lot of thought for people to convince themselves it is correct).
It's not just better engineering/datastructures vs research algorithms.
The one shining counterexample is the Rice folks who wrote their massively scalar compiler in nuweb (one of many literate programming environments), so the descriptions/papers and code were in the same place - these are very very readable and useful papers in my experience.
Nowadays it's coming back to the earlier daysdue to github/et al. People seem to try to make the code more like the paper algorithm since they now release the code.
Word2vec appears to be a counterexample (maybe because they released the code they didn't feel a need to get the paper as right)
- bollu 7y agoAs someone who works on compiler optimisations, I'd love to get a link the Rice compiler's source code --- do you happen to have a link?
- DannyBee 7y agoNot sure i still have it around ping me at the email in my profile and i'll see what i can do. It used to be on their ftp server, which they took down. I expect if you email ken kennedy over at rice, he may be able to find it as well.
- acqq 7y agoIt also appeared interesting to me, but then I discovered that I already have a nice book from the Rice compiler people: https://www.amazon.com/Engineering-Compiler-Keith-Cooper/dp/012088478X https://www.amazon.com/Engineering-Compiler-Keith-Cooper/dp/... And the example of the paper with literate code: https://www.cs.ucsb.edu/~ckrintz/papers/shared.ps.gz https://www.cs.ucsb.edu/~ckrintz/papers/shared.ps.gz Still it would be nice if somebody decides to get and also make available the papers or code for which the links are now dead, e.g. those linked from here: http://keith.rice.edu/publications-2/technical-reports/ http://keith.rice.edu/publications-2/technical-reports/
- nullwasamistake 7y agoI ran into the same thing when implementing a hash table sorting algorithm from a recent paper. Nowhere in the paper does it mention that table size MUST be a power of two. The new table structure is supposedly more memory efficient than anything else out there. That's the whole point of it. So it's nice that they leave out "btw only works with size power of two". I got 2/3 of the way through an optimized implementation before I realized it wasn't any more efficient than the previous contender, in fact much less so, if you couldn't fit your set into exactly a power of two size. Not outright lying but creative ommission for sure
- ur-whale 7y agoI think it's ok to names names in this specific instance: you'll save other people a lot of pain.
- nullwasamistake 7y agoIt's only been implemented ~3 times besides the paper reference and I do too much ranting on HN to risk connecting it to my professional image. Particularly critisicm of big tech companies I may want to work for someday. Sorry. It's very niche, I doubt many will run into it. Writing your own hash table is generally considered a bad idea :). I was just very bored and annoyed with memory limits. It will only affect implementors, which is less than 5 people in 4 years. Good example of implementor beware though, I'm sure it's a common issue
- opportune 7y agoIs it more efficient in terms of algorithmic complexity or just performance on real systems? I don't think it's creative omission if it's a complexity improvement but it's definitely worse if the performance gains were just empirical but relied on that one condition.
- bjourne 7y agoBacking arrays for fast hash tables are always powers of 2. That's how they are implemented in all mainstream languages. Details are often omitted in academia because of publishing constraints or because the authors thought they were obvious.
- bayareanative 7y agoEditors gotta be more rigorous and only accept papers with completely reproducible portable examples, i.e., docker images, literate code and source code repos. Pseudocode is helpful to be platform neutral, but if it's not precise enough to implemented as code, then it's still a proprietary figment of someone else's imagination akin to the squishy social sciences where almost anything goes, not rigorously reproducible science. Keep the standards high or the quality will taper off. PS: Sometimes I think some researchers think they're helping themselves keep their research proprietary so they will able to monetize their special knowledge or implementation, especially if no one else can make it work ("knowledge" (job) security/silo). Why do the hard work of figuring out how to make a novel AI/ML algorithm if it can be readily commercially monetized without recompense? (Modern Western civ doesn't have a good patronage system to uniformly support arts, trades and sciences.)
- opportune 7y agoIn some fields, like in ML/AI or in other data-sciencey fields, keeping your code / training data closed prevents other researchers from building or improving on your work. It's more than just monetization, in that case it's just tragedy-of-the-commons career growth
- duckmysick 7y ago> keeping your code / training data closed prevents other researchers from building or improving on your work. I might be naive in this regard, but isn't that the main point of doing research?
- dekhn 7y agoSure, but the challenge is, if you're in a competitive field and you make it easy for your competitors, you're going to have a harder time establishing job security. Currently many fields like biology, CS, ML, physics have fewer well-paying job positions than contenders, so every competitive advantage makes a difference. I know plenty of professors who got there by carefully writing papers that lacked specific details on how to reproduce a cutting-edge, "hot" paper.
- karlding 7y agoWhat if you simply worked on the AST/token level and converted that into pseudocode, assuming you either annotated your functions with a description or named them following some sort of convention? Then you could write your code and then "compile" your source files to pseudocode. Seems like this could be useful for writing specification documents or anything safety critical..