feature_histogram.hpp 22.1 KB
Newer Older
Guolin Ke's avatar
Guolin Ke committed
1
2
3
4
#ifndef LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_
#define LIGHTGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_

#include "split_info.hpp"
Guolin Ke's avatar
Guolin Ke committed
5
6
7

#include <LightGBM/utils/array_args.h>
#include <LightGBM/dataset.h>
Guolin Ke's avatar
Guolin Ke committed
8
9
10

#include <cstring>

Guolin Ke's avatar
Guolin Ke committed
11
namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
12
{
Guolin Ke's avatar
Guolin Ke committed
13

Guolin Ke's avatar
Guolin Ke committed
14
15
16
class FeatureMetainfo {
public:
  int num_bin;
Guolin Ke's avatar
Guolin Ke committed
17
  MissingType missing_type;
18
  int8_t bias = 0;
Guolin Ke's avatar
Guolin Ke committed
19
  uint32_t default_bin;
Guolin Ke's avatar
Guolin Ke committed
20
21
22
  /*! \brief pointer of tree config */
  const TreeConfig* tree_config;
};
Guolin Ke's avatar
Guolin Ke committed
23
24
25
26
27
/*!
* \brief FeatureHistogram is used to construct and store a histogram for a feature.
*/
class FeatureHistogram {
public:
Guolin Ke's avatar
Guolin Ke committed
28
  FeatureHistogram() {
Guolin Ke's avatar
Guolin Ke committed
29
    data_ = nullptr;
Guolin Ke's avatar
Guolin Ke committed
30
  }
Guolin Ke's avatar
Guolin Ke committed
31

Guolin Ke's avatar
Guolin Ke committed
32
33
34
  ~FeatureHistogram() {
  }

Guolin Ke's avatar
Guolin Ke committed
35
36
37
38
39
  /*! \brief Disable copy */
  FeatureHistogram& operator=(const FeatureHistogram&) = delete;
  /*! \brief Disable copy */
  FeatureHistogram(const FeatureHistogram&) = delete;

Guolin Ke's avatar
Guolin Ke committed
40
41
42
43
44
  /*!
  * \brief Init the feature histogram
  * \param feature the feature data for this histogram
  * \param min_num_data_one_leaf minimal number of data in one leaf
  */
45
  void Init(HistogramBinEntry* data, const FeatureMetainfo* meta, BinType bin_type) {
Guolin Ke's avatar
Guolin Ke committed
46
47
    meta_ = meta;
    data_ = data;
48
49
    if (bin_type == BinType::NumericalBin) {
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdNumerical, this, std::placeholders::_1
Guolin Ke's avatar
Guolin Ke committed
50
                                           , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4);
51
52
    } else {
      find_best_threshold_fun_ = std::bind(&FeatureHistogram::FindBestThresholdCategorical, this, std::placeholders::_1
Guolin Ke's avatar
Guolin Ke committed
53
                                           , std::placeholders::_2, std::placeholders::_3, std::placeholders::_4);
54
    }
Guolin Ke's avatar
Guolin Ke committed
55
56
  }

Guolin Ke's avatar
Guolin Ke committed
57
58
  HistogramBinEntry* RawData() {
    return data_;
Guolin Ke's avatar
Guolin Ke committed
59
60
61
62
63
64
  }
  /*!
  * \brief Subtract current histograms with other
  * \param other The histogram that want to subtract
  */
  void Subtract(const FeatureHistogram& other) {
Guolin Ke's avatar
Guolin Ke committed
65
    for (int i = 0; i < meta_->num_bin - meta_->bias; ++i) {
Guolin Ke's avatar
Guolin Ke committed
66
67
68
69
70
      data_[i].cnt -= other.data_[i].cnt;
      data_[i].sum_gradients -= other.data_[i].sum_gradients;
      data_[i].sum_hessians -= other.data_[i].sum_hessians;
    }
  }
71

Guolin Ke's avatar
Guolin Ke committed
72
  void FindBestThreshold(double sum_gradient, double sum_hessian, data_size_t num_data,
Guolin Ke's avatar
Guolin Ke committed
73
                         SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
74
    output->default_left = true;
Guolin Ke's avatar
Guolin Ke committed
75
    output->gain = kMinScore;
76
77
78
79
    find_best_threshold_fun_(sum_gradient, sum_hessian + 2 * kEpsilon, num_data, output);
  }

  void FindBestThresholdNumerical(double sum_gradient, double sum_hessian, data_size_t num_data,
Guolin Ke's avatar
Guolin Ke committed
80
                                  SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
81
82

    is_splittable_ = false;
Guolin Ke's avatar
Guolin Ke committed
83
84
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian,
                                         meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
Guolin Ke's avatar
Guolin Ke committed
85
    double min_gain_shift = gain_shift + meta_->tree_config->min_gain_to_split;
Guolin Ke's avatar
Guolin Ke committed
86
87
88
89
90
91
92
93
    if (meta_->num_bin > 2 && meta_->missing_type != MissingType::None) {
      if (meta_->missing_type == MissingType::Zero) {
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_gain_shift, output, -1, true, false);
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_gain_shift, output, 1, true, false);
      } else {
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_gain_shift, output, -1, false, true);
        FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_gain_shift, output, 1, false, true);
      }
94
    } else {
Guolin Ke's avatar
Guolin Ke committed
95
96
97
98
99
      FindBestThresholdSequence(sum_gradient, sum_hessian, num_data, min_gain_shift, output, -1, false, false);
      // fix the direction error when only have 2 bins
      if (meta_->missing_type == MissingType::NaN) {
        output->default_left = false;
      }
Guolin Ke's avatar
Guolin Ke committed
100
    }
Guolin Ke's avatar
Guolin Ke committed
101
    output->gain -= min_gain_shift;
Guolin Ke's avatar
Guolin Ke committed
102
  }
103
104

  void FindBestThresholdCategorical(double sum_gradient, double sum_hessian, data_size_t num_data,
Guolin Ke's avatar
Guolin Ke committed
105
                                    SplitInfo* output) {
Guolin Ke's avatar
Guolin Ke committed
106
    output->default_left = false;
107
    double best_gain = kMinScore;
108
    data_size_t best_left_count = 0;
ChenZhiyong's avatar
ChenZhiyong committed
109
110
111
    double best_sum_left_gradient = 0;
    double best_sum_left_hessian = 0;
    double gain_shift = GetLeafSplitGain(sum_gradient, sum_hessian, meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
Guolin Ke's avatar
Guolin Ke committed
112
    
113
    double min_gain_shift = gain_shift + meta_->tree_config->min_gain_to_split;
ChenZhiyong's avatar
ChenZhiyong committed
114
115
116
117
118
    bool is_full_categorical = meta_->missing_type == MissingType::None;
    int used_bin = meta_->num_bin - 1;

    if (is_full_categorical) ++used_bin;

Guolin Ke's avatar
Guolin Ke committed
119
120
    const double smooth_hess = std::max(meta_->tree_config->min_cat_smooth,
                                        std::min(meta_->tree_config->cat_smooth_ratio * num_data, meta_->tree_config->max_cat_smooth));
ChenZhiyong's avatar
ChenZhiyong committed
121

Guolin Ke's avatar
Guolin Ke committed
122
123
124
125
126
127
128
129
    const int min_data_per_cat = static_cast<int>(smooth_hess);
    std::vector<int> sorted_idx;
    for (int i = 0; i < used_bin; ++i) {
      if (data_[i].cnt >= min_data_per_cat) {
        sorted_idx.push_back(i);
      }
    }
    used_bin = static_cast<int>(sorted_idx.size());
ChenZhiyong's avatar
ChenZhiyong committed
130

Guolin Ke's avatar
Guolin Ke committed
131
132
133
134
    const double l2 = meta_->tree_config->lambda_l2 + meta_->tree_config->cat_l2;

    auto ctr_fun = [&smooth_hess](double sum_grad, double sum_hess) {
      return (sum_grad) / (sum_hess + smooth_hess);
ChenZhiyong's avatar
ChenZhiyong committed
135
136
137
    };
    std::sort(sorted_idx.begin(), sorted_idx.end(),
              [this, &ctr_fun](int i, int j) {
Guolin Ke's avatar
Guolin Ke committed
138
      return ctr_fun(data_[i].sum_gradients, data_[i].cnt) < ctr_fun(data_[j].sum_gradients, data_[j].cnt);
ChenZhiyong's avatar
ChenZhiyong committed
139
140
141
142
    });

    std::vector<int> find_direction(1, 1);
    std::vector<int> start_position(1, 0);
Guolin Ke's avatar
Guolin Ke committed
143
144
145
    find_direction.push_back(-1);
    start_position.push_back(used_bin - 1);
    const int max_num_cat = std::min(meta_->tree_config->max_cat_threshold, (used_bin + 1) / 2);
ChenZhiyong's avatar
ChenZhiyong committed
146

147
    is_splittable_ = false;
ChenZhiyong's avatar
ChenZhiyong committed
148
149
150
151
152
    int best_threshold = -1;
    int best_dir = 1;
    for (size_t out_i = 0; out_i < find_direction.size(); ++out_i) {
      auto dir = find_direction[out_i];
      auto start_pos = start_position[out_i];
Guolin Ke's avatar
Guolin Ke committed
153
      data_size_t min_data_per_group = meta_->tree_config->min_data_per_group;
ChenZhiyong's avatar
ChenZhiyong committed
154
155
156
157
      data_size_t cnt_cur_group = 0;
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;
Guolin Ke's avatar
Guolin Ke committed
158
      for (int i = 0; i < used_bin && i < max_num_cat; ++i) {
ChenZhiyong's avatar
ChenZhiyong committed
159
160
        auto t = sorted_idx[start_pos];
        start_pos += dir;
161

ChenZhiyong's avatar
ChenZhiyong committed
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
        sum_left_gradient += data_[t].sum_gradients;
        sum_left_hessian += data_[t].sum_hessians;
        left_count += data_[t].cnt;
        cnt_cur_group += data_[t].cnt;

        if (left_count < meta_->tree_config->min_data_in_leaf
            || sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t right_count = num_data - left_count;
        if (right_count < meta_->tree_config->min_data_in_leaf || right_count < min_data_per_group) break;

        double sum_right_hessian = sum_hessian - sum_left_hessian;
        if (sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

        if (cnt_cur_group < min_data_per_group) continue;

        cnt_cur_group = 0;
178

ChenZhiyong's avatar
ChenZhiyong committed
179
        double sum_right_gradient = sum_gradient - sum_left_gradient;
Guolin Ke's avatar
Guolin Ke committed
180
181
        double current_gain = GetLeafSplitGain(sum_left_gradient, sum_left_hessian, meta_->tree_config->lambda_l1, l2)
          + GetLeafSplitGain(sum_right_gradient, sum_right_hessian, meta_->tree_config->lambda_l1, l2);
ChenZhiyong's avatar
ChenZhiyong committed
182
183
184
185
186
187
188
189
190
191
        if (current_gain <= min_gain_shift) continue;
        is_splittable_ = true;
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          best_threshold = i;
          best_gain = current_gain;
          best_dir = dir;
        }
192
193
      }
    }
194

195
    if (is_splittable_) {
Guolin Ke's avatar
Guolin Ke committed
196
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
197
                                                        meta_->tree_config->lambda_l1, l2);
198
199
200
201
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
Guolin Ke's avatar
Guolin Ke committed
202
                                                         sum_hessian - best_sum_left_hessian,
Guolin Ke's avatar
Guolin Ke committed
203
                                                         meta_->tree_config->lambda_l1, l2);
204
205
206
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
Guolin Ke's avatar
Guolin Ke committed
207
      output->gain = best_gain - min_gain_shift;
ChenZhiyong's avatar
ChenZhiyong committed
208
209
210
211
      output->num_cat_threshold = best_threshold + 1;
      output->cat_threshold = std::vector<uint32_t>(output->num_cat_threshold);
      if (best_dir == 1) {
        for (int i = 0; i < output->num_cat_threshold; ++i) {
Guolin Ke's avatar
Guolin Ke committed
212
          auto t = sorted_idx[i];
Guolin Ke's avatar
Guolin Ke committed
213
          output->cat_threshold[i] = t;
ChenZhiyong's avatar
ChenZhiyong committed
214
215
216
        }
      } else {
        for (int i = 0; i < output->num_cat_threshold; ++i) {
Guolin Ke's avatar
Guolin Ke committed
217
          auto t = sorted_idx[used_bin - 1 - i];
Guolin Ke's avatar
Guolin Ke committed
218
          output->cat_threshold[i] = t;
ChenZhiyong's avatar
ChenZhiyong committed
219
220
        }
      }
221
    }
222
223
  }

Guolin Ke's avatar
Guolin Ke committed
224
225
226
227
  /*!
  * \brief Binary size of this histogram
  */
  int SizeOfHistgram() const {
Guolin Ke's avatar
Guolin Ke committed
228
    return (meta_->num_bin - meta_->bias) * sizeof(HistogramBinEntry);
Guolin Ke's avatar
Guolin Ke committed
229
230
231
232
233
  }

  /*!
  * \brief Restore histogram from memory
  */
Guolin Ke's avatar
Guolin Ke committed
234
235
  void FromMemory(char* memory_data) {
    std::memcpy(data_, memory_data, (meta_->num_bin - meta_->bias) * sizeof(HistogramBinEntry));
Guolin Ke's avatar
Guolin Ke committed
236
237
238
239
240
241
242
243
244
245
246
247
248
  }

  /*!
  * \brief True if this histogram can be splitted
  */
  bool is_splittable() { return is_splittable_; }

  /*!
  * \brief Set splittable to this histogram
  */
  void set_is_splittable(bool val) { is_splittable_ = val; }

  /*!
249
  * \brief Calculate the split gain based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
250
251
252
253
  * \param sum_gradients
  * \param sum_hessians
  * \return split gain
  */
Guolin Ke's avatar
Guolin Ke committed
254
  static double GetLeafSplitGain(double sum_gradients, double sum_hessians, double l1, double l2) {
255
    double abs_sum_gradients = std::fabs(sum_gradients);
Guolin Ke's avatar
Guolin Ke committed
256
    double reg_abs_sum_gradients = std::max(0.0, abs_sum_gradients - l1);
Guolin Ke's avatar
Guolin Ke committed
257
    return (reg_abs_sum_gradients * reg_abs_sum_gradients)
Guolin Ke's avatar
Guolin Ke committed
258
      / (sum_hessians + l2);
Guolin Ke's avatar
Guolin Ke committed
259

Guolin Ke's avatar
Guolin Ke committed
260
261
262
  }

  /*!
263
  * \brief Calculate the output of a leaf based on regularized sum_gradients and sum_hessians
Guolin Ke's avatar
Guolin Ke committed
264
265
266
267
  * \param sum_gradients
  * \param sum_hessians
  * \return leaf output
  */
Guolin Ke's avatar
Guolin Ke committed
268
  static double CalculateSplittedLeafOutput(double sum_gradients, double sum_hessians, double l1, double l2) {
269
    double abs_sum_gradients = std::fabs(sum_gradients);
Guolin Ke's avatar
Guolin Ke committed
270
    double reg_abs_sum_gradients = std::max(0.0, abs_sum_gradients - l1);
Guolin Ke's avatar
Guolin Ke committed
271
    return -std::copysign(reg_abs_sum_gradients, sum_gradients)
Guolin Ke's avatar
Guolin Ke committed
272
      / (sum_hessians + l2);
Guolin Ke's avatar
Guolin Ke committed
273
  }
Guolin Ke's avatar
Guolin Ke committed
274
275
276

private:

Guolin Ke's avatar
Guolin Ke committed
277
  void FindBestThresholdSequence(double sum_gradient, double sum_hessian, data_size_t num_data, double min_gain_shift,
Guolin Ke's avatar
Guolin Ke committed
278
                                 SplitInfo* output, int dir, bool skip_default_bin, bool use_na_as_missing) {
Guolin Ke's avatar
Guolin Ke committed
279

280
    const int8_t bias = meta_->bias;
Guolin Ke's avatar
Guolin Ke committed
281
282
283
284
285
286
287
288
289
290
291
292
293

    double best_sum_left_gradient = NAN;
    double best_sum_left_hessian = NAN;
    double best_gain = kMinScore;
    data_size_t best_left_count = 0;
    uint32_t best_threshold = static_cast<uint32_t>(meta_->num_bin);

    if (dir == -1) {

      double sum_right_gradient = 0.0f;
      double sum_right_hessian = kEpsilon;
      data_size_t right_count = 0;

Guolin Ke's avatar
Guolin Ke committed
294
      int t = meta_->num_bin - 1 - bias - use_na_as_missing;
Guolin Ke's avatar
Guolin Ke committed
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
      const int t_end = 1 - bias;

      // from right to left, and we don't need data in bin0
      for (; t >= t_end; --t) {

        // need to skip default bin
        if (skip_default_bin && (t + bias) == static_cast<int>(meta_->default_bin)) { continue; }

        sum_right_gradient += data_[t].sum_gradients;
        sum_right_hessian += data_[t].sum_hessians;
        right_count += data_[t].cnt;
        // if data not enough, or sum hessian too small
        if (right_count < meta_->tree_config->min_data_in_leaf
            || sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t left_count = num_data - right_count;
        // if data not enough
        if (left_count < meta_->tree_config->min_data_in_leaf) break;

        double sum_left_hessian = sum_hessian - sum_right_hessian;
        // if sum hessian too small
        if (sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

        double sum_left_gradient = sum_gradient - sum_right_gradient;
        // current split gain
        double current_gain = GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
                                               meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2)
          + GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
                             meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
        // gain with split is worse than without split
        if (current_gain <= min_gain_shift) continue;

        // mark to is splittable
        is_splittable_ = true;
        // better split point
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          // left is <= threshold, right is > threshold.  so this is t-1
          best_threshold = static_cast<uint32_t>(t - 1 + bias);
          best_gain = current_gain;
        }
      }
ChenZhiyong's avatar
ChenZhiyong committed
338
    } else {
Guolin Ke's avatar
Guolin Ke committed
339
340
341
342
343
344
345
      double sum_left_gradient = 0.0f;
      double sum_left_hessian = kEpsilon;
      data_size_t left_count = 0;

      int t = 0;
      const int t_end = meta_->num_bin - 2 - bias;

Guolin Ke's avatar
Guolin Ke committed
346
347
348
349
350
351
352
353
354
355
356
357
      if (use_na_as_missing && bias == 1) {
        sum_left_gradient = sum_gradient;
        sum_left_hessian = sum_hessian - kEpsilon;
        left_count = num_data;
        for (int i = 0; i < meta_->num_bin - bias; ++i) {
          sum_left_gradient -= data_[i].sum_gradients;
          sum_left_hessian -= data_[i].sum_hessians;
          left_count -= data_[i].cnt;
        }
        t = -1;
      }

Guolin Ke's avatar
Guolin Ke committed
358
359
360
361
      for (; t <= t_end; ++t) {

        // need to skip default bin
        if (skip_default_bin && (t + bias) == static_cast<int>(meta_->default_bin)) { continue; }
Guolin Ke's avatar
Guolin Ke committed
362
363
364
365
366
        if (t >= 0) {
          sum_left_gradient += data_[t].sum_gradients;
          sum_left_hessian += data_[t].sum_hessians;
          left_count += data_[t].cnt;
        }
Guolin Ke's avatar
Guolin Ke committed
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
        // if data not enough, or sum hessian too small
        if (left_count < meta_->tree_config->min_data_in_leaf
            || sum_left_hessian < meta_->tree_config->min_sum_hessian_in_leaf) continue;
        data_size_t right_count = num_data - left_count;
        // if data not enough
        if (right_count < meta_->tree_config->min_data_in_leaf) break;

        double sum_right_hessian = sum_hessian - sum_left_hessian;
        // if sum hessian too small
        if (sum_right_hessian < meta_->tree_config->min_sum_hessian_in_leaf) break;

        double sum_right_gradient = sum_gradient - sum_left_gradient;
        // current split gain
        double current_gain = GetLeafSplitGain(sum_left_gradient, sum_left_hessian,
                                               meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2)
          + GetLeafSplitGain(sum_right_gradient, sum_right_hessian,
                             meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
        // gain with split is worse than without split
        if (current_gain <= min_gain_shift) continue;

        // mark to is splittable
        is_splittable_ = true;
        // better split point
        if (current_gain > best_gain) {
          best_left_count = left_count;
          best_sum_left_gradient = sum_left_gradient;
          best_sum_left_hessian = sum_left_hessian;
          best_threshold = static_cast<uint32_t>(t + bias);
          best_gain = current_gain;
        }
      }
    }

    if (is_splittable_ && best_gain > output->gain) {
      // update split information
      output->threshold = best_threshold;
      output->left_output = CalculateSplittedLeafOutput(best_sum_left_gradient, best_sum_left_hessian,
                                                        meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
      output->left_count = best_left_count;
      output->left_sum_gradient = best_sum_left_gradient;
      output->left_sum_hessian = best_sum_left_hessian - kEpsilon;
      output->right_output = CalculateSplittedLeafOutput(sum_gradient - best_sum_left_gradient,
                                                         sum_hessian - best_sum_left_hessian,
                                                         meta_->tree_config->lambda_l1, meta_->tree_config->lambda_l2);
      output->right_count = num_data - best_left_count;
      output->right_sum_gradient = sum_gradient - best_sum_left_gradient;
      output->right_sum_hessian = sum_hessian - best_sum_left_hessian - kEpsilon;
      output->gain = best_gain;
Guolin Ke's avatar
Guolin Ke committed
415
      output->default_left = dir == -1;
Guolin Ke's avatar
Guolin Ke committed
416
417
418
    }
  }

Guolin Ke's avatar
Guolin Ke committed
419
  const FeatureMetainfo* meta_;
Guolin Ke's avatar
Guolin Ke committed
420
  /*! \brief sum of gradient of each bin */
Guolin Ke's avatar
Guolin Ke committed
421
422
  HistogramBinEntry* data_;
  //std::vector<HistogramBinEntry> data_;
Guolin Ke's avatar
Guolin Ke committed
423
424
  /*! \brief False if this histogram cannot split */
  bool is_splittable_ = true;
425
426

  std::function<void(double, double, data_size_t, SplitInfo*)> find_best_threshold_fun_;
Guolin Ke's avatar
Guolin Ke committed
427
};
Guolin Ke's avatar
Guolin Ke committed
428
429
430
431
432
433
class HistogramPool {
public:
  /*!
  * \brief Constructor
  */
  HistogramPool() {
Guolin Ke's avatar
Guolin Ke committed
434
435
    cache_size_ = 0;
    total_size_ = 0;
Guolin Ke's avatar
Guolin Ke committed
436
437
438
439
440
441
442
443
444
445
446
  }
  /*!
  * \brief Destructor
  */
  ~HistogramPool() {
  }
  /*!
  * \brief Reset pool size
  * \param cache_size Max cache size
  * \param total_size Total size will be used
  */
Guolin Ke's avatar
Guolin Ke committed
447
  void Reset(int cache_size, int total_size) {
Guolin Ke's avatar
Guolin Ke committed
448
449
450
451
452
453
454
455
456
    cache_size_ = cache_size;
    // at least need 2 bucket to store smaller leaf and larger leaf
    CHECK(cache_size_ >= 2);
    total_size_ = total_size;
    if (cache_size_ > total_size_) {
      cache_size_ = total_size_;
    }
    is_enough_ = (cache_size_ == total_size_);
    if (!is_enough_) {
457
458
459
      mapper_.resize(total_size_);
      inverse_mapper_.resize(cache_size_);
      last_used_time_.resize(cache_size_);
Guolin Ke's avatar
Guolin Ke committed
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
      ResetMap();
    }
  }
  /*!
  * \brief Reset mapper
  */
  void ResetMap() {
    if (!is_enough_) {
      cur_time_ = 0;
      std::fill(mapper_.begin(), mapper_.end(), -1);
      std::fill(inverse_mapper_.begin(), inverse_mapper_.end(), -1);
      std::fill(last_used_time_.begin(), last_used_time_.end(), 0);
    }
  }

Guolin Ke's avatar
Guolin Ke committed
475
476
  void DynamicChangeSize(const Dataset* train_data, const TreeConfig* tree_config, int cache_size, int total_size) {
    if (feature_metas_.empty()) {
Guolin Ke's avatar
Guolin Ke committed
477
478
479
480
      int num_feature = train_data->num_features();
      feature_metas_.resize(num_feature);
      #pragma omp parallel for schedule(static, 512) if(num_feature >= 1024)
      for (int i = 0; i < num_feature; ++i) {
Guolin Ke's avatar
Guolin Ke committed
481
        feature_metas_[i].num_bin = train_data->FeatureNumBin(i);
Guolin Ke's avatar
Guolin Ke committed
482
        feature_metas_[i].default_bin = train_data->FeatureBinMapper(i)->GetDefaultBin();
Guolin Ke's avatar
Guolin Ke committed
483
        feature_metas_[i].missing_type = train_data->FeatureBinMapper(i)->missing_type();
Guolin Ke's avatar
Guolin Ke committed
484
485
486
487
488
489
490
        if (train_data->FeatureBinMapper(i)->GetDefaultBin() == 0) {
          feature_metas_[i].bias = 1;
        } else {
          feature_metas_[i].bias = 0;
        }
        feature_metas_[i].tree_config = tree_config;
      }
Guolin Ke's avatar
Guolin Ke committed
491
    }
Guolin Ke's avatar
Guolin Ke committed
492
493
    uint64_t num_total_bin = train_data->NumTotalBin();
    Log::Info("Total Bins %d", num_total_bin);
Guolin Ke's avatar
Guolin Ke committed
494
    int old_cache_size = static_cast<int>(pool_.size());
Guolin Ke's avatar
Guolin Ke committed
495
    Reset(cache_size, total_size);
Guolin Ke's avatar
Guolin Ke committed
496
497
498
499
500
501

    if (cache_size > old_cache_size) {
      pool_.resize(cache_size);
      data_.resize(cache_size);
    }

502
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
503
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
504
    for (int i = old_cache_size; i < cache_size; ++i) {
505
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
506
507
508
509
510
      pool_[i].reset(new FeatureHistogram[train_data->num_features()]);
      data_[i].resize(num_total_bin);
      uint64_t offset = 0;
      for (int j = 0; j < train_data->num_features(); ++j) {
        offset += static_cast<uint64_t>(train_data->SubFeatureBinOffset(j));
511
        pool_[i][j].Init(data_[i].data() + offset, &feature_metas_[j], train_data->FeatureBinMapper(j)->bin_type());
Guolin Ke's avatar
Guolin Ke committed
512
513
514
515
516
517
518
        auto num_bin = train_data->FeatureNumBin(j);
        if (train_data->FeatureBinMapper(j)->GetDefaultBin() == 0) {
          num_bin -= 1;
        }
        offset += static_cast<uint64_t>(num_bin);
      }
      CHECK(offset == num_total_bin);
519
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
520
    }
521
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
522
523
  }

Guolin Ke's avatar
Guolin Ke committed
524
  void ResetConfig(const TreeConfig* tree_config) {
Guolin Ke's avatar
Guolin Ke committed
525
526
527
    int size = static_cast<int>(feature_metas_.size());
    #pragma omp parallel for schedule(static, 512) if(size >= 1024)
    for (int i = 0; i < size; ++i) {
Guolin Ke's avatar
Guolin Ke committed
528
      feature_metas_[i].tree_config = tree_config;
Guolin Ke's avatar
Guolin Ke committed
529
530
    }
  }
Guolin Ke's avatar
Guolin Ke committed
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
  /*!
  * \brief Get data for the specific index
  * \param idx which index want to get
  * \param out output data will store into this
  * \return True if this index is in the pool, False if this index is not in the pool
  */
  bool Get(int idx, FeatureHistogram** out) {
    if (is_enough_) {
      *out = pool_[idx].get();
      return true;
    } else if (mapper_[idx] >= 0) {
      int slot = mapper_[idx];
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;
      return true;
    } else {
      // choose the least used slot 
      int slot = static_cast<int>(ArrayArgs<int>::ArgMin(last_used_time_));
      *out = pool_[slot].get();
      last_used_time_[slot] = ++cur_time_;

      // reset previous mapper
      if (inverse_mapper_[slot] >= 0) mapper_[inverse_mapper_[slot]] = -1;

      // update current mapper
      mapper_[idx] = slot;
      inverse_mapper_[slot] = idx;
      return false;
    }
  }

  /*!
  * \brief Move data from one index to another index
  * \param src_idx
  * \param dst_idx
  */
  void Move(int src_idx, int dst_idx) {
    if (is_enough_) {
      std::swap(pool_[src_idx], pool_[dst_idx]);
      return;
    }
    if (mapper_[src_idx] < 0) {
      return;
    }
    // get slot of src idx
    int slot = mapper_[src_idx];
    // reset src_idx
    mapper_[src_idx] = -1;

    // move to dst idx
    mapper_[dst_idx] = slot;
    last_used_time_[slot] = ++cur_time_;
    inverse_mapper_[slot] = dst_idx;
  }
private:
  std::vector<std::unique_ptr<FeatureHistogram[]>> pool_;
Guolin Ke's avatar
Guolin Ke committed
587
588
  std::vector<std::vector<HistogramBinEntry>> data_;
  std::vector<FeatureMetainfo> feature_metas_;
Guolin Ke's avatar
Guolin Ke committed
589
590
591
592
593
594
595
596
597
  int cache_size_;
  int total_size_;
  bool is_enough_ = false;
  std::vector<int> mapper_;
  std::vector<int> inverse_mapper_;
  std::vector<int> last_used_time_;
  int cur_time_ = 0;
};

Guolin Ke's avatar
Guolin Ke committed
598
}  // namespace LightGBM
Guolin Ke's avatar
Guolin Ke committed
599
#endif   // LightGBM_TREELEARNER_FEATURE_HISTOGRAM_HPP_