dataset.cpp 61.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;
    }
  }
Guolin Ke's avatar
Guolin Ke committed
380
381
382
383
384
385
386
387
388
389
390
391
392
393

  if (!io_config.monotone_constraints.empty()) {
    CHECK(static_cast<size_t>(num_total_features_) == io_config.monotone_constraints.size());
    monotone_types_.resize(num_features_);
    for (int i = 0; i < num_total_features_; ++i) {
      int inner_fidx = InnerFeatureIndex(i);
      if (inner_fidx >= 0) {
        monotone_types_[inner_fidx] = io_config.monotone_constraints[i];
      }
    }
    if (ArrayArgs<int8_t>::CheckAllZero(monotone_types_)) {
      monotone_types_.clear();
    }
  }
Guolin Ke's avatar
Guolin Ke committed
394
395
396
397
398
399
400
401
402
403
404
405
406
  if (!io_config.feature_contri.empty()) {
    CHECK(static_cast<size_t>(num_total_features_) == io_config.feature_contri.size());
    feature_penalty_.resize(num_features_);
    for (int i = 0; i < num_total_features_; ++i) {
      int inner_fidx = InnerFeatureIndex(i);
      if (inner_fidx >= 0) {
        feature_penalty_[inner_fidx] = std::max(0.0, io_config.feature_contri[i]);
      }
    }
    if (ArrayArgs<double>::CheckAll(feature_penalty_, 1.0)) {
      feature_penalty_.clear();
    }
  }
Belinda Trotta's avatar
Belinda Trotta committed
407
408
409
410
411
412
  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());
  }
413
  forced_bin_bounds_ = forced_bins;
414
415
416
417
418
419
420
421
422
423
424
425
426
427
  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;
}

void Dataset::ResetConfig(const char* parameters) {
  auto param = Config::Str2Map(parameters);
  Config io_config;
  io_config.Set(param);
  if (param.count("max_bin") && io_config.max_bin != max_bin_) {
    Log::Warning("Cannot change max_bin after constructed Dataset handle.");
  }
Belinda Trotta's avatar
Belinda Trotta committed
428
429
430
  if (param.count("max_bin_by_feature") && io_config.max_bin_by_feature != max_bin_by_feature_) {
    Log::Warning("Cannot change max_bin_by_feature after constructed Dataset handle.");
  }
431
432
433
434
435
436
437
438
439
440
441
442
  if (param.count("bin_construct_sample_cnt") && io_config.bin_construct_sample_cnt != bin_construct_sample_cnt_) {
    Log::Warning("Cannot change bin_construct_sample_cnt after constructed Dataset handle.");
  }
  if (param.count("min_data_in_bin") && io_config.min_data_in_bin != min_data_in_bin_) {
    Log::Warning("Cannot change min_data_in_bin after constructed Dataset handle.");
  }
  if (param.count("use_missing") && io_config.use_missing != use_missing_) {
    Log::Warning("Cannot change use_missing after constructed Dataset handle.");
  }
  if (param.count("zero_as_missing") && io_config.zero_as_missing != zero_as_missing_) {
    Log::Warning("Cannot change zero_as_missing after constructed Dataset handle.");
  }
443
444
445
  if (param.count("forcedbins_filename")) {
    Log::Warning("Cannot change forced bins after constructed Dataset handle.");
  }
Guolin Ke's avatar
Guolin Ke committed
446

447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
  if (!io_config.monotone_constraints.empty()) {
    CHECK(static_cast<size_t>(num_total_features_) == io_config.monotone_constraints.size());
    monotone_types_.resize(num_features_);
    for (int i = 0; i < num_total_features_; ++i) {
      int inner_fidx = InnerFeatureIndex(i);
      if (inner_fidx >= 0) {
        monotone_types_[inner_fidx] = io_config.monotone_constraints[i];
      }
    }
    if (ArrayArgs<int8_t>::CheckAllZero(monotone_types_)) {
      monotone_types_.clear();
    }
  }
  if (!io_config.feature_contri.empty()) {
    CHECK(static_cast<size_t>(num_total_features_) == io_config.feature_contri.size());
    feature_penalty_.resize(num_features_);
    for (int i = 0; i < num_total_features_; ++i) {
      int inner_fidx = InnerFeatureIndex(i);
      if (inner_fidx >= 0) {
        feature_penalty_[inner_fidx] = std::max(0.0, io_config.feature_contri[i]);
      }
    }
    if (ArrayArgs<double>::CheckAll(feature_penalty_, 1.0)) {
      feature_penalty_.clear();
    }
  }
Guolin Ke's avatar
Guolin Ke committed
473
474
}

Guolin Ke's avatar
Guolin Ke committed
475
void Dataset::FinishLoad() {
Guolin Ke's avatar
Guolin Ke committed
476
  if (is_finish_load_) { return; }
477
478
  if (num_groups_ > 0) {
    for (int i = 0; i < num_groups_; ++i) {
479
      feature_groups_[i]->FinishLoad();
480
    }
Guolin Ke's avatar
Guolin Ke committed
481
  }
Guolin Ke's avatar
Guolin Ke committed
482
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
483
}
Guolin Ke's avatar
Guolin Ke committed
484

485
486
487
488
489
490
491
492
493

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);
494
  const data_size_t min_block_size = 4096;
495
496
  const int n_block =
      std::min(num_threads, (num_data + min_block_size - 1) / min_block_size);
497
498
  const data_size_t block_size = (num_data + n_block - 1) / n_block;
  if (ret->IsSparse()) {
499
#pragma omp parallel for schedule(static)
500
501
    for (int tid = 0; tid < n_block; ++tid) {
      std::vector<uint32_t> cur_data;
502
      cur_data.reserve(most_freq_bins.size());
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
      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 {
525
#pragma omp parallel for schedule(static)
526
    for (int tid = 0; tid < n_block; ++tid) {
527
      std::vector<uint32_t> cur_data(most_freq_bins.size(), 0);
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
      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;
            }
          }
544
          cur_data[j] = cur_bin;
545
546
547
548
549
550
551
552
        }
        ret->PushOneRow(tid, i, cur_data);
      }
    }
  }
}

MultiValBin* Dataset::GetMultiBinFromSparseFeatures() const {
553
554
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromSparseFeatures",
                                 global_timer);
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
  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;
571
572
573
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
574
575
576
577
578
579

  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) {
580
581
      iters[tid].emplace_back(
          feature_groups_[multi_group_id]->SubFeatureIterator(i));
582
    }
583
584
585
586
    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();
587
588
  }
  sum_sparse_rate /= num_feature;
589
590
  Log::Debug("Dataset::GetMultiBinFromSparseFeatures: sparse rate %f",
             sum_sparse_rate);
591
  std::unique_ptr<MultiValBin> ret;
592
593
594
595
  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());
596
597
598
599
600
  ret->FinishLoad();
  return ret.release();
}

MultiValBin* Dataset::GetMultiBinFromAllFeatures() const {
601
602
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromAllFeatures",
                                 global_timer);
603
  int num_threads = 1;
604
605
606
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
  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) {
627
628
          iters[tid].emplace_back(
              feature_groups_[gid]->SubFeatureIterator(fid));
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
        }
      }
    } 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());
645
646
647
648
649
650
651
  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());
652
653
654
655
  ret->FinishLoad();
  return ret.release();
}

656
657
658
659
660
661
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);
662
  if (force_colwise && force_rowwise) {
663
664
665
    Log::Fatal(
        "Cannot set both `force_col_wise` and `force_row_wise` to `true` at "
        "the same time");
666
667
668
669
670
671
  }
  if (num_groups_ <= 0) {
    return nullptr;
  }
  if (force_colwise) {
    *is_hist_col_wise = true;
672
673
674
    TrainingTempState* temp_state = new TrainingTempState();
    temp_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
    return temp_state;
675
676
  } else if (force_rowwise) {
    *is_hist_col_wise = false;
677
678
679
    TrainingTempState* temp_state = new TrainingTempState();
    temp_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    return temp_state;
680
681
682
  } else {
    std::unique_ptr<MultiValBin> sparse_bin;
    std::unique_ptr<MultiValBin> all_bin;
683
684
685
686
687
688
689
    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;
690
    auto start_time = std::chrono::steady_clock::now();
691
    colwise_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
692
    col_wise_init_time = std::chrono::steady_clock::now() - start_time;
693

694
    start_time = std::chrono::steady_clock::now();
695
696
697
698
    rowwise_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>
        hist_data(NumTotalBin() * 2);

699
    row_wise_init_time = std::chrono::steady_clock::now() - start_time;
700
701
702
703
704
    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());
705
    std::chrono::duration<double, std::milli> col_wise_time, row_wise_time;
706
    start_time = std::chrono::steady_clock::now();
707
708
709
    ConstructHistograms(is_feature_used, nullptr, num_data_, gradients,
                        hessians, gradients, hessians, is_constant_hessian,
                        true, colwise_state.get(), hist_data.data());
710
711
    col_wise_time = std::chrono::steady_clock::now() - start_time;
    start_time = std::chrono::steady_clock::now();
712
713
714
    ConstructHistogramsMultiVal(nullptr, num_data_, gradients, hessians,
                                is_constant_hessian, rowwise_state.get(),
                                hist_data.data());
715
    row_wise_time = std::chrono::steady_clock::now() - start_time;
716
    Log::Debug("col-wise cost %f seconds, row-wise cost %f seconds",
717
               col_wise_time * 1e-3, row_wise_time * 1e-3);
718
719
    if (col_wise_time < row_wise_time) {
      *is_hist_col_wise = true;
720
721
      auto overhead_cost = row_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
722
723
          "Auto-choosing col-wise multi-threading, the overhead of testing was "
          "%f "
724
          "seconds.\nYou can set `force_col_wise=true` to remove the "
725
726
          "overhead.",
          overhead_cost * 1e-3);
727
      return colwise_state.release();
728
729
    } else {
      *is_hist_col_wise = false;
730
731
      auto overhead_cost = col_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
732
733
          "Auto-choosing row-wise multi-threading, the overhead of testing was "
          "%f "
734
735
          "seconds.\nYou can set `force_row_wise=true` to remove the "
          "overhead.\nAnd if memory is not enough, you can set "
736
737
          "`force_col_wise=true`.",
          overhead_cost * 1e-3);
738
      if (rowwise_state->multi_val_bin->IsSparse()) {
739
        Log::Debug("Using Sparse Multi-Val Bin");
740
      } else {
741
        Log::Debug("Using Dense Multi-Val Bin");
742
      }
743
      return rowwise_state.release();
744
745
746
747
    }
  }
}

748
void Dataset::CopyFeatureMapperFrom(const Dataset* dataset) {
Guolin Ke's avatar
Guolin Ke committed
749
  feature_groups_.clear();
Guolin Ke's avatar
Guolin Ke committed
750
  num_features_ = dataset->num_features_;
Guolin Ke's avatar
Guolin Ke committed
751
  num_groups_ = dataset->num_groups_;
Guolin Ke's avatar
Guolin Ke committed
752
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
753
  for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
754
    feature_groups_.emplace_back(new FeatureGroup(*dataset->feature_groups_[i], num_data_));
Guolin Ke's avatar
Guolin Ke committed
755
  }
Guolin Ke's avatar
Guolin Ke committed
756
  feature_groups_.shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
757
758
759
  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
760
  label_idx_ = dataset->label_idx_;
Guolin Ke's avatar
Guolin Ke committed
761
762
763
764
765
766
  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_;
Guolin Ke's avatar
Guolin Ke committed
767
  monotone_types_ = dataset->monotone_types_;
Guolin Ke's avatar
Guolin Ke committed
768
  feature_penalty_ = dataset->feature_penalty_;
769
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
770
  feature_need_push_zeros_ = dataset->feature_need_push_zeros_;
Guolin Ke's avatar
Guolin Ke committed
771
772
773
774
775
776
777
778
779
}

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
780
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
781
782
783
  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
784
785
786
    if (bin_mappers.back()->GetDefaultBin() != bin_mappers.back()->GetMostFreqBin()) {
      feature_need_push_zeros_.push_back(i);
    }
787
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
    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;
    }
  }
Guolin Ke's avatar
Guolin Ke committed
820
  monotone_types_ = dataset->monotone_types_;
Guolin Ke's avatar
Guolin Ke committed
821
  feature_penalty_ = dataset->feature_penalty_;
822
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
823
824
}

Guolin Ke's avatar
Guolin Ke committed
825
826
827
void Dataset::ReSize(data_size_t num_data) {
  if (num_data_ != num_data) {
    num_data_ = num_data;
828
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
829
    #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
830
    for (int group = 0; group < num_groups_; ++group) {
831
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
832
      feature_groups_[group]->ReSize(num_data_);
833
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
834
    }
835
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
836
837
838
839
840
  }
}

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_);
841
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
842
  #pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
843
  for (int group = 0; group < num_groups_; ++group) {
844
    OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
845
    feature_groups_[group]->CopySubset(fullset->feature_groups_[group].get(), used_indices, num_used_indices);
846
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
847
  }
848
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
849
  if (need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
850
    metadata_.Init(fullset->metadata_, used_indices, num_used_indices);
Guolin Ke's avatar
Guolin Ke committed
851
  }
Guolin Ke's avatar
Guolin Ke committed
852
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
853
854
}

855
bool Dataset::SetFloatField(const char* field_name, const float* field_data, data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
856
857
858
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
859
    #ifdef LABEL_T_USE_DOUBLE
860
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
861
    #else
862
    metadata_.SetLabel(field_data, num_element);
863
    #endif
Guolin Ke's avatar
Guolin Ke committed
864
  } else if (name == std::string("weight") || name == std::string("weights")) {
865
    #ifdef LABEL_T_USE_DOUBLE
866
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
867
    #else
868
    metadata_.SetWeights(field_data, num_element);
869
    #endif
Guolin Ke's avatar
Guolin Ke committed
870
871
872
873
874
875
876
877
878
879
  } 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")) {
880
    metadata_.SetInitScore(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
881
  } else {
882
    return false;
Guolin Ke's avatar
Guolin Ke committed
883
  }
884
  return true;
Guolin Ke's avatar
Guolin Ke committed
885
886
}

887
888
889
890
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
891
    metadata_.SetQuery(field_data, num_element);
892
893
894
895
896
897
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
898
bool Dataset::GetFloatField(const char* field_name, data_size_t* out_len, const float** out_ptr) {
899
900
901
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
902
    #ifdef LABEL_T_USE_DOUBLE
903
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
904
    #else
905
906
    *out_ptr = metadata_.label();
    *out_len = num_data_;
907
    #endif
908
  } else if (name == std::string("weight") || name == std::string("weights")) {
909
    #ifdef LABEL_T_USE_DOUBLE
910
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
911
    #else
912
913
    *out_ptr = metadata_.weights();
    *out_len = num_data_;
914
    #endif
Guolin Ke's avatar
Guolin Ke committed
915
916
917
918
919
920
921
922
923
924
  } 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")) {
925
    *out_ptr = metadata_.init_score();
Guolin Ke's avatar
Guolin Ke committed
926
    *out_len = static_cast<data_size_t>(metadata_.num_init_score());
927
  } else if (name == std::string("feature_penalty")) {
928
    *out_ptr = feature_penalty_.data();
Guolin Ke's avatar
Guolin Ke committed
929
    *out_len = static_cast<data_size_t>(feature_penalty_.size());
930
  } else {
931
932
    return false;
  }
933
  return true;
934
935
}

Guolin Ke's avatar
Guolin Ke committed
936
bool Dataset::GetIntField(const char* field_name, data_size_t* out_len, const int** out_ptr) {
937
938
939
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
940
    *out_ptr = metadata_.query_boundaries();
Guolin Ke's avatar
Guolin Ke committed
941
    *out_len = metadata_.num_queries() + 1;
Guolin Ke's avatar
Guolin Ke committed
942
943
944
  } else {
    return false;
  }
945
  return true;
946
947
}

948
949
950
951
952
bool Dataset::GetInt8Field(const char* field_name, data_size_t* out_len, const int8_t** out_ptr) {
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("monotone_constraints")) {
    *out_ptr = monotone_types_.data();
Guolin Ke's avatar
Guolin Ke committed
953
    *out_len = static_cast<data_size_t>(monotone_types_.size());
954
955
956
957
958
959
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
960
void Dataset::SaveBinaryFile(const char* bin_filename) {
Guolin Ke's avatar
Guolin Ke committed
961
  if (bin_filename != nullptr
Guolin Ke's avatar
Guolin Ke committed
962
      && std::string(bin_filename) == data_filename_) {
963
    Log::Warning("Bianry file %s already exists", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
964
965
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
966
  // if not pass a filename, just append ".bin" of original file
Guolin Ke's avatar
Guolin Ke committed
967
  std::string bin_filename_str(data_filename_);
Guolin Ke's avatar
Guolin Ke committed
968
969
970
971
  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
972
  bool is_file_existed = false;
973
974

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
975
    is_file_existed = true;
976
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
977
  }
Guolin Ke's avatar
Guolin Ke committed
978

Guolin Ke's avatar
Guolin Ke committed
979
  if (!is_file_existed) {
980
981
    auto writer = VirtualFileWriter::Make(bin_filename);
    if (!writer->Init()) {
Guolin Ke's avatar
Guolin Ke committed
982
      Log::Fatal("Cannot write binary data to %s ", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
983
    }
984
    Log::Info("Saving data to binary file %s", bin_filename);
985
    size_t size_of_token = std::strlen(binary_file_token);
986
    writer->Write(binary_file_token, size_of_token);
Guolin Ke's avatar
Guolin Ke committed
987
    // get size of header
Guolin Ke's avatar
Guolin Ke committed
988
    size_t size_of_header = sizeof(num_data_) + sizeof(num_features_) + sizeof(num_total_features_)
989
      + sizeof(int) * num_total_features_ + sizeof(label_idx_) + sizeof(num_groups_)
Guolin Ke's avatar
Guolin Ke committed
990
      + 3 * sizeof(int) * num_features_ + sizeof(uint64_t) * (num_groups_ + 1) + 2 * sizeof(int) * num_groups_ + sizeof(int8_t) * num_features_
Belinda Trotta's avatar
Belinda Trotta committed
991
      + sizeof(double) * num_features_ + sizeof(int32_t) * num_total_features_ + sizeof(int) * 3 + sizeof(bool) * 2;
992
993
994
995
    // size of feature names
    for (int i = 0; i < num_total_features_; ++i) {
      size_of_header += feature_names_[i].size() + sizeof(int);
    }
996
997
998
999
    // 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);
    }
1000
    writer->Write(&size_of_header, sizeof(size_of_header));
Guolin Ke's avatar
Guolin Ke committed
1001
    // write header
1002
1003
1004
1005
    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_));
1006
1007
1008
1009
1010
    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_));
1011
1012
1013
1014
1015
1016
1017
1018
    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_);
Guolin Ke's avatar
Guolin Ke committed
1019
1020
1021
1022
1023
1024
1025
    if (monotone_types_.empty()) {
      ArrayArgs<int8_t>::Assign(&monotone_types_, 0, num_features_);
    }
    writer->Write(monotone_types_.data(), sizeof(int8_t) * num_features_);
    if (ArrayArgs<int8_t>::CheckAllZero(monotone_types_)) {
      monotone_types_.clear();
    }
Guolin Ke's avatar
Guolin Ke committed
1026
1027
1028
1029
1030
1031
1032
    if (feature_penalty_.empty()) {
      ArrayArgs<double>::Assign(&feature_penalty_, 1.0, num_features_);
    }
    writer->Write(feature_penalty_.data(), sizeof(double) * num_features_);
    if (ArrayArgs<double>::CheckAll(feature_penalty_, 1.0)) {
      feature_penalty_.clear();
    }
Belinda Trotta's avatar
Belinda Trotta committed
1033
1034
1035
1036
1037
1038
1039
    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();
    }
1040
1041
1042
    // write feature names
    for (int i = 0; i < num_total_features_; ++i) {
      int str_len = static_cast<int>(feature_names_[i].size());
1043
      writer->Write(&str_len, sizeof(int));
1044
      const char* c_str = feature_names_[i].c_str();
1045
      writer->Write(c_str, sizeof(char) * str_len);
1046
    }
1047
1048
1049
1050
    // 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));
1051

1052
1053
1054
1055
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
1056

Guolin Ke's avatar
Guolin Ke committed
1057
1058
    // get size of meta data
    size_t size_of_metadata = metadata_.SizesInByte();
1059
    writer->Write(&size_of_metadata, sizeof(size_of_metadata));
Guolin Ke's avatar
Guolin Ke committed
1060
    // write meta data
1061
    metadata_.SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
1062
1063

    // write feature data
Guolin Ke's avatar
Guolin Ke committed
1064
    for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1065
      // get size of feature
Guolin Ke's avatar
Guolin Ke committed
1066
      size_t size_of_feature = feature_groups_[i]->SizesInByte();
1067
      writer->Write(&size_of_feature, sizeof(size_of_feature));
Guolin Ke's avatar
Guolin Ke committed
1068
      // write feature
1069
      feature_groups_[i]->SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
1070
1071
1072
1073
    }
  }
}

1074
void Dataset::DumpTextFile(const char* text_filename) {
Guolin Ke's avatar
Guolin Ke committed
1075
1076
1077
1078
1079
1080
  FILE* file = NULL;
#if _MSC_VER
  fopen_s(&file, text_filename, "wt");
#else
  file = fopen(text_filename, "wt");
#endif
1081
1082
1083
1084
1085
  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: ");
1086
  for (auto n : feature_names_) {
1087
1088
1089
    fprintf(file, "%s, ", n.c_str());
  }
  fprintf(file, "\nmonotone_constraints: ");
1090
  for (auto i : monotone_types_) {
1091
1092
1093
    fprintf(file, "%d, ", i);
  }
  fprintf(file, "\nfeature_penalty: ");
1094
  for (auto i : feature_penalty_) {
1095
1096
    fprintf(file, "%lf, ", i);
  }
Belinda Trotta's avatar
Belinda Trotta committed
1097
1098
1099
1100
  fprintf(file, "\nmax_bin_by_feature: ");
  for (auto i : max_bin_by_feature_) {
    fprintf(file, "%d, ", i);
  }
1101
  fprintf(file, "\n");
1102
  for (auto n : feature_names_) {
1103
1104
    fprintf(file, "%s, ", n.c_str());
  }
1105
1106
1107
1108
1109
1110
1111
  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]);
    }
  }
1112
1113
  std::vector<std::unique_ptr<BinIterator>> iterators;
  iterators.reserve(num_features_);
1114
  for (int j = 0; j < num_features_; ++j) {
1115
1116
1117
1118
    auto group_idx = feature2group_[j];
    auto sub_idx = feature2subfeature_[j];
    iterators.emplace_back(feature_groups_[group_idx]->SubFeatureIterator(sub_idx));
  }
1119
  for (data_size_t i = 0; i < num_data_; ++i) {
1120
    fprintf(file, "\n");
1121
    for (int j = 0; j < num_total_features_; ++j) {
1122
      auto inner_feature_idx = used_feature_map_[j];
1123
1124
      if (inner_feature_idx < 0) {
        fprintf(file, "NA, ");
1125
      } else {
Guolin Ke's avatar
Guolin Ke committed
1126
        fprintf(file, "%d, ", iterators[inner_feature_idx]->Get(i));
1127
1128
1129
1130
1131
1132
      }
    }
  }
  fclose(file);
}

1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273

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();
1274
1275
1276
  if (multi_val_bin == nullptr) {
    return;
  }
1277
  int num_threads = 1;
1278
1279
1280
#pragma omp parallel
#pragma omp master
  { num_threads = omp_get_num_threads(); }
1281
1282
1283

  global_timer.Start("Dataset::sparse_bin_histogram");
  const int num_bin = multi_val_bin->num_bin();
1284
1285
  const int num_bin_aligned =
      (num_bin + kAlignedSize - 1) / kAlignedSize * kAlignedSize;
1286
  const int min_data_block_size = 1024;
1287
1288
  const int n_data_block = std::min(
      num_threads, (num_data + min_data_block_size - 1) / min_data_block_size);
1289
1290
  const int data_block_size = (num_data + n_data_block - 1) / n_data_block;

1291
1292
1293
1294
  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);
1295
  }
1296
1297
1298
1299
1300
  auto origin_hist_data = hist_data;
  if (temp_state->use_subfeature) {
    hist_data = temp_state->TempBuf();
  }
#pragma omp parallel for schedule(static)
1301
1302
1303
1304
1305
  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) {
1306
1307
      data_ptr = temp_state->hist_buf.data() +
                 static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1308
    }
1309
    std::memset(reinterpret_cast<void*>(data_ptr), 0, num_bin * kHistEntrySize);
1310
1311
    if (data_indices != nullptr && num_data < num_data_) {
      if (!is_constant_hessian) {
1312
1313
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          hessians, data_ptr);
1314
      } else {
1315
1316
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          data_ptr);
1317
1318
1319
      }
    } else {
      if (!is_constant_hessian) {
1320
1321
        multi_val_bin->ConstructHistogram(start, end, gradients, hessians,
                                          data_ptr);
1322
1323
1324
1325
1326
1327
1328
1329
1330
      } 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;
1331
1332
  const int n_bin_block = std::min(
      num_threads, (num_bin + min_bin_block_size - 1) / min_bin_block_size);
1333
1334
  const int bin_block_size = (num_bin + n_bin_block - 1) / n_bin_block;
  if (!is_constant_hessian) {
1335
#pragma omp parallel for schedule(static)
1336
1337
1338
1339
    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) {
1340
1341
        auto src_ptr = temp_state->hist_buf.data() +
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1342
1343
1344
1345
1346
1347
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
    }
  } else {
1348
#pragma omp parallel for schedule(static)
1349
1350
1351
1352
    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) {
1353
1354
        auto src_ptr = temp_state->hist_buf.data() +
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1355
1356
1357
1358
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
1359
      for (int i = start; i < end; ++i) {
1360
1361
1362
1363
1364
        GET_HESS(hist_data, i) = GET_HESS(hist_data, i) * hessians[0];
      }
    }
  }
  global_timer.Stop("Dataset::sparse_bin_histogram_merge");
1365
1366
1367
  global_timer.Start("Dataset::sparse_bin_histogram_move");
  temp_state->HistMove(hist_data, origin_hist_data);
  global_timer.Stop("Dataset::sparse_bin_histogram_move");
1368
1369
}

1370
1371
1372
1373
1374
1375
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 {
1376
1377
  Common::FunctionTimer fun_timer("Dataset::ConstructHistograms", global_timer);
  if (num_data < 0 || hist_data == nullptr) {
Guolin Ke's avatar
Guolin Ke committed
1378
1379
    return;
  }
1380
  if (!is_colwise) {
1381
1382
1383
    return ConstructHistogramsMultiVal(data_indices, num_data, gradients,
                                       hessians, is_constant_hessian,
                                       temp_state, hist_data);
1384
1385
1386
1387
1388
  }
  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
1389
1390
  for (int group = 0; group < num_groups_; ++group) {
    const int f_cnt = group_feature_cnt_[group];
1391
    bool is_group_used = false;
Guolin Ke's avatar
Guolin Ke committed
1392
1393
1394
    for (int j = 0; j < f_cnt; ++j) {
      const int fidx = group_feature_start_[group] + j;
      if (is_feature_used[fidx]) {
1395
        is_group_used = true;
Guolin Ke's avatar
Guolin Ke committed
1396
1397
1398
        break;
      }
    }
1399
    if (is_group_used) {
1400
1401
1402
1403
      if (feature_groups_[group]->is_multi_val_) {
        multi_val_groud_id = group;
      } else {
        used_dense_group.push_back(group);
1404
      }
Guolin Ke's avatar
Guolin Ke committed
1405
    }
1406
1407
1408
1409
1410
1411
1412
1413
1414
  }
  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) {
1415
#pragma omp parallel for schedule(static)
1416
1417
1418
1419
1420
        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 {
1421
#pragma omp parallel for schedule(static)
1422
1423
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
1424
1425
        }
      }
1426
1427
1428
1429
      ptr_ordered_grad = ordered_gradients;
      ptr_ordered_hess = ordered_hessians;
      if (!is_constant_hessian) {
        OMP_INIT_EX();
1430
#pragma omp parallel for schedule(static)
1431
1432
1433
1434
1435
1436
1437
        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,
1438
                      num_bin * kHistEntrySize);
1439
          // construct histograms for smaller leaf
1440
          feature_groups_[group]->bin_data_->ConstructHistogram(
1441
1442
              data_indices, 0, num_data, ptr_ordered_grad, ptr_ordered_hess,
              data_ptr);
1443
          OMP_LOOP_EX_END();
1444
        }
1445
1446
1447
1448
        OMP_THROW_EX();

      } else {
        OMP_INIT_EX();
1449
#pragma omp parallel for schedule(static)
1450
1451
1452
1453
1454
1455
1456
        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,
1457
                      num_bin * kHistEntrySize);
1458
          // construct histograms for smaller leaf
1459
          feature_groups_[group]->bin_data_->ConstructHistogram(
1460
1461
1462
1463
1464
1465
              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();
1466
        }
1467
        OMP_THROW_EX();
1468
      }
1469
    } else {
1470
1471
      if (!is_constant_hessian) {
        OMP_INIT_EX();
1472
#pragma omp parallel for schedule(static)
1473
1474
1475
1476
1477
1478
1479
        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,
1480
                      num_bin * kHistEntrySize);
1481
          // construct histograms for smaller leaf
1482
          feature_groups_[group]->bin_data_->ConstructHistogram(
1483
1484
              0, num_data, ptr_ordered_grad, ptr_ordered_hess, data_ptr);
          OMP_LOOP_EX_END();
1485
        }
1486
1487
1488
        OMP_THROW_EX();
      } else {
        OMP_INIT_EX();
1489
#pragma omp parallel for schedule(static)
1490
1491
1492
1493
1494
1495
1496
        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,
1497
                      num_bin * kHistEntrySize);
1498
1499
1500
1501
1502
1503
1504
1505
          // 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();
1506
        }
1507
        OMP_THROW_EX();
1508
      }
Guolin Ke's avatar
Guolin Ke committed
1509
1510
    }
  }
1511
1512
  global_timer.Stop("Dataset::dense_bin_histogram");
  if (multi_val_groud_id >= 0) {
1513
1514
1515
    ConstructHistogramsMultiVal(
        data_indices, num_data, gradients, hessians, is_constant_hessian,
        temp_state, hist_data + group_bin_boundaries_[multi_val_groud_id] * 2);
1516
  }
Guolin Ke's avatar
Guolin Ke committed
1517
1518
}

1519
void Dataset::FixHistogram(int feature_idx, double sum_gradient, double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1520
1521
1522
  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
1523
1524
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1525
    const int num_bin = bin_mapper->num_bin();
1526
1527
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1528
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1529
      if (i != most_freq_bin) {
1530
1531
        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
1532
1533
1534
1535
1536
      }
    }
  }
}

1537
template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1538
1539
void PushVector(std::vector<T>* dest, const std::vector<T>& src) {
  dest->reserve(dest->size() + src.size());
1540
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1541
    dest->push_back(i);
1542
1543
1544
1545
  }
}

template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1546
1547
void PushOffset(std::vector<T>* dest, const std::vector<T>& src, const T& offset) {
  dest->reserve(dest->size() + src.size());
1548
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1549
    dest->push_back(i + offset);
1550
1551
1552
1553
  }
}

template<typename T>
Guolin Ke's avatar
Guolin Ke committed
1554
1555
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()) {
1556
    PushVector(dest, src);
Guolin Ke's avatar
Guolin Ke committed
1557
  } else if (!dest->empty() && src.empty()) {
1558
    for (size_t i = 0; i < src_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1559
      dest->push_back(deflt);
1560
    }
Guolin Ke's avatar
Guolin Ke committed
1561
  } else if (dest->empty() && !src.empty()) {
1562
    for (size_t i = 0; i < dest_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1563
      dest->push_back(deflt);
1564
1565
1566
1567
1568
    }
    PushVector(dest, src);
  }
}

1569
void Dataset::AddFeaturesFrom(Dataset* other) {
1570
  if (other->num_data_ != num_data_) {
1571
1572
    throw std::runtime_error("Cannot add features from other Dataset with a different number of rows");
  }
Guolin Ke's avatar
Guolin Ke committed
1573
1574
1575
  PushVector(&feature_names_, other->feature_names_);
  PushVector(&feature2subfeature_, other->feature2subfeature_);
  PushVector(&group_feature_cnt_, other->group_feature_cnt_);
1576
  PushVector(&forced_bin_bounds_, other->forced_bin_bounds_);
1577
  feature_groups_.reserve(other->feature_groups_.size());
Guolin Ke's avatar
Guolin Ke committed
1578
1579
  // FIXME: fix the multiple multi-val feature groups, they need to be merged
  // into one multi-val group
1580
  for (auto& fg : other->feature_groups_) {
1581
1582
    feature_groups_.emplace_back(new FeatureGroup(*fg));
  }
1583
1584
  for (auto feature_idx : other->used_feature_map_) {
    if (feature_idx >= 0) {
1585
1586
1587
1588
1589
      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
1590
1591
  PushOffset(&real_feature_idx_, other->real_feature_idx_, num_total_features_);
  PushOffset(&feature2group_, other->feature2group_, num_groups_);
1592
1593
  auto bin_offset = group_bin_boundaries_.back();
  // Skip the leading 0 when copying group_bin_boundaries.
1594
  for (auto i = other->group_bin_boundaries_.begin()+1; i < other->group_bin_boundaries_.end(); ++i) {
1595
1596
    group_bin_boundaries_.push_back(*i + bin_offset);
  }
Guolin Ke's avatar
Guolin Ke committed
1597
  PushOffset(&group_feature_start_, other->group_feature_start_, num_features_);
1598

Guolin Ke's avatar
Guolin Ke committed
1599
1600
  PushClearIfEmpty(&monotone_types_, num_total_features_, other->monotone_types_, other->num_total_features_, (int8_t)0);
  PushClearIfEmpty(&feature_penalty_, num_total_features_, other->feature_penalty_, other->num_total_features_, 1.0);
1601
  PushClearIfEmpty(&max_bin_by_feature_, num_total_features_, other->max_bin_by_feature_, other->num_total_features_, -1);
1602

1603
1604
1605
1606
1607
  num_features_ += other->num_features_;
  num_total_features_ += other->num_total_features_;
  num_groups_ += other->num_groups_;
}

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