dataset.cpp 56.5 KB
Newer Older
1
2
3
4
/*!
 * Copyright (c) 2016 Microsoft Corporation. All rights reserved.
 * Licensed under the MIT License. See LICENSE file in the project root for license information.
 */
Guolin Ke's avatar
Guolin Ke committed
5
#include <LightGBM/dataset.h>
6

Guolin Ke's avatar
Guolin Ke committed
7
#include <LightGBM/feature_group.h>
8
#include <LightGBM/utils/array_args.h>
9
#include <LightGBM/utils/openmp_wrapper.h>
Guolin Ke's avatar
Guolin Ke committed
10
#include <LightGBM/utils/threading.h>
Guolin Ke's avatar
Guolin Ke committed
11

12
#include <limits>
zhangyafeikimi's avatar
zhangyafeikimi committed
13
#include <chrono>
Guolin Ke's avatar
Guolin Ke committed
14
#include <cstdio>
Guolin Ke's avatar
Guolin Ke committed
15
#include <sstream>
16
#include <unordered_map>
Guolin Ke's avatar
Guolin Ke committed
17

18

Guolin Ke's avatar
Guolin Ke committed
19
20
namespace LightGBM {

21
const char* Dataset::binary_file_token = "______LightGBM_Binary_File_Token______\n";
Guolin Ke's avatar
Guolin Ke committed
22

Guolin Ke's avatar
Guolin Ke committed
23
Dataset::Dataset() {
24
  data_filename_ = "noname";
Guolin Ke's avatar
Guolin Ke committed
25
  num_data_ = 0;
Guolin Ke's avatar
Guolin Ke committed
26
  is_finish_load_ = false;
Guolin Ke's avatar
Guolin Ke committed
27
28
}

29
Dataset::Dataset(data_size_t num_data) {
Guolin Ke's avatar
Guolin Ke committed
30
  CHECK(num_data > 0);
Guolin Ke's avatar
Guolin Ke committed
31
  data_filename_ = "noname";
Guolin Ke's avatar
Guolin Ke committed
32
  num_data_ = num_data;
Guolin Ke's avatar
Guolin Ke committed
33
  metadata_.Init(num_data_, NO_SPECIFIC, NO_SPECIFIC);
Guolin Ke's avatar
Guolin Ke committed
34
  is_finish_load_ = false;
Guolin Ke's avatar
Guolin Ke committed
35
  group_bin_boundaries_.push_back(0);
Guolin Ke's avatar
Guolin Ke committed
36
37
}

Guolin Ke's avatar
Guolin Ke committed
38
Dataset::~Dataset() {
Guolin Ke's avatar
Guolin Ke committed
39
}
Guolin Ke's avatar
Guolin Ke committed
40

Guolin Ke's avatar
Guolin Ke committed
41
42
43
44
45
46
47
48
49
50
std::vector<std::vector<int>> NoGroup(
  const std::vector<int>& used_features) {
  std::vector<std::vector<int>> features_in_group;
  features_in_group.resize(used_features.size());
  for (size_t i = 0; i < used_features.size(); ++i) {
    features_in_group[i].emplace_back(used_features[i]);
  }
  return features_in_group;
}

51
int GetConfilctCount(const std::vector<bool>& mark, const int* indices, int num_indices, data_size_t max_cnt) {
Guolin Ke's avatar
Guolin Ke committed
52
53
54
55
  int ret = 0;
  for (int i = 0; i < num_indices; ++i) {
    if (mark[indices[i]]) {
      ++ret;
56
57
58
    }
    if (ret > max_cnt) {
      return -1;
Guolin Ke's avatar
Guolin Ke committed
59
60
61
62
    }
  }
  return ret;
}
63
64

void MarkUsed(std::vector<bool>* mark, const int* indices, data_size_t num_indices) {
Guolin Ke's avatar
Guolin Ke committed
65
  auto& ref_mark = *mark;
Guolin Ke's avatar
Guolin Ke committed
66
  for (int i = 0; i < num_indices; ++i) {
Guolin Ke's avatar
Guolin Ke committed
67
    ref_mark[indices[i]] = true;
Guolin Ke's avatar
Guolin Ke committed
68
69
70
  }
}

Guolin Ke's avatar
Guolin Ke committed
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
std::vector<int> FixSampleIndices(const BinMapper* bin_mapper, int num_total_samples, int num_indices, const int* sample_indices, const double* sample_values) {
  std::vector<int> ret;
  if (bin_mapper->GetDefaultBin() == bin_mapper->GetMostFreqBin()) {
    return ret;
  }
  int i = 0, j = 0;
  while (i < num_total_samples) {
    if (j < num_indices && sample_indices[j] < i) {
      ++j;
    } else if (j < num_indices && sample_indices[j] == i) {
      if (bin_mapper->ValueToBin(sample_values[j]) != bin_mapper->GetMostFreqBin()) {
        ret.push_back(i);
      }
      ++i;
    } else {
      ret.push_back(i++);
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
92
93
94
95
std::vector<std::vector<int>> FindGroups(const std::vector<std::unique_ptr<BinMapper>>& bin_mappers,
                                         const std::vector<int>& find_order,
                                         int** sample_indices,
                                         const int* num_per_col,
96
                                         int num_sample_col,
97
                                         data_size_t total_sample_cnt,
Guolin Ke's avatar
Guolin Ke committed
98
                                         data_size_t num_data,
99
                                         bool is_use_gpu,
Guolin Ke's avatar
Guolin Ke committed
100
                                         bool is_sparse,
101
                                         std::vector<int8_t>* multi_val_group) {
Guolin Ke's avatar
Guolin Ke committed
102
  const int max_search_group = 100;
103
104
105
106
  const int max_bin_per_group = 256;
  const data_size_t single_val_max_conflict_cnt = static_cast<data_size_t>(total_sample_cnt / 10000);
  multi_val_group->clear();

Guolin Ke's avatar
Guolin Ke committed
107
108
109
  Random rand(num_data);
  std::vector<std::vector<int>> features_in_group;
  std::vector<std::vector<bool>> conflict_marks;
110
111
  std::vector<data_size_t> group_used_row_cnt;
  std::vector<data_size_t> group_total_data_cnt;
Guolin Ke's avatar
Guolin Ke committed
112
113
  std::vector<int> group_num_bin;

114
  // first round: fill the single val group
Guolin Ke's avatar
Guolin Ke committed
115
  for (auto fidx : find_order) {
116
    bool is_filtered_feature = fidx >= num_sample_col;
117
    const data_size_t cur_non_zero_cnt = is_filtered_feature ? 0 : num_per_col[fidx];
Guolin Ke's avatar
Guolin Ke committed
118
119
    std::vector<int> available_groups;
    for (int gid = 0; gid < static_cast<int>(features_in_group.size()); ++gid) {
120
121
122
      auto cur_num_bin = group_num_bin[gid] + bin_mappers[fidx]->num_bin() + (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0);
      if (group_total_data_cnt[gid] + cur_non_zero_cnt <= total_sample_cnt + single_val_max_conflict_cnt) {
        if (!is_use_gpu || cur_num_bin <= max_bin_per_group) {
Guolin Ke's avatar
Guolin Ke committed
123
124
          available_groups.push_back(gid);
        }
Guolin Ke's avatar
Guolin Ke committed
125
126
127
128
129
130
      }
    }
    std::vector<int> search_groups;
    if (!available_groups.empty()) {
      int last = static_cast<int>(available_groups.size()) - 1;
      auto indices = rand.Sample(last, std::min(last, max_search_group - 1));
131
      // always push the last group
Guolin Ke's avatar
Guolin Ke committed
132
133
134
135
136
      search_groups.push_back(available_groups.back());
      for (auto idx : indices) {
        search_groups.push_back(available_groups[idx]);
      }
    }
137
138
    int best_gid = -1;
    int best_conflict_cnt = -1;
Guolin Ke's avatar
Guolin Ke committed
139
    for (auto gid : search_groups) {
140
141
142
143
144
      const data_size_t rest_max_cnt = single_val_max_conflict_cnt - group_total_data_cnt[gid] + group_used_row_cnt[gid];
      const data_size_t cnt = is_filtered_feature ? 0 : GetConfilctCount(conflict_marks[gid], sample_indices[fidx], num_per_col[fidx], rest_max_cnt);
      if (cnt >= 0 && cnt <= rest_max_cnt && cnt <= cur_non_zero_cnt / 2) {
        best_gid = gid;
        best_conflict_cnt = cnt;
Guolin Ke's avatar
Guolin Ke committed
145
146
147
        break;
      }
    }
148
149
150
151
152
153
154
155
156
    if (best_gid >= 0) {
      features_in_group[best_gid].push_back(fidx);
      group_total_data_cnt[best_gid] += cur_non_zero_cnt;
      group_used_row_cnt[best_gid] += cur_non_zero_cnt - best_conflict_cnt;
      if (!is_filtered_feature) {
        MarkUsed(&conflict_marks[best_gid], sample_indices[fidx], num_per_col[fidx]);
      }
      group_num_bin[best_gid] += bin_mappers[fidx]->num_bin() + (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0);
    } else {
Guolin Ke's avatar
Guolin Ke committed
157
158
159
      features_in_group.emplace_back();
      features_in_group.back().push_back(fidx);
      conflict_marks.emplace_back(total_sample_cnt, false);
160
161
162
      if (!is_filtered_feature) {
        MarkUsed(&(conflict_marks.back()), sample_indices[fidx], num_per_col[fidx]);
      }
163
164
165
166
167
      group_total_data_cnt.emplace_back(cur_non_zero_cnt);
      group_used_row_cnt.emplace_back(cur_non_zero_cnt);
      group_num_bin.push_back(1 + bin_mappers[fidx]->num_bin() + (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0));
    }
  }
Guolin Ke's avatar
Guolin Ke committed
168
169
170
171
  if (!is_sparse) {
    multi_val_group->resize(features_in_group.size(), false);
    return features_in_group;
  }
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
  std::vector<int> second_round_features;
  std::vector<std::vector<int>> features_in_group2;
  std::vector<std::vector<bool>> conflict_marks2;

  const double dense_threshold = 0.4;
  for (int gid = 0; gid < static_cast<int>(features_in_group.size()); ++gid) {
    const double dense_rate = static_cast<double>(group_used_row_cnt[gid]) / total_sample_cnt;
    if (dense_rate >= dense_threshold) {
      features_in_group2.push_back(std::move(features_in_group[gid]));
      conflict_marks2.push_back(std::move(conflict_marks[gid]));
    } else {
      for (auto fidx : features_in_group[gid]) {
        second_round_features.push_back(fidx);
      }
    }
  }

  features_in_group = features_in_group2;
  conflict_marks = conflict_marks2;
  multi_val_group->resize(features_in_group.size(), false);
  if (!second_round_features.empty()) {
    features_in_group.emplace_back();
    conflict_marks.emplace_back(total_sample_cnt, false);
    bool is_multi_val = is_use_gpu ? true : false;
    int conflict_cnt = 0;
    for (auto fidx : second_round_features) {
      features_in_group.back().push_back(fidx);
      if (!is_multi_val) {
        const int rest_max_cnt = single_val_max_conflict_cnt - conflict_cnt;
        const auto cnt = GetConfilctCount(conflict_marks.back(), sample_indices[fidx], num_per_col[fidx], rest_max_cnt);
        conflict_cnt += cnt;
        if (cnt < 0 || conflict_cnt > single_val_max_conflict_cnt) {
          is_multi_val = true;
          continue;
        }
        MarkUsed(&(conflict_marks.back()), sample_indices[fidx], num_per_col[fidx]);
Guolin Ke's avatar
Guolin Ke committed
208
      }
Guolin Ke's avatar
Guolin Ke committed
209
    }
210
    multi_val_group->push_back(is_multi_val);
Guolin Ke's avatar
Guolin Ke committed
211
212
213
214
  }
  return features_in_group;
}

Guolin Ke's avatar
Guolin Ke committed
215
std::vector<std::vector<int>> FastFeatureBundling(const std::vector<std::unique_ptr<BinMapper>>& bin_mappers,
Guolin Ke's avatar
Guolin Ke committed
216
                                                  int** sample_indices,
Guolin Ke's avatar
Guolin Ke committed
217
                                                  double** sample_values,
Guolin Ke's avatar
Guolin Ke committed
218
                                                  const int* num_per_col,
219
                                                  int num_sample_col,
220
                                                  data_size_t total_sample_cnt,
Guolin Ke's avatar
Guolin Ke committed
221
222
                                                  const std::vector<int>& used_features,
                                                  data_size_t num_data,
223
                                                  bool is_use_gpu,
Guolin Ke's avatar
Guolin Ke committed
224
                                                  bool is_sparse,
225
226
                                                  std::vector<int8_t>* multi_val_group) {
  Common::FunctionTimer fun_timer("Dataset::FastFeatureBundling", global_timer);
Guolin Ke's avatar
Guolin Ke committed
227
  std::vector<size_t> feature_non_zero_cnt;
228
  feature_non_zero_cnt.reserve(used_features.size());
Guolin Ke's avatar
Guolin Ke committed
229
230
  // put dense feature first
  for (auto fidx : used_features) {
231
232
233
234
235
    if (fidx < num_sample_col) {
      feature_non_zero_cnt.emplace_back(num_per_col[fidx]);
    } else {
      feature_non_zero_cnt.emplace_back(0);
    }
Guolin Ke's avatar
Guolin Ke committed
236
237
238
  }
  // sort by non zero cnt
  std::vector<int> sorted_idx;
239
  sorted_idx.reserve(used_features.size());
240
  for (int i = 0; i < static_cast<int>(used_features.size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
241
242
243
    sorted_idx.emplace_back(i);
  }
  // sort by non zero cnt, bigger first
244
245
  std::stable_sort(sorted_idx.begin(), sorted_idx.end(),
                   [&feature_non_zero_cnt](int a, int b) {
Guolin Ke's avatar
Guolin Ke committed
246
247
248
249
    return feature_non_zero_cnt[a] > feature_non_zero_cnt[b];
  });

  std::vector<int> feature_order_by_cnt;
250
  feature_order_by_cnt.reserve(sorted_idx.size());
Guolin Ke's avatar
Guolin Ke committed
251
252
253
  for (auto sidx : sorted_idx) {
    feature_order_by_cnt.push_back(used_features[sidx]);
  }
254

Guolin Ke's avatar
Guolin Ke committed
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
  std::vector<std::vector<int>> tmp_indices;
  std::vector<int> tmp_num_per_col(num_sample_col, 0);
  for (auto fidx : used_features) {
    if (fidx >= num_sample_col) {
      continue;
    }
    auto ret = FixSampleIndices(bin_mappers[fidx].get(), static_cast<int>(total_sample_cnt), num_per_col[fidx], sample_indices[fidx], sample_values[fidx]);
    if (!ret.empty()) {
      tmp_indices.push_back(ret);
      tmp_num_per_col[fidx] = static_cast<int>(ret.size());
      sample_indices[fidx] = tmp_indices.back().data();
    } else {
      tmp_num_per_col[fidx] = num_per_col[fidx];
    }
  }
270
  std::vector<int8_t> group_is_multi_val, group_is_multi_val2;
Guolin Ke's avatar
Guolin Ke committed
271
272
  auto features_in_group = FindGroups(bin_mappers, used_features, sample_indices, tmp_num_per_col.data(), num_sample_col, total_sample_cnt, num_data, is_use_gpu, is_sparse, &group_is_multi_val);
  auto group2 = FindGroups(bin_mappers, feature_order_by_cnt, sample_indices, tmp_num_per_col.data(), num_sample_col, total_sample_cnt, num_data, is_use_gpu, is_sparse, &group_is_multi_val2);
273

Guolin Ke's avatar
Guolin Ke committed
274
275
  if (features_in_group.size() > group2.size()) {
    features_in_group = group2;
276
    group_is_multi_val = group_is_multi_val2;
Guolin Ke's avatar
Guolin Ke committed
277
278
  }
  // shuffle groups
279
280
  int num_group = static_cast<int>(features_in_group.size());
  Random tmp_rand(num_data);
Guolin Ke's avatar
Guolin Ke committed
281
282
  for (int i = 0; i < num_group - 1; ++i) {
    int j = tmp_rand.NextShort(i + 1, num_group);
283
    std::swap(features_in_group[i], features_in_group[j]);
284
    // Using std::swap for vector<bool> will cause the wrong result.
285
    std::swap(group_is_multi_val[i], group_is_multi_val[j]);
Guolin Ke's avatar
Guolin Ke committed
286
  }
287
288
  *multi_val_group = group_is_multi_val;
  return features_in_group;
Guolin Ke's avatar
Guolin Ke committed
289
290
}

Guolin Ke's avatar
Guolin Ke committed
291
void Dataset::Construct(
Guolin Ke's avatar
Guolin Ke committed
292
  std::vector<std::unique_ptr<BinMapper>>* bin_mappers,
293
  int num_total_features,
294
  const std::vector<std::vector<double>>& forced_bins,
Guolin Ke's avatar
Guolin Ke committed
295
  int** sample_non_zero_indices,
Guolin Ke's avatar
Guolin Ke committed
296
  double** sample_values,
Guolin Ke's avatar
Guolin Ke committed
297
  const int* num_per_col,
298
  int num_sample_col,
Guolin Ke's avatar
Guolin Ke committed
299
  size_t total_sample_cnt,
Guolin Ke's avatar
Guolin Ke committed
300
  const Config& io_config) {
301
302
  num_total_features_ = num_total_features;
  CHECK(num_total_features_ == static_cast<int>(bin_mappers->size()));
Guolin Ke's avatar
Guolin Ke committed
303
304
  // get num_features
  std::vector<int> used_features;
Guolin Ke's avatar
Guolin Ke committed
305
  auto& ref_bin_mappers = *bin_mappers;
Guolin Ke's avatar
Guolin Ke committed
306
  for (int i = 0; i < static_cast<int>(bin_mappers->size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
307
    if (ref_bin_mappers[i] != nullptr && !ref_bin_mappers[i]->is_trivial()) {
Guolin Ke's avatar
Guolin Ke committed
308
      used_features.emplace_back(i);
Guolin Ke's avatar
Guolin Ke committed
309
    }
Guolin Ke's avatar
Guolin Ke committed
310
  }
Guolin Ke's avatar
Guolin Ke committed
311
  if (used_features.empty()) {
312
    Log::Warning("There are no meaningful features, as all feature values are constant.");
Guolin Ke's avatar
Guolin Ke committed
313
  }
Guolin Ke's avatar
Guolin Ke committed
314
  auto features_in_group = NoGroup(used_features);
315
  std::vector<int8_t> group_is_multi_val(used_features.size(), 0);
316
  if (io_config.enable_bundle && !used_features.empty()) {
Guolin Ke's avatar
Guolin Ke committed
317
    features_in_group = FastFeatureBundling(*bin_mappers,
318
                                            sample_non_zero_indices, sample_values, num_per_col, num_sample_col, static_cast<data_size_t>(total_sample_cnt),
Guolin Ke's avatar
Guolin Ke committed
319
                                            used_features, num_data_, io_config.device_type == std::string("gpu"), io_config.is_enable_sparse, &group_is_multi_val);
Guolin Ke's avatar
Guolin Ke committed
320
321
  }

Guolin Ke's avatar
Guolin Ke committed
322
323
324
325
326
327
328
329
330
331
  num_features_ = 0;
  for (const auto& fs : features_in_group) {
    num_features_ += static_cast<int>(fs.size());
  }
  int cur_fidx = 0;
  used_feature_map_ = std::vector<int>(num_total_features_, -1);
  num_groups_ = static_cast<int>(features_in_group.size());
  real_feature_idx_.resize(num_features_);
  feature2group_.resize(num_features_);
  feature2subfeature_.resize(num_features_);
332
  int num_multi_val_group = 0;
Guolin Ke's avatar
Guolin Ke committed
333
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
334
335
336
  for (int i = 0; i < num_groups_; ++i) {
    auto cur_features = features_in_group[i];
    int cur_cnt_features = static_cast<int>(cur_features.size());
337
338
339
    if (group_is_multi_val[i]) {
      ++num_multi_val_group;
    }
Guolin Ke's avatar
Guolin Ke committed
340
341
342
343
344
345
346
347
    // get bin_mappers
    std::vector<std::unique_ptr<BinMapper>> cur_bin_mappers;
    for (int j = 0; j < cur_cnt_features; ++j) {
      int real_fidx = cur_features[j];
      used_feature_map_[real_fidx] = cur_fidx;
      real_feature_idx_[cur_fidx] = real_fidx;
      feature2group_[cur_fidx] = i;
      feature2subfeature_[cur_fidx] = j;
Guolin Ke's avatar
Guolin Ke committed
348
      cur_bin_mappers.emplace_back(ref_bin_mappers[real_fidx].release());
Guolin Ke's avatar
Guolin Ke committed
349
350
351
      if (cur_bin_mappers.back()->GetDefaultBin() != cur_bin_mappers.back()->GetMostFreqBin()) {
        feature_need_push_zeros_.push_back(cur_fidx);
      }
Guolin Ke's avatar
Guolin Ke committed
352
353
354
      ++cur_fidx;
    }
    feature_groups_.emplace_back(std::unique_ptr<FeatureGroup>(
355
      new FeatureGroup(cur_cnt_features, group_is_multi_val[i], &cur_bin_mappers, num_data_)));
Guolin Ke's avatar
Guolin Ke committed
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
  }
  feature_groups_.shrink_to_fit();
  group_bin_boundaries_.clear();
  uint64_t num_total_bin = 0;
  group_bin_boundaries_.push_back(num_total_bin);
  for (int i = 0; i < num_groups_; ++i) {
    num_total_bin += feature_groups_[i]->num_total_bin_;
    group_bin_boundaries_.push_back(num_total_bin);
  }
  int last_group = 0;
  group_feature_start_.reserve(num_groups_);
  group_feature_cnt_.reserve(num_groups_);
  group_feature_start_.push_back(0);
  group_feature_cnt_.push_back(1);
  for (int i = 1; i < num_features_; ++i) {
    const int group = feature2group_[i];
    if (group == last_group) {
      group_feature_cnt_.back() = group_feature_cnt_.back() + 1;
    } else {
      group_feature_start_.push_back(i);
      group_feature_cnt_.push_back(1);
      last_group = group;
    }
  }
Belinda Trotta's avatar
Belinda Trotta committed
380
381
382
383
384
385
  if (!io_config.max_bin_by_feature.empty()) {
    CHECK(static_cast<size_t>(num_total_features_) == io_config.max_bin_by_feature.size());
    CHECK(*(std::min_element(io_config.max_bin_by_feature.begin(), io_config.max_bin_by_feature.end())) > 1);
    max_bin_by_feature_.resize(num_total_features_);
    max_bin_by_feature_.assign(io_config.max_bin_by_feature.begin(), io_config.max_bin_by_feature.end());
  }
386
  forced_bin_bounds_ = forced_bins;
387
388
389
390
391
392
393
  max_bin_ = io_config.max_bin;
  min_data_in_bin_ = io_config.min_data_in_bin;
  bin_construct_sample_cnt_ = io_config.bin_construct_sample_cnt;
  use_missing_ = io_config.use_missing;
  zero_as_missing_ = io_config.zero_as_missing;
}

Guolin Ke's avatar
Guolin Ke committed
394
void Dataset::FinishLoad() {
Guolin Ke's avatar
Guolin Ke committed
395
  if (is_finish_load_) { return; }
396
397
  if (num_groups_ > 0) {
    for (int i = 0; i < num_groups_; ++i) {
398
      feature_groups_[i]->FinishLoad();
399
    }
Guolin Ke's avatar
Guolin Ke committed
400
  }
Guolin Ke's avatar
Guolin Ke committed
401
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
402
}
Guolin Ke's avatar
Guolin Ke committed
403

404
405
406
407
408
409
410
411
412

void PushDataToMultiValBin(
    int num_threads, data_size_t num_data,
    const std::vector<uint32_t> most_freq_bins,
    const std::vector<uint32_t> offsets,
    std::vector<std::vector<std::unique_ptr<BinIterator>>>& iters,
    MultiValBin* ret) {
  Common::FunctionTimer fun_time("Dataset::PushDataToMultiValBin",
                                 global_timer);
413
  const data_size_t min_block_size = 4096;
414
415
  const int n_block =
      std::min(num_threads, (num_data + min_block_size - 1) / min_block_size);
416
417
  const data_size_t block_size = (num_data + n_block - 1) / n_block;
  if (ret->IsSparse()) {
418
#pragma omp parallel for schedule(static)
419
420
    for (int tid = 0; tid < n_block; ++tid) {
      std::vector<uint32_t> cur_data;
421
      cur_data.reserve(most_freq_bins.size());
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
      data_size_t start = tid * block_size;
      data_size_t end = std::min(num_data, start + block_size);
      for (size_t j = 0; j < most_freq_bins.size(); ++j) {
        iters[tid][j]->Reset(start);
      }
      for (data_size_t i = start; i < end; ++i) {
        cur_data.clear();
        for (size_t j = 0; j < most_freq_bins.size(); ++j) {
          auto cur_bin = iters[tid][j]->Get(i);
          if (cur_bin == most_freq_bins[j]) {
            continue;
          }
          cur_bin += offsets[j];
          if (most_freq_bins[j] == 0) {
            cur_bin -= 1;
          }
          cur_data.push_back(cur_bin);
        }
        ret->PushOneRow(tid, i, cur_data);
      }
    }
  } else {
444
#pragma omp parallel for schedule(static)
445
    for (int tid = 0; tid < n_block; ++tid) {
446
      std::vector<uint32_t> cur_data(most_freq_bins.size(), 0);
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
      data_size_t start = tid * block_size;
      data_size_t end = std::min(num_data, start + block_size);
      for (size_t j = 0; j < most_freq_bins.size(); ++j) {
        iters[tid][j]->Reset(start);
      }
      for (data_size_t i = start; i < end; ++i) {
        for (size_t j = 0; j < most_freq_bins.size(); ++j) {
          auto cur_bin = iters[tid][j]->Get(i);
          if (cur_bin == most_freq_bins[j]) {
            cur_bin = 0;
          } else {
            cur_bin += offsets[j];
            if (most_freq_bins[j] == 0) {
              cur_bin -= 1;
            }
          }
463
          cur_data[j] = cur_bin;
464
465
466
467
468
469
470
471
        }
        ret->PushOneRow(tid, i, cur_data);
      }
    }
  }
}

MultiValBin* Dataset::GetMultiBinFromSparseFeatures() const {
472
473
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromSparseFeatures",
                                 global_timer);
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
  int multi_group_id = -1;
  for (int i = 0; i < num_groups_; ++i) {
    if (feature_groups_[i]->is_multi_val_) {
      if (multi_group_id < 0) {
        multi_group_id = i;
      } else {
        Log::Fatal("Bug. There should be only one multi-val group.");
      }
    }
  }
  if (multi_group_id < 0) {
    return nullptr;
  }
  const auto& offsets = feature_groups_[multi_group_id]->bin_offsets_;
  const int num_feature = feature_groups_[multi_group_id]->num_feature_;
  int num_threads = 1;
490
491
492
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
493
494
495
496
497
498

  std::vector<std::vector<std::unique_ptr<BinIterator>>> iters(num_threads);
  std::vector<uint32_t> most_freq_bins;
  double sum_sparse_rate = 0;
  for (int i = 0; i < num_feature; ++i) {
    for (int tid = 0; tid < num_threads; ++tid) {
499
500
      iters[tid].emplace_back(
          feature_groups_[multi_group_id]->SubFeatureIterator(i));
501
    }
502
503
504
505
    most_freq_bins.push_back(
        feature_groups_[multi_group_id]->bin_mappers_[i]->GetMostFreqBin());
    sum_sparse_rate +=
        feature_groups_[multi_group_id]->bin_mappers_[i]->sparse_rate();
506
507
  }
  sum_sparse_rate /= num_feature;
508
509
  Log::Debug("Dataset::GetMultiBinFromSparseFeatures: sparse rate %f",
             sum_sparse_rate);
510
  std::unique_ptr<MultiValBin> ret;
511
512
513
514
  ret.reset(MultiValBin::CreateMultiValBin(num_data_, offsets.back(),
                                           num_feature, sum_sparse_rate));
  PushDataToMultiValBin(num_threads, num_data_, most_freq_bins, offsets, iters,
                        ret.get());
515
516
517
518
519
  ret->FinishLoad();
  return ret.release();
}

MultiValBin* Dataset::GetMultiBinFromAllFeatures() const {
520
521
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromAllFeatures",
                                 global_timer);
522
  int num_threads = 1;
523
524
525
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
  double sum_dense_ratio = 0;

  std::unique_ptr<MultiValBin> ret;
  std::vector<std::vector<std::unique_ptr<BinIterator>>> iters(num_threads);
  std::vector<uint32_t> most_freq_bins;
  std::vector<uint32_t> offsets;
  int num_total_bin = 1;
  offsets.push_back(num_total_bin);
  for (int gid = 0; gid < num_groups_; ++gid) {
    if (feature_groups_[gid]->is_multi_val_) {
      for (int fid = 0; fid < feature_groups_[gid]->num_feature_; ++fid) {
        const auto& bin_mapper = feature_groups_[gid]->bin_mappers_[fid];
        sum_dense_ratio += 1.0f - bin_mapper->sparse_rate();
        most_freq_bins.push_back(bin_mapper->GetMostFreqBin());
        num_total_bin += bin_mapper->num_bin();
        if (most_freq_bins.back() == 0) {
          num_total_bin -= 1;
        }
        offsets.push_back(num_total_bin);
        for (int tid = 0; tid < num_threads; ++tid) {
546
547
          iters[tid].emplace_back(
              feature_groups_[gid]->SubFeatureIterator(fid));
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
        }
      }
    } else {
      most_freq_bins.push_back(0);
      num_total_bin += feature_groups_[gid]->bin_offsets_.back() - 1;
      for (int tid = 0; tid < num_threads; ++tid) {
        iters[tid].emplace_back(feature_groups_[gid]->FeatureGroupIterator());
      }
      offsets.push_back(num_total_bin);
      for (int fid = 0; fid < feature_groups_[gid]->num_feature_; ++fid) {
        const auto& bin_mapper = feature_groups_[gid]->bin_mappers_[fid];
        sum_dense_ratio += 1.0f - bin_mapper->sparse_rate();
      }
    }
  }
  sum_dense_ratio /= static_cast<double>(most_freq_bins.size());
564
565
566
567
568
569
570
  Log::Debug("Dataset::GetMultiBinFromAllFeatures: sparse rate %f",
             1.0 - sum_dense_ratio);
  ret.reset(MultiValBin::CreateMultiValBin(
      num_data_, num_total_bin, static_cast<int>(most_freq_bins.size()),
      1.0 - sum_dense_ratio));
  PushDataToMultiValBin(num_threads, num_data_, most_freq_bins, offsets, iters,
                        ret.get());
571
572
573
574
  ret->FinishLoad();
  return ret.release();
}

575
576
577
578
579
580
TrainingTempState* Dataset::TestMultiThreadingMethod(
    score_t* gradients, score_t* hessians,
    const std::vector<int8_t>& is_feature_used, bool is_constant_hessian,
    bool force_colwise, bool force_rowwise, bool* is_hist_col_wise) const {
  Common::FunctionTimer fun_timer("Dataset::TestMultiThreadingMethod",
                                  global_timer);
581
  if (force_colwise && force_rowwise) {
582
583
584
    Log::Fatal(
        "Cannot set both `force_col_wise` and `force_row_wise` to `true` at "
        "the same time");
585
586
587
588
589
590
  }
  if (num_groups_ <= 0) {
    return nullptr;
  }
  if (force_colwise) {
    *is_hist_col_wise = true;
591
592
593
    TrainingTempState* temp_state = new TrainingTempState();
    temp_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
    return temp_state;
594
595
  } else if (force_rowwise) {
    *is_hist_col_wise = false;
596
597
598
    TrainingTempState* temp_state = new TrainingTempState();
    temp_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    return temp_state;
599
600
601
  } else {
    std::unique_ptr<MultiValBin> sparse_bin;
    std::unique_ptr<MultiValBin> all_bin;
602
603
604
605
606
607
608
    std::unique_ptr<TrainingTempState> colwise_state;
    std::unique_ptr<TrainingTempState> rowwise_state;
    colwise_state.reset(new TrainingTempState());
    rowwise_state.reset(new TrainingTempState());

    std::chrono::duration<double, std::milli> col_wise_init_time,
        row_wise_init_time;
609
    auto start_time = std::chrono::steady_clock::now();
610
    colwise_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
611
    col_wise_init_time = std::chrono::steady_clock::now() - start_time;
612

613
    start_time = std::chrono::steady_clock::now();
614
615
616
617
    rowwise_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>
        hist_data(NumTotalBin() * 2);

618
    row_wise_init_time = std::chrono::steady_clock::now() - start_time;
619
620
621
622
623
    Log::Debug(
        "init for col-wise cost %f seconds, init for row-wise cost %f seconds",
        col_wise_init_time * 1e-3, row_wise_init_time * 1e-3);
    InitTrain(is_feature_used, true, colwise_state.get());
    InitTrain(is_feature_used, false, rowwise_state.get());
624
    std::chrono::duration<double, std::milli> col_wise_time, row_wise_time;
625
    start_time = std::chrono::steady_clock::now();
626
627
628
    ConstructHistograms(is_feature_used, nullptr, num_data_, gradients,
                        hessians, gradients, hessians, is_constant_hessian,
                        true, colwise_state.get(), hist_data.data());
629
630
    col_wise_time = std::chrono::steady_clock::now() - start_time;
    start_time = std::chrono::steady_clock::now();
631
632
633
    ConstructHistogramsMultiVal(nullptr, num_data_, gradients, hessians,
                                is_constant_hessian, rowwise_state.get(),
                                hist_data.data());
634
    row_wise_time = std::chrono::steady_clock::now() - start_time;
635
    Log::Debug("col-wise cost %f seconds, row-wise cost %f seconds",
636
               col_wise_time * 1e-3, row_wise_time * 1e-3);
637
638
    if (col_wise_time < row_wise_time) {
      *is_hist_col_wise = true;
639
640
      auto overhead_cost = row_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
641
642
          "Auto-choosing col-wise multi-threading, the overhead of testing was "
          "%f "
643
          "seconds.\nYou can set `force_col_wise=true` to remove the "
644
645
          "overhead.",
          overhead_cost * 1e-3);
646
      return colwise_state.release();
647
648
    } else {
      *is_hist_col_wise = false;
649
650
      auto overhead_cost = col_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
651
652
          "Auto-choosing row-wise multi-threading, the overhead of testing was "
          "%f "
653
654
          "seconds.\nYou can set `force_row_wise=true` to remove the "
          "overhead.\nAnd if memory is not enough, you can set "
655
656
          "`force_col_wise=true`.",
          overhead_cost * 1e-3);
657
      if (rowwise_state->multi_val_bin->IsSparse()) {
658
        Log::Debug("Using Sparse Multi-Val Bin");
659
      } else {
660
        Log::Debug("Using Dense Multi-Val Bin");
661
      }
662
      return rowwise_state.release();
663
664
665
666
    }
  }
}

667
void Dataset::CopyFeatureMapperFrom(const Dataset* dataset) {
Guolin Ke's avatar
Guolin Ke committed
668
  feature_groups_.clear();
Guolin Ke's avatar
Guolin Ke committed
669
  num_features_ = dataset->num_features_;
Guolin Ke's avatar
Guolin Ke committed
670
  num_groups_ = dataset->num_groups_;
Guolin Ke's avatar
Guolin Ke committed
671
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
672
  for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
673
    feature_groups_.emplace_back(new FeatureGroup(*dataset->feature_groups_[i], num_data_));
Guolin Ke's avatar
Guolin Ke committed
674
  }
Guolin Ke's avatar
Guolin Ke committed
675
  feature_groups_.shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
676
677
678
  used_feature_map_ = dataset->used_feature_map_;
  num_total_features_ = dataset->num_total_features_;
  feature_names_ = dataset->feature_names_;
Guolin Ke's avatar
Guolin Ke committed
679
  label_idx_ = dataset->label_idx_;
Guolin Ke's avatar
Guolin Ke committed
680
681
682
683
684
685
  real_feature_idx_ = dataset->real_feature_idx_;
  feature2group_ = dataset->feature2group_;
  feature2subfeature_ = dataset->feature2subfeature_;
  group_bin_boundaries_ = dataset->group_bin_boundaries_;
  group_feature_start_ = dataset->group_feature_start_;
  group_feature_cnt_ = dataset->group_feature_cnt_;
686
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
687
  feature_need_push_zeros_ = dataset->feature_need_push_zeros_;
Guolin Ke's avatar
Guolin Ke committed
688
689
690
691
692
693
694
695
696
}

void Dataset::CreateValid(const Dataset* dataset) {
  feature_groups_.clear();
  num_features_ = dataset->num_features_;
  num_groups_ = num_features_;
  feature2group_.clear();
  feature2subfeature_.clear();
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
697
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
698
699
700
  for (int i = 0; i < num_features_; ++i) {
    std::vector<std::unique_ptr<BinMapper>> bin_mappers;
    bin_mappers.emplace_back(new BinMapper(*(dataset->FeatureBinMapper(i))));
Guolin Ke's avatar
Guolin Ke committed
701
702
703
    if (bin_mappers.back()->GetDefaultBin() != bin_mappers.back()->GetMostFreqBin()) {
      feature_need_push_zeros_.push_back(i);
    }
704
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
    feature2group_.push_back(i);
    feature2subfeature_.push_back(0);
  }

  feature_groups_.shrink_to_fit();
  used_feature_map_ = dataset->used_feature_map_;
  num_total_features_ = dataset->num_total_features_;
  feature_names_ = dataset->feature_names_;
  label_idx_ = dataset->label_idx_;
  real_feature_idx_ = dataset->real_feature_idx_;
  group_bin_boundaries_.clear();
  uint64_t num_total_bin = 0;
  group_bin_boundaries_.push_back(num_total_bin);
  for (int i = 0; i < num_groups_; ++i) {
    num_total_bin += feature_groups_[i]->num_total_bin_;
    group_bin_boundaries_.push_back(num_total_bin);
  }
  int last_group = 0;
  group_feature_start_.reserve(num_groups_);
  group_feature_cnt_.reserve(num_groups_);
  group_feature_start_.push_back(0);
  group_feature_cnt_.push_back(1);
  for (int i = 1; i < num_features_; ++i) {
    const int group = feature2group_[i];
    if (group == last_group) {
      group_feature_cnt_.back() = group_feature_cnt_.back() + 1;
    } else {
      group_feature_start_.push_back(i);
      group_feature_cnt_.push_back(1);
      last_group = group;
    }
  }
737
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
738
739
}

Guolin Ke's avatar
Guolin Ke committed
740
741
742
void Dataset::ReSize(data_size_t num_data) {
  if (num_data_ != num_data) {
    num_data_ = num_data;
743
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
744
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
745
    for (int group = 0; group < num_groups_; ++group) {
746
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
747
      feature_groups_[group]->ReSize(num_data_);
748
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
749
    }
750
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
751
752
753
754
755
  }
}

void Dataset::CopySubset(const Dataset* fullset, const data_size_t* used_indices, data_size_t num_used_indices, bool need_meta_data) {
  CHECK(num_used_indices == num_data_);
756
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
757
  #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
758
  for (int group = 0; group < num_groups_; ++group) {
759
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
760
    feature_groups_[group]->CopySubset(fullset->feature_groups_[group].get(), used_indices, num_used_indices);
761
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
762
  }
763
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
764
  if (need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
765
    metadata_.Init(fullset->metadata_, used_indices, num_used_indices);
Guolin Ke's avatar
Guolin Ke committed
766
  }
Guolin Ke's avatar
Guolin Ke committed
767
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
768
769
}

770
bool Dataset::SetFloatField(const char* field_name, const float* field_data, data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
771
772
773
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
774
    #ifdef LABEL_T_USE_DOUBLE
775
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
776
    #else
777
    metadata_.SetLabel(field_data, num_element);
778
    #endif
Guolin Ke's avatar
Guolin Ke committed
779
  } else if (name == std::string("weight") || name == std::string("weights")) {
780
    #ifdef LABEL_T_USE_DOUBLE
781
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
782
    #else
783
    metadata_.SetWeights(field_data, num_element);
784
    #endif
Guolin Ke's avatar
Guolin Ke committed
785
786
787
788
789
790
791
792
793
794
  } else {
    return false;
  }
  return true;
}

bool Dataset::SetDoubleField(const char* field_name, const double* field_data, data_size_t num_element) {
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
795
    metadata_.SetInitScore(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
796
  } else {
797
    return false;
Guolin Ke's avatar
Guolin Ke committed
798
  }
799
  return true;
Guolin Ke's avatar
Guolin Ke committed
800
801
}

802
803
804
805
bool Dataset::SetIntField(const char* field_name, const int* field_data, data_size_t num_element) {
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
Guolin Ke's avatar
Guolin Ke committed
806
    metadata_.SetQuery(field_data, num_element);
807
808
809
810
811
812
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
813
bool Dataset::GetFloatField(const char* field_name, data_size_t* out_len, const float** out_ptr) {
814
815
816
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
817
    #ifdef LABEL_T_USE_DOUBLE
818
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
819
    #else
820
821
    *out_ptr = metadata_.label();
    *out_len = num_data_;
822
    #endif
823
  } else if (name == std::string("weight") || name == std::string("weights")) {
824
    #ifdef LABEL_T_USE_DOUBLE
825
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
826
    #else
827
828
    *out_ptr = metadata_.weights();
    *out_len = num_data_;
829
    #endif
Guolin Ke's avatar
Guolin Ke committed
830
831
832
833
834
835
836
837
838
839
  } else {
    return false;
  }
  return true;
}

bool Dataset::GetDoubleField(const char* field_name, data_size_t* out_len, const double** out_ptr) {
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
840
    *out_ptr = metadata_.init_score();
Guolin Ke's avatar
Guolin Ke committed
841
    *out_len = static_cast<data_size_t>(metadata_.num_init_score());
842
  } else {
843
844
    return false;
  }
845
  return true;
846
847
}

Guolin Ke's avatar
Guolin Ke committed
848
bool Dataset::GetIntField(const char* field_name, data_size_t* out_len, const int** out_ptr) {
849
850
851
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
852
    *out_ptr = metadata_.query_boundaries();
Guolin Ke's avatar
Guolin Ke committed
853
    *out_len = metadata_.num_queries() + 1;
Guolin Ke's avatar
Guolin Ke committed
854
855
856
  } else {
    return false;
  }
857
  return true;
858
859
}

Guolin Ke's avatar
Guolin Ke committed
860
void Dataset::SaveBinaryFile(const char* bin_filename) {
Guolin Ke's avatar
Guolin Ke committed
861
  if (bin_filename != nullptr
Guolin Ke's avatar
Guolin Ke committed
862
      && std::string(bin_filename) == data_filename_) {
863
    Log::Warning("Bianry file %s already exists", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
864
865
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
866
  // if not pass a filename, just append ".bin" of original file
Guolin Ke's avatar
Guolin Ke committed
867
  std::string bin_filename_str(data_filename_);
Guolin Ke's avatar
Guolin Ke committed
868
869
870
871
  if (bin_filename == nullptr || bin_filename[0] == '\0') {
    bin_filename_str.append(".bin");
    bin_filename = bin_filename_str.c_str();
  }
Guolin Ke's avatar
Guolin Ke committed
872
  bool is_file_existed = false;
873
874

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
875
    is_file_existed = true;
876
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
877
  }
Guolin Ke's avatar
Guolin Ke committed
878

Guolin Ke's avatar
Guolin Ke committed
879
  if (!is_file_existed) {
880
881
    auto writer = VirtualFileWriter::Make(bin_filename);
    if (!writer->Init()) {
Guolin Ke's avatar
Guolin Ke committed
882
      Log::Fatal("Cannot write binary data to %s ", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
883
    }
884
    Log::Info("Saving data to binary file %s", bin_filename);
885
    size_t size_of_token = std::strlen(binary_file_token);
886
    writer->Write(binary_file_token, size_of_token);
Guolin Ke's avatar
Guolin Ke committed
887
    // get size of header
Guolin Ke's avatar
Guolin Ke committed
888
    size_t size_of_header = sizeof(num_data_) + sizeof(num_features_) + sizeof(num_total_features_)
889
      + sizeof(int) * num_total_features_ + sizeof(label_idx_) + sizeof(num_groups_)
890
891
      + 3 * sizeof(int) * num_features_ + sizeof(uint64_t) * (num_groups_ + 1) + 2 * sizeof(int) * num_groups_
      + sizeof(int32_t) * num_total_features_ + sizeof(int) * 3 + sizeof(bool) * 2;
892
893
894
895
    // size of feature names
    for (int i = 0; i < num_total_features_; ++i) {
      size_of_header += feature_names_[i].size() + sizeof(int);
    }
896
897
898
899
    // size of forced bins
    for (int i = 0; i < num_total_features_; ++i) {
      size_of_header += forced_bin_bounds_[i].size() * sizeof(double) + sizeof(int);
    }
900
    writer->Write(&size_of_header, sizeof(size_of_header));
Guolin Ke's avatar
Guolin Ke committed
901
    // write header
902
903
904
905
    writer->Write(&num_data_, sizeof(num_data_));
    writer->Write(&num_features_, sizeof(num_features_));
    writer->Write(&num_total_features_, sizeof(num_total_features_));
    writer->Write(&label_idx_, sizeof(label_idx_));
906
907
908
909
910
    writer->Write(&max_bin_, sizeof(max_bin_));
    writer->Write(&bin_construct_sample_cnt_, sizeof(bin_construct_sample_cnt_));
    writer->Write(&min_data_in_bin_, sizeof(min_data_in_bin_));
    writer->Write(&use_missing_, sizeof(use_missing_));
    writer->Write(&zero_as_missing_, sizeof(zero_as_missing_));
911
912
913
914
915
916
917
918
    writer->Write(used_feature_map_.data(), sizeof(int) * num_total_features_);
    writer->Write(&num_groups_, sizeof(num_groups_));
    writer->Write(real_feature_idx_.data(), sizeof(int) * num_features_);
    writer->Write(feature2group_.data(), sizeof(int) * num_features_);
    writer->Write(feature2subfeature_.data(), sizeof(int) * num_features_);
    writer->Write(group_bin_boundaries_.data(), sizeof(uint64_t) * (num_groups_ + 1));
    writer->Write(group_feature_start_.data(), sizeof(int) * num_groups_);
    writer->Write(group_feature_cnt_.data(), sizeof(int) * num_groups_);
Belinda Trotta's avatar
Belinda Trotta committed
919
920
921
922
923
924
925
    if (max_bin_by_feature_.empty()) {
      ArrayArgs<int32_t>::Assign(&max_bin_by_feature_, -1, num_total_features_);
    }
    writer->Write(max_bin_by_feature_.data(), sizeof(int32_t) * num_total_features_);
    if (ArrayArgs<int32_t>::CheckAll(max_bin_by_feature_, -1)) {
      max_bin_by_feature_.clear();
    }
926
927
928
    // write feature names
    for (int i = 0; i < num_total_features_; ++i) {
      int str_len = static_cast<int>(feature_names_[i].size());
929
      writer->Write(&str_len, sizeof(int));
930
      const char* c_str = feature_names_[i].c_str();
931
      writer->Write(c_str, sizeof(char) * str_len);
932
    }
933
934
935
936
    // write forced bins
    for (int i = 0; i < num_total_features_; ++i) {
      int num_bounds = static_cast<int>(forced_bin_bounds_[i].size());
      writer->Write(&num_bounds, sizeof(int));
937

938
939
940
941
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
942

Guolin Ke's avatar
Guolin Ke committed
943
944
    // get size of meta data
    size_t size_of_metadata = metadata_.SizesInByte();
945
    writer->Write(&size_of_metadata, sizeof(size_of_metadata));
Guolin Ke's avatar
Guolin Ke committed
946
    // write meta data
947
    metadata_.SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
948
949

    // write feature data
Guolin Ke's avatar
Guolin Ke committed
950
    for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
951
      // get size of feature
Guolin Ke's avatar
Guolin Ke committed
952
      size_t size_of_feature = feature_groups_[i]->SizesInByte();
953
      writer->Write(&size_of_feature, sizeof(size_of_feature));
Guolin Ke's avatar
Guolin Ke committed
954
      // write feature
955
      feature_groups_[i]->SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
956
957
958
959
    }
  }
}

960
void Dataset::DumpTextFile(const char* text_filename) {
Guolin Ke's avatar
Guolin Ke committed
961
962
963
964
965
966
  FILE* file = NULL;
#if _MSC_VER
  fopen_s(&file, text_filename, "wt");
#else
  file = fopen(text_filename, "wt");
#endif
967
968
969
970
971
  fprintf(file, "num_features: %d\n", num_features_);
  fprintf(file, "num_total_features: %d\n", num_total_features_);
  fprintf(file, "num_groups: %d\n", num_groups_);
  fprintf(file, "num_data: %d\n", num_data_);
  fprintf(file, "feature_names: ");
972
  for (auto n : feature_names_) {
973
974
    fprintf(file, "%s, ", n.c_str());
  }
Belinda Trotta's avatar
Belinda Trotta committed
975
976
977
978
  fprintf(file, "\nmax_bin_by_feature: ");
  for (auto i : max_bin_by_feature_) {
    fprintf(file, "%d, ", i);
  }
979
  fprintf(file, "\n");
980
  for (auto n : feature_names_) {
981
982
    fprintf(file, "%s, ", n.c_str());
  }
983
984
985
986
987
988
989
  fprintf(file, "\nforced_bins: ");
  for (int i = 0; i < num_total_features_; ++i) {
    fprintf(file, "\nfeature %d: ", i);
    for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
      fprintf(file, "%lf, ", forced_bin_bounds_[i][j]);
    }
  }
990
991
  std::vector<std::unique_ptr<BinIterator>> iterators;
  iterators.reserve(num_features_);
992
  for (int j = 0; j < num_features_; ++j) {
993
994
995
996
    auto group_idx = feature2group_[j];
    auto sub_idx = feature2subfeature_[j];
    iterators.emplace_back(feature_groups_[group_idx]->SubFeatureIterator(sub_idx));
  }
997
  for (data_size_t i = 0; i < num_data_; ++i) {
998
    fprintf(file, "\n");
999
    for (int j = 0; j < num_total_features_; ++j) {
1000
      auto inner_feature_idx = used_feature_map_[j];
1001
1002
      if (inner_feature_idx < 0) {
        fprintf(file, "NA, ");
1003
      } else {
Guolin Ke's avatar
Guolin Ke committed
1004
        fprintf(file, "%d, ", iterators[inner_feature_idx]->Get(i));
1005
1006
1007
1008
1009
1010
      }
    }
  }
  fclose(file);
}

1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151

void Dataset::InitTrain(const std::vector<int8_t>& is_feature_used,
                        bool is_colwise, TrainingTempState* temp_state) const {
  Common::FunctionTimer fun_time("Dataset::InitTrain", global_timer);
  temp_state->use_subfeature = false;
  if (temp_state->multi_val_bin == nullptr) {
    return;
  }
  global_timer.Start("Dataset::InitTrain.Prep");
  double sum_used_dense_ratio = 0.0;
  double sum_dense_ratio = 0.0;
  int num_used = 0;
  int total = 0;
  std::vector<int> used_feature_index;
  for (int i = 0; i < num_groups_; ++i) {
    int f_start = group_feature_start_[i];
    if (feature_groups_[i]->is_multi_val_ ) {
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        const auto dense_rate =
            1.0 - feature_groups_[i]->bin_mappers_[j]->sparse_rate();
        if (is_feature_used[f_start + j]) {
          ++num_used;
          used_feature_index.push_back(total);
          sum_used_dense_ratio += dense_rate;
        }
        sum_dense_ratio += dense_rate;
        ++total;
      }
    } else if (!is_colwise) {
      bool is_group_used = false;
      double dense_rate = 0;
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        if (is_feature_used[f_start + j]) {
          is_group_used = true;
        }
        dense_rate += 1.0 - feature_groups_[i]->bin_mappers_[j]->sparse_rate();
      }
      if (is_group_used) {
        ++num_used;
        used_feature_index.push_back(total);
        sum_used_dense_ratio += dense_rate;
      }
      sum_dense_ratio += dense_rate;
      ++total;
    }
  }
  global_timer.Stop("Dataset::InitTrain.Prep");
  const double k_subfeature_threshold = 0.6;
  if (sum_used_dense_ratio >= sum_dense_ratio * k_subfeature_threshold) {
    return;
  }
  temp_state->use_subfeature = true;
  global_timer.Start("Dataset::InitTrain.Prep");
  std::vector<uint32_t> upper_bound;
  std::vector<uint32_t> lower_bound;
  std::vector<uint32_t> delta;
  temp_state->hist_move_src.clear();
  temp_state->hist_move_dest.clear();
  temp_state->hist_move_size.clear();

  int num_total_bin = 1;
  int new_num_total_bin = 1;

  for (int i = 0; i < num_groups_; ++i) {
    int f_start = group_feature_start_[i];
    if (feature_groups_[i]->is_multi_val_) {
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        const auto& bin_mapper = feature_groups_[i]->bin_mappers_[j];
        int cur_num_bin = bin_mapper->num_bin();
        if (bin_mapper->GetMostFreqBin() == 0) {
          cur_num_bin -= 1;
        }
        num_total_bin += cur_num_bin;
        if (is_feature_used[f_start + j]) {
          new_num_total_bin += cur_num_bin;

          lower_bound.push_back(num_total_bin - cur_num_bin);
          upper_bound.push_back(num_total_bin);
          
          temp_state->hist_move_src.push_back(
              (new_num_total_bin - cur_num_bin) * 2);
          temp_state->hist_move_dest.push_back((num_total_bin - cur_num_bin) *
                                               2);
          temp_state->hist_move_size.push_back(cur_num_bin * 2);
          delta.push_back(num_total_bin - new_num_total_bin);
        }
      }
    } else if (!is_colwise) {
      bool is_group_used = false;
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        if (is_feature_used[f_start + j]) {
          is_group_used = true;
          break;
        }
      }
      int cur_num_bin = feature_groups_[i]->bin_offsets_.back() - 1;
      num_total_bin += cur_num_bin;
      if (is_group_used) {
        new_num_total_bin += cur_num_bin;

        lower_bound.push_back(num_total_bin - cur_num_bin);
        upper_bound.push_back(num_total_bin);

        temp_state->hist_move_src.push_back((new_num_total_bin - cur_num_bin) *
                                            2);
        temp_state->hist_move_dest.push_back((num_total_bin - cur_num_bin) * 2);
        temp_state->hist_move_size.push_back(cur_num_bin * 2);
        delta.push_back(num_total_bin - new_num_total_bin);
      }
    }
  }
  // avoid out of range
  lower_bound.push_back(num_total_bin);
  upper_bound.push_back(num_total_bin);
  global_timer.Stop("Dataset::InitTrain.Prep");
  global_timer.Start("Dataset::InitTrain.Resize");
  if (temp_state->multi_val_bin_subfeature == nullptr) {
    temp_state->multi_val_bin_subfeature.reset(
        temp_state->multi_val_bin->CreateLike(new_num_total_bin, num_used,
                                              sum_used_dense_ratio));
  } else {
    temp_state->multi_val_bin_subfeature->ReSizeForSubFeature(
        new_num_total_bin, num_used, sum_used_dense_ratio);
  }
  global_timer.Stop("Dataset::InitTrain.Resize");
  global_timer.Start("Dataset::InitTrain.CopySubFeature");
  temp_state->multi_val_bin_subfeature->CopySubFeature(
      temp_state->multi_val_bin.get(), used_feature_index, lower_bound,
      upper_bound, delta);
  global_timer.Stop("Dataset::InitTrain.CopySubFeature");
}

void Dataset::ConstructHistogramsMultiVal(
    const data_size_t* data_indices, data_size_t num_data,
    const score_t* gradients, const score_t* hessians, bool is_constant_hessian,
    TrainingTempState* temp_state, hist_t* hist_data) const {
  Common::FunctionTimer fun_time("Dataset::ConstructHistogramsMultiVal",
                                 global_timer);
  const auto multi_val_bin = temp_state->use_subfeature
                                 ? temp_state->multi_val_bin_subfeature.get()
                                 : temp_state->multi_val_bin.get();
1152
1153
1154
  if (multi_val_bin == nullptr) {
    return;
  }
1155
  int num_threads = 1;
1156
1157
1158
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
1159
1160
1161

  global_timer.Start("Dataset::sparse_bin_histogram");
  const int num_bin = multi_val_bin->num_bin();
1162
1163
  const int num_bin_aligned =
      (num_bin + kAlignedSize - 1) / kAlignedSize * kAlignedSize;
1164
  const int min_data_block_size = 1024;
1165
1166
  const int n_data_block = std::min(
      num_threads, (num_data + min_data_block_size - 1) / min_data_block_size);
1167
1168
  const int data_block_size = (num_data + n_data_block - 1) / n_data_block;

1169
1170
1171
1172
  const size_t buf_size =
      static_cast<size_t>(n_data_block - 1) * num_bin_aligned * 2;
  if (temp_state->hist_buf.size() < buf_size) {
    temp_state->hist_buf.resize(buf_size);
1173
  }
1174
1175
1176
1177
1178
  auto origin_hist_data = hist_data;
  if (temp_state->use_subfeature) {
    hist_data = temp_state->TempBuf();
  }
#pragma omp parallel for schedule(static)
1179
1180
1181
1182
1183
  for (int tid = 0; tid < n_data_block; ++tid) {
    data_size_t start = tid * data_block_size;
    data_size_t end = std::min(start + data_block_size, num_data);
    auto data_ptr = hist_data;
    if (tid > 0) {
1184
1185
      data_ptr = temp_state->hist_buf.data() +
                 static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1186
    }
1187
    std::memset(reinterpret_cast<void*>(data_ptr), 0, num_bin * kHistEntrySize);
1188
1189
    if (data_indices != nullptr && num_data < num_data_) {
      if (!is_constant_hessian) {
1190
1191
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          hessians, data_ptr);
1192
      } else {
1193
1194
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          data_ptr);
1195
1196
1197
      }
    } else {
      if (!is_constant_hessian) {
1198
1199
        multi_val_bin->ConstructHistogram(start, end, gradients, hessians,
                                          data_ptr);
1200
1201
1202
1203
1204
1205
1206
1207
1208
      } else {
        multi_val_bin->ConstructHistogram(start, end, gradients, data_ptr);
      }
    }
  }
  global_timer.Stop("Dataset::sparse_bin_histogram");

  global_timer.Start("Dataset::sparse_bin_histogram_merge");
  const int min_bin_block_size = 512;
1209
1210
  const int n_bin_block = std::min(
      num_threads, (num_bin + min_bin_block_size - 1) / min_bin_block_size);
1211
1212
  const int bin_block_size = (num_bin + n_bin_block - 1) / n_bin_block;
  if (!is_constant_hessian) {
1213
#pragma omp parallel for schedule(static)
1214
1215
1216
1217
    for (int t = 0; t < n_bin_block; ++t) {
      const int start = t * bin_block_size;
      const int end = std::min(start + bin_block_size, num_bin);
      for (int tid = 1; tid < n_data_block; ++tid) {
1218
1219
        auto src_ptr = temp_state->hist_buf.data() +
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1220
1221
1222
1223
1224
1225
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
    }
  } else {
1226
#pragma omp parallel for schedule(static)
1227
1228
1229
1230
    for (int t = 0; t < n_bin_block; ++t) {
      const int start = t * bin_block_size;
      const int end = std::min(start + bin_block_size, num_bin);
      for (int tid = 1; tid < n_data_block; ++tid) {
1231
1232
        auto src_ptr = temp_state->hist_buf.data() +
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1233
1234
1235
1236
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
1237
      for (int i = start; i < end; ++i) {
1238
1239
1240
1241
1242
        GET_HESS(hist_data, i) = GET_HESS(hist_data, i) * hessians[0];
      }
    }
  }
  global_timer.Stop("Dataset::sparse_bin_histogram_merge");
1243
1244
1245
  global_timer.Start("Dataset::sparse_bin_histogram_move");
  temp_state->HistMove(hist_data, origin_hist_data);
  global_timer.Stop("Dataset::sparse_bin_histogram_move");
1246
1247
}

1248
1249
1250
1251
1252
1253
void Dataset::ConstructHistograms(
    const std::vector<int8_t>& is_feature_used, const data_size_t* data_indices,
    data_size_t num_data, const score_t* gradients, const score_t* hessians,
    score_t* ordered_gradients, score_t* ordered_hessians,
    bool is_constant_hessian, bool is_colwise, TrainingTempState* temp_state,
    hist_t* hist_data) const {
1254
1255
  Common::FunctionTimer fun_timer("Dataset::ConstructHistograms", global_timer);
  if (num_data < 0 || hist_data == nullptr) {
Guolin Ke's avatar
Guolin Ke committed
1256
1257
    return;
  }
1258
  if (!is_colwise) {
1259
1260
1261
    return ConstructHistogramsMultiVal(data_indices, num_data, gradients,
                                       hessians, is_constant_hessian,
                                       temp_state, hist_data);
1262
1263
1264
1265
1266
  }
  global_timer.Start("Dataset::Get used group");
  std::vector<int> used_dense_group;
  int multi_val_groud_id = -1;
  used_dense_group.reserve(num_groups_);
Guolin Ke's avatar
Guolin Ke committed
1267
1268
  for (int group = 0; group < num_groups_; ++group) {
    const int f_cnt = group_feature_cnt_[group];
1269
    bool is_group_used = false;
Guolin Ke's avatar
Guolin Ke committed
1270
1271
1272
    for (int j = 0; j < f_cnt; ++j) {
      const int fidx = group_feature_start_[group] + j;
      if (is_feature_used[fidx]) {
1273
        is_group_used = true;
Guolin Ke's avatar
Guolin Ke committed
1274
1275
1276
        break;
      }
    }
1277
    if (is_group_used) {
1278
1279
1280
1281
      if (feature_groups_[group]->is_multi_val_) {
        multi_val_groud_id = group;
      } else {
        used_dense_group.push_back(group);
1282
      }
Guolin Ke's avatar
Guolin Ke committed
1283
    }
1284
1285
1286
1287
1288
1289
1290
1291
1292
  }
  int num_used_dense_group = static_cast<int>(used_dense_group.size());
  global_timer.Stop("Dataset::Get used group");
  global_timer.Start("Dataset::dense_bin_histogram");
  if (num_used_dense_group > 0) {
    auto ptr_ordered_grad = gradients;
    auto ptr_ordered_hess = hessians;
    if (data_indices != nullptr && num_data < num_data_) {
      if (!is_constant_hessian) {
1293
#pragma omp parallel for schedule(static)
1294
1295
1296
1297
1298
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
          ordered_hessians[i] = hessians[data_indices[i]];
        }
      } else {
1299
#pragma omp parallel for schedule(static)
1300
1301
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
1302
1303
        }
      }
1304
1305
1306
1307
      ptr_ordered_grad = ordered_gradients;
      ptr_ordered_hess = ordered_hessians;
      if (!is_constant_hessian) {
        OMP_INIT_EX();
1308
#pragma omp parallel for schedule(static)
1309
1310
1311
1312
1313
1314
1315
        for (int gi = 0; gi < num_used_dense_group; ++gi) {
          OMP_LOOP_EX_BEGIN();
          int group = used_dense_group[gi];
          // feature is not used
          auto data_ptr = hist_data + group_bin_boundaries_[group] * 2;
          const int num_bin = feature_groups_[group]->num_total_bin_;
          std::memset(reinterpret_cast<void*>(data_ptr), 0,
1316
                      num_bin * kHistEntrySize);
1317
          // construct histograms for smaller leaf
1318
          feature_groups_[group]->bin_data_->ConstructHistogram(
1319
1320
              data_indices, 0, num_data, ptr_ordered_grad, ptr_ordered_hess,
              data_ptr);
1321
          OMP_LOOP_EX_END();
1322
        }
1323
1324
1325
1326
        OMP_THROW_EX();

      } else {
        OMP_INIT_EX();
1327
#pragma omp parallel for schedule(static)
1328
1329
1330
1331
1332
1333
1334
        for (int gi = 0; gi < num_used_dense_group; ++gi) {
          OMP_LOOP_EX_BEGIN();
          int group = used_dense_group[gi];
          // feature is not used
          auto data_ptr = hist_data + group_bin_boundaries_[group] * 2;
          const int num_bin = feature_groups_[group]->num_total_bin_;
          std::memset(reinterpret_cast<void*>(data_ptr), 0,
1335
                      num_bin * kHistEntrySize);
1336
          // construct histograms for smaller leaf
1337
          feature_groups_[group]->bin_data_->ConstructHistogram(
1338
1339
1340
1341
1342
1343
              data_indices, 0, num_data, ptr_ordered_grad, data_ptr);
          // fixed hessian.
          for (int i = 0; i < num_bin; ++i) {
            GET_HESS(data_ptr, i) = GET_HESS(data_ptr, i) * hessians[0];
          }
          OMP_LOOP_EX_END();
1344
        }
1345
        OMP_THROW_EX();
1346
      }
1347
    } else {
1348
1349
      if (!is_constant_hessian) {
        OMP_INIT_EX();
1350
#pragma omp parallel for schedule(static)
1351
1352
1353
1354
1355
1356
1357
        for (int gi = 0; gi < num_used_dense_group; ++gi) {
          OMP_LOOP_EX_BEGIN();
          int group = used_dense_group[gi];
          // feature is not used
          auto data_ptr = hist_data + group_bin_boundaries_[group] * 2;
          const int num_bin = feature_groups_[group]->num_total_bin_;
          std::memset(reinterpret_cast<void*>(data_ptr), 0,
1358
                      num_bin * kHistEntrySize);
1359
          // construct histograms for smaller leaf
1360
          feature_groups_[group]->bin_data_->ConstructHistogram(
1361
1362
              0, num_data, ptr_ordered_grad, ptr_ordered_hess, data_ptr);
          OMP_LOOP_EX_END();
1363
        }
1364
1365
1366
        OMP_THROW_EX();
      } else {
        OMP_INIT_EX();
1367
#pragma omp parallel for schedule(static)
1368
1369
1370
1371
1372
1373
1374
        for (int gi = 0; gi < num_used_dense_group; ++gi) {
          OMP_LOOP_EX_BEGIN();
          int group = used_dense_group[gi];
          // feature is not used
          auto data_ptr = hist_data + group_bin_boundaries_[group] * 2;
          const int num_bin = feature_groups_[group]->num_total_bin_;
          std::memset(reinterpret_cast<void*>(data_ptr), 0,
1375
                      num_bin * kHistEntrySize);
1376
1377
1378
1379
1380
1381
1382
1383
          // construct histograms for smaller leaf
          feature_groups_[group]->bin_data_->ConstructHistogram(
              0, num_data, ptr_ordered_grad, data_ptr);
          // fixed hessian.
          for (int i = 0; i < num_bin; ++i) {
            GET_HESS(data_ptr, i) = GET_HESS(data_ptr, i) * hessians[0];
          }
          OMP_LOOP_EX_END();
1384
        }
1385
        OMP_THROW_EX();
1386
      }
Guolin Ke's avatar
Guolin Ke committed
1387
1388
    }
  }
1389
1390
  global_timer.Stop("Dataset::dense_bin_histogram");
  if (multi_val_groud_id >= 0) {
1391
1392
1393
    ConstructHistogramsMultiVal(
        data_indices, num_data, gradients, hessians, is_constant_hessian,
        temp_state, hist_data + group_bin_boundaries_[multi_val_groud_id] * 2);
1394
  }
Guolin Ke's avatar
Guolin Ke committed
1395
1396
}

1397
void Dataset::FixHistogram(int feature_idx, double sum_gradient, double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1398
1399
1400
  const int group = feature2group_[feature_idx];
  const int sub_feature = feature2subfeature_[feature_idx];
  const BinMapper* bin_mapper = feature_groups_[group]->bin_mappers_[sub_feature].get();
Guolin Ke's avatar
Guolin Ke committed
1401
1402
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1403
    const int num_bin = bin_mapper->num_bin();
1404
1405
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1406
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1407
      if (i != most_freq_bin) {
1408
1409
        GET_GRAD(data, most_freq_bin) -= GET_GRAD(data, i);
        GET_HESS(data, most_freq_bin) -= GET_HESS(data, i);
Guolin Ke's avatar
Guolin Ke committed
1410
1411
1412
1413
1414
      }
    }
  }
}

1415
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1416
1417
void PushVector(std::vector<T>* dest, const std::vector<T>& src) {
  dest->reserve(dest->size() + src.size());
1418
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1419
    dest->push_back(i);
1420
1421
1422
1423
  }
}

template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1424
1425
void PushOffset(std::vector<T>* dest, const std::vector<T>& src, const T& offset) {
  dest->reserve(dest->size() + src.size());
1426
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1427
    dest->push_back(i + offset);
1428
1429
1430
1431
  }
}

template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1432
1433
void PushClearIfEmpty(std::vector<T>* dest, const size_t dest_len, const std::vector<T>& src, const size_t src_len, const T& deflt) {
  if (!dest->empty() && !src.empty()) {
1434
    PushVector(dest, src);
Guolin Ke's avatar
Guolin Ke committed
1435
  } else if (!dest->empty() && src.empty()) {
1436
    for (size_t i = 0; i < src_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1437
      dest->push_back(deflt);
1438
    }
Guolin Ke's avatar
Guolin Ke committed
1439
  } else if (dest->empty() && !src.empty()) {
1440
    for (size_t i = 0; i < dest_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1441
      dest->push_back(deflt);
1442
1443
1444
1445
1446
    }
    PushVector(dest, src);
  }
}

1447
void Dataset::AddFeaturesFrom(Dataset* other) {
1448
  if (other->num_data_ != num_data_) {
1449
1450
    throw std::runtime_error("Cannot add features from other Dataset with a different number of rows");
  }
Guolin Ke's avatar
Guolin Ke committed
1451
1452
1453
  PushVector(&feature_names_, other->feature_names_);
  PushVector(&feature2subfeature_, other->feature2subfeature_);
  PushVector(&group_feature_cnt_, other->group_feature_cnt_);
1454
  PushVector(&forced_bin_bounds_, other->forced_bin_bounds_);
1455
  feature_groups_.reserve(other->feature_groups_.size());
Guolin Ke's avatar
Guolin Ke committed
1456
1457
  // FIXME: fix the multiple multi-val feature groups, they need to be merged
  // into one multi-val group
1458
  for (auto& fg : other->feature_groups_) {
1459
1460
    feature_groups_.emplace_back(new FeatureGroup(*fg));
  }
1461
1462
  for (auto feature_idx : other->used_feature_map_) {
    if (feature_idx >= 0) {
1463
1464
1465
1466
1467
      used_feature_map_.push_back(feature_idx + num_features_);
    } else {
      used_feature_map_.push_back(-1);  // Unused feature.
    }
  }
Guolin Ke's avatar
Guolin Ke committed
1468
1469
  PushOffset(&real_feature_idx_, other->real_feature_idx_, num_total_features_);
  PushOffset(&feature2group_, other->feature2group_, num_groups_);
1470
1471
  auto bin_offset = group_bin_boundaries_.back();
  // Skip the leading 0 when copying group_bin_boundaries.
1472
  for (auto i = other->group_bin_boundaries_.begin()+1; i < other->group_bin_boundaries_.end(); ++i) {
1473
1474
    group_bin_boundaries_.push_back(*i + bin_offset);
  }
Guolin Ke's avatar
Guolin Ke committed
1475
  PushOffset(&group_feature_start_, other->group_feature_start_, num_features_);
1476
  PushClearIfEmpty(&max_bin_by_feature_, num_total_features_, other->max_bin_by_feature_, other->num_total_features_, -1);
1477

1478
1479
1480
1481
1482
  num_features_ += other->num_features_;
  num_total_features_ += other->num_total_features_;
  num_groups_ += other->num_groups_;
}

Guolin Ke's avatar
Guolin Ke committed
1483
}  // namespace LightGBM