Data structures and algorithms

[fanf]

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships." - Linus Torvalds

"If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming." - Rob Pike

"Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious." - Fred Brooks

Comments

[simont]

It occurs to me that compiler optimisation is a prominent exception to this rule. (I don't really want to say 'counterexample', since it doesn't invalidate the sensibleness of the rule in many other contexts.)

In a compiler mid-end, carefully chosen data structure representation can only take you so far. Certainly you can do things like using a flowgraph representation rather than linear code with explicit branches and labels, and using virtual rather than physical regs for as long as possible, and doing SSA if that seems like a good idea, and so on; but sooner or later you still end up with a long list of instructions to do a bunch of things in a particular order and you have to ask yourself, 'What other list of instructions can I prove to be semantically equivalent to this one and judge to have better performance and/or code size?', and there are lots and lots of different techniques for finding such lists and very few of them are immediately obvious given the input data structure.

[fanf]

Yes, I think that's true to a large extent. But there are still examples of this rule in action inside compilers: isn't SSA exactly the kind of crucial change of representation that makes certain optimization algorithms easier?

[simont]

Easier, certainly, but still a long way from 'obvious given the data representation'! But I suppose if you're prepared to weaken the rule to say something closer to 'algorithms are easier if you pick the right data structure first' in place of 'algorithms are trivial and/or self-evident given the right data structure', then yes.