4 ms·

> a.map(g).map(f) ≣ a.map(x => f(g(x))) > But the one on the left will be slower and use a lot more memory. Is it really true? I mean, GC will clean the inter

> a.map(g).map(f) ≣ a.map(x => f(g(x))) > But the one on the left will be slower and use a lot more memory. Is it really true? I mean, GC will clean the intermediate array, won't it? And the speed won't be significantly slower. It's still linear complexity anyway.

tomkwong 7y ago
Imagine that the size of the intermediate array is half of your computer's memory. It matters because by composition it reduces the memory footprint from 2x to 1x.
- privethedge 7y ago
  Then it is 8Gb of pointers. I doubt it's practical to worry about such extreme cases.
tom_mellior 7y ago
Dragging a large data structure through the cache only once rather than twice can be beneficial. Also, GC will clean the intermediate array, but (depending on the specifics of the language and the data types involved) it might first have to make yet another scan through the data structure. So yes, it's linear, but possibly 2-3x slower.
- privethedge 7y ago
  Then why do I have the following results? const a = [...Array(1000000).keys()]; const m = 8; let leftAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(Math.tan).map(Math.sin); const t1 = performance.now(); leftAvg += (t1 - t0)/m; } let rightAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(x => Math.sin(Math.tan(x))); const t1 = performance.now(); rightAvg += (t1 - t0)/m; } console.log(leftAvg, rightAvg, leftAvg/rightAvg); // JS Firefox 70: 264 360.75 0.7318087318087318 var a = Enumerable.Range(0, 10000000).Select(x => (double)x).ToArray(); double[] xs1 = null; double[] xs2 = null; var m = 16; var leftAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs1 = a.Select(Math.Tan).ToArray().Select(Math.Sin).ToArray(); watch.Stop(); leftAvg += (double)watch.ElapsedMilliseconds / m; } var rightAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs2 = a.Select(x => Math.Sin(Math.Tan(x))).ToArray(); watch.Stop(); rightAvg += (double)watch.ElapsedMilliseconds / m; } Console.WriteLine($"{leftAvg} {rightAvg} {leftAvg / rightAvg}"); // C# Results: 505.75 602.25 0.839767538397675
  - tom_mellior 7y ago
    Hard to tell without more information, and probably more runs. Did the code run often enough for the JIT compiler to warm up sufficiently? If you're running in interpreted mode, or only baseline compiled mode, you have other overheads. Also, and this is admittedly something I should not have glossed over: The reading and writing costs of fused maps might be sped up by the factors I mentioned, but in your loops you also have allocations, which have their own costs and can complicate things. And the computation is not free either, though at sufficiently large sizes the memory accesses should dominate sind and tan, I think. It also matters how this code is compiled exactly. The C# version (I know nothing about C# or how good its compiler is) looks like it must first allocate some kind of dynamic stream, and only when ToArray() is called can it allocate the final array, so there might be extra copying. Maybe the compiler is smart enough to optimize a sequence of arr.Select().ToArray() to allocate a target array of the size of arr right away, I don't know. Also, the JavaScript version uses a smaller array than the C# version, is that on purpose? 1000000 unboxed doubles are only 8 MB, which is not very big: On the machine I'm typing this on, L3 cache is 6 MB. My advice would be to run the JavaScript version many times, for many more than 8 iterations, and with sizes increasing stepwise up to a GB or so. Also try replacing the maps with preallocated arrays and hand-written loops that contain only the computations, not the allocations. I know this sounds like I'm trying to give you homework, which I'm not, but benchmarking is hard, and there are many factors to take into account.
    - tom_mellior 7y ago
      > And the computation is not free either, though at sufficiently large sizes the memory accesses should dominate sind and tan, I think. Looks like I was wrong about this! You might want to retry your experiments with cheaper operations than sin and tan. I wrote a little C benchmark to test this more: #include <stdio.h> #include <time.h> #include <math.h> extern void sinTanSeparate(double *a, double *b, int n) { for (int i = 0; i < n; i++) { b[i] = tan(a[i]); } for (int i = 0; i < n; i++) { b[i] = sin(b[i]); } } extern void sinTanFused(double *a, double *b, int n) { for (int i = 0; i < n; i++) { b[i] = sin(tan(a[i])); } } #define N (128 * 1024 * 1024) #define RUNS 5 double a[N]; double b[N]; int main(void) { clock_t start, end; printf("will do %d runs over %zu MB of data\n\n", RUNS, sizeof a / (1024 * 1024)); for (int i = 0; i < RUNS; i++) { start = clock(); sinTanSeparate(a, b, N); end = clock(); printf("separate: %f sec\n", ((double) end - start) / CLOCKS_PER_SEC); } printf("\n"); for (int i = 0; i < RUNS; i++) { start = clock(); sinTanFused(a, b, N); end = clock(); printf("fused: %f sec\n", ((double) end - start) / CLOCKS_PER_SEC); } return 0; } Compiling this with gcc -O3 gives: will do 5 runs over 1024 MB of data separate: 1.461349 sec separate: 1.020120 sec separate: 1.019002 sec separate: 1.019888 sec separate: 1.018454 sec fused: 1.014774 sec fused: 1.014724 sec fused: 1.013895 sec fused: 1.016440 sec fused: 1.013729 sec So almost no difference, though with enough runs I think this would be significant. Interestingly, although C is not JIT compiled, even here there is a "warmup" effect. I guess these are initial page faults or something. But if we now comment out <math.h> and instead use some cheap "fake" implementations of in and tan: // #include <math.h> #define tan(x) (x + 1) #define sin(x) (x + 2) we get very different behavior: will do 5 runs over 1024 MB of data separate: 0.548558 sec separate: 0.154741 sec separate: 0.151271 sec separate: 0.150542 sec separate: 0.151337 sec fused: 0.078880 sec fused: 0.074742 sec fused: 0.078313 sec fused: 0.076987 sec fused: 0.077729 sec Here the computation is so cheap that it's really other effects that dominate, and you get a 2x difference.

tomkwong 7y ago

Imagine that the size of the intermediate array is half of your computer's memory. It matters because by composition it reduces the memory footprint from 2x to 1x.

privethedge 7y ago
Then it is 8Gb of pointers. I doubt it's practical to worry about such extreme cases.

tom_mellior 7y ago

Dragging a large data structure through the cache only once rather than twice can be beneficial. Also, GC will clean the intermediate array, but (depending on the specifics of the language and the data types involved) it might first have to make yet another scan through the data structure. So yes, it's linear, but possibly 2-3x slower.

privethedge 7y ago
Then why do I have the following results? const a = [...Array(1000000).keys()]; const m = 8; let leftAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(Math.tan).map(Math.sin); const t1 = performance.now(); leftAvg += (t1 - t0)/m; } let rightAvg = .0; for(let _ of Array(m)) { const t0 = performance.now(); a.map(x => Math.sin(Math.tan(x))); const t1 = performance.now(); rightAvg += (t1 - t0)/m; } console.log(leftAvg, rightAvg, leftAvg/rightAvg); // JS Firefox 70: 264 360.75 0.7318087318087318 var a = Enumerable.Range(0, 10000000).Select(x => (double)x).ToArray(); double[] xs1 = null; double[] xs2 = null; var m = 16; var leftAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs1 = a.Select(Math.Tan).ToArray().Select(Math.Sin).ToArray(); watch.Stop(); leftAvg += (double)watch.ElapsedMilliseconds / m; } var rightAvg = .0; foreach (var _ in Enumerable.Range(0, m)) { var watch = System.Diagnostics.Stopwatch.StartNew(); xs2 = a.Select(x => Math.Sin(Math.Tan(x))).ToArray(); watch.Stop(); rightAvg += (double)watch.ElapsedMilliseconds / m; } Console.WriteLine($"{leftAvg} {rightAvg} {leftAvg / rightAvg}"); // C# Results: 505.75 602.25 0.839767538397675
- tom_mellior 7y ago
  Hard to tell without more information, and probably more runs. Did the code run often enough for the JIT compiler to warm up sufficiently? If you're running in interpreted mode, or only baseline compiled mode, you have other overheads. Also, and this is admittedly something I should not have glossed over: The reading and writing costs of fused maps might be sped up by the factors I mentioned, but in your loops you also have allocations, which have their own costs and can complicate things. And the computation is not free either, though at sufficiently large sizes the memory accesses should dominate sind and tan, I think. It also matters how this code is compiled exactly. The C# version (I know nothing about C# or how good its compiler is) looks like it must first allocate some kind of dynamic stream, and only when ToArray() is called can it allocate the final array, so there might be extra copying. Maybe the compiler is smart enough to optimize a sequence of arr.Select().ToArray() to allocate a target array of the size of arr right away, I don't know. Also, the JavaScript version uses a smaller array than the C# version, is that on purpose? 1000000 unboxed doubles are only 8 MB, which is not very big: On the machine I'm typing this on, L3 cache is 6 MB. My advice would be to run the JavaScript version many times, for many more than 8 iterations, and with sizes increasing stepwise up to a GB or so. Also try replacing the maps with preallocated arrays and hand-written loops that contain only the computations, not the allocations. I know this sounds like I'm trying to give you homework, which I'm not, but benchmarking is hard, and there are many factors to take into account.
  - tom_mellior 7y ago
    > And the computation is not free either, though at sufficiently large sizes the memory accesses should dominate sind and tan, I think. Looks like I was wrong about this! You might want to retry your experiments with cheaper operations than sin and tan. I wrote a little C benchmark to test this more: #include <stdio.h> #include <time.h> #include <math.h> extern void sinTanSeparate(double *a, double *b, int n) { for (int i = 0; i < n; i++) { b[i] = tan(a[i]); } for (int i = 0; i < n; i++) { b[i] = sin(b[i]); } } extern void sinTanFused(double *a, double *b, int n) { for (int i = 0; i < n; i++) { b[i] = sin(tan(a[i])); } } #define N (128 * 1024 * 1024) #define RUNS 5 double a[N]; double b[N]; int main(void) { clock_t start, end; printf("will do %d runs over %zu MB of data\n\n", RUNS, sizeof a / (1024 * 1024)); for (int i = 0; i < RUNS; i++) { start = clock(); sinTanSeparate(a, b, N); end = clock(); printf("separate: %f sec\n", ((double) end - start) / CLOCKS_PER_SEC); } printf("\n"); for (int i = 0; i < RUNS; i++) { start = clock(); sinTanFused(a, b, N); end = clock(); printf("fused: %f sec\n", ((double) end - start) / CLOCKS_PER_SEC); } return 0; } Compiling this with gcc -O3 gives: will do 5 runs over 1024 MB of data separate: 1.461349 sec separate: 1.020120 sec separate: 1.019002 sec separate: 1.019888 sec separate: 1.018454 sec fused: 1.014774 sec fused: 1.014724 sec fused: 1.013895 sec fused: 1.016440 sec fused: 1.013729 sec So almost no difference, though with enough runs I think this would be significant. Interestingly, although C is not JIT compiled, even here there is a "warmup" effect. I guess these are initial page faults or something. But if we now comment out <math.h> and instead use some cheap "fake" implementations of in and tan: // #include <math.h> #define tan(x) (x + 1) #define sin(x) (x + 2) we get very different behavior: will do 5 runs over 1024 MB of data separate: 0.548558 sec separate: 0.154741 sec separate: 0.151271 sec separate: 0.150542 sec separate: 0.151337 sec fused: 0.078880 sec fused: 0.074742 sec fused: 0.078313 sec fused: 0.076987 sec fused: 0.077729 sec Here the computation is so cheap that it's really other effects that dominate, and you get a 2x difference.