Re: S-expression I/O in Ada

[Georg Bauhaus <rm.dash-bauhaus@futureapps.de>]

On 18.08.10 15:24, Natasha Kerensikova wrote:

> There is probably a difference in complexity for all operations, but
> they are not specified, and generally not predictable.

Complexity is, in fact, specified, in Implementation Advice,
which is generally trustworthy. It is written by implementers,
and complexity has been part of the design of the containers.
Predictability is quite important, I assume it will be even
more important with the new bounded forms of the containers,
to be used in computers with limits on memory, and where
timing matters much, hence predictable performance of
container operations is required.
(They may not be a good choice for storing arbitrarily sized
S_Expressions, but illustrate the point: different complexities
are one important criterion for choosing among the containers.)

> But these are pretty small and platform-specific details, I believe it's
> way too early in my project to care about them.

A Yes to ignoring container differences for one reason,
and a No for one and a half reasons, IMO:

Yes-1. It is certainly o.K. to not think about the specific
  container for an application if both meet the needs---from
  an abstract point of view.  In fact, the adapter patterns
  of template libraries can be interpreted to be a manifestation
  of this view, I think.

No-1. The differences in execution can be significant, even
   from a feasibility point of view.  O(log N) versus
   O(1) or O(N log N) can matter much, sometimes preventing
   choice of an otherwise convenient container; the LRM has advice
   (limits, actually) as to which complexity bounds a specific
   container's operations must not exceed.
   (I fail to see why Ada.Containers are platform-specific?
   (Insofar as the complexity measures are not given WRT some
    computer architecture.))

   An example is a filter that must process loads of
   different data items coming in quickly trough some wire.
   A Set can be used to see whether an item is good
   or bad: generate a key from an item and perform look-up.
   A List or Vector can be used, too. But, if many keys are
   possible, Sets can be searched sufficiently faster
   than searching a list or vector for the key. The latter
   might actually be so slow that the program cannot process
   enough items per second.

   The filter program will exclude the use of any container
   but Map or Set, then.

No-1.5. At some point, memory consumption or sufficient
   speed might matter: I cannot, of course, tell but users
   of S_Expression might have rather large expressions
   or need to manipulate them in rather small memories.
   Operations related to S_Expression may need to be fast
   enough, etc.

The good news is in the common set of container operations:
One can indeed switch containers fairly easily when a
change is needed because of changing requirements, or because
of new requirements. If you can start your implementation with
a small subset of operations, lists seems fine, then.


Georg