[racket] Performance. Higher-order function

FWIW, the optimization coach confirms both unrollings, and the fact that
neither `build-string1` nor `test1` (you wrote `test2`, was that a
mistake?) are ever inlined.

Reaching out for the decompiler would not have been necessary. :)

Vincent



At Mon, 4 Aug 2014 06:47:34 +0100,
Matthew Flatt wrote:
> 
> Well... a function call is expensive relative to some things, such as
> adding fixnums to produce a fixnum.
> 
> 
> My read of your initial results is that calling an unknown function is
> similar to the cost of one iteration in a loop that sets a character in
> a string.
> 
> More precisely, decompiling the program shows that the compiler unrolls
> the loop in `test1` by 4 iterations, so one call to an unknown function
> is the same cost as 4 generic `<`s on fixnums, 4 generic `+ 1`s on
> fixnums, 4 `integer->char`s, 4 `string-set!s`, and one jump to a known
> function (to recur).
> 
> The `build-string1` loop is similarly unrolled 4 times, and the call to
> `build-string1` is not inlined in `test3`, so we really can compare the
> unknown function call in `test3` to the overall loop overhead plus
> `string-set!`s of `test1`. And the fact that neither `build-string1`
> nor `test2 is inlined is consistent with `test2` and `test3` having the
> same performance.
> 
> If I change the `for` body of `test1` with a constant, then the time is
> cut in half. So, a `string-set!` takes up about half of the time.
> 
> 
> Putting that all together, it looks like a call to an unknown function
> takes about twice the time of a `string-set!` --- which (due to various
> tag and bounds checks for the string assignment) costs the same as a
> small pile of generic arithmetic on fixnums. That could be considered
> expensive in a tight loop.
> 
> I would hesitate to say that higher order functions are always slow,
> because many uses do more work around the call than set one character
> in a string.
> 
> 
> At Mon, 04 Aug 2014 07:42:53 +0400, Roman Klochkov wrote:
> >  > unknown function call is expensive
> > 
> > So, higher order function always slow. 
> > Thus, to improve performance, one should use for/fold, for/list, ... and never 
> > use map, foldl, build-string, ... with lambda.
> > Is it correct?
> > 
> > Sun, 3 Aug 2014 13:15:57 -0400 от Matthias Felleisen <matthias at ccs.neu.edu>:
> > >
> > >Because build-string calls an unknown function 1000 x 100000 times, and an 
> > unknown function call is expensive. 
> > >
> > >Racket could possible collapse all modules and perform additional in-lining 
> > optimizations eventually, which may help here. But it doesn't yet. 
> > >
> > >-- Matthias
> > >
> > >
> > >
> > >On Aug 3, 2014, at 5:15 AM, Roman Klochkov wrote:
> > >>Are higher order function always slow?
> > >>...
> > >>---
> > >>
> > >>So I see, that build-string version is about two times slower, than 
> > set-in-the-loop. Why so much? I expected about 10-20% difference.
> > >>-- 
> > >>Roman Klochkov ____________________
> > >> Racket Users list:
> > >>  http://lists.racket-lang.org/users
> > >
> > 
> > 
> > -- 
> > Roman Klochkov
> > ____________________
> >   Racket Users list:
> >   http://lists.racket-lang.org/users
> 
> ____________________
>   Racket Users list:
>   http://lists.racket-lang.org/users