Re: GCC 4.0 Ada.Containers Cursor danger.

[Georg Bauhaus <bauhaus@futureapps.de>]

Dmitriy Anisimkov wrote:

(I can't tell for sure whether you are responding to my message because your
answer doesn't provide context, but after guessing and inspecting
message headers, I think you are responding to my post?)

> Maybe i do not good understand the meaning of "versatility", but I was
> able fast to do whatever i want whithout cursors under ADT.

You keep saying, "Mine was fast!" and you don't tell us how
fast compared to what. How can repeated hashing be as fast as
direct access via a cursor? How can a linear search be as fast as
direct access via a cursor?  Fast enough for you is very different
from being fast enough for an application that expects O(1) or
O(N log N) with a suitable factor.

As has been said, there is a performance cost if
you don't use cursors and use, for example, copying.
There is a performance cost if a library forces its user to
repeatedly look up a key by recomputing slots each time, for example.

There is a different cost if checking is done everywhere.


Or consider (I'm picking up your linked list example)

   while
     my_pointer_from_node_to_node /=  find_sentinel_node(container)
   loop
      mess_around_with_elements;
      update(my_pointer_from_node_to_node);
   end loop;

This is a place where there is a performance issue.
For "normal" algorithms, a recommendation might be to find the sentinel
node just once.

declare
   stop_here: Some_Node_Type := find_sentinel_node(container);
begin
   while
     my_pointer_from_node_to_node /= stop_here
   loop
      mess_around_with_elements;
      update(my_pointer_from_node_to_node);
   end loop;
end;

Can you assume that the sentinel node found before the first
iteration remains valid when you mess around with the elements inside
the loop?  No.

So you say we need a safe container and we need the first
formulation of the loop, not the second, which is likely faster.

However, even if find_sentinel_node(container) finds a valid
node each time, how do we know whether mess_around_with_elements
will do no harm? So we should have checking in each and every place,
you say? And you say that there is no significant cost if we
check every use of an element? No cost if a library allows
only recomputed searches for the very same element, no caching
via cursors?

But why do we mess_around_with_elements in the first place?


> If you could show me the code where you think cursors is fastest, i
> could try to provide example with same functionality without cursors
> with the same or better speed.

I though we were talking
about using keys for lookup or using cursors for lookup. Here is
a silly example using Cursors (which of course can be programmed
differently, e.g. not using Containers at all etc. but this is beside
the point). I don't think that *using* *lookup* *by* *key* will
be faster than direct access via Cursor.  See the case statement.



with Ada.Calendar;
with String_Maps;
  -- String values associated with Time values

procedure Silly is

   use Ada.Calendar;

   type Request_From_Somewhere is (On, Off);
   procedure read(r: out Request_From_Somewhere; t: out Time) is separate;

   request: Request_From_Somewhere;

   box: String_Maps.Map;
   now: Time;
   zero: constant Time := Clock;

   here, there: String_Maps.Cursor;
   yes: Boolean;

begin
   -- insert the two elements, assigning Cursors on the way:

   String_Maps.Insert(box, "one", zero, here, yes);
   String_Maps.Insert(box, "another", zero, there, yes);

   loop
      -- read a request, and depending on the requested value,
      read(request, now);

      -- swap the values stored with "one" and "another".
      case request is
         when On =>
            String_Maps.replace_element(here, now);
            String_Maps.replace_element(there, zero);
         when Off =>
            String_Maps.replace_element(here, zero);
            String_Maps.replace_element(there, now);
      end case;
   end loop;

end Silly;