[feature request] continued accerelate ConstructHistogram

[guolinke]

ConstructHistogram (in src\io\**_bin.hpp and src_io\dataset.cpp) is the most time-consuming part of LightGBM.

The speed here is mainly bounded by the memory bandwidth.

There are two construction algorithms:

1. col-wise, which scans columns and constructs its corresponding histogram one-by-one

   • Pros: better scalability in multi-threading. smaller memory consumption.
   • Cons: redundancy memory access for gradients and hessians for each column needs one pass of them.

2. row-wise, which scans the rows one-by-one, and constructs all feature histograms at once.

   • Pros: sparse-aware and no redundancy memory access for gradients and hessians.
   • Cons: poor scalability in multi-threading. larger memory consumption.

Currently, LightGBM implements them both, and automatically choose the faster one during run-time.

Maybe there is a better algorithm and we can continue to explore it.

[StrikerRUS]

Closed in favor of being in #2302. We decided to keep all feature requests in one place.

Welcome to contribute this feature! Please re-open this issue (or post a comment if you are not a topic starter) if you are actively working on implementing this feature.

[guolinke]

#3522 reduces the memory overhead for dense row-wise histograms, besides, it adjusts the block size and achieves a better speed-up.