Why does "Principled Refactor" improve performance?

[gruhn]

Section "A Principled Refactor" in chapter 6 states that turning:

compose(map(f), map(g))

into

map(compose(f, g))

can improve runtime performance. I understand that I have to loop data sets only once with the second version but mapping each item also became more expensive, right?

I would expect that appling f first for each item and then g for each item is the same as appling both in a single run since: f*n + g*n = (f + g)*n.

So were exactly does the difference come from? Do I actually split runtime in half and if not what is the estimated performance gain? Is this JavaScript specific or universally true? Does it have to do with memory impact of intermediate results or something?

[scole66]

The performance gain comes entirely (if my reasoning is correct) in removing the overhead of map.

"compose" (presumably) adds no overhead; so f*n + g*n = (f + g)*n is definitely a true statement.

But map(f) really costs (f+o) * n (where o is your map overhead).

Which means that compose(map(f), map(g) costs (f+o)*n + (g+o)*n = (f+g)*n + 2o*n

whereas map(compose(f,g)) costs (f+g+o)*n, for a o*n discount over the prior.

[KtorZ]

Note that, this operation is called "map fusion" or "list fusion" and is something that is also usually automagically done by some compilers in FP languages. The overhead in both time and memory of traversing two lists is usually bigger than the cost of the composition. The exact performance gain is sort of hard to give out of any context because it depends on the nature of the function f and g and on the size of the list, but it's usually a good idea to favour composition over repeated traversals.