Subject: Re: data hygiene [Re: Why is Scheme not a Lisp?]
From: Erik Naggum <>
Date: Sat, 23 Mar 2002 07:53:28 GMT
Newsgroups: comp.lang.lisp
Message-ID: <>

* "Paul F. Dietz"
| Mr. Naggum, no, it is not just plain wrong.  *You* are just plain wrong.
| *Study* that algorithm I posted.  Build the dependency graph of the
| loads.  You will see that the maximum path length in the alist graph is
| N+O(1) vs. 2N+O(1) for the plist.

  Mr. Dietz, you are anti-productive.  There is more to this than the
  "maximum path length".  Nobody has _ever_ disputed these claims, but you
  continue to neglect the _additional_ costs: things like cache lines and
  the register requirements of your algorithm.  What you offer us is a
  _complication_ that has absolutely no value at the level you offer it --
  it has significant value in understanding _some_ issues, but when you
  refuse to listen to the measurable facts, something is just plain wrong.

  Optimization is about making things execute more efficiently, faster in
  this case.  When your code runs significantly slower then mine (93 ns vs
  71 ns on my machine), there is something _wrong_ in your premises to
  optimization.  Is this so hard to understand and accept?  A 28% increase
  in the time spended on scanning an alist is not optimization in my book.

| I've presented a trivial proof that you cannot (it's right in front of
| you there.)

  What is right in front of me is not just proofs, but also measurements.
  Since you diss my measurements, I must assume that you are either unable
  to deal with the real world or have a personal problem, since you could
  very easily _repeat_ these measurements in a straight-forward scientific
  way, yet you cling to your proofs.  I find this _extremely_ annoying.

  We are, or at least I am, discussing optimization on a real machine with
  real registers and real memory.  It is very useful to be able to talk
  about some abstract machine with abstract registers and abstract memory,
  but optimization of real machines obey many _additional_ constraints.  A
  proof that considers only one set of constraints and completely ignores
  all others is not useful when discussing which will run faster on actual
  hardware.  And let us not forget that some of these optimizations give
  you a lower cost of some things at the expense of higher costs of other
  things.  Optimizing access into an alist many thousands of key-value
  pairs long is precisely the kind of stupid thing that people who learn
  that Lisp is for List Processing would do.  Real programmers would find
  that not only is there no benefit to your more complex algorithm, it has
  far higher costs than savings.

  If I have "mistaken" this discussion for being some academic exercise in
  theoretical "optimization" apart from implementation, please let me know.
  I have sort of based my entire line of reasoning on the kinds of design
  choices people were inclined to make because "alists are faster than
  plists".  Theoretical optimization with a large number of registers is
  fine -- as long as it actually runs faster, too.  A _potential_ to run
  faster given a more perfect universe does not impress me when I want raw

| How about you show me an algorithm that does plist search in better than
| 2N+O(1) load latency?

  So you want others to compete with you on your home ground and refuse
  adamantly to consider any other premises.  How interesting.

  I have tried to make you realize that I have discussed actual hardware.
  There has been absolutely no secrecy around what I have been doing, but I
  have continually found that you want to discuss something else that does
  not yield better results.  I am profoundly sorry to see that you are
  completely oblivious to hardware and think a _more_ optimal algorithm can
  reasonably be expected to run _slower_ than a less optimal algorithm.  I
  consider an algorithm to be faster when it _is_ faster, as _measured_.

| Funny, I was wondering the same thing.

  Yeah, another case of the mirror game is brewing.  Sheesh, some people.

  But obviously we have different purposes: You want to "prove" algorithmic
  optimization on an abstract machine with an infinite number of registers
  and constant memory access costs.  I actually want to obtain the fastest
  implementation of a algorithm on a given machine (repeated for more
  machines as necessary), including its variable memory costs due to
  multi-level caching, its register shortage, etc, and I consider more
  complex algorithms that run slower to be going in the wrong direction.

  It is time to realize that "optimization" is both a mathematical and an
  engineering discipline.  I had sort of hoped you could have figured out
  what _I_ have been demonstrating, when you are so bloody eager to shoe me
  stuff that does not answer any question anybody had asked before you came
  along.  So, you have given us a nice proof that does not matter, code
  that runs slower than my _far_ simpler code (which even checks for nil in
  the alist, which you skimped on!), and you still huff and puff.  What
  makes you tick?  I am frankly seriously annoyed by people who refuse to
  listen to simple, repeatable, measurable facts and prefer their theories.

  In a fight against something, the fight has value, victory has none.
  In a fight for something, the fight is a loss, victory merely relief.