Ada Outperforms Assembly: A Case Study

http://www.seas.gwu.edu/~adagroup/sigada-website/lawlis.html

by cygwin98 • 15 years ago

46 32 15 years ago

seas.gwu.edu

zwieback• 15 years ago

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.

Stormbringer• 15 years ago

From the article it describes the assembly programmer as an: "experienced assembly developer"

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.

Someone• 15 years ago

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.

userulluipeste• 15 years ago

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.

rbanffy3• 15 years ago

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.

russell• 15 years ago

Back 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.

rbanffy3• 15 years ago

I have the utmost respect for anyone who programs a computer that has two round monitors ;-)

DarkShikari• 15 years ago

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):

  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: 59

blackguardx• 15 years ago

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.

chrisjsmith• 15 years ago

Bollocks.

bediger• 15 years ago

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.

_mhp_• 15 years ago

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.

chopsueyar6• 15 years ago

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?

callmeed• 15 years ago

Ada was uned in my first two comp sci classes at junior college. Our instructors were defense contractor programmers at Vandenberg AFB.

dxbydt• 15 years ago

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.

chopsueyar6• 15 years ago

Go Mountaineers!

Are there currently any decent developer jobs in WV? I would love to move to the Greebrier County area.

Montani Semper Liberi

ahi5• 15 years ago

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.

chopsueyar6• 15 years ago

Out of personal curiosity, what was your reasoning when deciding to attend GWU?

Would you recommend it to others?

hedgie2• 15 years ago

"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.

davemarchevsky• 15 years ago

I'm (hopefully) going to graduate GWU's CS program in May 2012; Ada is no longer part of the curriculum AFAIK.

vbtemp• 15 years ago

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

ahi5• 15 years ago

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.

hedgie2• 15 years ago

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.

vlisivka• 15 years ago

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.

Ada Outperforms Assembly: A Case Study

Related Stories