From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,f2690a5e963b61b6 X-Google-Attributes: gid103376,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news3.google.com!news1.google.com!proxad.net!proxad.net!newsfeed.arcor.de!news.arcor.de!not-for-mail Date: Wed, 06 Jul 2005 20:12:46 +0200 From: Georg Bauhaus Organization: future apps GmbH User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.7.8) Gecko/20050513 Debian/1.7.8-1 X-Accept-Language: en MIME-Version: 1.0 Newsgroups: comp.lang.ada Subject: Re: GCC 4.0 Ada.Containers Cursor danger. References: <1120474891.635131.216700@g44g2000cwa.googlegroups.com> <1120575076.876798.108220@g44g2000cwa.googlegroups.com> <1120583470.429264.325450@g43g2000cwa.googlegroups.com> <1120639461.224146.235430@g44g2000cwa.googlegroups.com> <1120642489.101644.74190@o13g2000cwo.googlegroups.com> <1120643138.031761.212450@g43g2000cwa.googlegroups.com> <42cbb52c$0$10807$9b4e6d93@newsread4.arcor-online.net> <1120666922.733581.179180@g47g2000cwa.googlegroups.com> In-Reply-To: <1120666922.733581.179180@g47g2000cwa.googlegroups.com> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Message-ID: <42cc1f0f$0$10808$9b4e6d93@newsread4.arcor-online.net> NNTP-Posting-Date: 06 Jul 2005 20:12:31 MEST NNTP-Posting-Host: f897cf66.newsread4.arcor-online.net X-Trace: DXC=>dI0;f3@n^da1IKbSTkC[i:ejgIfPPlddjW\KbG]kaMhliQbn6H@_Eini6]Q:=P9Ihe`Bh@Z?dZ]MOide X-Complaints-To: abuse@arcor.de Xref: g2news1.google.com comp.lang.ada:11907 Date: 2005-07-06T20:12:31+02:00 List-Id: 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;