Re: Extended globbing seems to have become much slower in recent versions of Zsh

[Peter Stephenson <p.stephenson@samsung.com>]

On Fri, 04 Mar 2016 14:22:23 +0100
Jesper Nygårds <jesper.nygards@gmail.com> wrote:
> I don't know if this is relevant, but I have some more findings. I wanted
> to know which sub directory was contributing the most to the amount of time
> taken to process the root directory. I then realized that the sum of the
> time it took to process each sub directory separately was much lower than
> processing the whole root directory at once. In the run below, you can see
> that whilst it takes about 36 seconds to process the root directory, it
> only takes about 13 seconds to process all directories one at a time.
> Furthermore, when I descend into the sub directory taking the longest time
> in the first run, and run all its sub directories in sequence, the sum of
> these sub-sub directories is significantly lower than for the whole sub
> directory. So obviously the processing time is not linear with the number
> of files.

You'd think that would point towards something higher level than the
pattern matching itself, anyway.  Brainstorming [this is a euphemism for
I haven't the first clue what I'm talking about]...

- Memory management associated with multiple directories; could be
allocation or heap management.

- Poor structuring of globbing code meaning it's repeating operations,
i.e. it's not walking trees in a sensible fashion.

- Some auxiliary operation associated with the file tree that's
giving a similar effect to the foregoing (i.e. we walk the tree itself OK
but then repeat some associated operation that should be cached).

- Some form of context switching problem [now it's really getting silly]

Most of these guesses ought to be amenable to tracing through some sort
of profiling suite.  Even some fprintfs to check what directories we've
handled at what point might help.

pws