Report TODOs

[amarisch]

Analysis

• Update(): taking terms accessing very long vectors
  • So far we have gained 1.5X speed up by blocking, allowing some variable reuse
  • Feature blocking is faster but increases cache references. Varying # features and # samples seem to get the same results. Picked 2,2 combo which uses the least # of references See cache reference log
  • Understanding why master_noupdate with addpd did not get 2X speedup compare to master_noupdate without intrinsics (I sent @xivid screenshots of the 2 different assembly)
  • Need a master_noupdate_float branch that uses ps packed_single instructions to add count and gradient. This branch can/will be combined with feature_blocking_cumulator_float
• Cumulate()
  • Combined all cumulate() calls into one and got 2.5X speedup
  • Understanding why the performance of cumulate() drops when sample size gets large. The function is not directly dependent on the size of the sample. There is a drop in performance when sample size > 2^17. Cumulate() is not directly dependent on sample size. The number of candidates gets larger (HistogramMatrix gets larger) when sample size is larger. I tried accumulating 8 candidates at once (instead of 4) but that reduces the performance for smaller datasets. Then I tried accumulating 8 candidates at once only when num_candidates > 50. The improvement in performance is minimal.
  • We need a feature_blocking_cumulator_float branch that uses only floats and ps packed_single instructions
• get_best_split()
  • has many fp mult and div instructions and hence benefits from using a smaller datatype (float instead of double)

Memory Analysis

• we seem to have a lot of L3 cache misses. Need to come up with a good reason why and if we have any solutions
• Need to figure out why even the smallest dataset mslr.10 also gave us 20% L3 cache miss.
• Whoever has time and wants to play with PAPI and look into L2 cache misses. (perf only gives L1 and LLC)

Linux Spec:
Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz (Coffee Lake)
L1: 32KB, L2: 256KB, L3:9216KB
gcc version 7.3.0; Ubuntu 18.04

[meetvora]

Just a point about the PAPI idea. PAPI too only gives L1 and LLC misses. This link is a good example of that (the first few lines). The answer also shows that PAPI reported correct values than Perf but that was mainly because Perf reported misses due to Kernel calls. In all our analysis, we have negligible miss rate due to kernel.