Frances Allen has died
ibm.com
ibm.com
She was in her 30s when she wrote it.
It was the survey of the state of the art at the time, but obviously it is not the state of the art now. Then why should you read it? Because it is written in two layers.
The first layer goes, we tried many optimization ideas, but only these were effective in practice: inlining, register allocation, etc. Others were not. Surprisingly, this layer is still mostly true today! This is both happy and sad depending on your view. Personally I think it testifies that compiler is a mature field, and it matured by 1970. (And that Frances Allen did lion's share of work maturing it.)
The second layer is, so here is how you should do inlining, register allocation, etc. While this layer is also full of gems, it is necessarily badly outdated. The paper predates graph coloring register allocation, for example. On the other hand, ironically, the state of the art 1970s algorithms are often a good choice today when you want an algorithm that is fast and low memory. (Ironic, because they were slow and high memory at the time!) This doesn't apply when there is an important new concern, for example cache locality, but happily it mostly doesn't affect compiler.
I think there should be a project to write the-state-of-the-art-in-1970s compiler. It would be a great simple and minimal alternative to GCC and LLVM, and it would also work great as a JIT code generator. We probably should name it Fran.
Simple things can run at higher speeds than complex things. Simplicity should be an architectural element, not a quality, but a feature.
Your idea for the Fran compiler is excellent. Throw in METAII from Dewey Schorre and it can be language agnostic.
> graph coloring register allocation
I knew some people working on linear optimization, at the time one of the most performance-intensive applications around (with real money/competitiveness in many industries riding on it). The compiler that produced the best code, by quite a bit, was the IBM FORTRAN compiler (3090 was the preferred target at the time), which also didn't do graph coloring. It just allocated the registers by loops from innermost to outermost.
¯\_(ツ)_/¯\
For a simple compiler, we should also look at Wirth's works, and Wirth's rule: an optimization has to pay for itself, that is, the compiler compiling itself with the optimization both in the executable and in the source code has to be faster than without it in both places.
That will result in a compiler best at optimizing programs that behave like compilers. Which may be fine for simple compilers, but it's worth keeping in mind that will not be a good compiler for domains where the programs don't behave like compilers (such as scientific computing, or even ML these days) that also want high performance.
I saw her 2007 Turing Award speech. I have tremendous respect for Fran and like your idea to name a codegen after her :-)
Vectorizing compilers have been around since at least the late 1970s; the Cray 1[0] had a vectorizing compiler in 1978.
Lamport’s Parallel Execution of DO Loops[1] was published in 1974.
(Never even mind the Single Static Information form.)
I wonder if part of the reason SSA is not implemented from the start by many compilers, is precisely because it came too late to be included in seminal works like A Catalogue of Optimizing Transformations; so people that rely on those works as a canon of "classes of optimization techniques that work" won't even be aware of it.
-----
More snarky: the earliest dataflow analysis paper I can find is from 1972. :)
More seriously, my recollection (having been about 20 years since I last took a compilers course) is that it took a while for even researchers to be convinced of the advantages of SSA, as the transformation causes a quadratic blowup in code size for the worst case (but it turns out to be less in real-world cases).
Also Sussman & Steele proposed CPS in 1975 which is closely related to SSA.
(Also, plenty of the compilers and/or JITs that I'm talking about are far newer. The first attempt to get a JVM to use SSA optimization during JIT — within SafeTSA — only occurred in 2000. Such an approach was copied by pretty much every JVM implementation by 2005, suggesting that a legacy of incompatible architecture was never the problem, but rather that JVM implementors just didn't think it was a worthwhile technique until they saw it demonstrated for their particular workloads.)
CPS is closely theoretically related to SSA (it carries equivalent information across lexical boundaries) but CPS isn't a basis for optimization transforms in the same way that SSA is. You can't hoist loop invariants using CPS... as far as I know, at least.
In 1990 I don't think SSA was broadly considered to be the basis of a good optimizing compiler the way it is today. So the "author of a flagship optimizing compiler" would be gambling on an unknown that looked good in a couple new papers. The Cytron paper on how to efficiently compute it came out in 1991. So SSA was still a WIP.
It wasn't really until the late 1990s IMO, that SSA became widespread and into the 2000s when it became the standard.
The safe TSA papers from 2000-2001 were the papers that showed that SSA was practical in a JIT environment. The fact that this approach was adopted less than 5 years after those papers come out suggest that compiler authors are in fact reading research papers.
Rearchitecting a production JIT to use a different IR for theoretical gains when nobody's demonstrated those gains on a toy JIT is high risk and demonstrating those gains on a toy JIT is research, not development.
If you just want to write a compiler for fun, I can understand not reading up on state of the art theory beforehand. And then it's accidentally actually useful to other people and it's too far into development to change the fundamental architecture.
Dependence analysis, automatic vectorization, and automatic parallelization were invented after 1971.
Fast algorithms for computing dominators[2] were late-70s.
Graph coloring register allocators were introduced in the early 1980s.
[0] https://en.m.wikipedia.org/wiki/Very_long_instruction_word
[1] https://en.m.wikipedia.org/wiki/Trace_scheduling
[2] https://en.m.wikipedia.org/wiki/Dominator_(graph_theory)
About two weeks after I started working there, she showed up in my office, and introduced herself. She'd heard about a new PL person joining, and she'd gone and gotten my dissertation and read it, so that she could come talk to me about it. Not that my dissertation was anything special: that's just the way that Fran was.
She was an amazing person. Brilliant, and kind, and generous. The world needs more people like her.
I heard that she was working on a software product that among many other things would do fast matrix multiplication using some parallelism.
So, just for the heck of it, I wrote and ran a little routine in PL/I that used PL/I's feature of multi-tasking to get some parallelism and showed my code to her. She was a little surprised I'd written the code, had a smile, and explained why her work closer to some hardware features (I don't recall the details) would be faster!
I wasn't surprised or disappointed that my little PL/I tasking code would be slower than what she was doing, but at least I got her to explain the hardware she was using and how she was exploiting it!
As I recall, she was married to Jack Schwartz at Courant Institute of NYU and as in
Nelson Dunford and Jacob T. Schwartz, Linear Operators.
But I think you maybe need to work on how you present this anecdote - as it is, it reads like you tried to mansplain her own research to a Turing Award winner. I hope you approached with more humility than this telling suggests?
Also, you should be aware that contextualizing professional women in terms of who their husband is or what his credentials are has long been used to underplay women’s individual achievements. Again, I don’t think that’s your intent, but you could consider whether, in the case of talking about Jacob Schwartz, you would have been moved to drop in the detail of who he was married to?
That is actually very common in my experience when people talk to me about some guy and they think I might have heard of his wife.
Why the question mark at the end? Are you expecting the poster to reply for your own benefit or is it that you'd enjoy seeing him/her apologise publicly for sharing a personal (and presumably happy, at least to them) memory of a former work colleague who has just died. A memory that you have just tortuously construed into a supposed sexist encouter with literally zero insight, context or knowledge ?
Perhaps you might wish to consider your own humility.
https://news.ycombinator.com/newsguidelines.html
graycat's comment contains several details that go against your interpretation. For example the fact that Fran "had a smile" and patiently explained to him why his "little PL/I routine" would be slower than her state-of-the-art optimization work is clearly intended to depict the narrator as naive, and Fran as the expert. The mention of PL/I means that this anecdote likely took place fifty years ago, decades before she Turing Award winner. And the story makes it perfectly clear who ended up being the explainer and who the explainee. Indeed, that seems to be its main point.
As for the marriage bit, the strongest plausible interpretation is simply that it's interesting. Anyone familiar with computer science history would be interested to find out that the two of them had been married, and certainly that goes both ways: an anecdote about Schwartz would be enhanced by mentioning his marriage to a famous compiler optimization researcher. Indeed, it's not hard to find web pages about Schwartz that do this.
I don't think your points are entirely ungrounded, but they weren't the most plausible or good-faith reading of the comment. The cost of introducing an ideological scolding into a discussion like this is non-zero, so there needs to be a bar to clear. That's one reason why we have that guideline, which has proven to work well in situations like this: it basically leads to scolding for egregious cases, forgiveness for borderline cases, and open-mindedness in unclear ones.
Imagine the frozen look of disgust on everyone's face. Imagine the flush of shame coming to your cheeks.
That's what you did. You should apologize for that.
The irony is that your and jameshart's motivations are likely similar. You're both reacting to a perceived slight and standing up for someone who you believe deserved to be treated better. That's a positive motivation, but we need to learn to take the shame bit out. Otherwise it just escalates, and where do we end up?
Are they?
The fundamental premise of jameshart's comment is that group membership is what counts. jamehart assumes graycat is a man, that men talk to women in certain (oppressive) ways, and therefore graycat must show humility--or else.
The comment is nonsensical and incoherent interpreted any other way, and it obviously uses shame as a threat. A threat such as this is only effective if graycat is actually not a misogynist; if he were, he would just ignore it.
In other words, the essential characteristic of jameshart's comment is an appeal to graycat's moral self-doubt and it relies on his fear, guilt, or ignorance. jameshart expects graycat to renounce or revise his anecdote without discussion, under threat of being considered morally unworthy.
This kind of comment must not have a place on HN.
Edit: maybe it would be of interest to add that, from the therapeutic work I've been involved in, it is clear that people's motivations in these areas can often be traced to family dynamics—which is to say, to love. Even when it doesn't look or sound like love, love is usually the driving force. I often think of Chesterton's line, "The soldier fights not because he hates what is in front of him, but because he loves what is behind him". You can say the same thing about political and ideological battles, which after all are (quoting a different celebrity) war by other means.
This is an optimistic view, because the more we can see and acknowledge that love in each other, the less we need to be in conflict. The challenge is that such love often goes through complex transformations and distortions which can be hard to disentangle.
So long as I believe a person is merely mistaken--that is, they lack evidence or the proper method of thinking, but are otherwise virtuous--then I will forgive them a thousand grievances and "acknowledge [the] love" in them. If they are important to me and I don't have to give up something more important, I would be willing to invest the time to bridge our differences. A relationship is the earned reward of the participants' virtues.
But if a person consciously takes a single step toward evil, they are a threat to my life. It would be self-destructive for me to try to see the love in the thug mugging me at gunpoint. It disrespects the people I admire and destroys the value of those positive relationships. Such a person might work to reform their character, but I have no obligation toward them.
I've come to the conclusion there are people in this world who act out of hatred for life and fear of living.
There are soldiers who fight for evil causes, and they are evil. Robert E Lee was offered a senior role in the Union army, but chose to fight for the Confederates. Some might say he fought for love of southern culture or his home or family or any number of other inessential factors; they evade the essential that Lee fought to preserve slavery.
There are soldiers who fight for good causes, and they are good. Sherman fought slavery and he obliterated everything in his path that supported slavery.
To equivocate between the two rewards the wicked and damns the good. Any ethical method that fails to distinguish the essential difference between the two is at best useless, and at worst a tool in the service of evil.
Minimizing conflict is a standard that is anti-life. We should be in conflict with evil. The test I apply in online discussion is to ask myself "What is this person advocating for? If this person achieved their ideal outcome, what would that look like?"
The opinion I've come to regarding comments like jameshart's is that they actively advocate for nothing--nihilism. I don't see any evidence indicating they want to replace something bad with something good. In this case, they want to replace a sentimental anecdote with silence.
By the way, I know these views are radically different. If you are curious about other applications or how it might apply to family interactions, PM me and I'd be happy to chat.
Now that you call it out, I realize that it's probably a mistaken assumption, because Greg spells it "greycat" not "graycat". But it wasn't an unreasonable assumption for HN.
If the OP was trying to share a moment when they enjoyed learning from a great mind, the way they told that story was not a good way to express that. I wanted to give them the feedback that they might want to reframe the story because, telling it the way they did they run the risk of coming across as having behaved poorly. I feel I approached that with reasonable tact and in a spirit of good faith.
I appreciate dang’s commentary back to me about exercising the principle of charity. But I don’t accept that I was nasty. And I don’t appreciate your presumption of bad faith on my part.
Optimizing Compilers for Parallel Computers, lecture by Frances E. Allen https://www.youtube.com/watch?v=Qv-wXcUxrmE
Frances Allen, 2006, ACM A.M. Turing Award Lecture, "Compiling for Performance: A Personal Tour" https://www.youtube.com/watch?v=NjoU-MjCws4
Later, my wife was the first to receive the IBM PhD fellowship established in Fran's honor. Fran awarded it to her at a conference (Grace Hopper I think) and of course was gracious, offering to help as your career moved forward. Thankful for that investment in our future.
"In our conversation she talks about what that transition was like as well as why it is important to increase the diversity in the field and how C has grievously wounded the study of computer science."
First female winner of the Turing Award.
Lots of other notable stuff.
Sadly, this is the first I've heard of her. Hopefully all that means is I'm not a real programmer.
Edit: To be clear, I really meant "I hope other people here are familiar with her work, even though I am not because I'm not a real programmer." I'm happy to see that some people are, in fact, familiar with her and her work.
Many worthwhile people in the world. Not all of them are famous to the people who would love to know them.
At least we can both get to know her more starting now.
Sadly, no, it's not just that. Most my immediate colleagues, for example, don't know of her or her work, either. It's one heck of a field.
She had expressed some dismay, in interviews, at being the first woman to win the Turing Award. Not the Turing Award part, of course, the "first woman" part. She was far from being the first deserving candidate who didn't happen to be a dude. So I hope she wouldn't mind linking this here, even today: https://www.hillelwayne.com/important-women-in-cs/
Just to put the second part of your comment in perspective, there have only been 3 female winners of the Turing award, total, by my count.
At university we would say that computer science was the art, where programming was the craft[1]. It is probably fairer to state that programming is an application of the science.
[1] Though with less of a sneery tone than used when people said "mathematics is the art where computer science is the craft"
It can be quite easy to draw a clean line between theoreticians and implementors in other fields. Biologists and veterinarians, physicists and engineers, etc. But who was the last major computer science theoretician who wasn't also a skilled programmer or system architect (or both)? Alonzo Church?
Is this just because achievements are usually recognized in retrospect, or is this because the 50s to 70s were the most influential portion of computer science (since all groundbreaking things were discovered in the beginning), or is this because women were pushed out more and more by the 70s?
For example: [0]
> Any idea why this one in particular made you feel that way?
Perhaps there's something to do with the fame of the person?
It's difficult to say but it appears that the implicit HN 'criteria' for this is in computer science is to at least be famous enough to be an ACM Turing Award winner. Maybe this is why the reception to the death of another fellow computer scientist and engineer was low. [0]
Nevertheless, they are both worthy of the HN black bar to recognise their achievements to computer science. But I would expect to see a black bar for Frances Allen's passing but unfortunately not for Bill English.
Given my reason for clicking the link, I believe it's the first time I've seen her mentioned on HN. I likely would have clicked on any article with the name Frances in the title and remembered the name if I had ever seen it before.
Because I'm a woman, I actively keep my eye out for female role models. I have a fairly strong math background (for the world at large -- not for the HN crowd) and spent some time looking up info on Maryam Mirzakhani, the first female Fields Medalist, and even blogged about it at the time.
Given my interest in female role models and my personal association with the name Frances, I think I would have known the name had I ever seen it before. It would have likely stuck with me.
I've been here eleven years. It seems I've never seen her name before. And, in fact, if you search for it, it comes up (in the titles section, as part of a description, not really a title) only once ten years ago (until the past 24 hours).
I literally just looked it up, because I wasn't sure. The simple rule presented is that if it's Frances with an e like in "her", then it's the name historically used for women, and if it's Francis with an i like in "him" then it's the name historically used for men.
It truly is a shame that the farther you go back in computer science, the more likely names whose traditional gendering is somewhat ambiguous are to refer to women, and how now that luminaries of the field are passing away, how much more even the field was between the sexes in the past.
We often talk about how we need to bring more women into the field of Computer Science, but I think it's important to note we're trying to bring them back into the field, because they were here from the beginning and it wouldn't be the same without their contributions.
I think this isn't really the time or place to get into gender issues and the field of Computer Science, especially not for me. I see things very different from most other people here and that makes communication challenging.
In this case, that would amount to a terrible derail from the focus on honoring the work and life of Frances Allen.
It's worth noting that, according to the article, Frances Allen actually spent some time focusing on exactly that.
As important as distinguishing her work in the world of computing and programming, Fran was also committed to her team by embracing their ideas and synergies and, in particular, supporting women. She spent many years as a mentor through IBM’s mentor program.
...and later...
“Professionally, Fran spent a lifetime working to advance the field of computing and pioneer new breakthroughs. Personally, she was equally focused on inspiring and motivating young people – especially women – to do the same,” said Fran’s nephew, Ryan McKee, on the IEEE honor.
So I imagine she would be quite happy to have the topic brought up (at least in a positive manner) in discussion of her life and career.
That said, I brought that up to highlight her achievements and character, not to bring you into that conversation if you don't want to be in it, which is your choice, and I can see avoiding that topic as a useful strategy if you think it can't or won't be handled appropriately by the people involved. As such, don't feel compelled to respond about any of that if you don't want to. :)
Edit: It occurs to me now you might have been referring to something entirely different than I thought, in which case I wasn't trying to bring anything of that into the discussion at all, and my wording was purely an attempt to avoid that type of discussion as well.
I've given my guidance for this issue today: We are here to honor the life and work of Frances Allen. Everyone please, kindly, focus on that and don't be offended that I'm trying to step away from the discussion at this point.
I would guess that people who work on building compilers and compiler optimization are more likely to know her name than programmers.
I read one of Frances’ papers on compiler optimization, and while some of it went over my head, it was still valuable information; the world is a sadder place without her.