Subject: Re: data hygiene [Re: Why is Scheme not a Lisp?] From: Erik Naggum <erik@naggum.net> Date: Fri, 22 Mar 2002 07:22:08 GMT Newsgroups: comp.lang.lisp Message-ID: <3225770541321057@naggum.net> * "Paul F. Dietz" | This is a *trivial* consequence of the structure of the dependency graph | of the loads. Both graphs have ~3 N nodes, but the length of the | critical path in the alist search is N vs. 2N for the plist. This is just plain wrong. Please understand that we are doing assoc, not member, on alists, OK? The car of an alist is just as much on the critical path as the cdr of a plist. This is frighteningly obvious if you spend the time to __study it rather than make up your mind and then spend your time to "prove" it. | As Mr. Pitman requested, let's see the code. Here's a software | pipelined implementation of (assoc ... :test #'eq), concentrating | on the case of a non-null key. What does "concentrating on the case of a non-null key" mean? | You will notice that in the main loop (not counting epilogue code), | between any load and the first use of its result you will find at least | two other loads. You can't do as well with plist search -- there aren't | as many other loads to fit between the cdrs. I have asked you to work this out for plists, too, but you keep posting only code relevant to alists. I am not interested in what you have to say about alists as long as you make _no_ effort to show what you can do similarly with plists. Can you please understand this? | If we're on a machine in which (1) load latency dominates, and (2) three | loads can be in progress at once, then this algorithm will take time | N+O(1) (in units of load latency). *Any* plist algorithm would take time | 2 N in this model of computation -- you can't start one critical path | load until the previous one is completed, and there are 2 N such loads. *sigh*. Yes, that is precisely what you can do. There is no difference. Work it out similarly for plists. CAN YOU DO THIS, PLEASE!? Christ! Your code is extremely unlikely to have any effect, by the way. If you have to grab data from external memory, you need _way_ more than two intervening loads. An L1 cache hit is basically free, so the point is to get stuff into the L1 cache. This does not happen any differently in your code than in a straight version of alist-get and plist-get that I posted. I wonder why you are so stubborn about something that is clearly wrong. /// -- 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.