Re: Copying string slices before calling subroutines?

[Jeffrey Creem <jeff@thecreems.com>]

Dmitry A. Kazakov wrote:
> On Fri, 04 May 2007 11:44:14 +0200, Jacob Sparre Andersen wrote:
> 
>> Jacob Sparre Andersen wrote:
>>> Dmitry A. Kazakov wrote:
>>>> On Fri, 04 May 2007 08:53:59 +0200, Jacob Sparre Andersen wrote:
>>>>>      for Lines in 1 .. 10 loop
>>>>>         Last := Index (Source  => Text (Text'First .. Last - 1),
>>>> Did you check if GNAT did not copy the string slice before calling to
>>>> Index?
>>> No.  Do you have any suggestion for a way to check it.  The
>>> reference manual (section 6.2) seems to indicate that it is up to
>>> the compiler to decide.
>> I have found a strong indication that GNAT copies the whole string
>> slice onto the stack before calling Index:
> 
> So, Index was innocent.
> 

I don't know that I'd say that...Though it might be innocent in this 
case, a quick look at the source code (which then remaps index to a 
common string search package) looks to me like there are other 
opportunities where some versions of the Index call will make another 
copy in cases when it need not and further this does not appear to match 
the comments in the package.

Specifically, in the trunk of the current FSF Ada in a-strsea.adb at the 
top of the package it says (formatting adjusted on this comment)

--  Note: This code is derived from the ADAR.CSH public domain Ada 83
--  versions of the Appendix C string handling packages (code extracted
--  from Ada.Strings.Fixed). A significant change is that we optimize
--  the case of identity mappings for Count and Index, and also
--  Index_Non_Blank is specialized (rather than using the
--   general Index routine).


Great! Sounds promising...Lets take a look at one of them


  function Index
      (Source  : String;
       Pattern : String;
       Going   : Direction := Forward;
       Mapping : Maps.Character_Mapping := Maps.Identity) return Natural
    is
       Cur_Index     : Natural;
       Mapped_Source : String (Source'Range);

    begin
       if Pattern = "" then
          raise Pattern_Error;
       end if;

       for J in Source'Range loop
          Mapped_Source (J) := Value (Mapping, Source (J));
       end loop;

       --  Forwards case

       if Going = Forward then
          for J in 1 .. Source'Length - Pattern'Length + 1 loop
             Cur_Index := Source'First + J - 1;

             if Pattern = Mapped_Source
                            (Cur_Index .. Cur_Index + Pattern'Length - 1)
             then
                return Cur_Index;
             end if;
          end loop;

       --  Backwards case

       else
          for J in reverse 1 .. Source'Length - Pattern'Length + 1 loop
             Cur_Index := Source'First + J - 1;

             if Pattern = Mapped_Source
                            (Cur_Index .. Cur_Index + Pattern'Length - 1)
             then
                return Cur_Index;
             end if;
          end loop;
       end if;

       --  Fall through if no match found. Note that the loops are skipped
       --  completely in the case of the pattern being longer than the 
source.

       return 0;
    end Index;



Hmm...I don't see the optimization for identity mappings anyplace...



You can probably stop reading here as the formatting is ugly but the 
license for the above code snippet is:


--          Copyright (C) 1992-2005, Free Software Foundation, Inc. 
     --
-- 
     --
-- GNAT is free software;  you can  redistribute it  and/or modify it 
under --
-- terms of the  GNU General Public License as published  by the Free 
Soft- --
-- ware  Foundation;  either version 2,  or (at your option) any later 
ver- --
-- sion.  GNAT is distributed in the hope that it will be useful, but 
WITH- --
-- OUT ANY WARRANTY;  without even the  implied warranty of 
MERCHANTABILITY --
-- or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public 
License --
-- for  more details.  You should have  received  a copy of the GNU 
General --
-- Public License  distributed with GNAT;  see file COPYING.  If not, 
write --
-- to  the  Free Software Foundation,  51  Franklin  Street,  Fifth 
Floor, --
-- Boston, MA 02110-1301, USA. 
     --
-- 
     --
-- As a special exception,  if other files  instantiate  generics from 
this --
-- unit, or you link  this unit with other files  to produce an 
executable, --
-- this  unit  does not  by itself cause  the resulting  executable  to 
  be --
-- covered  by the  GNU  General  Public  License.  This exception does 
not --
-- however invalidate  any other reasons why  the executable file  might 
be --
-- covered by the  GNU Public License. 
     --
-- 
     --
-- GNAT was originally developed  by the GNAT team at  New York 
University. --
-- Extensive contributions were provided by Ada Core Technologies Inc. 
     --