* Kimmo T Takkunen | When reading this it occurred to me that there may be people out there | who actually need maximum speed on assoc-lists.
Well, that is one possible way to see it, but I see it more as an exercise in showing that choosing alists or plists because one has better theoretical performance than the other is all bunk, because in practice it does not appear to matter. Not one person out there has found test results that clearly contradict my findings, which tells me that (1) modern processors do not appreciate software that does the same kind of optimization they try to do, (2) to make the access times matter, you need to ensure that you fight the cache and have long memory latency, and (3) even when you do, memory organization matters more than the algorithm. In other words, mine is an elaborate argument to ask people not to bother optimizing these things because (1) if the hardware can do it, just let it do it, and (2) before any of this matters significantly, you would profit from switching to something other than alists and plist.
I have some problems figuring out why some people think that just because you set up a fairly elaborate counter-argument, you actually argue in favor of the _opposite_ of what you demonstrate to be false. E.g., when I found that alists and plists were just as fast in normal usage and I saw equal execution times, my attempt at an explanation was that the number of memory references were the same, and that memory latency was not at issue, some think I failed to get the other point that provably had a _negative_ impact on performance. I find this so amazingly useless that I wonder how people think. So, in summary, no, I do not argue for maximum speed of alists (or plists), I reject the notion that the maximum path length argument matters one hoot to actual performance of actual code running on actual machines, because it measurably does not. And if you cannot imagine the glee that some people would take in "proving me wrong", I can, so when nobody steps forward to do it, we can be very certain that the measurements I have made are generally applicable, so the argument remains quite simple: do not use "performance" as an excuse to choose alists over plists when other concerns should weigh more.
| I have made two little functions that may or may not help. They do finds | on lists using move-to-front and transpose heuristics. Both of them | modify element ordering in the list they are working with.
Thanks, this is useful, but I think I would prefer one that kept track of the number of times a key has been visited and maintained a list sorted on that number. This could be done in a training session or at runtime. For instance, many astonishingly stupid C-based programmers have built "command tables" with strings as keys and perform a strncasecmp call for every string in the list until they have a match, which is dumb enough in itself, but then also fail to sort the "command table" in the order of the most likely high use. These are the same people who would no doubt call Lisp slow if they did the exact same thing in Lisp, but still think that C is fast.
/// -- 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.
> > Eric has a special style, and if can't cope that is your problem.
> What about Erik's (note the spelling, please) inability to cope with > many other styles?
From what I have seen (I haven't been here for long), it seems to me that it usually starts when Erik critizises some technology and someone takes it personally and a vicious cycle starts.
Well, I am not here to discuss Erik, so I think I'll leave it at that. And please note that I set follow-ups only to cll.
Apologies for the spelling mistake Erik. (I knew that, just managed to hit the wrong key which is on the other side of the keyboard... duh)
x...@xahlee.org (Xah Lee) wrote: >I would advice you programing geeks, spare a science fiction, spare a >language debate, and read a couple of _text books_ on anthropology, >sociology, law, economics, history, and political science. Then, you >will realize your tech brain knew nothing about humanity and society.
Adam Tissa wrote: > S Campion <vaguely_reminesc...@hotmail.com> wrote:
[...]
Well, well, well. Fascinating.
1. From "S Campion"'s article headers:
| From: S Campion <vaguely_reminesc...@hotmail.com> | NNTP-Posting-Host: 210.49.79.94
2. From "Adam Tissa"'s article headers:
| From: Adam Tissa <verb_precedes_adject...@yahoo.com> | NNTP-Posting-Host: 210.49.79.94
I notice in Adam S Campion-Tissa's list of newsgroups a bunch of Christian ones. Perhaps Mr S. Adam Tissa-Campion considers themselves a Christian. I'll remind him of Luke 12:2-3, and Mark 5:9. Oh, and maybe Matthew 7:1-2.
Followups directed to alt.flame, as they deserve.
-- Gareth McCaughan Gareth.McCaug...@pobox.com .sig under construc
On Sat, 23 Mar 2002 11:19:22 GMT, Erik Naggum <e...@naggum.net> wrote:
>* jewel100...@yahoo.com (jewel100...@yahoo.com) >| And you are too immature and egocentric to behave ?
> No, that would be you. I am not like you, and I can say that because you > have chosen to introduce yourself to me the way you have. Please do not > insult people by extrapolating from yourself -- it gets you into trouble. > I tend to get very irritated by stupid people like yourself, especially > when they are both so conceited and so ill-behaving that they post such > moronic rhetorical questions
Rhetorical question from me: what all this has in common with Lisp or Scheme?
Erik Naggum <e...@naggum.net> writes: > Lispworks generally does not inline even car or cdr as I have seen it, > either, while Allegro CL makes them a single instruction. (Good job!)
In case anyone is left with the wrong impression, LW does too (that was MCL Erann Gat was using, anyway). -- Pekka P. Pirinen GOOD ADVICE: Something old men give young men when they can no longer give them a bad example. - Gideon Wurdz
> Lispworks generally does not inline even car or cdr as I have seen it, > either, while Allegro CL makes them a single instruction. (Good job!)
* Pekka P. Pirinen | In case anyone is left with the wrong impression, LW does too (that | was MCL Erann Gat was using, anyway).
One does not need "impressions". Just grab a trial edition, compile some test code with the appropriate declarations and disassemble. I was fairly disappointed. Even CMUCL did better. Others may come to other conclusions with different code.
/// -- 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.
Erik Naggum <e...@naggum.net> writes: > * Erik Naggum > > Lispworks generally does not inline even car or cdr as I have seen it, > > either, while Allegro CL makes them a single instruction. (Good job!)
> * Pekka P. Pirinen > | In case anyone is left with the wrong impression, LW does too (that > | was MCL Erann Gat was using, anyway).
> One does not need "impressions". Just grab a trial edition, compile some > test code with the appropriate declarations and disassemble. I was > fairly disappointed. Even CMUCL did better. Others may come to other > conclusions with different code.
I don't really read modern assembly code, alas, so I can't comment with authority, but just so we're all on the same page, the following is from LispWorks 4.2 Enteprise on a PC ... I certainly see some inlining here if you set the SAFETY setting to 2, and even more if you set it to 0.
The problem is probably less that it's not doing an optimization and more that both the default optimize settings vary among implementations, and also that the _meanings_ of the optimize settings are not standard...
I'm a little leary of using trial editions as proof of what a commercial implementation is capable of, btw.
On Mon, 25 Mar 2002 17:03:13 GMT, Kent M Pitman <pit...@world.std.com> wrote:
> I don't really read modern assembly code, alas, so I can't comment with > authority, but just so we're all on the same page, the following is from > LispWorks 4.2 Enteprise on a PC ... I certainly see some inlining here > if you set the SAFETY setting to 2, and even more if you set it to 0.
Windows or Linux? I pasted your examples into LW 4.2 on Linux running on a K7 and got the same results, only the addresses of the jmp and call were different.
Now I am really curious, why the constant 200015BC in the first cmp is the same in both cases...
> On Mon, 25 Mar 2002 17:03:13 GMT, > Kent M Pitman <pit...@world.std.com> wrote:
> > I don't really read modern assembly code, alas, so I can't comment with > > authority, but just so we're all on the same page, the following is from > > LispWorks 4.2 Enteprise on a PC ... I certainly see some inlining here > > if you set the SAFETY setting to 2, and even more if you set it to 0.
> Windows or Linux?
Windows
> I pasted your examples into LW 4.2 on Linux running on a K7 and got > the same results, only the addresses of the jmp and call were different.
> Now I am really curious, why the constant 200015BC in the first > cmp is the same in both cases...
Perhaps one is fixed early in the system build and doesn't follow the conditional inclusion of system-dependent code the presence or absence of which implicitly changes the magnitude of subsequent addresses? I dunno. Just a guess... It's way below the level of abstraction at which I usually prefer to hang around.
s...@xss.de (Stefan Schmiedl) writes: > Now I am really curious, why the constant 200015BC in the first > cmp is the same in both cases... > > 0: 3B25BC150020 cmp esp, [200015BC] ; T
The "; T" usually means that the literal constant there represents the value of T. Since most Lisp implementations locate their heaps in the same place in memory for the same architecture/OS, they can hardcode those constants directly.
-- -> -/ - Rahul Jain - \- <- -> -\ http://linux.rice.edu/~rahul -=- mailto:rj...@techie.com /- <- -> -/ "Structure is nothing if it is all you got. Skeletons spook \- <- -> -\ people if [they] try to walk around on their own. I really /- <- -> -/ wonder why XML does not." -- Erik Naggum, comp.lang.lisp \- <- |--|--------|--------------|----|-------------|------|---------|-----|-| (c)1996-2002, All rights reserved. Disclaimer available upon request.
* Kent M Pitman <pit...@world.std.com> | The problem is probably less that it's not doing an optimization and more | that both the default optimize settings vary among implementations, and | also that the _meanings_ of the optimize settings are not standard...
The declaim caused all other implementations to compile to the fastest inline code they could. LispWorks still makes calls to cddr-1arg.
| I'm a little leary of using trial editions as proof of what a commercial | implementation is capable of, btw.
Well, I think that if anyone purposefully crippled the compiler in the trial edition, they would seriously have hurt their possibility of getting new customers.
/// -- 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.
Raymond Toy <t...@rtp.ericsson.se> writes: > >>>>> "Thomas" == Thomas F Burdick <t...@conquest.OCF.Berkeley.EDU> writes:
> Thomas> I wish I'd had enough time to engage this thread, because this is > Thomas> exactly the sort of nonsense I find fun. I was also happy to find > Thomas> that I'm not the only one who finds SPARCs utterly impossible to > Thomas> benchmark on.
> What makes Sparcs so bad? I use Sparcs all the time, but I don't > normally need this kind of extra fine timing info.
Oh, I love SPARCs, but I just have a hell of a time constructing benchmarks for them. I'm not sure what the cause is, but I've noticed that if I micro-optimize the assembly language produced by, say, GCC -- in a way that I'm 95% sure should make it faster -- I can't always construct benchmarks that show a speed up. Sometimes I see a slow down. When I put the hand-optimized code back into the application I pulled it out of, the application will speed up. I just figured there was something wrong with my brain wrt SPARC benchmarking (which could still be true), but I was sort of comforted to see that Duane has a similar problem. This doesn't happen to me on IA-32 (I really hope my brain hasn't been wired for that horror of an architecture!).
-- /|_ .-----------------------. ,' .\ / | No to Imperialist war | ,--' _,' | Wage class war! | / / `-----------------------' ( -. | | ) | (`-. '--.) `. )----'
t...@apocalypse.OCF.Berkeley.EDU (Thomas F. Burdick) writes:
> Oh, I love SPARCs, but I just have a hell of a time constructing > benchmarks for them. I'm not sure what the cause is, but I've noticed > that if I micro-optimize the assembly language produced by, say, GCC > -- in a way that I'm 95% sure should make it faster -- I can't always > construct benchmarks that show a speed up. Sometimes I see a slow > down. When I put the hand-optimized code back into the application I > pulled it out of, the application will speed up.
Maybe this has to do with cache effects. Since there's no reordering in SPARC, it should be horribly sensitive to cache misses (which, incidentally, is what Intel seems to be most concerned about with the IA-64, explaining their elaborate and awesome cache design for the McKinley). Cache behavior should change pretty significantly between microbenchmarks and real-world code, so I wouldn't be too surprised if that were the case.
-- -> -/ - Rahul Jain - \- <- -> -\ http://linux.rice.edu/~rahul -=- mailto:rj...@techie.com /- <- -> -/ "Structure is nothing if it is all you got. Skeletons spook \- <- -> -\ people if [they] try to walk around on their own. I really /- <- -> -/ wonder why XML does not." -- Erik Naggum, comp.lang.lisp \- <- |--|--------|--------------|----|-------------|------|---------|-----|-| (c)1996-2002, All rights reserved. Disclaimer available upon request.
> > What makes Sparcs so bad? I use Sparcs all the time, but I don't > > normally need this kind of extra fine timing info.
> Oh, I love SPARCs, but I just have a hell of a time constructing > benchmarks for them. I'm not sure what the cause is, but I've noticed > that if I micro-optimize the assembly language produced by, say, GCC > -- in a way that I'm 95% sure should make it faster -- I can't always > construct benchmarks that show a speed up....
SPARCs are very sensitive to instruction alignment. I don't know whether the alignments that matter have to do with the instruction buffer, instruction cache, or branch target, or (probably) all three, but I have noticed that inserting nop instructions in front of a tight loop can make it run as much as 2.5 times as fast (or as slow).
As a compiler writer, I used this alist/plist example as a micro- benchmark to see how much effort I should put into instruction scheduling for the SPARC. I wrote two versions of the linear search for both alists and plists. The first version is a trivial translation of Erann Gat's code into Scheme. The second versions were pipelined by hand. When compiled to unsafe code by Twobit, both of the simple versions execute 10 SPARC instructions per iteration, both pipelined versions execute 12, and all versions execute 3 loads per iteration.
I timed all four versions on each of two benchmarks. The first benchmark (1000000x1000) performs one million fruitless searches of a list with 1000 entries (i.e. 2000 elements in the plist), which presumably fits within the primary data cache. The second benchmark (1000x1000000) performs 1000 fruitless searches of a list with one million entries, which presumably does not fit within any data cache. I ran these benchmarks on a SunBlade 100 with no other users; I think it clocks at about 400 MHz. The results, in seconds (i.e. nanoseconds per entry searched):
These timings are the average of three runs, with no more than 0.2% deviation from the mean for 1000000x1000, and with no more than 3.3% deviation for 1000x1000000.
Now, to give you an idea of how sensitive the SPARC is to instruction ordering, here are the timings on that same machine for a different but equally good Scheme compiler:
> Oh, another thing Scheme says to people when it refuses to give people > the freedom do what they think is best is: "You couldn't figure out the > Right Thing on your own if you tried".
> ... People are not _naturally_ > "higher-order thinkers", but there is much evidence to support a view > that some people have a hard time dealing with "horizontal complexity" > and much prefer "vertical complexity" on very small initial space.
where is that evidence? give a reference to significant research.
* ozan s yigit <o...@blue.cs.yorku.ca> | where is that evidence? give a reference to significant research.
Yup, another revengeful moron. We just cannot do without them, can we?
What is _wrong_ with you guys? Why do you have such a huge problem just living your own lives that you have to run after people you hate to taunt them with completely idiotic passive-aggressive and so hostile rhetorical "question" like these? Get a _life_, ozan s yigit! And just _behave_!
/// -- 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.
? ... People are not _naturally_ ? "higher-order thinkers", but there is much evidence to support a view ? that some people have a hard time dealing with "horizontal complexity" ? and much prefer "vertical complexity" on very small initial space.
> | where is that evidence? give a reference to significant research.
? [crap elided] We just cannot do without them, can we?
no you cannot, especially if you choose to spew hateful rhetoric about intellectual honesty and learning. this is a real question about a curious claim. what evidence, what research? go look it up, post a reference for that "much evidence" when you are done with your spluttering.
oz --- the factual burden of a science varies inversely with its degree of maturity. -- Peter Medawar
Learn to behave, get a life, and stop believing that you can order people around. Please take your time. I may want to answer your questions when you manage to present yourself as a human being, but it is not likely. In any case, please cease and desist with your abusive behavior.
/// -- 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.
? ... People are not _naturally_ ? "higher-order thinkers", but there is much evidence to support a view ? that some people have a hard time dealing with "horizontal complexity" ? and much prefer "vertical complexity" on very small initial space.
so, are you going to just drool and splutter as is your custom, or post something worth reading to support this curious "people are not _naturally_ "higher-order thinkers"" claim? here, i'll even include something possibly relevant to get you started.
oz --- obref: Merlin Donald, "Origins of the Modern Mind" Harvard, 1991.
