Subject: Re: data hygiene [Re: Why is Scheme not a Lisp?] From: Erik Naggum <erik@naggum.net> Date: Sat, 23 Mar 2002 13:59:59 GMT Newsgroups: comp.lang.lisp Message-ID: <3225880811573244@naggum.net> * Matthias Blume | No, that was not his purpose. Paul showed an algorithmic optimization | for a machine that can have 3 loads independently in flight (so that | they do not have to wait for each other). Nothing about infinite | registers and other such nonsense. They are not needed. I have spent some time with the documentation for my processor, and it has four-way concurrent access to the level 2 cache, request-response access to syste memory, and instantaneous level 1 cache access. As near as I can tell, my simple alist-get function exercises the kinds of optimizations that Paul has described and the branch prediction is done the right way with Allegro CL's code, so there should be no pipeline flushes at all. As near as I can tell, the code I have written in alist-get-expand, as compiled by Allegro CL cannot be improved upon. Now, I have tried to optimize Paul's code similarly, but it is in dire need of registers in order to keep from accessing the level 1 cache to swap registers with memory. Paul's code is 27% slower than my simple alist-get-expand. | Now, there *are* machines where multiple loads (but not infinitely many) | can be independently in flight. There are literally thousands of people | in the world doing research of how to efficiently program for such | machines. Very nice. If Paul is one of them, his code should have run faster than mine. It does not. | In the beginning you were, IIRC, demonstrating that you need the same | number of CARs and CDRs in either case -- which (while certainly correct) | showed that you didn't even understand at that time what Paul was talking | about. (Well, at least you were hiding it well... :-) I have tried to argue that the same number of memory accesses are needed. Paul did a much better job of explaining his case after it became clear that he was not actually interested in optimizing his code, but instead optimizing the algorithm. The result is slower execution. I remain resoundingly unimpressed. | Paul was saying that there are machines where this can be an advantage. | You say "on my machine it doesn't". No, I have asked for information on which machines it does apply since I cannot find any such machine. Please pay attention if you want to accuse people of ill will and stupidity, will you? Otherwise, you are the offender. | Fine, neither of you has contradicted the other. A counterexample is | does not disprove an existentially quantified statement. Had Paul said | "this will always make a difference", he would have been wrong. But he | didn't. What he has indeed said is that his code should run faster, yet has not shown that it actually does on any extant hardware. However, it appears that the benefits that he talks about are handled at the hardware level in my processor and that his software pipelining works _against_ the hardware because of the register shortage. In other words, it works better to do this in software on CPUs that lack hardware support for pipelining, and that it has no effect at all on machines with enough registers. If there are no processors that can do 3 concurrent memory accesses that do _not_ do sufficient pipeline entirely on their own, this is useful, but if modern processors all do this on their own, there is simply no point in doing software pipelining, and the effect should be noticeable regardless. In particular, there should be _no_ difference in execution time between scanning a list of a million elements (to get rid of the cache) and scanning the cars of a list of a million conses, i.e., heavily optimized member and assoc should run just as quickly on the same list. I would like to see timings on at least one processor where this is the case. | In any case, let's talk about something more useful. How about: Which | implementation of bubblesort runs fastest? I am actually happy that you are so bemused that this beats daytime TV. /// -- 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.