Ada Outperforms Assembly: A Case Study(seas.gwu.edu)
seas.gwu.edu
Ada Outperforms Assembly: A Case Study
http://www.seas.gwu.edu/~adagroup/sigada-website/lawlis.html
7 comments
I do not find this example convincing. The assembly was written and, I assume, optimized for one CPU, but it was timed on a more expensive, _pipelined_ processor.
The Ada compiler was written for that processor. That could make a big difference. For example, starting every function on a mod 16 boundary can be a big win on some architectures.
The Ada compiler was written for that processor. That could make a big difference. For example, starting every function on a mod 16 boundary can be a big win on some architectures.
I worked with TI320 in the same time period quite a bit and remember the Tartan compilers (not Ada, though). It's easy to believe that a compiler beats a naive assembly code writer. The pipelining example is a good one, it can take hours poring over the manual to figure out how to best arrange your assembly instructions to keep the 320 pipeline flowing. The compilers at the time knew some of the tricks but it was still usually possible to hand-optimize the compiler output quite a bit.
Programming a DSP, like driving an F1 car or flying a F-22, is supposed to be a very hard thing to do. Machines optimized for performance don't relate well to humans.
A smart compiler can remember and apply a number of optimizations far greater than I would be able to remember. The weirder the processor, the better. A really smart development tool could even benchmark variations to find the best one.
My 6502 assembly code was much better than what the Aztec C compiler could spit, but the 6502 was a sweet processor to program. DSPs (as GPUs, BTW) are anything but sweet.
And, BTW, I wouldn't try to hand tune assembly code with a modern x86 even if my life depended on it.
A smart compiler can remember and apply a number of optimizations far greater than I would be able to remember. The weirder the processor, the better. A really smart development tool could even benchmark variations to find the best one.
My 6502 assembly code was much better than what the Aztec C compiler could spit, but the 6502 was a sweet processor to program. DSPs (as GPUs, BTW) are anything but sweet.
And, BTW, I wouldn't try to hand tune assembly code with a modern x86 even if my life depended on it.
And, BTW, I wouldn't try to hand tune assembly code with a modern x86 even if my life depended on it.
Writing fast modern x86 assembly is often way easier than for most any other CPU because instruction ordering generally doesn't matter much as a result of OOE (outside of Atom, at least). This basically lets you BS together a function without thinking too hard about anything other than the individual instructions.
It's trivial to beat the performance of typical C code by a factor of 10-20 in many situations, particularly in the case of DSP functions, as per the topic.
Some typical cases (measured in cycles):
Writing fast modern x86 assembly is often way easier than for most any other CPU because instruction ordering generally doesn't matter much as a result of OOE (outside of Atom, at least). This basically lets you BS together a function without thinking too hard about anything other than the individual instructions.
It's trivial to beat the performance of typical C code by a factor of 10-20 in many situations, particularly in the case of DSP functions, as per the topic.
Some typical cases (measured in cycles):
8x8 iDCT, 16-bit input to 8-bit output:
add8x8_idct8_c: 779
add8x8_idct8_sse2: 56
6-tap interpolation filter, 8-bit input, 16-bit intermediate, 8-bit output:
hpel_filter_c: 13093
hpel_filter_ssse3: 1770
Bilinear downscaling filter, 8-bit input, 8-bit output:
lowres_init_c: 16308
lowres_init_ssse3: 672
4 SAD comparison operations on 16x16 8-bit pixel blocks, unaligned input:
sad_x4_16x16_c: 1873
sad_x4_16x16_sse2: 95
Variance on 16x16 block, 8-bit input:
var_16x16_c: 536
var_16x16_sse2: 59Back in the days I did a lot of assembly programming for the CDC 6400/6600 computers. The instruction set was simple, but processor flow wasnt. IIRC there were 3 or so integer units and 1 floating point unit. If a result wasnt ready when an instruction needed it, the processing flow would stall until it was ready. So you needed to remember the instruction timings for each of the models, how many processing unit you were using, etc. to get maximum thruput. This is stuff that a compiler does easily, humans less so. Part of my team was writing hand tuned libraries and part was writing the compilers to produce optimal code. I got to see the trade-offs.
Rick James, now at Yahoo, was the king of assembly. He wrote a character move library that was faster than the character move hardware, $100K add-on. He kept getting poached from my projects, because, even at CDC, there weren't many as good as he was.
Then there is the productivity issue. The HLC programmer can produce 10x the number of instructions more than the assembly programmer.
Rick James, now at Yahoo, was the king of assembly. He wrote a character move library that was faster than the character move hardware, $100K add-on. He kept getting poached from my projects, because, even at CDC, there weren't many as good as he was.
Then there is the productivity issue. The HLC programmer can produce 10x the number of instructions more than the assembly programmer.
I have the utmost respect for anyone who programs a computer that has two round monitors ;-)
I think it really depends on what filter or function you are implementing. For example, programming an FIR filter in assembly is easier to do on a DSP than on a conventional processor. It is true that DSPs are designed for speed, but they do that by making the architecture and instruction set match the problem space. So programming a DSP to do DSP isn't that bad.
To make a programming analogy, a DSP is like a domain specific language. It is more efficient and easier to use when used in that domain.
To make a programming analogy, a DSP is like a domain specific language. It is more efficient and easier to use when used in that domain.
When I attended GWU, we were required to take two semesters of Ada.
The professor who wrote the Ada 95 book would give us cash as we found logical or typographical errors in the book.
Not sure if there are any other universities that push Ada so hard in intro classes. Perhaps this has changed now.
Any recent GWU compsci people care to comment?
The professor who wrote the Ada 95 book would give us cash as we found logical or typographical errors in the book.
Not sure if there are any other universities that push Ada so hard in intro classes. Perhaps this has changed now.
Any recent GWU compsci people care to comment?
I studied Ada 3 semesters & taught Ada 1 semester at WVU. I think it had to do with the fact that West Virginia Univ was big on defense, NASA & FBI projects which mandated Ada. Some of those avenues have materialized bigtime:
http://www.fbi.gov/news/pressrel/press-releases/west-virgini...
Ultimately I felt it was not such a fair deal for the students. Over 50% of grad CS WVU students were non-US, so they would never get to work on these Defense related stuff due to sec-clearance. Ada was also touted as a successful example of design-by-committee, which I found quite nauseating.
Ultimately I felt it was not such a fair deal for the students. Over 50% of grad CS WVU students were non-US, so they would never get to work on these Defense related stuff due to sec-clearance. Ada was also touted as a successful example of design-by-committee, which I found quite nauseating.
Go Mountaineers!
Are there currently any decent developer jobs in WV? I would love to move to the Greebrier County area.
Montani Semper Liberi
Are there currently any decent developer jobs in WV? I would love to move to the Greebrier County area.
Montani Semper Liberi
Maybe I'm recent enough. I enrolled and took intro courses in Fall of 2001, graduated in 2005. My intro courses, IIRC "intro to CS" and "algos & data structures" were Ada. 2nd year Software Engineering was Java. I think students starting Fall of 2002 had an entirely Java curriculum. At the time I was kind of annoyed to be learning Ada rather than Java, especially because the faculty member who wrote the assigned Ada textbook couldn't be bothered to actually teach the course. However, looking back on it I think Ada is a better language for learning than Java because everything is so explicit. I still have Ada on my resume, mostly for shits and giggles. I'd take it off if I was applying anywhere that might ask me to prove it.
EDIT: Reconsidering. Ada pushes you toward the waterfall development process which can be dangerous for newbs to internalize.
EDIT: Reconsidering. Ada pushes you toward the waterfall development process which can be dangerous for newbs to internalize.
Out of personal curiosity, what was your reasoning when deciding to attend GWU?
Would you recommend it to others?
Would you recommend it to others?
Location, location, location. Columbia said no thanks. CMU said "okay, but no CS major". Case Western offered better money and athletics but it's in Cleveland. Johns Hopkins seemed like 80% premed jackasses. I didn't consider Georgetown because when I was looking at schools my dad didn't want to pay for parking.
I initially wrote out a very long description of GW before I realized you had attended. So shortened considerably:
I went to grad school at U of Michigan and have come to the conclusion that most colleges/universities are basically the same. For such an important decision with such wide-ranging consequences, where you go to school is relatively hard to screw up. Undergraduate education is mostly foolish and cult-like behavior--Go Blue!--in a pretty setting where you can find an education and lifelong friends if you look for them. When people recommend a school they are usually recommending the cult. I went to Freshman orientation on my 18th birthday. I had been away from home a week and living down the street from the State Department and the White House when the Pentagon went boom. GW was my training ground for adulthood. The experience is so integral to who I am, to recommend it feels a bit odd.
I initially wrote out a very long description of GW before I realized you had attended. So shortened considerably:
I went to grad school at U of Michigan and have come to the conclusion that most colleges/universities are basically the same. For such an important decision with such wide-ranging consequences, where you go to school is relatively hard to screw up. Undergraduate education is mostly foolish and cult-like behavior--Go Blue!--in a pretty setting where you can find an education and lifelong friends if you look for them. When people recommend a school they are usually recommending the cult. I went to Freshman orientation on my 18th birthday. I had been away from home a week and living down the street from the State Department and the White House when the Pentagon went boom. GW was my training ground for adulthood. The experience is so integral to who I am, to recommend it feels a bit odd.
Thurston Hall?
Lafayette at 21st and I. I don't think I would have survived Thurston.
You haven't lived until you've experienced 4 people living in a 400sqft room with one bathroom, all NAT'ing a single Ricochet wireless modem, simultaneously downloading MP3s from UPenn student's FTP sites.
It was before Thurston had an ethernet network. All of the other dorms seemed to have direct fiber and media converters.
1300 people in a 9 story building. Especially fun, when a block from the dorm, somebody ran over a fire hydrant, and the water supply had to be shut off for several blocks, including Thurston (there were no tank toilets). 8 hours of clogged toilets on every single floor, including the public bathrooms and study lounges.
...or the false fire alarms, where all 1300 students evacuate from only two sets of stairwells.
...or when facilities management decides it is warm enough to enable air conditioning.
Good memories. I have more, but this is enough for now.
It was before Thurston had an ethernet network. All of the other dorms seemed to have direct fiber and media converters.
1300 people in a 9 story building. Especially fun, when a block from the dorm, somebody ran over a fire hydrant, and the water supply had to be shut off for several blocks, including Thurston (there were no tank toilets). 8 hours of clogged toilets on every single floor, including the public bathrooms and study lounges.
...or the false fire alarms, where all 1300 students evacuate from only two sets of stairwells.
...or when facilities management decides it is warm enough to enable air conditioning.
Good memories. I have more, but this is enough for now.
"Ada pushes you toward the waterfall development process which can be dangerous for newbs to internalize."
Why do you say that? We use ada with spiral development.
Why do you say that? We use ada with spiral development.
No Ada at my (big ten) school but I work coding Ada at my current job.
The language is amazing. Most of my errors are related to copy-paste oversights (Message_1 instead of Message_2). The typing is very elegant.
Also, Java stole Ada's way of handling exceptions. Instead of try catch you have begin/exception.
It's a shame so few people use Ada. They recently converted GNAT (a free Ada compiler and a very good one) to work with lego mindstorms. It's still big in safety critical areas (transport systems - the trains in europe run ada and lots of avionics code is in ada, the medical field and if I hear correctly banks sometimes use it as well).
It takes longer to get it to compile but having no array indexing errors is so worth it.
The language is amazing. Most of my errors are related to copy-paste oversights (Message_1 instead of Message_2). The typing is very elegant.
Also, Java stole Ada's way of handling exceptions. Instead of try catch you have begin/exception.
It's a shame so few people use Ada. They recently converted GNAT (a free Ada compiler and a very good one) to work with lego mindstorms. It's still big in safety critical areas (transport systems - the trains in europe run ada and lots of avionics code is in ada, the medical field and if I hear correctly banks sometimes use it as well).
It takes longer to get it to compile but having no array indexing errors is so worth it.
Ada was uned in my first two comp sci classes at junior college. Our instructors were defense contractor programmers at Vandenberg AFB.
Feldman's last year was my first year there. He had a great legacy, but in his final years he wasn't too popular among the students, and I think not too many people were sad to see him go at that point.
EDIT: That said, the last thing I expected to see scanning the HN headlines today was something from gwu.edu :-P
EDIT: That said, the last thing I expected to see scanning the HN headlines today was something from gwu.edu :-P
I wasn't going to name names, but I remember many people not being pleased that we were required to buy his textbook even though he had clearly checked out. In fairness, he had a great reputation because he was a very good teacher. He just took his sweet time retiring.
http://www.amazon.com/Ada-95-Problem-Solving-Program/dp/0201...
IS this the book you guys used?
IS this the book you guys used?
The 3rd edition looks familiar.
I'm (hopefully) going to graduate GWU's CS program in May 2012; Ada is no longer part of the curriculum AFAIK.
I've asked myself (like many others I think) - which is the most "efficient" PL? From this article it can be concluded that it's not so much the language itself like it is the compiler implementation. And programming in assembly is just stupid, unless you work on some compiler optimization or hacking disassembled code.
Typical success story:
We wrote program in language X and then rewrote it in language Y, so Y is better language than X, because our program is much better after rewrite.
We wrote program in language X and then rewrote it in language Y, so Y is better language than X, because our program is much better after rewrite.
Bollocks.
I was inclinded towards that view myself, based on the date: 1992 was when the US DoD was still pushing Ada pretty darn hard. I personally found the story hard to believe, but I have no experience with DSP assembly.
I have got experience of DSP assembly (mostly 320C25 stuff, a little 'C50), and I initially doubted the story. DSPs like the 'C25 were pretty easy to work with since the instructions were all the same length (ignoring memory wait states for the moment). But with the 'C50 (and the 'C30 from the article), delayed branching was introduced. Whilst you can optimise for that in your head, it becomes a pain and often results in hard-to-maintain code. Adding a couple of NOPs makes it much easier!
The article highlighted common sub-expression elimination too, which again can be done manually. But (and this is the crux IMHO) writing optimal code continuously at this level is mentally tiring (leading to bugs) and often gives brittle unmaintainable code. A compiler never needs to worry about this as it generates fresh code every time rather than maintaining the code from the last build. But a human will learn to avoid brittle code and hence won't be able to take advantage of the possible optimisations.
The article highlighted common sub-expression elimination too, which again can be done manually. But (and this is the crux IMHO) writing optimal code continuously at this level is mentally tiring (leading to bugs) and often gives brittle unmaintainable code. A compiler never needs to worry about this as it generates fresh code every time rather than maintaining the code from the last build. But a human will learn to avoid brittle code and hence won't be able to take advantage of the possible optimisations.
From the article it describes the ADA programmer as: "This developer had very limited Ada experience, having written only one Ada program, consisting of approximately 5000 lines of code, while working for a previous employer."
One of the key points of the article is that the code produced by the inexperienced ADA developer beat the experienced Assembly developer. I think a lot of people will struggle with this (because they think "well, logically the code gets turned into assembly anyway when it is compiled, so a sufficiently advanced assembly programmer _must_ be at least as good as a compiler), but the same claims (high level languages beating assembly) have been floating around for years.
In this case study at least, jumping straight to assembly (for size/performance reasons) turned out to be a premature optimisation of the sort we should avoid.