Re: The Computer Language Shootout Benchmarks

["Matthew Heaney" <mheaney@on2.com>]

Tapio Kelloniemi wrote:
> "Matthew Heaney" <mheaney@on2.com> wrote:
> >And why do you assume that???
>
> Because GNAT.[Dynamic_]HTable has been designed to be extremely efficient.

And why do you assume that Ada.Containers.Hashed_Maps aren't also
designed to be extremely efficient?  Why would the designer do it any
other way?


> Note that this is just an assumption, I have not read the code of GNAT's
> HTable implementation,

If you haven't read the sources, then how do you know?


> but at least GNAT.Dynamic_Tables is more efficient
> than Ada.COntainers.Vectors

But we were talking about Dynamic_Tables vs. Hashed_Maps.


> since it does not use controlled types,

A specious argument, since the only thing controlled types are used for
is to reclaim storage when the scope of the declaration of the
container object ends.  The fact that the hashed_map container type
privately derives from type Controlled has no bearing on the efficiency
of insertions, deletions, or searches.



> it allows
> direct access to the data structure

Again, this is a specious argument, since having access to the
underlying data structure is irrelevant.  It's direct access to an
element that's important.

The standard library provides something very close to direct access: it
allows in situ access to elements via Query_Element and Update_Element.


> and it uses realloc to resize the table.

Well obviously this will only work if the element type isn't
controlled.  So you're comparing apples to oranges, since the standard
containers must support any non-limited type, including controlled type
and discriminated types.


> When Ada.Containers container is resized, new memory must be allocated, data
> must be copied and the old memory must be freed. Realloc may avoid this.

This is all very confused.

In the case of the vector container, then yes, to expand the container
(that is, increase its capacity), then you must allocate a new, longer
internal array (assuming it's implemented that way), and then copy the
existing items onto the new array.

It is specious to argue that "realloc can avoid this," since you can't
use realloc to expand an array whose components are controlled or have
default initialization.  (Or to put it another way, you could use
realloc, but then you'd have to use compiler magic to perform
controlled actions.)

Furthermore, your argument ignores the fact the expansion of the vector
capacity is not done willy-nilly.  Expansion occurs in a specific way,
such that the *amortized* cost of insertion has a time complexity of
O(1).  Hard to beat that!  So the realloc argument is a red herring,
since you can't do any better then O(1).

The situation for hashed containers is a different.  When a hashed
container expands, then elements aren't copied, they are moved.  This
is distinctly unlike the case for vector.

A hashed container has an internal hash table, which is just an array
whose components are pointers to nodes, which hold an element and a
pointer to the next node in that bucket.  When you expand a hashed
container, you allocate a new buckets array, then re-hash elements from
the old buckets array onto the new one.  To be sure there is a cost for
this, but it's not because of copying of elements.

Again, realloc wouldn't help here, since you have to ensure that each
bucket is initialized to null (indicating that there are no elements in
that bucket).


> However, my opinion is that Ada.Containers is much more convenient and also
> safer.

And on that point we agree.

Note that I'm giving a tutorial on the standard container library in
Porto on 5 June.

Regards,
Matt