fundamental tradeoffs in programming

[gusl]

Image you are to write a certain function 'f'. The purpose of calling it is to do X for every element of a list (and optionally Y; this is controlled by a flag)

Which of the following is better?

(a)

function f()
  for 1:1000
    do X
    if(flag)
      do Y

(b)

function f()
  for 1:1000
    do X
  if(flag)
    for 1:1000
      do Y

In all languages I know, (a) is more elegant but (b) is more efficient.

In Lisp, another alternative exists: you can write a macro to do a partial evaluation given the value of 'flag'. This is as efficient as (b), but whether it's elegant is debatable. Personally I've never seen an IDE that makes code-rewriting macros nice to work with.

Comments

[nibot.livejournal.com]

I don't think this is a language issue so much as an architecture issue.

(a) is much more efficient if memory access is expensive;

Actually, I think (a) is better in most cases. Your CPU's branch prediction will probably take care of the "if(flag)" quite nicely.

[the-locster.livejournal.com]

I agree that it's an architecture issue. For starters the reason it's generally more efficient to use two loops is because of the expense of incorrect branch prediction; if there is no branch prediction then there's no difference, and it;s not an academic point as you might see this (or less heavyweight branch prediction) in multi-core architectures such as the Cell chip which take the approach that more work can be done by trimming back the complex architectures required to speedup single cores and use the transistor real estate for more cores instead - and then you get into how to produce parallel algorithms efficiently and elegantly.

[bhudson.livejournal.com]

Version c:
if flag then loop x, y
else loop x

I hadn't read Gustavo's version quite right at first; thought his b was my c.

[ikeepaleopard]

At a higher level than branch prediction, many languages these days are implemented with a jit, which will optimize the test out if it turns out to be expensive.

[gustavolacerda.livejournal.com]

http://en.wikipedia.org/wiki/Just-in-time_compilation

[bhudson.livejournal.com]

Screw the JIT -- this is just loop invariant optimization. Cheap and easy.

[ikeepaleopard]

Not so easy if X and and Y are effectful.

[gustavolacerda.livejournal.com]

are you confident enough in your compilers that you'd never consider writing (b)?

[bhudson.livejournal.com]

I'm confident enough in Amdahl's Law that I would write the cleaner form until required to check the disassembly.

[lo5an.livejournal.com]

In my experience, elegance and human readability should trump efficiency until there is empirical evidence of a need for optimization. I guess that makes me a knuthist.

[gustavolacerda.livejournal.com]

I have the same leanings... as a programmer, I like to push the burden away from myself, and onto the people who make compilers.

[chrisamaphone]

right. i feel like the point of having programming languages at all is to have the ability to separate these concerns.

[gustavolacerda.livejournal.com]

yeah, and ultimately, a programmer should be able to write a BubbleSort or a BogoSort and expect a good sort to run.
Maybe this will happen in my lifetime. :-p