Mark H Weaver <m...@netris.org> writes: > Hi David, > > David Kastrup <d...@gnu.org> writes: >> I don't think I need yet another data structure deficient in some >> respects. We have vectors that can't grow, hashtables that can grow but >> only index through a hash function, vlists that can grow but have >> immutable content... > [...] >> Why not just have a superset without arbitrary restriction and implement >> the other structures based on that? Then each one just needs to enforce >> its personal restrictions in its accessor functions, and otherwise just >> use what is there in the general mechanism. > > Simpler data structures can usually be implemented with less memory, > shorter code sequences with fewer conditional branches and less space in > the instruction cache, which in turn means they can be implemented more > efficiently. Therefore, to allow efficient compilation, primitive data > structures should be very simple, with more complex structures built on > simpler ones instead of the other way around. > > For example, consider resizable vectors vs fixed-size vectors. A > fixed-size vector can be represented as a single memory block that > contains both the length and the elements together. A resizable vector > requires an additional level of pointer indirection, which inevitably > means slower accesses and greater code size. Furthermore, fixed-size > vectors allow the possibility of compiling in an unsafe mode where > out-of-bounds checks can be skipped.
I have a really hard time swallowing an efficiency argument for Scheme that is weak enough in comparison with the associated drawbacks not to find consideration in the C++ standard template library. What kind of performance gains are we talking about in a typical vector-heavy application? 0.5%? Scheme is, to some degree, a computer theoretic language. But in this case, this seems to me more like a "don't ask, don't tell" scenario regarding the possibility of using one underlying primitive type that dares to be a trifle more flexible than the theoretically achievable minimum. Scheme implementations have considerable leeway concerning their memory and data layout. -- David Kastrup