Adaptive data structures (WAS: Parallelizing)

hbaker@netcom.com (Henry Baker) wrote:
[snip]
>There has been a lot of work on automatically choosing data structures. I
>seem to recall that Jim Low's thesis in the 1970's was on this subject.
>However, instead of building this intelligence into the compiler, it might be
>nice to build this into a 'smart' template capability for C++ (or C+++).


Hm, I hadn't heard about this. I'll look into it. I'm working on a set
of container classes for sequences that have the same semantics but
different performance characteristics. There are classes for forward
linked lists, bidirectional linked lists, and arrays, along with
corresponding classes for their iterators. Insertions, deletions,
random/relative access, etc. can be performed uniformly on objects of
these classes but with different performance characteristics, By
contrast, with the C++ Standard Template Library, the semantics are
tied directly to the representation--one cannot randomly access a
linked list even though every now and then it would be convenient to.
I've thought for some time now that container semantics should be
considered separate from performance. Performance is often a tuning
issue that the programmer can't really understand until a system is
built. Even then, an adaptive data structure might be preferable
over choosing one representation that will always have the same
performance characteristics regardless of the environment within
which it is executed.


It had crossed my mind to further unify these classes. You've given
me something to think about. A container class could have a default
representation and a default heuristic for determining when to modify
or change its representation. (The actual mechanism for changing
representation could be handled any number of ways.) The programmer
could give an initial hint as to how this class will be used. In
addition, the programmer could provide an application-specific
heuristic, for example, in the form of a call-back function or
through inheritance, to override the default heuristic.


BTW, I read a paper a few months ago about why iterators are bad. You
wrote that didn't you? I've found that some programmers use iterators
all over the place while others, like myself, use mapping and
searching mechanisms. I wonder why the dichotomy.


--
Paul Long plong@perf.com http://www.teleport.com/~pciwww/
--

Return to the comp.compilers page.
Search the comp.compilers archives again.