One more heap optimization trick for zsh < 5.2

One more heap optimization trick for zsh < 5.2

[Sebastian Gniazdowski]

Hello,
there's this trick that makes the operation faster on zsh < 5.2 (5.2
is optimized):

repeat 1; do
    list=( "${(@M)list:#(#i)*$~search_pattern*}" )
done

I've recently found my system to be less responding to this trick. Not
sure what's happening. I thought that there's maybe an even better way
to change how heap works for given operation? What else could allocate
new heap (what's AFAIK "repeat 1; do" block does)?

Best regards,
Sebastian Gniazdowski

Re: One more heap optimization trick for zsh < 5.2

[Bart Schaefer]

On May 8, 11:34am, Sebastian Gniazdowski wrote:
} Subject: One more heap optimization trick for zsh < 5.2
}
} repeat 1; do
}     list=( "${(@M)list:#(#i)*$~search_pattern*}" )
} done
} 
} I've recently found my system to be less responding to this trick.

Is $list getting larger e.g. you are accumulating more shell history
to be searched or the like?  IIRC the "repeat 1" trick caused a new
heap arena to be pushed instead of searching for free space in an
existing heap, but if $list is large enough to need multiple heap
arenas you may end up right back in the free space hunt.

} I thought that there's maybe an even better way
} to change how heap works for given operation?

If the size of $list is indeed the deciding factor here, I would
suspect that you're now running into heap management during the
pattern match against $~search_pattern, and there's really nothing
at the level of shell coding that can change pattern match behavior.

But all of that is speculation.

Re: One more heap optimization trick for zsh < 5.2

[Sebastian Gniazdowski]

On 8 May 2016 at 18:35, Bart Schaefer <schaefer@brasslantern.com> wrote:
> If the size of $list is indeed the deciding factor here, I would
> suspect that you're now running into heap management during the
> pattern match against $~search_pattern, and there's really nothing
> at the level of shell coding that can change pattern match behavior.

I was testing the same input with 89k lines. The cause now
accidentally clarified. It's about zplugin's shadowing of autoload
function that does the neat trick that allows to copycat what autoload
does:

# declare -f n-list
n-list () {
    --zplg-reload-and-run
/Users/sgniazdowski/.zplugin/plugins/psprint---zsh-navigation-tools ''
n-list "$@"
}

https://github.com/psprint/zplugin/blob/28b615c6d728b22ec87a86026e7a463d731184ae/zplugin.zsh#L273-L287

First run is slow, second is normal and fast:

https://asciinema.org/a/99ercap3i6nri6ybiiayd0ejb

It's hard to describe what *reload-and-run does but you are the author
of this neat trick so I can skip this. How do you think what can be
happening inside Zsh?

Best regards,
Sebastian Gniazdowski

Re: One more heap optimization trick for zsh < 5.2

[Bart Schaefer]

On Mon, May 16, 2016 at 8:01 AM, Sebastian Gniazdowski
<sgniazdowski@gmail.com> wrote:
>
> I was testing the same input with 89k lines. The cause now
> accidentally clarified. It's about zplugin's shadowing of autoload

Are you sure it's the wrapper and not the autoloading?  It's pretty
common for the first run of an autoloaded function to be slower than
subsequent runs.

> It's hard to describe what *reload-and-run does

It temporarily alters FPATH when invoking an autoloaded function so
that the function is found in / loaded from a particular location.

> How do you think what can be
> happening inside Zsh?

Other than the normal autoloading stuff, nothing I can think of.  Is
the value of FPATH becoming especially large?  Could the slowdown be
external to zsh, e.g., opening/reading of directories in the fpath
search slower?

Re: One more heap optimization trick for zsh < 5.2

[Sebastian Gniazdowski]

[-- Attachment #1: Type: text/plain, Size: 1813 bytes --]

On 17 May 2016 at 12:18, Bart Schaefer <schaefer@brasslantern.com> wrote:
> On Mon, May 16, 2016 at 8:01 AM, Sebastian Gniazdowski
> <sgniazdowski@gmail.com> wrote:
>>
>> I was testing the same input with 89k lines. The cause now
>> accidentally clarified. It's about zplugin's shadowing of autoload
>
> Are you sure it's the wrapper and not the autoloading?  It's pretty
> common for the first run of an autoloaded function to be slower than
> subsequent runs.

I tested with zplugin and without it, and slow down occurs in first
case. Also, I wanted to move a normal function outside a file to make
it autoloaded function. It started to be painfully slow when used with
zplugin. Luckily I can optimize for 5.1 and use normal hand-made
"autoload -X" body instead of the wrapper. So zplugin's future is in
general safe.

Tried to construct synthetic test (attached). In general the results
are inconsistent. Their order changes depending even on given run.
Could came up with following alerting times:

# ./aload2.zsh.txt
More special autoload:
( aload_fun; )  3,68s user 0,18s system 98% cpu 3,909 total
Special autoload:
( aload_fun; )  3,08s user 0,18s system 99% cpu 3,277 total
Normal autoload:
( aload_fun; )  3,83s user 0,18s system 99% cpu 4,026 total

# ./aload2.zsh.txt
More special autoload:
( aload_fun; )  2,90s user 0,19s system 99% cpu 3,115 total
Special autoload:
( aload_fun; )  3,24s user 0,18s system 99% cpu 3,436 total
Normal autoload:
( aload_fun; )  3,62s user 0,18s system 99% cpu 3,812 total

# ./aload2.zsh.txt
More special autoload:
( aload_fun; )  2,86s user 0,18s system 99% cpu 3,050 total
Special autoload:
( aload_fun; )  3,22s user 0,18s system 99% cpu 3,402 total
Normal autoload:
( aload_fun; )  3,94s user 0,19s system 99% cpu 4,148 total

Best regards,
Sebastian Gniazdowski

[-- Attachment #2: aload2.zsh.txt --]
[-- Type: text/plain, Size: 927 bytes --]

#!/bin/zsh

emulate -LR zsh

--reload-and-run () {
    local fpath_prefix="$1" autoload_opts="$2" func="$3"
    shift 3
    unfunction "$func"
    local FPATH="$fpath_prefix":"${FPATH}"
    builtin autoload $=autoload_opts "$func"
    "$func" "$@"
}

fbody='#!/bin/zsh
str=""
str=${(r:100000::_:)str};
arr=( "${(@s::)str}" )
repeat 100; do
    arr2=( "${(@M)arr:#(#a1)_}" )
done

#print -rl "${arr2[@]}"
'

echo "$fbody" > aload_fun
#chmod +x aload_fun

# More special autoload
PLUGIN_DIR=`pwd`
eval "
function aload_fun {
    --reload-and-run ${(q)PLUGIN_DIR} '' aload_fun
}
"
echo "More special autoload:"
time ( aload_fun )
unfunction aload_fun

# Special autoload
eval "
function aload_fun {
    local FPATH=$FPATH:`pwd`
    autoload -X
}
"
echo "Special autoload:"
time ( aload_fun )
unfunction aload_fun

# Normal autoload
FPATH+=:`pwd`
autoload aload_fun
echo "Normal autoload:"
time ( aload_fun )
unfunction aload_fun

Re: One more heap optimization trick for zsh < 5.2

[Bart Schaefer]

On May 16,  5:01pm, Sebastian Gniazdowski wrote:
} Subject: Re: One more heap optimization trick for zsh < 5.2
}
} I was testing the same input with 89k lines. The cause now
} accidentally clarified. It's about zplugin's shadowing of autoload

I was writing this off until I noticed that it's not just that the
first n-list takes a long time to begin, but that every motion in
the zcurses display takes a long time to update the viewport.

This means that it has to be something that's happening in the loop
inside the n-list function, affecting every iteration.

Consequently it must be one of n-list-input or n-list-draw, both of
which are declared with [the shadowed] autoload inside n-list itself.
Something about nesting calls to --zplg-reload-and-run is causing
the issue.  It might have something to do with retaining the old copy
of the function body until the call stack unwinds and it can safely
be freed; a large value for $argv would therefore also hang around
(two copies of it) for all of that time.

Incidentally, the way n-list is currently written, it will re-autoload
those functions and re-create all the _nlist_* helpers EVERY TIME IT
IS RUN.  Mostly that's all of no net effect, but it must be slowing
down each call to n-list at least a little bit.

Anyway, once n-list has run at least once, n-list-draw and n-list-input
are fully defined without --zplg-reload-and-run, so the slowdown during
the loop goes away.  I still don't know exactly *why* this would make
any difference, but a zprof pass *might* reveal something useful.

Re: One more heap optimization trick for zsh < 5.2

[Sebastian Gniazdowski]

[-- Attachment #1: Type: text/plain, Size: 2686 bytes --]

On 11 June 2016 at 05:30, Bart Schaefer <schaefer@brasslantern.com> wrote:
> This means that it has to be something that's happening in the loop
> inside the n-list function, affecting every iteration.

Agree

> Consequently it must be one of n-list-input or n-list-draw, both of
> which are declared with [the shadowed] autoload inside n-list itself.
> Something about nesting calls to --zplg-reload-and-run is causing
> the issue.

Hmm didn't thought about that, about nesting

> It might have something to do with retaining the old copy
> of the function body until the call stack unwinds and it can safely
> be freed; a large value for $argv would therefore also hang around
> (two copies of it) for all of that time.

That's apparently a hit. I attach two test files. First doesn't pass
anything to sub-function:

# ./aload.zsh2.txt
Normal autoload:
( aload_fun_main; )  10,91s user 0,23s system 99% cpu 11,156 total
Special autoload:
( aload_fun_main; )  9,54s user 0,23s system 99% cpu 9,792 total
More special autoload:
( aload_fun_main; )  9,15s user 0,22s system 99% cpu 9,393 total

# ./aload.zsh2.txt
Normal autoload:
( aload_fun_main; )  8,85s user 0,22s system 99% cpu 9,103 total
Special autoload:
( aload_fun_main; )  8,15s user 0,23s system 99% cpu 8,405 total
More special autoload:
( aload_fun_main; )  9,36s user 0,22s system 99% cpu 9,596 total

# ./aload.zsh2.txt
Normal autoload:
( aload_fun_main; )  10,22s user 0,22s system 99% cpu 10,454 total
Special autoload:
( aload_fun_main; )  9,73s user 0,22s system 99% cpu 9,971 total
More special autoload:
( aload_fun_main; )  8,02s user 0,22s system 99% cpu 8,262 total

(I wonder why the varying). Second one passes long array to sub-function:

# ./aload.zsh3.txt
Normal autoload:
( aload_fun_main; )  11,58s user 0,25s system 99% cpu 11,847 total
Special autoload:
( aload_fun_main; )  10,77s user 0,25s system 99% cpu 11,042 total
More special autoload:
( aload_fun_main; )  18,38s user 0,27s system 99% cpu 18,679 total

# ./aload.zsh3.txt
Normal autoload:
( aload_fun_main; )  10,99s user 0,25s system 99% cpu 11,270 total
Special autoload:
( aload_fun_main; )  10,71s user 0,26s system 99% cpu 10,984 total
More special autoload:
( aload_fun_main; )  19,02s user 0,28s system 99% cpu 19,329 total

> Incidentally, the way n-list is currently written, it will re-autoload
> those functions and re-create all the _nlist_* helpers EVERY TIME IT
> IS RUN.  Mostly that's all of no net effect, but it must be slowing
> down each call to n-list at least a little bit.

I have a check if the function exists and don't do autoload, like the
real autoload function does afaik.

-- 
Best regards,
Sebastian Gniazdowski

[-- Attachment #2: aload.zsh3.txt --]
[-- Type: text/plain, Size: 1330 bytes --]

#!/bin/zsh

emulate -LR zsh

--reload-and-run () {
    local fpath_prefix="$1" autoload_opts="$2" func="$3"
    shift 3
    unfunction "$func"
    local FPATH="$fpath_prefix":"${FPATH}"
    builtin autoload $=autoload_opts "$func"
    "$func" "$@"
}

fbody1='#!/bin/zsh
str=""
str=${(r:100000::_:)str};
arr=( "${(@s::)str}" )
repeat 10; do
    aload_fun "${arr[@]}"
done
'

fbody2='#!/bin/zsh
str=""
str=${(r:100000::_:)str};
arr=( "${(@s::)str}" )
repeat 10; do
    arr2=( "${(@M)arr:#(#a1)_}" )
done
'

echo "$fbody1" > aload_fun_main
echo "$fbody2" > aload_fun

# Normal autoload
FPATH+=:`pwd`
autoload aload_fun_main
autoload aload_fun
echo "Normal autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun

# Special autoload
eval "
function aload_fun_main {
    local FPATH=$FPATH:`pwd`
    autoload -X
}
"
eval "
function aload_fun {
    local FPATH=$FPATH:`pwd`
    autoload -X
}
"
echo "Special autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun

# More special autoload
PLUGIN_DIR=`pwd`
eval "
function aload_fun_main {
    --reload-and-run ${(q)PLUGIN_DIR} '' aload_fun_main
}
"
eval "
function aload_fun {
    --reload-and-run ${(q)PLUGIN_DIR} '' aload_fun
}
"
echo "More special autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun


[-- Attachment #3: aload.zsh2.txt --]
[-- Type: text/plain, Size: 1368 bytes --]

#!/bin/zsh

emulate -LR zsh

--reload-and-run () {
    local fpath_prefix="$1" autoload_opts="$2" func="$3"
    shift 3
    unfunction "$func"
    local FPATH="$fpath_prefix":"${FPATH}"
    builtin autoload $=autoload_opts "$func"
    "$func" "$@"
}

fbody1='#!/bin/zsh
str=""
str=${(r:100000::_:)str};
arr=( "${(@s::)str}" )
repeat 10; do
    aload_fun
done

#print -rl "${arr2[@]}"
'

fbody2='#!/bin/zsh
str=""
str=${(r:100000::_:)str};
arr=( "${(@s::)str}" )
repeat 10; do
    arr2=( "${(@M)arr:#(#a1)_}" )
done

#print -rl "${arr2[@]}"
'

echo "$fbody1" > aload_fun_main
echo "$fbody2" > aload_fun

# Normal autoload
FPATH+=:`pwd`
autoload aload_fun_main
autoload aload_fun
echo "Normal autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun

# Special autoload
eval "
function aload_fun_main {
    local FPATH=$FPATH:`pwd`
    autoload -X
}
"
eval "
function aload_fun {
    local FPATH=$FPATH:`pwd`
    autoload -X
}
"
echo "Special autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun

# More special autoload
PLUGIN_DIR=`pwd`
eval "
function aload_fun_main {
    --reload-and-run ${(q)PLUGIN_DIR} '' aload_fun_main
}
"
eval "
function aload_fun {
    --reload-and-run ${(q)PLUGIN_DIR} '' aload_fun
}
"
echo "More special autoload:"
time ( aload_fun_main )
unfunction aload_fun_main
unfunction aload_fun

Re: One more heap optimization trick for zsh < 5.2

[Sebastian Gniazdowski]

Tried to do:
    repeat 1; do
        "$func" "$@"
    done

in --reload-and-run(), instead of simply calling $func, but no use..

Best regards,
Sebastian Gniazdowski

Re: One more heap optimization trick for zsh < 5.2

[Bart Schaefer]

On Jun 11,  9:40am, Sebastian Gniazdowski wrote:
}
} > It might have something to do with retaining the old copy
} > of the function body until the call stack unwinds and it can safely
} > be freed; a large value for $argv would therefore also hang around
} > (two copies of it) for all of that time.
} 
} That's apparently a hit. I attach two test files.

I modified one of the tests to simply print $funcstack in each of the
possible function calls on one pass (repeat 1).  That yields:

Normal autoload:
aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt
aload_fun aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt

Special autoload:
aload_fun_main (eval) aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt
aload_fun (eval) aload_fun aload_fun_main (eval) aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt

More special autoload:
--reload-and-run aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt
aload_fun_main --reload-and-run aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt
--reload-and-run aload_fun aload_fun_main --reload-and-run aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt
aload_fun --reload-and-run aload_fun aload_fun_main --reload-and-run aload_fun_main /home/schaefer/Mail/detach.dir/aload.zsh2.txt


So the "more special" version makes twice as many function calls as the
"special" one, and both of the latter have deeper call stacks than the
"normal" one.  From your timings, "more special" takes about twice as
long as either, which sort of makes sense given double the number of
calls.

However, that doesn't explain why it remains slow in the n-list loop. I
again changed aload_fun_main (fbody1) to use "repeat 2" and it does not
show any extra call stack depth on the second pass, so it's not that it
is e.g. somehow finding the "wrong" aload_fun body.