Re: Fwd: curious...

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Please keep replies on the list, so that other developers may chime in.

According to Kyle Sallee on 10/20/2006 11:53 PM:
> On 10/20/06, Eric Blake <address@hidden> wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> According to Kyle Sallee on 10/20/2006 4:48 PM:
>>
>> Thanks for your concerns.  Yes, libtool developers are aware of the pain
>> of slow scripts, and have made efforts recently to speed things up, but
>> there are still lurking corners that could use improvements.  One speed
>> factor comes if you use bash 3.1 or newer, where libtool takes advantage
>> of the new += assignment operator to make variable concatenation faster
>> than the quadratic behavior of older shells.
> 
> Excellent.
> I only used += for (( numeric )) assignments and not strings.
> Thanks for the tip.
> 
> Too bad that technique is not backward compatible with /bin/sh
> libtool is a /bin/sh script?

Libtool is a sh script, but at ./configure time, it hunts for a better
shell than /bin/sh if one is available.  In other words, if your copy of
bash is easy to find and is faster than /bin/sh, libtool will favor your bash.

> 
>> > Is it out of the question to keep lists separated by line feeds
>> > instead of spaces and then use the sort and uniq instead
>> > of case statements?
>>
>> Yes - invoking external processes is noticeably slower than keeping
>> execution limited within shell builtins.
> 
> I agree that is true in some instances.

On some platforms, such as cygwin, where you can only fork about 100 times
per second, it is true in ALL instances.  Sticking to shell builtins IS
faster, unless the shell has buggy algorithms.

> Handling a 5 iterration loop with case statements and
> that reassignment is do-able quickly by without using coreutils.
> But with the way libtool worked during koffice
> compilation I conjecture that about half the
> CPU time was spent running libtool scripts.
> 
> What about this...
> 
> Instead of building two arrays at once just build one at a time
> And only make one assignment...  An assignment on the outside.
> 
> deps="$(  for something in $somethings; do
>    case  something in
>     particuliar) echo "$something"  ;;
>    esac
>  done
> )"
> 
> So that the really large string is built inside a subshell.
> That way it is not like:
> 
> for  something in $somethings; do
>  case  something in
>    particuliar) deps="$something $deps"  ;;
>  esac
> done
> 
> So in this scenario we do not resort to the extra invocations
> of sort and uniq which can be costly when working on very small lists.
> We use instead just one subshell.
> Yes creating the subshell costs a little bit in time,
> but it more than paid for in contrast to snowballing a string variable.
> 
> And if you want to keep it on a line then it can do something like
> echo -n
> inside case statement
> and after the for loop completes do an
> echo
> to add the finishing line feed.
> 
> Ah, wait, if each echo uses an external echo command
> rather than a builtin then this suggestion would be the slowest.

Indeed - which is why the libtool development team was the one that
reported to the bash developer that bash 3.0 that snowballing variables,
which led to the introduction of bash 3.1's += operator, which led to
current libtool using += in places when it knows it is available.  It is
now just a question of finding all the places where += should be used.

> 
> 
> I am not complaining.
> I am merely presupposing that it is possibile,
> but have not put it to the test.
> If it is not being done already then there is probably
> a good reason for it, like someone tried it and it did
> not work or broke /bin/sh compatibility?
> 
> If there is no short answer such as...
> "It did not work for reason X,"
> then I may be tempted to give it a try.
> But if the CPU cycles are unavoidable
> then I will have to accept that the libtool
> script will take more CPU cycles to run than the linker.
> 
> 
>> > And for the for loop inside, perhaps that could be done
>> > with utilities?
>> >
>> > specialdeplibs="$( echo "$deplibs" | tr ' ' '\n' | sort | uniq -d )"
>> > libs="$( echo "$deplibs" | tr ' ' '\n' | sort -u )"
>>
>> This is actually slower on platforms with noticeable fork penalties.
> 
> Yes I realize subshells and pipes and new processes can be expensive.
> When dealing with data in pipes it can be a good idea
> to send as much through at a time as possibile.
> 
> However, it would be a wise idea to know when to use algorithims
> with looped case statements snowballing variables and when
> to use algorithims involving subshells and coreutils.
> As I pointed out the amount of data being handled effects
> that difference and as you pointed out the platform effects
> how costly those fork penalities are.
> However, both can be determined, yes?
> The platform can be known and given a value.
> And the length of the variables handled can be counted.
> And those two numbers can be multipled together to give a value.
> If that value is above a certain number then perhaps algorithims
> using subshells and forks are a faster choice to use
> than snowballing a variable?
> 
>> $() is out of the question - it is not portable.  Using `` is the same
>> speed as $() (both versions invoke a subshell), just slightly different
>> syntax.
> 
> So there are no instances where like
> $( something $( particuliar ) )
> nested?

Libtool does not use $().  It is not portable to all /bin/sh in current
use.  It uses `` instead.

> I do not recall the method for nesting backticks.
> But it probably would not be necessary or maybe
> not even desirable with libtool?
> 
>> > Would you like me to hack a little on libtool just to
>> > increase it's execution speed or are such changes
>> > trivial to accomplish now that I mentioned it?
>>
>> You would not be the first to be making such contributions, and if your
>> copyright assignment is in place, your contributions would certainly be
>> appreciated.
> 
> Then, perhaps I shall get a fresh look at it from cvs/svn.
> About the copyright assignment being in place
> what documentation do you recommend I follow, please,
> because if I had in mind some changes I probably would
> just upload a gzip compressed diff -r -U2 to the list,
> but that may not be the desired method?
> 

Read http://www.gnu.org/software/libtool/contribute.html.

- --
Life is short - so eat dessert first!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFFOhRv84KuGfSFAYARAu6aAKDPgnNIsMFgQv769WccNJL7QOh5WgCgmfEZ
wdfKeTPNfpoc4saUgW2Tx2s=
=zpcD
-----END PGP SIGNATURE-----