Help understanding scan adverb

Community Support
,
1

https://learninghub.kx.com/forums/topic/help-understanding-scan-adverb

Hi,
I understand how scan works with a diadyc function such as (+) or (*), and hence implemented my version of a exponential moving average like that :

fun_ema:{[lambda; liste];

({[lambda; x; y]; (lambda*y)+ (x*1-lambda)}[lambda]\) liste

}


In the book I am reading, their operation over 1million lines is almost 2.5 times faster with this structure:

expma1:{[lambda;vector]

/ lambda -- memory

/ vector -- data

{[x;y;z] (x*y)+z}\[ first vector; 1 - lambda; vector * lambda]

};



Can someone explain how it works ?
Thank you very much


2

Testing speed and equivalence: 

fun_ema:{[lambda; liste];({[lambda; x; y]; (lambda*y)+ (x*1-lambda)}[lambda]\) liste}
expma1:{[lambda;vector] {[x;y;z] (x*y)+z}\[ first vector; 1-lambda; vector * lambda]};
q)a:10
q)b:til 1000000
q)\ts r1:fun_ema[a;b]
174 32777680
q)\ts r2:expma1[a;b]
91 41166288
q)r1~r2
1b


Your fun_ema performs *, +, *, - a total of count[b] times. The operations are all on atom type data.

expma1 performs *, + a total of count[b] times and -, * once. The single use of * is on vector type data.


q uses vector instructions for speed. These take advantage of CPU instructions to be more efficient


q)a:til 1000000
q)b: til 1000000
q)\ts a+b  // + operates on vectors and is fast
1 8388800
q)\ts a+'b // Using ' to force + to loop through each pair of atoms is much slower
26 32777488
q)\ts {x+y}'[a;b] //Wrapping in an unnecessary lambda is slower again
62 32777792


Since 4.0, kdb further sped up large vector operations by adding Multithreaded primitives which will spread the vector operations across multiple threads when available.


  • https://code.kx.com/q/ref/maps/#each
  • https://en.wikipedia.org/wiki/Single_instruction,_multiple_data
  • https://en.wikipedia.org/wiki/SSE4