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

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

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 <limits>
Guolin Ke's avatar
Guolin Ke committed
16
#include <sstream>
17
#include <unordered_map>
Guolin Ke's avatar
Guolin Ke committed
18
19
20

namespace LightGBM {

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

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

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

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

Guolin Ke's avatar
Guolin Ke committed
41
std::vector<std::vector<int>> NoGroup(const std::vector<int>& used_features) {
Guolin Ke's avatar
Guolin Ke committed
42
43
44
45
46
47
48
49
  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;
}

Guolin Ke's avatar
Guolin Ke committed
50
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

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

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

Guolin Ke's avatar
Guolin Ke committed
97
98
99
100
101
102
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, int num_sample_col, data_size_t total_sample_cnt,
    data_size_t num_data, bool is_use_gpu, bool is_sparse,
    std::vector<int8_t>* multi_val_group) {
Guolin Ke's avatar
Guolin Ke committed
103
  const int max_search_group = 100;
104
  const int max_bin_per_group = 256;
Guolin Ke's avatar
Guolin Ke committed
105
106
  const data_size_t single_val_max_conflict_cnt =
      static_cast<data_size_t>(total_sample_cnt / 10000);
107
108
  multi_val_group->clear();

Guolin Ke's avatar
Guolin Ke committed
109
110
111
  Random rand(num_data);
  std::vector<std::vector<int>> features_in_group;
  std::vector<std::vector<bool>> conflict_marks;
112
113
  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
114
115
  std::vector<int> group_num_bin;

116
  // first round: fill the single val group
Guolin Ke's avatar
Guolin Ke committed
117
  for (auto fidx : find_order) {
118
    bool is_filtered_feature = fidx >= num_sample_col;
Guolin Ke's avatar
Guolin Ke committed
119
120
    const data_size_t cur_non_zero_cnt =
        is_filtered_feature ? 0 : num_per_col[fidx];
Guolin Ke's avatar
Guolin Ke committed
121
122
    std::vector<int> available_groups;
    for (int gid = 0; gid < static_cast<int>(features_in_group.size()); ++gid) {
Guolin Ke's avatar
Guolin Ke committed
123
124
125
126
      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) {
127
        if (!is_use_gpu || cur_num_bin <= max_bin_per_group) {
Guolin Ke's avatar
Guolin Ke committed
128
129
          available_groups.push_back(gid);
        }
Guolin Ke's avatar
Guolin Ke committed
130
131
132
133
134
135
      }
    }
    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));
136
      // always push the last group
Guolin Ke's avatar
Guolin Ke committed
137
138
139
140
141
      search_groups.push_back(available_groups.back());
      for (auto idx : indices) {
        search_groups.push_back(available_groups[idx]);
      }
    }
142
143
    int best_gid = -1;
    int best_conflict_cnt = -1;
Guolin Ke's avatar
Guolin Ke committed
144
    for (auto gid : search_groups) {
Guolin Ke's avatar
Guolin Ke committed
145
146
147
148
149
150
151
152
      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);
153
154
155
      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
156
157
158
        break;
      }
    }
159
160
161
162
163
    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) {
Guolin Ke's avatar
Guolin Ke committed
164
165
        MarkUsed(&conflict_marks[best_gid], sample_indices[fidx],
                 num_per_col[fidx]);
166
      }
Guolin Ke's avatar
Guolin Ke committed
167
168
169
      group_num_bin[best_gid] +=
          bin_mappers[fidx]->num_bin() +
          (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0);
170
    } else {
Guolin Ke's avatar
Guolin Ke committed
171
172
173
      features_in_group.emplace_back();
      features_in_group.back().push_back(fidx);
      conflict_marks.emplace_back(total_sample_cnt, false);
174
      if (!is_filtered_feature) {
Guolin Ke's avatar
Guolin Ke committed
175
176
        MarkUsed(&(conflict_marks.back()), sample_indices[fidx],
                 num_per_col[fidx]);
177
      }
178
179
      group_total_data_cnt.emplace_back(cur_non_zero_cnt);
      group_used_row_cnt.emplace_back(cur_non_zero_cnt);
Guolin Ke's avatar
Guolin Ke committed
180
181
182
      group_num_bin.push_back(
          1 + bin_mappers[fidx]->num_bin() +
          (bin_mappers[fidx]->GetDefaultBin() == 0 ? -1 : 0));
183
184
    }
  }
Guolin Ke's avatar
Guolin Ke committed
185
186
187
188
  if (!is_sparse) {
    multi_val_group->resize(features_in_group.size(), false);
    return features_in_group;
  }
189
190
191
192
193
194
  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) {
Guolin Ke's avatar
Guolin Ke committed
195
196
    const double dense_rate =
        static_cast<double>(group_used_row_cnt[gid]) / total_sample_cnt;
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
    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;
Guolin Ke's avatar
Guolin Ke committed
219
220
221
        const auto cnt =
            GetConfilctCount(conflict_marks.back(), sample_indices[fidx],
                             num_per_col[fidx], rest_max_cnt);
222
223
224
225
226
        conflict_cnt += cnt;
        if (cnt < 0 || conflict_cnt > single_val_max_conflict_cnt) {
          is_multi_val = true;
          continue;
        }
Guolin Ke's avatar
Guolin Ke committed
227
228
        MarkUsed(&(conflict_marks.back()), sample_indices[fidx],
                 num_per_col[fidx]);
Guolin Ke's avatar
Guolin Ke committed
229
      }
Guolin Ke's avatar
Guolin Ke committed
230
    }
231
    multi_val_group->push_back(is_multi_val);
Guolin Ke's avatar
Guolin Ke committed
232
233
234
235
  }
  return features_in_group;
}

Guolin Ke's avatar
Guolin Ke committed
236
237
238
239
240
241
std::vector<std::vector<int>> FastFeatureBundling(
    const std::vector<std::unique_ptr<BinMapper>>& bin_mappers,
    int** sample_indices, double** sample_values, const int* num_per_col,
    int num_sample_col, data_size_t total_sample_cnt,
    const std::vector<int>& used_features, data_size_t num_data,
    bool is_use_gpu, bool is_sparse, std::vector<int8_t>* multi_val_group) {
242
  Common::FunctionTimer fun_timer("Dataset::FastFeatureBundling", global_timer);
Guolin Ke's avatar
Guolin Ke committed
243
  std::vector<size_t> feature_non_zero_cnt;
244
  feature_non_zero_cnt.reserve(used_features.size());
Guolin Ke's avatar
Guolin Ke committed
245
246
  // put dense feature first
  for (auto fidx : used_features) {
247
248
249
250
251
    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
252
253
254
  }
  // sort by non zero cnt
  std::vector<int> sorted_idx;
255
  sorted_idx.reserve(used_features.size());
256
  for (int i = 0; i < static_cast<int>(used_features.size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
257
258
259
    sorted_idx.emplace_back(i);
  }
  // sort by non zero cnt, bigger first
260
261
  std::stable_sort(sorted_idx.begin(), sorted_idx.end(),
                   [&feature_non_zero_cnt](int a, int b) {
Guolin Ke's avatar
Guolin Ke committed
262
263
                     return feature_non_zero_cnt[a] > feature_non_zero_cnt[b];
                   });
Guolin Ke's avatar
Guolin Ke committed
264
265

  std::vector<int> feature_order_by_cnt;
266
  feature_order_by_cnt.reserve(sorted_idx.size());
Guolin Ke's avatar
Guolin Ke committed
267
268
269
  for (auto sidx : sorted_idx) {
    feature_order_by_cnt.push_back(used_features[sidx]);
  }
270

Guolin Ke's avatar
Guolin Ke committed
271
272
273
274
275
276
  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;
    }
Guolin Ke's avatar
Guolin Ke committed
277
278
279
    auto ret = FixSampleIndices(
        bin_mappers[fidx].get(), static_cast<int>(total_sample_cnt),
        num_per_col[fidx], sample_indices[fidx], sample_values[fidx]);
Guolin Ke's avatar
Guolin Ke committed
280
281
282
283
284
285
286
287
    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];
    }
  }
288
  std::vector<int8_t> group_is_multi_val, group_is_multi_val2;
Guolin Ke's avatar
Guolin Ke committed
289
290
291
292
293
294
295
296
  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);
297

Guolin Ke's avatar
Guolin Ke committed
298
299
  if (features_in_group.size() > group2.size()) {
    features_in_group = group2;
300
    group_is_multi_val = group_is_multi_val2;
Guolin Ke's avatar
Guolin Ke committed
301
302
  }
  // shuffle groups
303
304
  int num_group = static_cast<int>(features_in_group.size());
  Random tmp_rand(num_data);
Guolin Ke's avatar
Guolin Ke committed
305
306
  for (int i = 0; i < num_group - 1; ++i) {
    int j = tmp_rand.NextShort(i + 1, num_group);
307
    std::swap(features_in_group[i], features_in_group[j]);
308
    // Using std::swap for vector<bool> will cause the wrong result.
309
    std::swap(group_is_multi_val[i], group_is_multi_val[j]);
Guolin Ke's avatar
Guolin Ke committed
310
  }
311
312
  *multi_val_group = group_is_multi_val;
  return features_in_group;
Guolin Ke's avatar
Guolin Ke committed
313
314
}

Guolin Ke's avatar
Guolin Ke committed
315
316
317
318
319
320
void Dataset::Construct(std::vector<std::unique_ptr<BinMapper>>* bin_mappers,
                        int num_total_features,
                        const std::vector<std::vector<double>>& forced_bins,
                        int** sample_non_zero_indices, double** sample_values,
                        const int* num_per_col, int num_sample_col,
                        size_t total_sample_cnt, const Config& io_config) {
321
322
  num_total_features_ = num_total_features;
  CHECK(num_total_features_ == static_cast<int>(bin_mappers->size()));
Guolin Ke's avatar
Guolin Ke committed
323
324
  // get num_features
  std::vector<int> used_features;
Guolin Ke's avatar
Guolin Ke committed
325
  auto& ref_bin_mappers = *bin_mappers;
Guolin Ke's avatar
Guolin Ke committed
326
  for (int i = 0; i < static_cast<int>(bin_mappers->size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
327
    if (ref_bin_mappers[i] != nullptr && !ref_bin_mappers[i]->is_trivial()) {
Guolin Ke's avatar
Guolin Ke committed
328
      used_features.emplace_back(i);
Guolin Ke's avatar
Guolin Ke committed
329
    }
Guolin Ke's avatar
Guolin Ke committed
330
  }
Guolin Ke's avatar
Guolin Ke committed
331
  if (used_features.empty()) {
Guolin Ke's avatar
Guolin Ke committed
332
333
334
    Log::Warning(
        "There are no meaningful features, as all feature values are "
        "constant.");
Guolin Ke's avatar
Guolin Ke committed
335
  }
Guolin Ke's avatar
Guolin Ke committed
336
  auto features_in_group = NoGroup(used_features);
337
  std::vector<int8_t> group_is_multi_val(used_features.size(), 0);
338
  if (io_config.enable_bundle && !used_features.empty()) {
Guolin Ke's avatar
Guolin Ke committed
339
340
341
342
343
    features_in_group = FastFeatureBundling(
        *bin_mappers, sample_non_zero_indices, sample_values, num_per_col,
        num_sample_col, static_cast<data_size_t>(total_sample_cnt),
        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
344
345
  }

Guolin Ke's avatar
Guolin Ke committed
346
347
348
349
350
351
352
353
354
355
  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_);
356
  int num_multi_val_group = 0;
Guolin Ke's avatar
Guolin Ke committed
357
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
358
359
360
  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());
361
362
363
    if (group_is_multi_val[i]) {
      ++num_multi_val_group;
    }
Guolin Ke's avatar
Guolin Ke committed
364
365
366
367
368
369
370
371
    // 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
372
      cur_bin_mappers.emplace_back(ref_bin_mappers[real_fidx].release());
Guolin Ke's avatar
Guolin Ke committed
373
374
      if (cur_bin_mappers.back()->GetDefaultBin() !=
          cur_bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
375
376
        feature_need_push_zeros_.push_back(cur_fidx);
      }
Guolin Ke's avatar
Guolin Ke committed
377
378
      ++cur_fidx;
    }
Guolin Ke's avatar
Guolin Ke committed
379
380
    feature_groups_.emplace_back(std::unique_ptr<FeatureGroup>(new FeatureGroup(
        cur_cnt_features, group_is_multi_val[i], &cur_bin_mappers, num_data_)));
Guolin Ke's avatar
Guolin Ke committed
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
  }
  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
405
  if (!io_config.max_bin_by_feature.empty()) {
406
407
408
409
    CHECK_EQ(static_cast<size_t>(num_total_features_),
             io_config.max_bin_by_feature.size());
    CHECK_GT(*(std::min_element(io_config.max_bin_by_feature.begin(),
                                io_config.max_bin_by_feature.end())), 1);
Belinda Trotta's avatar
Belinda Trotta committed
410
    max_bin_by_feature_.resize(num_total_features_);
Guolin Ke's avatar
Guolin Ke committed
411
412
    max_bin_by_feature_.assign(io_config.max_bin_by_feature.begin(),
                               io_config.max_bin_by_feature.end());
Belinda Trotta's avatar
Belinda Trotta committed
413
  }
414
  forced_bin_bounds_ = forced_bins;
415
416
417
418
419
420
421
  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
422
void Dataset::FinishLoad() {
Guolin Ke's avatar
Guolin Ke committed
423
424
425
  if (is_finish_load_) {
    return;
  }
426
427
  if (num_groups_ > 0) {
    for (int i = 0; i < num_groups_; ++i) {
428
      feature_groups_[i]->FinishLoad();
429
    }
Guolin Ke's avatar
Guolin Ke committed
430
  }
Guolin Ke's avatar
Guolin Ke committed
431
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
432
}
Guolin Ke's avatar
Guolin Ke committed
433

434
void PushDataToMultiValBin(
Guolin Ke's avatar
Guolin Ke committed
435
    data_size_t num_data, const std::vector<uint32_t> most_freq_bins,
436
437
438
439
440
    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);
441
  if (ret->IsSparse()) {
Guolin Ke's avatar
Guolin Ke committed
442
443
444
445
446
447
    Threading::For<data_size_t>(
        0, num_data, 1024, [&](int tid, data_size_t start, data_size_t end) {
          std::vector<uint32_t> cur_data;
          cur_data.reserve(most_freq_bins.size());
          for (size_t j = 0; j < most_freq_bins.size(); ++j) {
            iters[tid][j]->Reset(start);
448
          }
Guolin Ke's avatar
Guolin Ke committed
449
450
451
452
453
454
455
456
457
458
459
460
461
462
          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);
463
          }
Guolin Ke's avatar
Guolin Ke committed
464
        });
465
  } else {
Guolin Ke's avatar
Guolin Ke committed
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
    Threading::For<data_size_t>(
        0, num_data, 1024, [&](int tid, data_size_t start, data_size_t end) {
          std::vector<uint32_t> cur_data(most_freq_bins.size(), 0);
          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;
                }
              }
              cur_data[j] = cur_bin;
484
            }
Guolin Ke's avatar
Guolin Ke committed
485
            ret->PushOneRow(tid, i, cur_data);
486
          }
Guolin Ke's avatar
Guolin Ke committed
487
        });
488
489
490
491
  }
}

MultiValBin* Dataset::GetMultiBinFromSparseFeatures() const {
492
493
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromSparseFeatures",
                                 global_timer);
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
  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_;
509
  int num_threads = OMP_NUM_THREADS();
510
511
512
513
514

  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) {
Guolin Ke's avatar
Guolin Ke committed
515
#pragma omp parallel for schedule(static)
516
    for (int tid = 0; tid < num_threads; ++tid) {
517
518
      iters[tid].emplace_back(
          feature_groups_[multi_group_id]->SubFeatureIterator(i));
519
    }
520
521
522
523
    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();
524
525
  }
  sum_sparse_rate /= num_feature;
526
527
  Log::Debug("Dataset::GetMultiBinFromSparseFeatures: sparse rate %f",
             sum_sparse_rate);
528
  std::unique_ptr<MultiValBin> ret;
529
530
  ret.reset(MultiValBin::CreateMultiValBin(num_data_, offsets.back(),
                                           num_feature, sum_sparse_rate));
Guolin Ke's avatar
Guolin Ke committed
531
  PushDataToMultiValBin(num_data_, most_freq_bins, offsets, iters, ret.get());
532
533
534
535
536
  ret->FinishLoad();
  return ret.release();
}

MultiValBin* Dataset::GetMultiBinFromAllFeatures() const {
537
538
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromAllFeatures",
                                 global_timer);
539
  int num_threads = OMP_NUM_THREADS();
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
  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);
Guolin Ke's avatar
Guolin Ke committed
559
#pragma omp parallel for schedule(static)
560
        for (int tid = 0; tid < num_threads; ++tid) {
561
562
          iters[tid].emplace_back(
              feature_groups_[gid]->SubFeatureIterator(fid));
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
        }
      }
    } 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());
579
580
581
582
583
  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));
Guolin Ke's avatar
Guolin Ke committed
584
  PushDataToMultiValBin(num_data_, most_freq_bins, offsets, iters, ret.get());
585
586
587
588
  ret->FinishLoad();
  return ret.release();
}

589
TrainingShareStates* Dataset::GetShareStates(
590
591
    score_t* gradients, score_t* hessians,
    const std::vector<int8_t>& is_feature_used, bool is_constant_hessian,
592
    bool force_colwise, bool force_rowwise) const {
593
594
  Common::FunctionTimer fun_timer("Dataset::TestMultiThreadingMethod",
                                  global_timer);
595
  if (force_colwise && force_rowwise) {
596
597
598
    Log::Fatal(
        "Cannot set both `force_col_wise` and `force_row_wise` to `true` at "
        "the same time");
599
600
  }
  if (num_groups_ <= 0) {
601
602
603
604
    TrainingShareStates* share_state = new TrainingShareStates();
    share_state->is_colwise = true;
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
605
606
  }
  if (force_colwise) {
607
608
609
610
611
    TrainingShareStates* share_state = new TrainingShareStates();
    share_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
    share_state->is_colwise = true;
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
612
  } else if (force_rowwise) {
613
614
615
616
617
    TrainingShareStates* share_state = new TrainingShareStates();
    share_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    share_state->is_colwise = false;
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
618
619
620
  } else {
    std::unique_ptr<MultiValBin> sparse_bin;
    std::unique_ptr<MultiValBin> all_bin;
621
622
623
624
    std::unique_ptr<TrainingShareStates> colwise_state;
    std::unique_ptr<TrainingShareStates> rowwise_state;
    colwise_state.reset(new TrainingShareStates());
    rowwise_state.reset(new TrainingShareStates());
625
626
627

    std::chrono::duration<double, std::milli> col_wise_init_time,
        row_wise_init_time;
628
    auto start_time = std::chrono::steady_clock::now();
629
    colwise_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
630
    col_wise_init_time = std::chrono::steady_clock::now() - start_time;
631

632
    start_time = std::chrono::steady_clock::now();
633
634
635
636
    rowwise_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>
        hist_data(NumTotalBin() * 2);

637
    row_wise_init_time = std::chrono::steady_clock::now() - start_time;
638
639
640
    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);
641
642
643
644
645
646
    colwise_state->is_colwise = true;
    colwise_state->is_constant_hessian = is_constant_hessian;
    InitTrain(is_feature_used, colwise_state.get());
    rowwise_state->is_colwise = false;
    rowwise_state->is_constant_hessian = is_constant_hessian;
    InitTrain(is_feature_used, rowwise_state.get());
647
    std::chrono::duration<double, std::milli> col_wise_time, row_wise_time;
648
    start_time = std::chrono::steady_clock::now();
649
    ConstructHistograms(is_feature_used, nullptr, num_data_, gradients,
650
651
                        hessians, gradients, hessians, colwise_state.get(),
                        hist_data.data());
652
653
    col_wise_time = std::chrono::steady_clock::now() - start_time;
    start_time = std::chrono::steady_clock::now();
654
    ConstructHistogramsMultiVal(nullptr, num_data_, gradients, hessians,
655
                                rowwise_state.get(), hist_data.data());
656
    row_wise_time = std::chrono::steady_clock::now() - start_time;
657
    Log::Debug("col-wise cost %f seconds, row-wise cost %f seconds",
658
               col_wise_time * 1e-3, row_wise_time * 1e-3);
659
    if (col_wise_time < row_wise_time) {
660
661
      auto overhead_cost = row_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
662
          "Auto-choosing col-wise multi-threading, the overhead of testing was "
Nikita Titov's avatar
Nikita Titov committed
663
664
          "%f seconds.\n"
          "You can set `force_col_wise=true` to remove the overhead.",
665
          overhead_cost * 1e-3);
666
      return colwise_state.release();
667
    } else {
668
669
      auto overhead_cost = col_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
670
          "Auto-choosing row-wise multi-threading, the overhead of testing was "
Nikita Titov's avatar
Nikita Titov committed
671
672
673
          "%f seconds.\n"
          "You can set `force_row_wise=true` to remove the overhead.\n"
          "And if memory is not enough, you can set `force_col_wise=true`.",
674
          overhead_cost * 1e-3);
675
      if (rowwise_state->multi_val_bin->IsSparse()) {
676
        Log::Debug("Using Sparse Multi-Val Bin");
677
      } else {
678
        Log::Debug("Using Dense Multi-Val Bin");
679
      }
680
      return rowwise_state.release();
681
682
683
684
    }
  }
}

685
void Dataset::CopyFeatureMapperFrom(const Dataset* dataset) {
Guolin Ke's avatar
Guolin Ke committed
686
  feature_groups_.clear();
Guolin Ke's avatar
Guolin Ke committed
687
  num_features_ = dataset->num_features_;
Guolin Ke's avatar
Guolin Ke committed
688
  num_groups_ = dataset->num_groups_;
Guolin Ke's avatar
Guolin Ke committed
689
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
690
  for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
691
692
    feature_groups_.emplace_back(
        new FeatureGroup(*dataset->feature_groups_[i], num_data_));
Guolin Ke's avatar
Guolin Ke committed
693
  }
Guolin Ke's avatar
Guolin Ke committed
694
  feature_groups_.shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
695
696
697
  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
698
  label_idx_ = dataset->label_idx_;
Guolin Ke's avatar
Guolin Ke committed
699
700
701
702
703
704
  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_;
705
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
706
  feature_need_push_zeros_ = dataset->feature_need_push_zeros_;
Guolin Ke's avatar
Guolin Ke committed
707
708
709
710
711
712
713
714
715
}

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
716
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
717
718
719
  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
720
721
    if (bin_mappers.back()->GetDefaultBin() !=
        bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
722
723
      feature_need_push_zeros_.push_back(i);
    }
724
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
    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;
    }
  }
757
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
758
759
}

Guolin Ke's avatar
Guolin Ke committed
760
761
762
void Dataset::ReSize(data_size_t num_data) {
  if (num_data_ != num_data) {
    num_data_ = num_data;
763
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
764
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
765
    for (int group = 0; group < num_groups_; ++group) {
766
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
767
      feature_groups_[group]->ReSize(num_data_);
768
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
769
    }
770
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
771
772
773
  }
}

774
void Dataset::CopySubrow(const Dataset* fullset,
Guolin Ke's avatar
Guolin Ke committed
775
776
                         const data_size_t* used_indices,
                         data_size_t num_used_indices, bool need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
777
  CHECK(num_used_indices == num_data_);
778
  OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
779
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
780
  for (int group = 0; group < num_groups_; ++group) {
781
    OMP_LOOP_EX_BEGIN();
782
    feature_groups_[group]->CopySubrow(fullset->feature_groups_[group].get(),
Guolin Ke's avatar
Guolin Ke committed
783
                                       used_indices, num_used_indices);
784
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
785
  }
786
  OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
787
  if (need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
788
    metadata_.Init(fullset->metadata_, used_indices, num_used_indices);
Guolin Ke's avatar
Guolin Ke committed
789
  }
Guolin Ke's avatar
Guolin Ke committed
790
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
791
792
}

Guolin Ke's avatar
Guolin Ke committed
793
794
bool Dataset::SetFloatField(const char* field_name, const float* field_data,
                            data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
795
796
797
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
Guolin Ke's avatar
Guolin Ke committed
798
#ifdef LABEL_T_USE_DOUBLE
799
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
800
#else
801
    metadata_.SetLabel(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
802
#endif
Guolin Ke's avatar
Guolin Ke committed
803
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
804
#ifdef LABEL_T_USE_DOUBLE
805
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
806
#else
807
    metadata_.SetWeights(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
808
#endif
Guolin Ke's avatar
Guolin Ke committed
809
810
811
812
813
814
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
815
816
bool Dataset::SetDoubleField(const char* field_name, const double* field_data,
                             data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
817
818
819
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
820
    metadata_.SetInitScore(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
821
  } else {
822
    return false;
Guolin Ke's avatar
Guolin Ke committed
823
  }
824
  return true;
Guolin Ke's avatar
Guolin Ke committed
825
826
}

Guolin Ke's avatar
Guolin Ke committed
827
828
bool Dataset::SetIntField(const char* field_name, const int* field_data,
                          data_size_t num_element) {
829
830
831
  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
832
    metadata_.SetQuery(field_data, num_element);
833
834
835
836
837
838
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
839
840
bool Dataset::GetFloatField(const char* field_name, data_size_t* out_len,
                            const float** out_ptr) {
841
842
843
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("label") || name == std::string("target")) {
Guolin Ke's avatar
Guolin Ke committed
844
#ifdef LABEL_T_USE_DOUBLE
845
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
846
#else
847
848
    *out_ptr = metadata_.label();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
849
#endif
850
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
851
#ifdef LABEL_T_USE_DOUBLE
852
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
853
#else
854
855
    *out_ptr = metadata_.weights();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
856
#endif
Guolin Ke's avatar
Guolin Ke committed
857
858
859
860
861
862
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
863
864
bool Dataset::GetDoubleField(const char* field_name, data_size_t* out_len,
                             const double** out_ptr) {
Guolin Ke's avatar
Guolin Ke committed
865
866
867
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
868
    *out_ptr = metadata_.init_score();
Guolin Ke's avatar
Guolin Ke committed
869
    *out_len = static_cast<data_size_t>(metadata_.num_init_score());
870
  } else {
871
872
    return false;
  }
873
  return true;
874
875
}

Guolin Ke's avatar
Guolin Ke committed
876
877
bool Dataset::GetIntField(const char* field_name, data_size_t* out_len,
                          const int** out_ptr) {
878
879
880
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
881
    *out_ptr = metadata_.query_boundaries();
Guolin Ke's avatar
Guolin Ke committed
882
    *out_len = metadata_.num_queries() + 1;
Guolin Ke's avatar
Guolin Ke committed
883
884
885
  } else {
    return false;
  }
886
  return true;
887
888
}

Guolin Ke's avatar
Guolin Ke committed
889
void Dataset::SaveBinaryFile(const char* bin_filename) {
Guolin Ke's avatar
Guolin Ke committed
890
  if (bin_filename != nullptr && std::string(bin_filename) == data_filename_) {
891
    Log::Warning("Bianry file %s already exists", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
892
893
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
894
  // if not pass a filename, just append ".bin" of original file
Guolin Ke's avatar
Guolin Ke committed
895
  std::string bin_filename_str(data_filename_);
Guolin Ke's avatar
Guolin Ke committed
896
897
898
899
  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
900
  bool is_file_existed = false;
901
902

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
903
    is_file_existed = true;
904
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
905
  }
Guolin Ke's avatar
Guolin Ke committed
906

Guolin Ke's avatar
Guolin Ke committed
907
  if (!is_file_existed) {
908
909
    auto writer = VirtualFileWriter::Make(bin_filename);
    if (!writer->Init()) {
Guolin Ke's avatar
Guolin Ke committed
910
      Log::Fatal("Cannot write binary data to %s ", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
911
    }
912
    Log::Info("Saving data to binary file %s", bin_filename);
913
    size_t size_of_token = std::strlen(binary_file_token);
914
    writer->Write(binary_file_token, size_of_token);
Guolin Ke's avatar
Guolin Ke committed
915
    // get size of header
Guolin Ke's avatar
Guolin Ke committed
916
    size_t size_of_header = sizeof(num_data_) + sizeof(num_features_) + sizeof(num_total_features_)
917
      + sizeof(int) * num_total_features_ + sizeof(label_idx_) + sizeof(num_groups_)
918
919
      + 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;
Guolin Ke's avatar
Guolin Ke committed
920

921
922
923
924
    // size of feature names
    for (int i = 0; i < num_total_features_; ++i) {
      size_of_header += feature_names_[i].size() + sizeof(int);
    }
925
926
    // size of forced bins
    for (int i = 0; i < num_total_features_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
927
928
      size_of_header +=
          forced_bin_bounds_[i].size() * sizeof(double) + sizeof(int);
929
    }
930
    writer->Write(&size_of_header, sizeof(size_of_header));
Guolin Ke's avatar
Guolin Ke committed
931
    // write header
932
933
934
935
    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_));
936
    writer->Write(&max_bin_, sizeof(max_bin_));
Guolin Ke's avatar
Guolin Ke committed
937
938
    writer->Write(&bin_construct_sample_cnt_,
                  sizeof(bin_construct_sample_cnt_));
939
940
941
    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_));
942
943
944
945
946
    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_);
Guolin Ke's avatar
Guolin Ke committed
947
948
    writer->Write(group_bin_boundaries_.data(),
                  sizeof(uint64_t) * (num_groups_ + 1));
949
950
    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
951
952
953
    if (max_bin_by_feature_.empty()) {
      ArrayArgs<int32_t>::Assign(&max_bin_by_feature_, -1, num_total_features_);
    }
Guolin Ke's avatar
Guolin Ke committed
954
955
    writer->Write(max_bin_by_feature_.data(),
                  sizeof(int32_t) * num_total_features_);
Belinda Trotta's avatar
Belinda Trotta committed
956
957
958
    if (ArrayArgs<int32_t>::CheckAll(max_bin_by_feature_, -1)) {
      max_bin_by_feature_.clear();
    }
959
960
961
    // write feature names
    for (int i = 0; i < num_total_features_; ++i) {
      int str_len = static_cast<int>(feature_names_[i].size());
962
      writer->Write(&str_len, sizeof(int));
963
      const char* c_str = feature_names_[i].c_str();
964
      writer->Write(c_str, sizeof(char) * str_len);
965
    }
966
967
968
969
    // 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));
970

971
972
973
974
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
975

Guolin Ke's avatar
Guolin Ke committed
976
977
    // get size of meta data
    size_t size_of_metadata = metadata_.SizesInByte();
978
    writer->Write(&size_of_metadata, sizeof(size_of_metadata));
Guolin Ke's avatar
Guolin Ke committed
979
    // write meta data
980
    metadata_.SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
981
982

    // write feature data
Guolin Ke's avatar
Guolin Ke committed
983
    for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
984
      // get size of feature
Guolin Ke's avatar
Guolin Ke committed
985
      size_t size_of_feature = feature_groups_[i]->SizesInByte();
986
      writer->Write(&size_of_feature, sizeof(size_of_feature));
Guolin Ke's avatar
Guolin Ke committed
987
      // write feature
988
      feature_groups_[i]->SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
989
990
991
992
    }
  }
}

993
void Dataset::DumpTextFile(const char* text_filename) {
Guolin Ke's avatar
Guolin Ke committed
994
995
996
997
998
999
  FILE* file = NULL;
#if _MSC_VER
  fopen_s(&file, text_filename, "wt");
#else
  file = fopen(text_filename, "wt");
#endif
1000
1001
1002
1003
1004
  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: ");
1005
  for (auto n : feature_names_) {
1006
1007
    fprintf(file, "%s, ", n.c_str());
  }
Belinda Trotta's avatar
Belinda Trotta committed
1008
1009
1010
1011
  fprintf(file, "\nmax_bin_by_feature: ");
  for (auto i : max_bin_by_feature_) {
    fprintf(file, "%d, ", i);
  }
1012
  fprintf(file, "\n");
1013
  for (auto n : feature_names_) {
1014
1015
    fprintf(file, "%s, ", n.c_str());
  }
1016
1017
1018
1019
1020
1021
1022
  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]);
    }
  }
1023
1024
  std::vector<std::unique_ptr<BinIterator>> iterators;
  iterators.reserve(num_features_);
1025
  for (int j = 0; j < num_features_; ++j) {
1026
1027
    auto group_idx = feature2group_[j];
    auto sub_idx = feature2subfeature_[j];
Guolin Ke's avatar
Guolin Ke committed
1028
1029
    iterators.emplace_back(
        feature_groups_[group_idx]->SubFeatureIterator(sub_idx));
1030
  }
1031
  for (data_size_t i = 0; i < num_data_; ++i) {
1032
    fprintf(file, "\n");
1033
    for (int j = 0; j < num_total_features_; ++j) {
1034
      auto inner_feature_idx = used_feature_map_[j];
1035
1036
      if (inner_feature_idx < 0) {
        fprintf(file, "NA, ");
1037
      } else {
Guolin Ke's avatar
Guolin Ke committed
1038
        fprintf(file, "%d, ", iterators[inner_feature_idx]->Get(i));
1039
1040
1041
1042
1043
1044
      }
    }
  }
  fclose(file);
}

1045
void Dataset::InitTrain(const std::vector<int8_t>& is_feature_used,
1046
                        TrainingShareStates* share_state) const {
1047
  Common::FunctionTimer fun_time("Dataset::InitTrain", global_timer);
1048
1049
  share_state->is_use_subcol = false;
  if (share_state->multi_val_bin == nullptr) {
1050
1051
    return;
  }
1052
  const auto multi_val_bin = share_state->multi_val_bin.get();
1053
1054
1055
1056
1057
1058
1059
  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];
Nikita Titov's avatar
Nikita Titov committed
1060
    if (feature_groups_[i]->is_multi_val_) {
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
      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;
      }
1072
    } else if (!share_state->is_colwise) {
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
      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;
    }
  }
  const double k_subfeature_threshold = 0.6;
  if (sum_used_dense_ratio >= sum_dense_ratio * k_subfeature_threshold) {
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
    // only need to copy subset
    if (share_state->is_use_subrow && !share_state->is_subrow_copied) {
      if (share_state->multi_val_bin_subset == nullptr) {
        share_state->multi_val_bin_subset.reset(multi_val_bin->CreateLike(
            share_state->bagging_indices_cnt, multi_val_bin->num_bin(), total,
            multi_val_bin->num_element_per_row()));
      } else {
        share_state->multi_val_bin_subset->ReSize(
            share_state->bagging_indices_cnt, multi_val_bin->num_bin(), total,
            multi_val_bin->num_element_per_row());
      }
      share_state->multi_val_bin_subset->CopySubrow(
          multi_val_bin, share_state->bagging_use_indices,
          share_state->bagging_indices_cnt);
      // avoid to copy subset many times
      share_state->is_subrow_copied = true;
    }
  } else {
    share_state->is_use_subcol = true;
    std::vector<uint32_t> upper_bound;
    std::vector<uint32_t> lower_bound;
    std::vector<uint32_t> delta;
    share_state->hist_move_src.clear();
    share_state->hist_move_dest.clear();
    share_state->hist_move_size.clear();
1117

1118
1119
    int num_total_bin = 1;
    int new_num_total_bin = 1;
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
    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);

            share_state->hist_move_src.push_back(
                (new_num_total_bin - cur_num_bin) * 2);
            share_state->hist_move_dest.push_back((num_total_bin - cur_num_bin) *
                                                 2);
            share_state->hist_move_size.push_back(cur_num_bin * 2);
            delta.push_back(num_total_bin - new_num_total_bin);
          }
        }
      } else if (!share_state->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;
          }
1152
        }
1153
        int cur_num_bin = feature_groups_[i]->bin_offsets_.back() - 1;
1154
        num_total_bin += cur_num_bin;
1155
        if (is_group_used) {
1156
1157
1158
1159
          new_num_total_bin += cur_num_bin;

          lower_bound.push_back(num_total_bin - cur_num_bin);
          upper_bound.push_back(num_total_bin);
Nikita Titov's avatar
Nikita Titov committed
1160

1161
          share_state->hist_move_src.push_back(
1162
              (new_num_total_bin - cur_num_bin) * 2);
1163
1164
1165
          share_state->hist_move_dest.push_back((num_total_bin - cur_num_bin) *
                                               2);
          share_state->hist_move_size.push_back(cur_num_bin * 2);
1166
1167
1168
          delta.push_back(num_total_bin - new_num_total_bin);
        }
      }
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
    }
    // avoid out of range
    lower_bound.push_back(num_total_bin);
    upper_bound.push_back(num_total_bin);
    data_size_t num_data =
        share_state->is_use_subrow ? share_state->bagging_indices_cnt : num_data_;
    if (share_state->multi_val_bin_subset == nullptr) {
      share_state->multi_val_bin_subset.reset(multi_val_bin->CreateLike(
          num_data, new_num_total_bin, num_used, sum_used_dense_ratio));
    } else {
      share_state->multi_val_bin_subset->ReSize(num_data, new_num_total_bin,
                                               num_used, sum_used_dense_ratio);
    }
    if (share_state->is_use_subrow) {
      share_state->multi_val_bin_subset->CopySubrowAndSubcol(
          multi_val_bin, share_state->bagging_use_indices,
          share_state->bagging_indices_cnt, used_feature_index, lower_bound,
          upper_bound, delta);
      // may need to recopy subset
      share_state->is_subrow_copied = false;
    } else {
      share_state->multi_val_bin_subset->CopySubcol(
          multi_val_bin, used_feature_index, lower_bound, upper_bound, delta);
1192
1193
1194
1195
    }
  }
}

1196
1197
1198
1199
1200
1201
void Dataset::ConstructHistogramsMultiVal(const data_size_t* data_indices,
                                          data_size_t num_data,
                                          const score_t* gradients,
                                          const score_t* hessians,
                                          TrainingShareStates* share_state,
                                          hist_t* hist_data) const {
1202
1203
  Common::FunctionTimer fun_time("Dataset::ConstructHistogramsMultiVal",
                                 global_timer);
1204
1205
1206
1207
  const auto multi_val_bin =
      (share_state->is_use_subcol || share_state->is_use_subrow)
          ? share_state->multi_val_bin_subset.get()
          : share_state->multi_val_bin.get();
1208
1209
1210
  if (multi_val_bin == nullptr) {
    return;
  }
1211
  int num_threads = OMP_NUM_THREADS();
1212
1213
1214

  global_timer.Start("Dataset::sparse_bin_histogram");
  const int num_bin = multi_val_bin->num_bin();
1215
1216
  const int num_bin_aligned =
      (num_bin + kAlignedSize - 1) / kAlignedSize * kAlignedSize;
Guolin Ke's avatar
Guolin Ke committed
1217
1218
1219
1220
  int n_data_block = 1;
  int data_block_size = num_data;
  Threading::BlockInfo<data_size_t>(num_threads, num_data, 1024,
                                    &n_data_block, &data_block_size);
1221
1222
  const size_t buf_size =
      static_cast<size_t>(n_data_block - 1) * num_bin_aligned * 2;
1223
1224
  if (share_state->hist_buf.size() < buf_size) {
    share_state->hist_buf.resize(buf_size);
1225
  }
1226
  auto origin_hist_data = hist_data;
1227
1228
  if (share_state->is_use_subcol) {
    hist_data = share_state->TempBuf();
1229
  }
Guolin Ke's avatar
Guolin Ke committed
1230
  OMP_INIT_EX();
1231
#pragma omp parallel for schedule(static)
1232
  for (int tid = 0; tid < n_data_block; ++tid) {
Guolin Ke's avatar
Guolin Ke committed
1233
    OMP_LOOP_EX_BEGIN();
1234
1235
1236
1237
    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) {
1238
      data_ptr = share_state->hist_buf.data() +
1239
                 static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1240
    }
1241
    std::memset(reinterpret_cast<void*>(data_ptr), 0, num_bin * kHistEntrySize);
1242
    if (data_indices != nullptr && num_data < num_data_) {
1243
      if (!share_state->is_constant_hessian) {
1244
1245
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          hessians, data_ptr);
1246
      } else {
1247
1248
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
                                          data_ptr);
1249
1250
      }
    } else {
1251
      if (!share_state->is_constant_hessian) {
1252
1253
        multi_val_bin->ConstructHistogram(start, end, gradients, hessians,
                                          data_ptr);
1254
1255
1256
1257
      } else {
        multi_val_bin->ConstructHistogram(start, end, gradients, data_ptr);
      }
    }
Guolin Ke's avatar
Guolin Ke committed
1258
    OMP_LOOP_EX_END();
1259
  }
Guolin Ke's avatar
Guolin Ke committed
1260
  OMP_THROW_EX();
1261
1262
1263
  global_timer.Stop("Dataset::sparse_bin_histogram");

  global_timer.Start("Dataset::sparse_bin_histogram_merge");
Guolin Ke's avatar
Guolin Ke committed
1264
1265
1266
1267
  int n_bin_block = 1;
  int bin_block_size = num_bin;
  Threading::BlockInfo<data_size_t>(num_threads, num_bin, 512, &n_bin_block,
                                    &bin_block_size);
1268
  if (!share_state->is_constant_hessian) {
1269
#pragma omp parallel for schedule(static)
1270
1271
1272
1273
    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) {
1274
        auto src_ptr = share_state->hist_buf.data() +
1275
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1276
1277
1278
1279
1280
1281
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
    }
  } else {
1282
#pragma omp parallel for schedule(static)
1283
1284
1285
1286
    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) {
1287
        auto src_ptr = share_state->hist_buf.data() +
1288
                       static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1289
1290
1291
1292
        for (int i = start * 2; i < end * 2; ++i) {
          hist_data[i] += src_ptr[i];
        }
      }
1293
      for (int i = start; i < end; ++i) {
1294
1295
1296
1297
1298
        GET_HESS(hist_data, i) = GET_HESS(hist_data, i) * hessians[0];
      }
    }
  }
  global_timer.Stop("Dataset::sparse_bin_histogram_merge");
1299
  global_timer.Start("Dataset::sparse_bin_histogram_move");
1300
  share_state->HistMove(hist_data, origin_hist_data);
1301
  global_timer.Stop("Dataset::sparse_bin_histogram_move");
1302
1303
}

1304
1305
1306
1307
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,
1308
    TrainingShareStates* share_state, hist_t* hist_data) const {
1309
1310
  Common::FunctionTimer fun_timer("Dataset::ConstructHistograms", global_timer);
  if (num_data < 0 || hist_data == nullptr) {
Guolin Ke's avatar
Guolin Ke committed
1311
1312
    return;
  }
1313
  if (!share_state->is_colwise) {
1314
    return ConstructHistogramsMultiVal(data_indices, num_data, gradients,
1315
                                       hessians, share_state, hist_data);
1316
1317
1318
1319
1320
  }
  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
1321
1322
  for (int group = 0; group < num_groups_; ++group) {
    const int f_cnt = group_feature_cnt_[group];
1323
    bool is_group_used = false;
Guolin Ke's avatar
Guolin Ke committed
1324
1325
1326
    for (int j = 0; j < f_cnt; ++j) {
      const int fidx = group_feature_start_[group] + j;
      if (is_feature_used[fidx]) {
1327
        is_group_used = true;
Guolin Ke's avatar
Guolin Ke committed
1328
1329
1330
        break;
      }
    }
1331
    if (is_group_used) {
1332
1333
1334
1335
      if (feature_groups_[group]->is_multi_val_) {
        multi_val_groud_id = group;
      } else {
        used_dense_group.push_back(group);
1336
      }
Guolin Ke's avatar
Guolin Ke committed
1337
    }
1338
1339
1340
1341
1342
1343
1344
1345
  }
  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_) {
1346
      if (!share_state->is_constant_hessian) {
Guolin Ke's avatar
Guolin Ke committed
1347
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1348
1349
1350
1351
1352
        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 {
Guolin Ke's avatar
Guolin Ke committed
1353
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1354
1355
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
1356
1357
        }
      }
1358
1359
      ptr_ordered_grad = ordered_gradients;
      ptr_ordered_hess = ordered_hessians;
1360
      if (!share_state->is_constant_hessian) {
1361
        OMP_INIT_EX();
1362
#pragma omp parallel for schedule(static)
1363
1364
1365
1366
1367
1368
1369
        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,
1370
                      num_bin * kHistEntrySize);
1371
          // construct histograms for smaller leaf
1372
          feature_groups_[group]->bin_data_->ConstructHistogram(
1373
1374
              data_indices, 0, num_data, ptr_ordered_grad, ptr_ordered_hess,
              data_ptr);
1375
          OMP_LOOP_EX_END();
1376
        }
1377
1378
1379
1380
        OMP_THROW_EX();

      } else {
        OMP_INIT_EX();
1381
#pragma omp parallel for schedule(static)
1382
1383
1384
1385
1386
1387
1388
        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,
1389
                      num_bin * kHistEntrySize);
1390
          // construct histograms for smaller leaf
1391
          feature_groups_[group]->bin_data_->ConstructHistogram(
1392
1393
1394
1395
1396
1397
              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();
1398
        }
1399
        OMP_THROW_EX();
1400
      }
1401
    } else {
1402
      if (!share_state->is_constant_hessian) {
1403
        OMP_INIT_EX();
1404
#pragma omp parallel for schedule(static)
1405
1406
1407
1408
1409
1410
1411
        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,
1412
                      num_bin * kHistEntrySize);
1413
          // construct histograms for smaller leaf
1414
          feature_groups_[group]->bin_data_->ConstructHistogram(
1415
1416
              0, num_data, ptr_ordered_grad, ptr_ordered_hess, data_ptr);
          OMP_LOOP_EX_END();
1417
        }
1418
1419
1420
        OMP_THROW_EX();
      } else {
        OMP_INIT_EX();
1421
#pragma omp parallel for schedule(static)
1422
1423
1424
1425
1426
1427
1428
        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,
1429
                      num_bin * kHistEntrySize);
1430
1431
1432
1433
1434
1435
1436
1437
          // 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();
1438
        }
1439
        OMP_THROW_EX();
1440
      }
Guolin Ke's avatar
Guolin Ke committed
1441
1442
    }
  }
1443
1444
  global_timer.Stop("Dataset::dense_bin_histogram");
  if (multi_val_groud_id >= 0) {
1445
    ConstructHistogramsMultiVal(
1446
1447
        data_indices, num_data, gradients, hessians, share_state,
        hist_data + group_bin_boundaries_[multi_val_groud_id] * 2);
1448
  }
Guolin Ke's avatar
Guolin Ke committed
1449
1450
}

Guolin Ke's avatar
Guolin Ke committed
1451
1452
void Dataset::FixHistogram(int feature_idx, double sum_gradient,
                           double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1453
1454
  const int group = feature2group_[feature_idx];
  const int sub_feature = feature2subfeature_[feature_idx];
Guolin Ke's avatar
Guolin Ke committed
1455
1456
  const BinMapper* bin_mapper =
      feature_groups_[group]->bin_mappers_[sub_feature].get();
Guolin Ke's avatar
Guolin Ke committed
1457
1458
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1459
    const int num_bin = bin_mapper->num_bin();
1460
1461
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1462
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1463
      if (i != most_freq_bin) {
1464
1465
        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
1466
1467
1468
1469
1470
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
1471
template <typename T>
Guolin Ke's avatar
Guolin Ke committed
1472
1473
void PushVector(std::vector<T>* dest, const std::vector<T>& src) {
  dest->reserve(dest->size() + src.size());
1474
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1475
    dest->push_back(i);
1476
1477
1478
  }
}

Guolin Ke's avatar
Guolin Ke committed
1479
1480
1481
template <typename T>
void PushOffset(std::vector<T>* dest, const std::vector<T>& src,
                const T& offset) {
Guolin Ke's avatar
Guolin Ke committed
1482
  dest->reserve(dest->size() + src.size());
1483
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1484
    dest->push_back(i + offset);
1485
1486
1487
  }
}

Guolin Ke's avatar
Guolin Ke committed
1488
1489
1490
1491
template <typename T>
void PushClearIfEmpty(std::vector<T>* dest, const size_t dest_len,
                      const std::vector<T>& src, const size_t src_len,
                      const T& deflt) {
Guolin Ke's avatar
Guolin Ke committed
1492
  if (!dest->empty() && !src.empty()) {
1493
    PushVector(dest, src);
Guolin Ke's avatar
Guolin Ke committed
1494
  } else if (!dest->empty() && src.empty()) {
1495
    for (size_t i = 0; i < src_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1496
      dest->push_back(deflt);
1497
    }
Guolin Ke's avatar
Guolin Ke committed
1498
  } else if (dest->empty() && !src.empty()) {
1499
    for (size_t i = 0; i < dest_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1500
      dest->push_back(deflt);
1501
1502
1503
1504
1505
    }
    PushVector(dest, src);
  }
}

1506
void Dataset::AddFeaturesFrom(Dataset* other) {
1507
  if (other->num_data_ != num_data_) {
1508
    Log::Fatal(
Guolin Ke's avatar
Guolin Ke committed
1509
1510
        "Cannot add features from other Dataset with a different number of "
        "rows");
1511
  }
Guolin Ke's avatar
Guolin Ke committed
1512
1513
1514
  PushVector(&feature_names_, other->feature_names_);
  PushVector(&feature2subfeature_, other->feature2subfeature_);
  PushVector(&group_feature_cnt_, other->group_feature_cnt_);
1515
  PushVector(&forced_bin_bounds_, other->forced_bin_bounds_);
1516
  feature_groups_.reserve(other->feature_groups_.size());
Guolin Ke's avatar
Guolin Ke committed
1517
1518
  // FIXME: fix the multiple multi-val feature groups, they need to be merged
  // into one multi-val group
1519
  for (auto& fg : other->feature_groups_) {
1520
1521
    feature_groups_.emplace_back(new FeatureGroup(*fg));
  }
1522
1523
  for (auto feature_idx : other->used_feature_map_) {
    if (feature_idx >= 0) {
1524
1525
1526
1527
1528
      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
1529
1530
  PushOffset(&real_feature_idx_, other->real_feature_idx_, num_total_features_);
  PushOffset(&feature2group_, other->feature2group_, num_groups_);
1531
1532
  auto bin_offset = group_bin_boundaries_.back();
  // Skip the leading 0 when copying group_bin_boundaries.
Guolin Ke's avatar
Guolin Ke committed
1533
1534
  for (auto i = other->group_bin_boundaries_.begin() + 1;
       i < other->group_bin_boundaries_.end(); ++i) {
1535
1536
    group_bin_boundaries_.push_back(*i + bin_offset);
  }
Guolin Ke's avatar
Guolin Ke committed
1537
  PushOffset(&group_feature_start_, other->group_feature_start_, num_features_);
1538
  PushClearIfEmpty(&max_bin_by_feature_, num_total_features_, other->max_bin_by_feature_, other->num_total_features_, -1);
1539

1540
1541
1542
1543
1544
  num_features_ += other->num_features_;
  num_total_features_ += other->num_total_features_;
  num_groups_ += other->num_groups_;
}

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