Idea for optimization (use case: iterate string with index parameter)

Idea for optimization (use case: iterate string with index parameter)

[Sebastian Gniazdowski]

Hello,
iterating string with index parameter is quite slow, because unicode characters are skipped and counted using mbrtowc(). This function takes much CPU time. It is called theta(0.5 * n^2) times when iterating string of length n. The goal is to make this theta(n).

The idea is to avoid calling mbrtowc by holding array of 5-10 structures with:
- pointer to beginning of string
- requested index (request to getarg() / getindex())
- computed in-string pointer for that index (by getarg() / getindex())

In general, the array would hold #N (5-10 or so) last string-index requests. If new request would target the same string, but index greater by 1, getarg() would call mbrtowc() once (via MB_METACHARLEN macro) reusing the previous in-string pointer.

So the idea is to catch not too large loops (using not too many scalar indexing) into the cache. For example, I saw z-sy-h uses such loops, my projects sometimes use them too. The point is that iterating a string and doing something with letters, e.g. counting brackets, is a very common use case, and the optimization would be triggered often.

I'm sharing as maybe there's better way to do this and I'm not sure when I'll get time to write this, and maybe someone has time and energy to do it. It would solve the rather shocking revelation of a typical C programmer, that strings are iterated like lists :)
--  
Sebastian Gniazdowski
psprint /at/ zdharma.org

Re: Idea for optimization (use case: iterate string with index parameter)

[Bart Schaefer]

On Fri, Jan 5, 2018 at 5:38 AM, Sebastian Gniazdowski
<psprint@zdharma.org> wrote:
> iterating string with index parameter is quite slow, because unicode characters are skipped and counted using mbrtowc().

I can't remember the last time I needed to do that kind of iteration.

> For example, I saw z-sy-h uses such loops, my projects sometimes use them too. The point is that iterating a string and doing something with letters, e.g. counting brackets, is a very common use case, and the optimization would be triggered often.

Hmm.  Whether this is worthwhile depends on the size of the typical
processed string.  I can see this affecting z-sy-h when e.g. running
zed on a big function, but probably not when editing a typical command
line.

Maybe it would be reasonable to do something in shell code, e.g.:

typeset -a iter=(${(s//)string})
for ((i=1; i <= $#iter; i++)); do something with $iter[i]; done
string=${(j//)iter} # if needed

That is more memory-intensive, of course, but it also assists with
cases of unordered access into the array of characters.

> In general, the array would hold #N (5-10 or so) last string-index requests. If new request would target the same string, but index greater by 1, getarg() would call mbrtowc() once (via MB_METACHARLEN macro) reusing the previous in-string pointer.

Why only when greater by 1?  If greater, scan to and record the next
needed position.  Same number of mbrtowc() conversions, overall.

Re: Idea for optimization (use case: iterate string with index parameter)

[Sebastian Gniazdowski]

On 5 Jan 2018 at 23:23:57, Bart Schaefer (schaefer@brasslantern.com) wrote:
> On Fri, Jan 5, 2018 at 5:38 AM, Sebastian Gniazdowski
> wrote:
> > iterating string with index parameter is quite slow, because unicode characters are  
> skipped and counted using mbrtowc().
>  
> I can't remember the last time I needed to do that kind of iteration.

Maybe indeed it's not that common. It's one of the basic things one can do with strings but in practice, hmm. I would accumulate that optimization though, as the overall optimization starts to give effects while it's largely composed of disappointing optimizations.

> typeset -a iter=(${(s//)string})
> for ((i=1; i <= $#iter; i++)); do something with $iter[i]; done
> string=${(j//)iter} # if needed
>  
> That is more memory-intensive, of course, but it also assists with
> cases of unordered access into the array of characters.

It might give some effects, I was doing "for letter in $iter" path blindly and missed the obvious $iter[i] way, and without index, "for letter ..." couldn't replace existing code.

> > In general, the array would hold #N (5-10 or so) last string-index requests. If new request  
> would target the same string, but index greater by 1, getarg() would call mbrtowc() once  
> (via MB_METACHARLEN macro) reusing the previous in-string pointer.
>  
> Why only when greater by 1? If greater, scan to and record the next
> needed position. Same number of mbrtowc() conversions, overall.

Yes this should be generalized this way, I didn't want to complicate example.

I recalled yesterday that for ASCII there's a short path that returns 1 and doesn't call mbrtowc() to compute size of character. In discussion on irc this yielded a conclusion that the cache should probably be 1-element only, because it would be an overkill for simple $string[2], etc. indexing. This way the code should be very simple. The params.c part in question is: 

https://github.com/zsh-users/zsh/blob/c2cc8b0fbefc9868fa83537f5b6d90fc1ec438dd/Src/params.c#L1478-L1489

I'm little afraid that getarg() might be called in some generalized situations, but heck it shouldn't be called for a="$b", so the cache might well survive in many typical loops. And maybe a 2-element cache will not add much code and not slow down simple indexing.

--  
Sebastian Gniazdowski
psprint /at/ zdharma.org