Path: utzoo!attcan!uunet!zaphod.mps.ohio-state.edu!think.com!barmar From: barmar@think.com (Barry Margolin) Newsgroups: comp.lang.misc Subject: Re: Answers, Chapter 1: TeX (was C's sins... and others) Message-ID: <1990Nov12.194544.14504@Think.COM> Date: 12 Nov 90 19:45:44 GMT References: <7AZ6O15@xds13.ferranti.com> <5347@lanl.gov> Sender: news@Think.COM Organization: Thinking Machines Corporation, Cambridge MA, USA Lines: 60 In article peter@ficc.ferranti.com (Peter da Silva) writes: >In article <5347@lanl.gov> jlg@lanl.gov (Jim Giles) writes: >> I know the IBM-PC is the cause of the ANSI restriction. > >And means that the ANSI restriction is pretty much irrelevent: if they'd >left it out, then your PC compilers would have kept doing whatever it is >they do, they would just be "sub ANSI". As it is you can assume that pointer >comparison is safe without restrictions so long as you're not on an 80x86. The 80x86 is not the only architecture with multi-level memory. There have been quite a few systems built with segmented or object-based memory architectures. I use a machine on which implementing pointer comparison between unrelated arrays is even harder than on an 80x86. On the 80x86 dealing with the segment number is just a performance issue. On my Lisp Machine, global and malloc'ed objects are allocated as individual arrays in the Lisp heap (pointers are a combination of an array and an index), and garbage collection can change the relative order in memory of two heap objects, so it wouldn't be correct to use the machine addresses when comparing pointers. There are ways consistent pointer comparison could be implemented in this system, but they're as unattractive as the mechanism for the 80x86. For instance, the arrays could have an extra element at the beginning that would contain its object number, a number that would be incremented for each object allocated; pointer comparison would first compare the object numbers, and only compare the offsets if the object numbers are equal (unfortunately, this would mean that pointer comparison could cause page faults). Or the C runtime could allocate a big array at program startup time, and do all its allocation out of that (growing it when necessary). Symbolics Fortran does this for all its static data. Pointers would just be indices into this one array, so comparison would just compare their values. However, one of the prime benefits of allocating each object as a separate array, though, is that the Lisp Machine's hardware array bounds checking will catch invalid array accesses, and this would be lost if a single array were used (actually, a variant using indirect arrays might work, but then comparisons would cause indirection and possible page faults, as above). And growing the C heap would be expensive, as it would have to be copied. You keep on talking about implementing a portable memory allocator in C. I presume you're talking about a design where it allocates big chunks of memory using the system's malloc(), and then doles out smaller pieces of this; pointer comparison would be used by your free primitive to determine which chunk the object came from. This can be done portably by using back pointers from the allocation points to the beginning of the chunk; this is faster than the comparison method (the former is constant time, the latter is O(Nchunks)), but it does require extra overhead for each allocated object. Other portable designs make similar tradeoffs. This just goes to show that memory management is best done using implementation-dependent techniques, because efficient memory management requires consideration of the memory architecture of the system. Portable memory allocators are nice toys, but don't expect them to be blazingly fast. -- Barry Margolin, Thinking Machines Corp. barmar@think.com {uunet,harvard}!think!barmar