>* I disagree with Hans that people will want to keep their mark(copy)/alloc >ratios high enough to keep the total memory to some some integer times the >live data. Memory is becoming cheaper faster than processors are becoming >faster,
...
I don't believe this. The doubling time for processors speeds is definitely less than two years. Memory costs hardly seem to be coming down at all.
Rob ====================================================================== Robert O'Callahan (r...@cs.cmu.edu) 2nd year CMU SCS PhD Home page: http://www.cs.cmu.edu/~roc Three million people, sixty million sheep, one America's Cup
> >* I disagree with Hans that people will want to keep their mark(copy)/alloc > >ratios high enough to keep the total memory to some some integer times the > >live data. Memory is becoming cheaper faster than processors are becoming > >faster,
> I don't believe this. The doubling time for processors speeds is > definitely less than two years. Memory costs hardly seem to be coming > down at all.
Thanks to everyone who pointed this out to me. Perhaps I'm looking at this with a much longer time scale -- 35 years or so. I'm also using the intuition that cycle time is linearly related to feature size, while memory space is quadratically related to feature size. Unfortunately, this intuition doesn't consider things like the strength of the dollar, the budgeting cycles of major DRAM vendors, etc. Also, the ability of Microsoft to waste memory so prodigiously has really raised the demand curve. (I understand that 'Bob' was going to require a minimum of 32 Mbytes. Whatever happened to 'Bob', anyway? Perhaps he succumbed to hype blood pressure...)
In article <WGD.95Oct19005...@martigny.ai.mit.edu>, w...@zurich.ai.mit.edu
(Bill Dubuque) wrote: > Cgol dates back to the late seventies at MIT LCS/AI Lab. > Pratt wrote cgol based upon his "top-down operator precedence > pahich is also used in Macsyma). See the Aho et. al. > Dragon book for a reference to Pratt's original paper on > this parser.
> I don't know if anyone has ported cgol from MacLisp to Common > Lisp. You could probably dig up the MacLisp source.
I believe that Macsyma uses cgol as its parser. So presumably if you have CL Macsyma, you also have CL cgol.
>In article <DGApp8....@undergrad.math.uwaterloo.ca>, >Carl Laurence Gonsalves <clgon...@undergrad.math.uwaterloo.ca> wrote: >>The incredible slowness of Java is only evidence of the inefficiency of >>garbage collection. [...] >>I'm also not saying that garbage collection is the only reason Java is >>slow. [...]
Which implies that it is _a_ reason, just not the only one.
>Several people seem to have misunderstood my point, so I thought I'd better >clarify. I am *not* saying that garbage collection is slow. What I am >saying is that Java is slow. I think most people agree on this. Java also >has garbage collection. (any disagreements?) >Now, when I said "evidence" perhaps I was using the wrong word. By evidence >I mean that (statistically speaking) the fact that Java is both slow and >has GC puts a point in the "GC is slow" bucket.
But it doesn't. If anything, it puts a point in the "system that uses GC is slow" bucket. It also puts one in the "system whose name starts with `J'" bucket.
Now, why do you think the first bucket is worth mentioning while the second is obviously silly? Presumably you think GC might well be a reason Java is slow. Moreover, that you describe the bucket as the "GC is slow" bucket suggests that your view is actually a stronger one.
I'm not trying to show that you think that "garbage collection is slow", just to say something about why people might have thought that was your view.
>The post I was originally replying to was saying that one could convince C >and C++ programmers that GC could be efficient by pointing at Java. That's >a silly statement since Java programs are very slow, and if anything the >slowness of Java will make many C and C++ programmers feel that GC must be >the cause of Java's slowness.
: Okay, tell me where I can get a Scheme compiler for the Amiga. :-)
I suspect that Gambit will go on it.
: But actually, I never said that "there aren't any Scheme or Lisp : compilers". In fact, I acknowledged their existence. I even read a paper on : Scheme->C. So I know they exist. I just haven't seen one.
Haven't looked terribly hard ;-)
: The Scheme interpreter I used the most was called "scm". I can't find any : man-pages for it, but it looks like it's interpreted to me. It might be : doing "incremental compiles" but the outward appearance is that of an : interpreter. It's interactive and slow.
Compared to say what? I've used it for all manner of things, including lashing in a PVM interface to enable me to write apps in Scheme that use PVM routines to communicate with other scheme / pvm processes written in C. no bother and it went like a dream.
Kindly provide some stats if you are claiming its slow, either that or try some of the other free lisp substrates and see how your mileage varies ;-)
: The Lisp that I use isn't CommonLisp. It's actually AutoLISP (the Lisp : interpreter built into AutoCAD). I was developing some small CAD : applications in AutoLisp. As far as I know there is no compiled AutoLISP : compiler, but I haven't really bothered to check. Interpreted Lisp was fast : enough for my purposes.
Which is essentially Xlisp based I think, which then might mean you have the save workspace function to generate .wks files...
: The fact that I haven't actually used or seen a Scheme or Lisp compiler is : probably dirrectly related to the fact that I don't do a lot in Scheme or : Lisp, and I don't really worry myself by looking for Scheme and/or Lisp : compilers. I personally don't like the parenthesized syntax of Lisp that : much, and I find it takes me a lot longer to develop in Lisp or Scheme : because I have to do a mental conversion. I'm certainly not saying that : parenthesized syntax is inferior. I just don't particularly enjoy : programming in a language like that. It's about as easy as hand coding : PostScript I find.
Oooooh, thats trolling for flamage <grin> I use whatever happens to float my boat for a particular project, Ive found SCM to be easily extensible in C for what I want...and I found it very very rapid to prototype stuff up in once you added the primitives to put in the app specific bits (this is tantamount to heresy, I realise this :-) that had to be glued in via C.
: Perhaps there is a similar language (like maybe Dylan, I haven't looked at : it yet) that I would find prefferable, but Scheme and Lisp aren't my : favorite languages. So I hope that helps you understand why I haven't : seen Scheme or Lisp compilers: I haven't really gone loooking for them.
Hmm, having a more in depth look might persuade you I guess, but it's your loss not to investigate what they have to offer..
In article <DGnB3F....@cogsci.ed.ac.uk> j...@cogsci.ed.ac.uk "Jeff Dalton" writes:
> What do you mean by "Allegro CommonLISP"? The one from Franz Inc that > runs on Suns and a number of other machines definitely includes a > compiler to native code. If you call everything that's incrementally > compiled or interactive (or maybe only both) an interpreter, you're > just wrong. As for speed, compiled code isn't much slower than > compiled C.
In fact, (sorry mention him again), in Writing Interactive Compilers and Interpreters, PJ Brown calls both compilers and interpreters by the same word: compilers. That's so much simpler, esp when the differences may be rather complicated.
> Did you actually compile anything, by the way?
I'd argue that even tokenised Basic interpreters compile. Microsoft's QuickBasic used a very interesting compiler, and yet it was also interactive and incremental. Perhaps it should still be called an interpreter because it used threaded code (an "address interpreter")? Forth traditionally used threaded code, but some implementations use native code. I've used both kinds, but the distinction I'd make is between the interactive & incremental compilers, and the "batch" variety.
You could make any argument you like, if you conveniently define enough of the terms you use to support it. That's why I like PJ Brown's terminology so much. Just call them _all_ compilers... -- <URL:http://www.demon.co.uk/community/index.html> <URL:http://www.enrapture.com/cybes/namaste.html> Current favourite word: hypersonic. As used by Fluffy. "You can never browse enough."
In article <DGo5A6....@undergrad.math.uwaterloo.ca> clgon...@undergrad.math.uwaterloo.ca "Carl Laurence Gonsalves" writes:
> Okay, tell me where I can get a Scheme compiler for the Amiga. :-)
XScheme? If it isn't available for the Amiga, then it should be easy to fix, assuming that you have a suitable C compiler.
> The Scheme interpreter I used the most was called "scm". I can't find any > man-pages for it, but it looks like it's interpreted to me. It might be > doing "incremental compiles" but the outward appearance is that of an > interpreter. It's interactive and slow.
I think you mean, "It's intepreted and slow." Interactive languages don't have to be slow. They can just as easily compile to native code. This is just a matter of compiler technology, and any good book on the subject should cover that. I have several...
> The Lisp that I use isn't CommonLisp. It's actually AutoLISP (the Lisp > interpreter built into AutoCAD). I was developing some small CAD > applications in AutoLisp. As far as I know there is no compiled AutoLISP > compiler, but I haven't really bothered to check. Interpreted Lisp was fast > enough for my purposes.
If AutoLISP is not fast enough for you, then you should contact AutoDesk and let them know. Perhaps they'll do something about, but if nobody demands better performance, then don't be suprised if you don't get it.
Please note that AutoLISP is not typical of Lisp systems in general. It's an embedded language, and it may be assumed that performance will depend more on AutoCAD than the language that extends it.
> The fact that I haven't actually used or seen a Scheme or Lisp compiler is > probably dirrectly related to the fact that I don't do a lot in Scheme or > Lisp, and I don't really worry myself by looking for Scheme and/or Lisp > compilers. I personally don't like the parenthesized syntax of Lisp that > much, and I find it takes me a lot longer to develop in Lisp or Scheme > because I have to do a mental conversion. I'm certainly not saying that > parenthesized syntax is inferior. I just don't particularly enjoy > programming in a language like that. It's about as easy as hand coding > PostScript I find.
Why then are you so concerned about the performance of these languages? Is the problem the fact that you can't avoid them? Are there any other languages that you'd rather avoid, or with featues that you have difficulty with? If you'd like some help in this area, please say so, so we can offer you some.
> Perhaps there is a similar language (like maybe Dylan, I haven't looked at > it yet) that I would find prefferable, but Scheme and Lisp aren't my > favorite languages. So I hope that helps you understand why I haven't > seen Scheme or Lisp compilers: I haven't really gone loooking for them.
You should certainly take a look at Dylan, but I think reading some good books on compiler theory may also help. It's a fascinating subject, even if you never intend to write a compiler. For example, they may help you with string handling in general (source code is a string, and so is object code). They may also help you understand the languages you use a little better.
> I don't think there is an AutoLISP compiler.
Ask AutoDesk about this. That's better than just assuming something, As people say, that only makes an ASS out of U and ME.
I believe that Macsyma uses cgol as its parser. So presumably if you have CL Macsyma, you also have CL cgol.
Macsyma doesn't use cgol but does use a 'top-down operator precedence parser', the same type of parser used in cgol. Again, see the Dragon book for Pratt's paper. Its absolutely trivial to implement one of the parsers in Lisp.
In fact, (sorry mention him again), in Writing Interactive Compilers and Interpreters, PJ Brown calls both compilers and interpreters by the same word: compilers. That's so much simpler, esp when the differences may be rather complicated.
> Did you actually compile anything, by the way?
I'd argue that even tokenised Basic interpreters compile. Microsoft's QuickBasic used a very interesting compiler, and yet it was also interactive and incremental. Perhaps it should still be called an interpreter because it used threaded code (an "address interpreter")? Forth traditionally used threaded code, but some implementations use native code. I've used both kinds, but the distinction I'd make is between the interactive & incremental compilers, and the "batch" variety.
You could make any argument you like, if you conveniently define enough of the terms you use to support it. That's why I like PJ Brown's terminology so much. Just call them _all_ compilers...
Rather than call every thing compilers, I prefer to make the distinction that an interpreter executes a set of instructions; a compiler translates them into another language. The hardware is an interpreter. Some programs are interpreters (that are themselves interpreted, usually by the hardware). Many other programs are compilers -- sometimes they translate the program into the language that is directly interpreted by the hardware (native code compilers), sometimes they translate the program into a language that is interpreted by another program (or another part of the same program).
Using those definitions, things like ParcPlace's Smalltalk system is an interesting beast: when a method is compiled it is translated into byte-codes; when the method is invoked, it is translated into machine code that is interpreted by the hardware (this translation is, presumably, only done if it's not already in memory). So, it is interactive, looking like what people tend to call interpreters, but it's really a double edged compiler (I think they prefer "incremental compiler")!
w...@zurich.ai.mit.edu (Bill Dubuque) wrote: >Again, see the Dragon book for Pratt's paper. Its absolutely >trivial to implement one of the parsers in Lisp.
>-Bill
Trivial to code, but don't forget that getting the operator precedence values 'right' is tricky stuff.
Other pratt parsers can be found in the symbolic algebra package for SCM, and in the siod 3.0 release that went out to comp.sources.unix a few years back.
But three things make the original CGOL stand out:
1. the use of dynamic binding of precedence values. so that the operator bindings changed as you entered different contexts. 2. that it was written in CGOL itself, making it more difficult to port to new lisp implementations. 3. the helper-functions for defining new syntax were quite clever. maybe too clever.
>>>>> On 19 Oct 95 00:51:16, w...@zurich.ai.mit.edu (Bill Dubuque) said:
Bill> I don't know if anyone has ported cgol from MacLisp to Common Bill> Lisp. You could probably dig up the MacLisp source.
A CL version and the Pratt memo are in ftp://peoplesparc.berkeley.edu/pub FWIW. (I think the Pratt parser in the JACAL system is written in a Scheme subset intended to aid a CL implementation.)
In article <JWD.95Oct20083...@ihnns792.ATT.COM> Joseph_W_Davison@.ATT.COM "nq8140700-Davison" writes:
> Rather than call every thing compilers, I prefer to make the distinction > that an interpreter executes a set of instructions; a compiler translates > them into another language. The hardware is an interpreter. Some programs > are interpreters (that are themselves interpreted, usually by the > hardware). Many other programs are compilers -- sometimes they translate > the program into the language that is directly interpreted by the hardware > (native code compilers), sometimes they translate the program into a > language that is interpreted by another program (or another part of the > same program).
Sometimes a language system compiles _and_ interprets. What do you call such a system? In some systems, the amount of compilation may depend on what you do with the code, like how often you run it.
> Using those definitions, things like ParcPlace's Smalltalk system is an > interesting beast: when a method is compiled it is translated into > byte-codes; when the method is invoked, it is translated into machine code > that is interpreted by the hardware (this translation is, presumably, only > done if it's not already in memory). So, it is interactive, looking like > what people tend to call interpreters, but it's really a double edged > compiler (I think they prefer "incremental compiler")!
Exactly. Apparently, Microsoft's QuickBasic will "recompile" the code as you move from one state (e.g. edit) to another (e.g. run), and then back again.
The Taos operating system uses the "virtual code" idea in its kernal, which makes the VP code portable (as long as you use Taos). You write your code using the VP assembler. Does that make the "compiler" part of the OS? If you want to think of it like that, then it could be what some people call a "throw away compiler".
ParcPlace Smalltalk uses a similar idea, as you said, but it works at the method level. Perhaps we could call it an "incremental throw away compiler"?
All these ideas are described by PJ Brown in Writing Interactive Compilers and Interpreters. The difference is that he was using Basic as his example language, and since he was writing in the mid 70s, it's not suprising that he used lines as the unit of compilation. -- <URL:http://www.demon.co.uk/community/index.html> <URL:http://www.enrapture.com/cybes/namaste.html> Current favourite word: hypersonic. As used by Fluffy. "You can never browse enough."
In article <KANDERSO.95Oct20141...@lager.bbn.com> kande...@lager.bbn.com (Ken Anderson) writes: > I've waited a few days hoping that there would be some clarification on > this "25x or so" figure before responding to this. Generally when the > runtimes of two programs that "do the same thing" differ by a factor that > large, they are doing something wildly different. I suspect that most of > the difference has little to do with one program being in Lisp and the > other in GCC.
I have tried changing C programs into perl before now, since perl's syntax is very close to C (or can be), this enabled me to test the relative speeds of compiled and interpretted code. Doing really basic stuff (floating point math) I found C 100 times faster (almost exactly actually). This isn't a criticism of perl, I am sure that perl would perform much better if I was doing string manipulation, but I just wanted to point out that in math intensive programs C or FORTRAN will often do miles better than interpretted languages.
> Memory is becoming cheaper faster than processors are > becoming faster,
Seems factually incorrect, at least locally. Processors have gotten faster in the last five years, whereas RAM as pretty much stayed constant at $40/megabyte (yes, not exact, but pretty close) for the last five years. Am I missing something? Five years is a pretty long trend.
> The original poster was asking whether GC could ever be faster than a > malloc/free implementation, not whether GC is expensive or cheap for > real programs. There are clearly cases where GC is intrinsically > faster than malloc/free, even if in most real cases, there isn't much > difference between the two.
Anecdotally the answer seems to be yes. An unpublished report on a large (>500,000 lines) program that was converted from explicit deallocation to an ambiguous-roots style collector resulted in a significant speedup. For non-disclosure reasons I cannot give more details, except to say that this program is a successful commercial application (both before and after conversion to GC), and the same group of programmers worked on both versions (ie, programmer variation would seem to be at best a second-order factor).
hba...@netcom.com (Henry Baker) writes: >* I disagree with Hans that people will want to keep their mark(copy)/alloc >ratios high enough to keep the total memory to some some integer times the >live data. Memory is becoming cheaper faster than processors are becoming >faster, so it will continue to be more appealing to allocate enough memory >to keep the fraction of the time spent in GC at a nearly negligible level >-- kind of like the current cost of 'refreshing DRAMs' (you didn't know >about this?) As a result, the 'sweep cost' _could_ (without clever >programming) become a significant fraction of GC time, although it would >still be a negligible cost overall.
Paul and others have already responded to much of Henry's message. But I think there's an important issue here. My experience has been that memory requirements of current garbage collected systems often prevent their acceptance. A significant contributing factor are GC algorithms that are much more generous than necessary in their memory use. The reasons I don't think this is acceptable:
1. I vaguely recall that memory was around $20/MB around 1991 (corrections appreciated). The current price is around $30/MB. Processors have gotten much faster since then.
2. As a result, I claim the average PC is grossly underconfigured with memory. Most PCs would gain much more from a memory upgrade than a processor upgrade, if they're running anything beyond DOS. RISC workstations tend to be configured a bit more reasonably, but users expect something in return for the extra money they paid for memory.
3. Not all programs are designed to take over a machine. Many programs are designed to run in the background while the machine is used for something else. Few users will be happy with a large memory footprint background program (or 20 of them) while they are running SML of NJ, or some CAD program, or Microsoft Word, or whatever, in the foreground.
4. Users expect that if your machine has N megabytes, you should be able to run an application that has nearly N megabytes live data without paging. If you tell them the real limit is .7N they'll grumble, but they might accept it. If you tell them it's N/5, you've lost.
I will agree that you should be able to tune the heap size. But my experience is that few users ever do such tuning.
Hans-J. Boehm (bo...@parc.xerox.com) Standard disclaimer ...
In article <hbaker-2510951016220...@10.0.2.15> hba...@netcom.com (Henry Baker) writes:
> In article <46jb8v$...@news.parc.xerox.com>, bo...@parc.xerox.com (Hans > Boehm) wrote:
> > 2. As a result, I claim the average PC is grossly underconfigured with > > memory. Most PCs would gain much more from a memory upgrade than a > > processor upgrade, if they're running anything beyond DOS. RISC > ^^^^ > > workstations tend to be configured a bit more reasonably, but users > > expect something in return for the extra money they paid for > > memory.
> The RISC 'revolution' has increased memory requirements for code by about > a factor of two.
Good point. I did some tests (years ago) by compiling the same program on a 68040 and then a Sparc and you are correct about the factor of two. This was for small programs. What I noticed was that as the programs got larger the factor got larger (than two). This was just something that I noticed and did not prove any results. Also, the CISC compiler may have been better than the RISC compiler for larger programs. But it was enough to make me start wondering about all the hype over RISC architectures at the time.
In article <QOBI.95Oct26104...@qobi.ai>, Jeffrey Mark Siskind wrote: >I'm told that on DEC ALPHAs, which use 64 bit points, that memory >requirements are doubled yet again.
>Data structure size affects not only paging performance but also caching >performance. Has anybody done a study to see what the tradeoffs are >between the increased instruction cost of CDR coding vs the potential >decreased cache-miss ratio? How would that change if minimal CDR-coding >hardware were added to RISC processors?
Yep. Work on the Titanium project at UC Berkeley has done some work so far on 'packed linked lists', packed binary trees (B-trees), etc. to look at dealing with the multi-level memory hierarchies that exist today and will exist in the future. Some very prelimary numbers on a couple of existing machines with just packed LLs showed pretty clearly that performance increased either a little below or a little above 2X where the data object size was around the cache line size.
: I would advise using .-relative addressing for all pointers (perhaps some : C compiler vendor/GNU is listening), and start using VM compression. Once you : have encoded pointers as _relative_ addresses instead of _absolute_ : addresses, then VM compression will work better.
Could you explain how using .-relative addressing improves compression? The way I understood it VM compression (a la Mac RamDoubler) only works really well if the pages to be compressed consist mostly of zeros.
-- [SCSI] ist ja bekanntlich so kompliziert, dass es nur die fuer ihre Bastelwut beruechtigten Apple-User benutzen. -- Detlef Grell, c't 8/95 -- Erik Corry ehco...@inet.uni-c.dk
hba...@netcom.com (Henry Baker) writes: >The RISC 'revolution' has increased memory requirements for code by about >a factor of two.
My impression is that code density varies a lot between CISC processors, and that code density for "32 bit" code on an X86 is nothing to write home about either. But RISC code is likely to be larger.
>Furthermore, due to RISC requirements for data alignment, RISC _data_ has >also gotten much less dense -- e.g., I'm not aware of any RISC Lisps which >do 'cdr-coding' anymore. I would imagine that the RISC revolution has >expanded data requirements by perhaps 1.5X.
I don't know about Lisp implementations. For C code, I don't believe this makes an appreciable difference. Borland and Microsoft C/C++ compilers have different defaults for alignment. The Microsoft compiler uses RISC-like alignments by default (which makes sense for time performance reasons) and the Borland compiler uses one byte alignments by default (probably for historical reasons). I suspect most important structures are manually aligned so they come out the same way in either case. But then the fields are also likely to be manually ordered to minimize loss, so even the loss over, say, a VAX representation is likely to be minimal.
>Therefore, unless you start using some form of VM >compression on code pages, you are probably in worse shape than before >RISC, because you are going to page fault more often than a CISC architecture >with the same amount of memory, and this is a very non-linear phenomenon. >(RISC processors should be very good at doing compression, so the overall >cost of this should be quite small.) >I would advise using .-relative addressing for all pointers (perhaps some >C compiler vendor/GNU is listening), and start using VM compression.
Please don't do that for C; you'll break conservative GC completely. (You'll also break at least all C code that calls third party libraries, and I doubt you'll have an ANSI conforming compiler. How do you handle union assignments? But I have my priorities straight :-))
>Once you >have encoded pointers as _relative_ addresses instead of _absolute_ >addresses, then VM compression will work better.
Presumably the right place to convert to relative pointers is in the compressor?
Hans-J. Boehm (bo...@parc.xerox.com) Standard disclaimer ...
In article <QOBI.95Oct26104...@qobi.ai>, Q...@CS.Toronto.EDU wrote: > I'm told that on DEC ALPHAs, which use 64 bit points, that memory requirements > are doubled yet again.
> Data structure size affects not only paging performance but also caching > performance. Has anybody done a study to see what the tradeoffs are between > the increased instruction cost of CDR coding vs the potential decreased > cache-miss ratio? How would that change if minimal CDR-coding hardware were > added to RISC processors?
I would believe that some sort of 'pointer-swizzling' idea might work better than checking the pointers on every access.
Hans Boehm <bo...@parc.xerox.com> wrote: >hba...@netcom.com (Henry Baker) writes:
>>The RISC 'revolution' has increased memory requirements for code by about >>a factor of two.
>My impression is that code density varies a lot between CISC processors, >and that code density for "32 bit" code on an X86 is nothing to write >home about either. But RISC code is likely to be larger.
The number I've heard bandied about is about 1.3 times CISC size, on average. I think early RISC compilers generated more bloated code, partly because they weren't mature (eventually optimizers got better at reducing code size without much speed penalty), and partly because some early RISC architectures (e.g., MIPS R2000?) required a lot of NOPs to ensure that pipeline constraints were preserved.
My impression is that everybody's using interlocked architectures that just stall as necessary, rather than requiring NOPS, because that makes it easier to design multiple generations of binary-compatible RISCs.
>>Furthermore, due to RISC requirements for data alignment, RISC _data_ has >>also gotten much less dense -- e.g., I'm not aware of any RISC Lisps which >>do 'cdr-coding' anymore. I would imagine that the RISC revolution has >>expanded data requirements by perhaps 1.5X.
I don't think CDR-coding would be worthwhile on modern CISCs either. (Though Henry may have been talking about counterfactual "Lisp-oriented modern CISCs", which haven't actually been built, partly due to marketing issues.)
At any rate, I don't think microcode would help any longer---CISC machines are going to have a RISC core, and you're going to want to do loads and stores in a single cycle. I'm not sure what impact CDR-coding support would have on a machine with single-cycle loads and stores. I'm not sure what should go into which parts of the hardware, and whether you can do it without an impact on the cycle time, at least in the uncommon case. Then again, I'm not sure it's a problem---I haven't worked it out.
I'm also not sure how big a win CDR-coding is in a modern dialect of Lisp, programmed in a modern, object-oriented style, or whether programming styles should change. I wouldn't be surprised if conventional Lisp list structures get less common over time, as people come up with alternative data structures using object-oriented features or whatever.
There's some data (from Bob Shaw's and Ben Zorn's theses) that bear on this, but there are lots of issues. (It appears that most object-oriented Lisp programs still use in the ballpark of half their memory for list cells. But that may be an artifact of poor compilers for object systems, and there might be a trend toward more and more object-orientedness as it gets relatively cheaper.)
At any rate, on stock hardware CDR coding is a big lose speedwise. Compressed VM is more general, because it can compress pointers in other kinds of data structures, as well as compressing nonpointer data.
> [ ... For C ] I suspect >most important structures are manually aligned so they come out the >same way in either case. But then the fields are also likely to be manually >ordered to minimize loss, so even the loss over, say, a VAX representation >is likely to be minimal.
>>Therefore, unless you start using some form of VM >>compression on code pages, you are probably in worse shape than before >>RISC, because you are going to page fault more often than a CISC architecture >>with the same amount of memory, and this is a very non-linear phenomenon. >>(RISC processors should be very good at doing compression, so the overall >>cost of this should be quite small.)
Yes, if you have very fast compression algorithms.
>>I would advise using .-relative addressing for all pointers (perhaps some >>C compiler vendor/GNU is listening), and start using VM compression.
VM compression is a good idea, but relative addressing isn't necessary for it to work quite well; pointers are highly compressible if you have any kind of decent locality in your data structures.
>Please don't do that for C; you'll break conservative GC completely. >(You'll also break at least all C code that calls third party libraries, >and I doubt you'll have an ANSI conforming compiler. How do you handle >union assignments? But I have my priorities straight :-)) >>Once you >>have encoded pointers as _relative_ addresses instead of _absolute_ >>addresses, then VM compression will work better. >Presumably the right place to convert to relative pointers is in the >compressor?
Yes. That's what we do in a compressed VM system we're developing. Actually, we don't bother to convert to relative explicitly, we just notice that the upper and middle bits of a lot of pointers are similar to upper and middle bits of lots of other nearby pointers, and exploit that.
-- | Paul R. Wilson, Comp. Sci. Dept., U of Texas @ Austin (wil...@cs.utexas.edu) | Papers on memory allocators, garbage collection, memory hierarchies, | persistence and Scheme interpreters and compilers available via ftp from | ftp.cs.utexas.edu, in pub/garbage (or http://www.cs.utexas.edu/users/wilson/)
In article <DH25zB...@kroete2.freinet.de>, ehco...@inet.uni-c.dk (Erik
Corry) wrote: > Henry Baker (hba...@netcom.com) wrote:
> : I would advise using .-relative addressing for all pointers (perhaps some > : C compiler vendor/GNU is listening), and start using VM compression. Once you > : have encoded pointers as _relative_ addresses instead of _absolute_ > : addresses, then VM compression will work better.
> Could you explain how using .-relative addressing improves compression? > The way I understood it VM compression (a la Mac RamDoubler) only works > really well if the pages to be compressed consist mostly of zeros.
If you allocate a list in sequence, and they are allocated contiguously, then one of the fields will point to a location .+n bytes subsequent. If these are relative pointers, then they will all be 'n', so a reasonable compression scheme -- e.g., gzip -- should be able to compress such a sequence.
I don't know how sophisticated RamDoubler's compression scheme is.
| I would advise using .-relative addressing for all pointers (perhaps | some C compiler vendor/GNU is listening), and start using VM | compression.
[Hans Boehm]
| Please don't do that for C; you'll break conservative GC completely. | (You'll also break at least all C code that calls third party | libraries, and I doubt you'll have an ANSI conforming compiler. How do | you handle union assignments? But I have my priorities straight :-))
this is odd. to build shared objects (libraries) under, e.g., SunOS 4, so-called "position-independent code" must be emitted by the assembler, and special considerations must be followed by the compiler. (not all C code can be compiled into shared objects, but I don't know what the conditions are.) given this, are you saying that shared objects would cause the compiler (or library) not to be conforming to ANSI C? if so, this is, IMNSHO, a problem in the standard (ISO C, actually) that should be fixed.
#<Erik 3023918552> -- a good picture may well be worth a thousand words, but on the WWW, even bad imagemaps cost tens of thousands of words.
bo...@parc.xerox.com (Hans Boehm) wrote: >1. I vaguely recall that memory was around $20/MB around 1991 >(corrections appreciated). The current price is around $30/MB. >Processors have gotten much faster since then.
Yea..This is one is a real problem. Why haven't dram prices tracked processors? I beleive that it was a bit earlier than 1991, however, I beleive that it was the far-east producers dumping on our market to drive out all of the competition and now have a monopoly. They are keeping prices high, but not so high that the uproar causes the US Goverment to do something about it. And why haven't the US companies gotten back into the market? Well they are staring to (IBM & TI) but always with Japanise partners. I read some time ago that the US has given up on the DRAM market. But if there is money to be made, why isn't the US Goverment protecting US-based companies from the unfair traiding practices of other countries?
Just my two cents worth. Mike -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Mike Christiansen mi...@metronet.com
