dataset.cpp 64.8 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
 */
6
7
8
#include <LightGBM/dataset.h>

#include <LightGBM/feature_group.h>
9
#include <LightGBM/cuda/vector_cudahost.h>
10
11
12
13
#include <LightGBM/utils/array_args.h>
#include <LightGBM/utils/openmp_wrapper.h>
#include <LightGBM/utils/threading.h>

14
15
16
17
18
19
#include <chrono>
#include <cstdio>
#include <limits>
#include <sstream>
#include <unordered_map>

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

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

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

33
Dataset::Dataset(data_size_t num_data) {
34
  CHECK_GT(num_data, 0);
Guolin Ke's avatar
Guolin Ke committed
35
  data_filename_ = "noname";
Guolin Ke's avatar
Guolin Ke committed
36
  num_data_ = num_data;
Guolin Ke's avatar
Guolin Ke committed
37
  metadata_.Init(num_data_, NO_SPECIFIC, NO_SPECIFIC);
Guolin Ke's avatar
Guolin Ke committed
38
  is_finish_load_ = false;
39
  wait_for_manual_finish_ = false;
Guolin Ke's avatar
Guolin Ke committed
40
  group_bin_boundaries_.push_back(0);
41
  has_raw_ = false;
Guolin Ke's avatar
Guolin Ke committed
42
43
}

Guolin Ke's avatar
Guolin Ke committed
44
Dataset::~Dataset() {}
Guolin Ke's avatar
Guolin Ke committed
45

46
std::vector<std::vector<int>> OneFeaturePerGroup(const std::vector<int>& used_features) {
Guolin Ke's avatar
Guolin Ke committed
47
48
49
50
51
52
53
54
  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;
}

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

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

Guolin Ke's avatar
Guolin Ke committed
77
78
79
80
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
81
82
83
84
85
86
87
88
89
  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
90
91
      if (bin_mapper->ValueToBin(sample_values[j]) !=
          bin_mapper->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
92
93
94
95
96
97
98
99
100
101
        ret.push_back(i);
      }
      ++i;
    } else {
      ret.push_back(i++);
    }
  }
  return ret;
}

Guolin Ke's avatar
Guolin Ke committed
102
103
104
105
106
107
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
108
  const int max_search_group = 100;
109
  const int max_bin_per_group = 256;
Guolin Ke's avatar
Guolin Ke committed
110
111
  const data_size_t single_val_max_conflict_cnt =
      static_cast<data_size_t>(total_sample_cnt / 10000);
112
113
  multi_val_group->clear();

Guolin Ke's avatar
Guolin Ke committed
114
115
116
  Random rand(num_data);
  std::vector<std::vector<int>> features_in_group;
  std::vector<std::vector<bool>> conflict_marks;
117
118
  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
119
120
  std::vector<int> group_num_bin;

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

Guolin Ke's avatar
Guolin Ke committed
241
242
243
244
245
246
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) {
247
  Common::FunctionTimer fun_timer("Dataset::FastFeatureBundling", global_timer);
Guolin Ke's avatar
Guolin Ke committed
248
  std::vector<size_t> feature_non_zero_cnt;
249
  feature_non_zero_cnt.reserve(used_features.size());
Guolin Ke's avatar
Guolin Ke committed
250
251
  // put dense feature first
  for (auto fidx : used_features) {
252
253
254
255
256
    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
257
258
259
  }
  // sort by non zero cnt
  std::vector<int> sorted_idx;
260
  sorted_idx.reserve(used_features.size());
261
  for (int i = 0; i < static_cast<int>(used_features.size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
262
263
264
    sorted_idx.emplace_back(i);
  }
  // sort by non zero cnt, bigger first
265
266
  std::stable_sort(sorted_idx.begin(), sorted_idx.end(),
                   [&feature_non_zero_cnt](int a, int b) {
Guolin Ke's avatar
Guolin Ke committed
267
268
                     return feature_non_zero_cnt[a] > feature_non_zero_cnt[b];
                   });
Guolin Ke's avatar
Guolin Ke committed
269
270

  std::vector<int> feature_order_by_cnt;
271
  feature_order_by_cnt.reserve(sorted_idx.size());
Guolin Ke's avatar
Guolin Ke committed
272
273
274
  for (auto sidx : sorted_idx) {
    feature_order_by_cnt.push_back(used_features[sidx]);
  }
275

Guolin Ke's avatar
Guolin Ke committed
276
277
278
279
280
281
  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
282
283
284
    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
285
286
287
288
289
290
291
292
    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];
    }
  }
293
  std::vector<int8_t> group_is_multi_val, group_is_multi_val2;
Guolin Ke's avatar
Guolin Ke committed
294
295
296
297
298
299
300
301
  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);
302

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

Guolin Ke's avatar
Guolin Ke committed
320
321
322
void Dataset::Construct(std::vector<std::unique_ptr<BinMapper>>* bin_mappers,
                        int num_total_features,
                        const std::vector<std::vector<double>>& forced_bins,
323
324
325
326
327
328
                        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) {
329
  num_total_features_ = num_total_features;
Nikita Titov's avatar
Nikita Titov committed
330
  CHECK_EQ(num_total_features_, static_cast<int>(bin_mappers->size()));
Guolin Ke's avatar
Guolin Ke committed
331
332
  // get num_features
  std::vector<int> used_features;
Guolin Ke's avatar
Guolin Ke committed
333
  auto& ref_bin_mappers = *bin_mappers;
Guolin Ke's avatar
Guolin Ke committed
334
  for (int i = 0; i < static_cast<int>(bin_mappers->size()); ++i) {
Guolin Ke's avatar
Guolin Ke committed
335
    if (ref_bin_mappers[i] != nullptr && !ref_bin_mappers[i]->is_trivial()) {
Guolin Ke's avatar
Guolin Ke committed
336
      used_features.emplace_back(i);
Guolin Ke's avatar
Guolin Ke committed
337
    }
Guolin Ke's avatar
Guolin Ke committed
338
  }
Guolin Ke's avatar
Guolin Ke committed
339
  if (used_features.empty()) {
Guolin Ke's avatar
Guolin Ke committed
340
    Log::Warning(
341
342
343
        "There are no meaningful features which satisfy the provided configuration. "
        "Decreasing Dataset parameters min_data_in_bin or min_data_in_leaf and re-constructing "
        "Dataset might resolve this warning.");
Guolin Ke's avatar
Guolin Ke committed
344
  }
345
  auto features_in_group = OneFeaturePerGroup(used_features);
346
347

  auto is_sparse = io_config.is_enable_sparse;
348
  if (io_config.device_type == std::string("cuda") || io_config.device_type == std::string("cuda_exp")) {
349
      LGBM_config_::current_device = lgbm_device_cuda;
350
      if ((io_config.device_type == std::string("cuda") || io_config.device_type == std::string("cuda_exp")) && is_sparse) {
351
        Log::Warning("Using sparse features with CUDA is currently not supported.");
352
        is_sparse = false;
353
354
355
      }
  }

356
  std::vector<int8_t> group_is_multi_val(used_features.size(), 0);
357
  if (io_config.enable_bundle && !used_features.empty()) {
358
359
    bool lgbm_is_gpu_used = io_config.device_type == std::string("gpu") || io_config.device_type == std::string("cuda")
      || io_config.device_type == std::string("cuda_exp");
Guolin Ke's avatar
Guolin Ke committed
360
361
362
    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),
363
364
        used_features, num_data_, lgbm_is_gpu_used,
        is_sparse, &group_is_multi_val);
Guolin Ke's avatar
Guolin Ke committed
365
366
  }

Guolin Ke's avatar
Guolin Ke committed
367
368
369
370
371
372
373
374
375
376
  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_);
Guolin Ke's avatar
Guolin Ke committed
377
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
378
379
380
381
382
  group_bin_boundaries_.clear();
  uint64_t num_total_bin = 0;
  group_bin_boundaries_.push_back(num_total_bin);
  group_feature_start_.resize(num_groups_);
  group_feature_cnt_.resize(num_groups_);
Guolin Ke's avatar
Guolin Ke committed
383
384
385
  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());
Guolin Ke's avatar
Guolin Ke committed
386
387
    group_feature_start_[i] = cur_fidx;
    group_feature_cnt_[i] = cur_cnt_features;
Guolin Ke's avatar
Guolin Ke committed
388
389
390
391
392
393
394
395
    // 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
396
      cur_bin_mappers.emplace_back(ref_bin_mappers[real_fidx].release());
Guolin Ke's avatar
Guolin Ke committed
397
398
      if (cur_bin_mappers.back()->GetDefaultBin() !=
          cur_bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
399
400
        feature_need_push_zeros_.push_back(cur_fidx);
      }
Guolin Ke's avatar
Guolin Ke committed
401
402
      ++cur_fidx;
    }
Guolin Ke's avatar
Guolin Ke committed
403
    feature_groups_.emplace_back(std::unique_ptr<FeatureGroup>(
404
      new FeatureGroup(cur_cnt_features, group_is_multi_val[i], &cur_bin_mappers, num_data_, i)));
Guolin Ke's avatar
Guolin Ke committed
405
406
407
    num_total_bin += feature_groups_[i]->num_total_bin_;
    group_bin_boundaries_.push_back(num_total_bin);
  }
Belinda Trotta's avatar
Belinda Trotta committed
408
  if (!io_config.max_bin_by_feature.empty()) {
409
410
411
412
    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
413
    max_bin_by_feature_.resize(num_total_features_);
Guolin Ke's avatar
Guolin Ke committed
414
415
    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
416
  }
417
  forced_bin_bounds_ = forced_bins;
418
419
420
421
422
  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;
423
424
425
426
427
428
429
430
431
432
433
434
  has_raw_ = false;
  if (io_config.linear_tree) {
    has_raw_ = true;
  }
  numeric_feature_map_ = std::vector<int>(num_features_, -1);
  num_numeric_features_ = 0;
  for (int i = 0; i < num_features_; ++i) {
    if (FeatureBinMapper(i)->bin_type() == BinType::NumericalBin) {
      numeric_feature_map_[i] = num_numeric_features_;
      ++num_numeric_features_;
    }
  }
435
436
  device_type_ = io_config.device_type;
  gpu_device_id_ = io_config.gpu_device_id;
437
438
}

Guolin Ke's avatar
Guolin Ke committed
439
void Dataset::FinishLoad() {
Guolin Ke's avatar
Guolin Ke committed
440
441
442
  if (is_finish_load_) {
    return;
  }
443
444
  if (num_groups_ > 0) {
    for (int i = 0; i < num_groups_; ++i) {
445
      feature_groups_[i]->FinishLoad();
446
    }
Guolin Ke's avatar
Guolin Ke committed
447
  }
448
449
  metadata_.FinishLoad();

450
451
452
453
454
455
456
457
  #ifdef USE_CUDA_EXP
  if (device_type_ == std::string("cuda_exp")) {
    CreateCUDAColumnData();
    metadata_.CreateCUDAMetadata(gpu_device_id_);
  } else {
    cuda_column_data_.reset(nullptr);
  }
  #endif  // USE_CUDA_EXP
Guolin Ke's avatar
Guolin Ke committed
458
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
459
}
Guolin Ke's avatar
Guolin Ke committed
460

461
void PushDataToMultiValBin(
Guolin Ke's avatar
Guolin Ke committed
462
    data_size_t num_data, const std::vector<uint32_t> most_freq_bins,
463
    const std::vector<uint32_t> offsets,
Guolin Ke's avatar
Guolin Ke committed
464
    std::vector<std::vector<std::unique_ptr<BinIterator>>>* iters,
465
466
467
    MultiValBin* ret) {
  Common::FunctionTimer fun_time("Dataset::PushDataToMultiValBin",
                                 global_timer);
468
  if (ret->IsSparse()) {
Guolin Ke's avatar
Guolin Ke committed
469
470
471
472
473
    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) {
Guolin Ke's avatar
Guolin Ke committed
474
            (*iters)[tid][j]->Reset(start);
475
          }
Guolin Ke's avatar
Guolin Ke committed
476
477
478
          for (data_size_t i = start; i < end; ++i) {
            cur_data.clear();
            for (size_t j = 0; j < most_freq_bins.size(); ++j) {
479
              // for sparse multi value bin, we store the feature bin values with offset added
Guolin Ke's avatar
Guolin Ke committed
480
              auto cur_bin = (*iters)[tid][j]->Get(i);
Guolin Ke's avatar
Guolin Ke committed
481
482
483
484
485
486
487
488
489
490
              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);
491
          }
Guolin Ke's avatar
Guolin Ke committed
492
        });
493
  } else {
Guolin Ke's avatar
Guolin Ke committed
494
495
496
497
    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) {
Guolin Ke's avatar
Guolin Ke committed
498
            (*iters)[tid][j]->Reset(start);
Guolin Ke's avatar
Guolin Ke committed
499
500
501
          }
          for (data_size_t i = start; i < end; ++i) {
            for (size_t j = 0; j < most_freq_bins.size(); ++j) {
502
              // for dense multi value bin, the feature bin values without offsets are used
Guolin Ke's avatar
Guolin Ke committed
503
              auto cur_bin = (*iters)[tid][j]->Get(i);
Guolin Ke's avatar
Guolin Ke committed
504
              cur_data[j] = cur_bin;
505
            }
Guolin Ke's avatar
Guolin Ke committed
506
            ret->PushOneRow(tid, i, cur_data);
507
          }
Guolin Ke's avatar
Guolin Ke committed
508
        });
509
510
511
  }
}

512
MultiValBin* Dataset::GetMultiBinFromSparseFeatures(const std::vector<uint32_t>& offsets) const {
513
514
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromSparseFeatures",
                                 global_timer);
515
516
517
518
519
520
521
522
523
524
525
526
527
528
  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 int num_feature = feature_groups_[multi_group_id]->num_feature_;
529
  int num_threads = OMP_NUM_THREADS();
530
531
532
533
534

  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) {
535
#pragma omp parallel for schedule(static, 1)
536
    for (int tid = 0; tid < num_threads; ++tid) {
537
538
      iters[tid].emplace_back(
          feature_groups_[multi_group_id]->SubFeatureIterator(i));
539
    }
540
541
542
543
    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();
544
545
  }
  sum_sparse_rate /= num_feature;
546
547
  Log::Debug("Dataset::GetMultiBinFromSparseFeatures: sparse rate %f",
             sum_sparse_rate);
548
  std::unique_ptr<MultiValBin> ret;
549
  ret.reset(MultiValBin::CreateMultiValBin(num_data_, offsets.back(),
550
                                           num_feature, sum_sparse_rate, offsets));
Guolin Ke's avatar
Guolin Ke committed
551
  PushDataToMultiValBin(num_data_, most_freq_bins, offsets, &iters, ret.get());
552
553
554
555
  ret->FinishLoad();
  return ret.release();
}

556
MultiValBin* Dataset::GetMultiBinFromAllFeatures(const std::vector<uint32_t>& offsets) const {
557
558
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromAllFeatures",
                                 global_timer);
559
  int num_threads = OMP_NUM_THREADS();
560
561
562
563
564
  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;
565
566
567
568
569
570
571
572
573
574
575
576
577
  int ncol = 0;
  for (int gid = 0; gid < num_groups_; ++gid) {
    if (feature_groups_[gid]->is_multi_val_) {
      ncol += feature_groups_[gid]->num_feature_;
    } else {
      ++ncol;
    }
    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 /= ncol;
578
579
580
581
582
  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];
        most_freq_bins.push_back(bin_mapper->GetMostFreqBin());
583
#pragma omp parallel for schedule(static, 1)
584
        for (int tid = 0; tid < num_threads; ++tid) {
585
586
          iters[tid].emplace_back(
              feature_groups_[gid]->SubFeatureIterator(fid));
587
588
589
590
591
592
593
594
595
        }
      }
    } else {
      most_freq_bins.push_back(0);
      for (int tid = 0; tid < num_threads; ++tid) {
        iters[tid].emplace_back(feature_groups_[gid]->FeatureGroupIterator());
      }
    }
  }
596
  CHECK(static_cast<int>(most_freq_bins.size()) == ncol);
597
598
599
  Log::Debug("Dataset::GetMultiBinFromAllFeatures: sparse rate %f",
             1.0 - sum_dense_ratio);
  ret.reset(MultiValBin::CreateMultiValBin(
600
      num_data_, offsets.back(), static_cast<int>(most_freq_bins.size()),
601
      1.0 - sum_dense_ratio, offsets));
Guolin Ke's avatar
Guolin Ke committed
602
  PushDataToMultiValBin(num_data_, most_freq_bins, offsets, &iters, ret.get());
603
604
605
606
  ret->FinishLoad();
  return ret.release();
}

607
TrainingShareStates* Dataset::GetShareStates(
608
609
    score_t* gradients, score_t* hessians,
    const std::vector<int8_t>& is_feature_used, bool is_constant_hessian,
610
    bool force_col_wise, bool force_row_wise) const {
611
612
  Common::FunctionTimer fun_timer("Dataset::TestMultiThreadingMethod",
                                  global_timer);
613
  if (force_col_wise && force_row_wise) {
614
    Log::Fatal(
615
        "Cannot set both of `force_col_wise` and `force_row_wise` to `true` at "
616
        "the same time");
617
618
  }
  if (num_groups_ <= 0) {
619
    TrainingShareStates* share_state = new TrainingShareStates();
620
    share_state->is_col_wise = true;
621
622
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
623
  }
624
  if (force_col_wise) {
625
    TrainingShareStates* share_state = new TrainingShareStates();
626
627
628
629
630
631
    std::vector<uint32_t> offsets;
    share_state->CalcBinOffsets(
      feature_groups_, &offsets, true);
    share_state->SetMultiValBin(GetMultiBinFromSparseFeatures(offsets),
      num_data_, feature_groups_, false, true);
    share_state->is_col_wise = true;
632
633
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
634
  } else if (force_row_wise) {
635
    TrainingShareStates* share_state = new TrainingShareStates();
636
637
638
639
640
641
    std::vector<uint32_t> offsets;
    share_state->CalcBinOffsets(
      feature_groups_, &offsets, false);
    share_state->SetMultiValBin(GetMultiBinFromAllFeatures(offsets), num_data_,
      feature_groups_, false, false);
    share_state->is_col_wise = false;
642
643
    share_state->is_constant_hessian = is_constant_hessian;
    return share_state;
644
645
646
  } else {
    std::unique_ptr<MultiValBin> sparse_bin;
    std::unique_ptr<MultiValBin> all_bin;
647
648
649
650
    std::unique_ptr<TrainingShareStates> col_wise_state;
    std::unique_ptr<TrainingShareStates> row_wise_state;
    col_wise_state.reset(new TrainingShareStates());
    row_wise_state.reset(new TrainingShareStates());
651

652
    std::chrono::duration<double, std::milli> col_wise_init_time, row_wise_init_time;
653
    auto start_time = std::chrono::steady_clock::now();
654
655
656
657
    std::vector<uint32_t> col_wise_offsets;
    col_wise_state->CalcBinOffsets(feature_groups_, &col_wise_offsets, true);
    col_wise_state->SetMultiValBin(GetMultiBinFromSparseFeatures(col_wise_offsets), num_data_,
      feature_groups_, false, true);
658
    col_wise_init_time = std::chrono::steady_clock::now() - start_time;
659

660
    start_time = std::chrono::steady_clock::now();
661
662
663
664
665
666
667
668
    std::vector<uint32_t> row_wise_offsets;
    row_wise_state->CalcBinOffsets(feature_groups_, &row_wise_offsets, false);
    row_wise_state->SetMultiValBin(GetMultiBinFromAllFeatures(row_wise_offsets), num_data_,
      feature_groups_, false, false);
    row_wise_init_time = std::chrono::steady_clock::now() - start_time;

    uint64_t max_total_bin = std::max<uint64_t>(row_wise_state->num_hist_total_bin(),
      col_wise_state->num_hist_total_bin());
669
    std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>
670
        hist_data(max_total_bin * 2);
671
672

    Log::Debug(
673
674
675
676
677
678
679
680
681
      "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);

    col_wise_state->is_col_wise = true;
    col_wise_state->is_constant_hessian = is_constant_hessian;
    InitTrain(is_feature_used, col_wise_state.get());
    row_wise_state->is_col_wise = false;
    row_wise_state->is_constant_hessian = is_constant_hessian;
    InitTrain(is_feature_used, row_wise_state.get());
682
    std::chrono::duration<double, std::milli> col_wise_time, row_wise_time;
683
    start_time = std::chrono::steady_clock::now();
684
    ConstructHistograms(is_feature_used, nullptr, num_data_, gradients,
685
                        hessians, gradients, hessians, col_wise_state.get(),
686
                        hist_data.data());
687
688
    col_wise_time = std::chrono::steady_clock::now() - start_time;
    start_time = std::chrono::steady_clock::now();
Guolin Ke's avatar
Guolin Ke committed
689
    ConstructHistograms(is_feature_used, nullptr, num_data_, gradients,
690
                        hessians, gradients, hessians, row_wise_state.get(),
Guolin Ke's avatar
Guolin Ke committed
691
                        hist_data.data());
692
    row_wise_time = std::chrono::steady_clock::now() - start_time;
693

694
    if (col_wise_time < row_wise_time) {
695
696
      auto overhead_cost = row_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
697
          "Auto-choosing col-wise multi-threading, the overhead of testing was "
Nikita Titov's avatar
Nikita Titov committed
698
699
          "%f seconds.\n"
          "You can set `force_col_wise=true` to remove the overhead.",
700
          overhead_cost * 1e-3);
701
      return col_wise_state.release();
702
    } else {
703
704
      auto overhead_cost = col_wise_init_time + row_wise_time + col_wise_time;
      Log::Warning(
705
          "Auto-choosing row-wise multi-threading, the overhead of testing was "
Nikita Titov's avatar
Nikita Titov committed
706
707
708
          "%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`.",
709
          overhead_cost * 1e-3);
710
      if (row_wise_state->IsSparseRowwise()) {
711
        Log::Debug("Using Sparse Multi-Val Bin");
712
      } else {
713
        Log::Debug("Using Dense Multi-Val Bin");
714
      }
715
      return row_wise_state.release();
716
717
718
719
    }
  }
}

720
void Dataset::CopyFeatureMapperFrom(const Dataset* dataset) {
Guolin Ke's avatar
Guolin Ke committed
721
  feature_groups_.clear();
Guolin Ke's avatar
Guolin Ke committed
722
  num_features_ = dataset->num_features_;
Guolin Ke's avatar
Guolin Ke committed
723
  num_groups_ = dataset->num_groups_;
724
  has_raw_ = dataset->has_raw();
Guolin Ke's avatar
Guolin Ke committed
725
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
726
  for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
727
728
    feature_groups_.emplace_back(
        new FeatureGroup(*dataset->feature_groups_[i], num_data_));
Guolin Ke's avatar
Guolin Ke committed
729
  }
Guolin Ke's avatar
Guolin Ke committed
730
  feature_groups_.shrink_to_fit();
Guolin Ke's avatar
Guolin Ke committed
731
732
733
  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
734
  label_idx_ = dataset->label_idx_;
Guolin Ke's avatar
Guolin Ke committed
735
736
737
738
739
740
  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_;
741
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
742
  feature_need_push_zeros_ = dataset->feature_need_push_zeros_;
743
744
745
746
747
  max_bin_ = dataset->max_bin_;
  min_data_in_bin_ = dataset->min_data_in_bin_;
  bin_construct_sample_cnt_ = dataset->bin_construct_sample_cnt_;
  use_missing_ = dataset->use_missing_;
  zero_as_missing_ = dataset->zero_as_missing_;
Guolin Ke's avatar
Guolin Ke committed
748
749
750
751
752
753
}

void Dataset::CreateValid(const Dataset* dataset) {
  feature_groups_.clear();
  num_features_ = dataset->num_features_;
  num_groups_ = num_features_;
754
755
756
757
758
  max_bin_ = dataset->max_bin_;
  min_data_in_bin_ = dataset->min_data_in_bin_;
  bin_construct_sample_cnt_ = dataset->bin_construct_sample_cnt_;
  use_missing_ = dataset->use_missing_;
  zero_as_missing_ = dataset->zero_as_missing_;
Guolin Ke's avatar
Guolin Ke committed
759
760
  feature2group_.clear();
  feature2subfeature_.clear();
761
762
763
764
  has_raw_ = dataset->has_raw();
  numeric_feature_map_ = dataset->numeric_feature_map_;
  num_numeric_features_ = dataset->num_numeric_features_;
  // copy feature bin mapper data
Guolin Ke's avatar
Guolin Ke committed
765
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
766
767
768
769
770
  group_bin_boundaries_.clear();
  uint64_t num_total_bin = 0;
  group_bin_boundaries_.push_back(num_total_bin);
  group_feature_start_.resize(num_groups_);
  group_feature_cnt_.resize(num_groups_);
Guolin Ke's avatar
Guolin Ke committed
771
772
773
  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
774
775
    if (bin_mappers.back()->GetDefaultBin() !=
        bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
776
777
      feature_need_push_zeros_.push_back(i);
    }
778
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
779
780
    feature2group_.push_back(i);
    feature2subfeature_.push_back(0);
Guolin Ke's avatar
Guolin Ke committed
781
782
783
784
    num_total_bin += feature_groups_[i]->num_total_bin_;
    group_bin_boundaries_.push_back(num_total_bin);
    group_feature_start_[i] = i;
    group_feature_cnt_[i] = 1;
Guolin Ke's avatar
Guolin Ke committed
785
786
787
788
789
790
791
792
  }

  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_;
793
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
794
795
  device_type_ = dataset->device_type_;
  gpu_device_id_ = dataset->gpu_device_id_;
Guolin Ke's avatar
Guolin Ke committed
796
797
}

Guolin Ke's avatar
Guolin Ke committed
798
799
800
void Dataset::ReSize(data_size_t num_data) {
  if (num_data_ != num_data) {
    num_data_ = num_data;
801
    OMP_INIT_EX();
Guolin Ke's avatar
Guolin Ke committed
802
#pragma omp parallel for schedule(static)
Guolin Ke's avatar
Guolin Ke committed
803
    for (int group = 0; group < num_groups_; ++group) {
804
      OMP_LOOP_EX_BEGIN();
Guolin Ke's avatar
Guolin Ke committed
805
      feature_groups_[group]->ReSize(num_data_);
806
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
807
    }
808
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
809
810
811
  }
}

812
void Dataset::CopySubrow(const Dataset* fullset,
Guolin Ke's avatar
Guolin Ke committed
813
814
                         const data_size_t* used_indices,
                         data_size_t num_used_indices, bool need_meta_data) {
Nikita Titov's avatar
Nikita Titov committed
815
  CHECK_EQ(num_used_indices, num_data_);
816
817
818
819

  std::vector<int> group_ids, subfeature_ids;
  group_ids.reserve(num_features_);
  subfeature_ids.reserve(num_features_);
Guolin Ke's avatar
Guolin Ke committed
820
  for (int group = 0; group < num_groups_; ++group) {
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
    if (fullset->IsMultiGroup(group)) {
      for (int sub_feature = 0; sub_feature <
          fullset->feature_groups_[group]->num_feature_; ++sub_feature) {
        group_ids.emplace_back(group);
        subfeature_ids.emplace_back(sub_feature);
      }
    } else {
      group_ids.emplace_back(group);
      subfeature_ids.emplace_back(-1);
    }
  }
  int num_copy_tasks = static_cast<int>(group_ids.size());

  OMP_INIT_EX();
  #pragma omp parallel for schedule(dynamic)
  for (int task_id = 0; task_id < num_copy_tasks; ++task_id) {
837
    OMP_LOOP_EX_BEGIN();
838
839
840
841
    int group = group_ids[task_id];
    int subfeature = subfeature_ids[task_id];
    feature_groups_[group]->CopySubrowByCol(fullset->feature_groups_[group].get(),
                                            used_indices, num_used_indices, subfeature);
842
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
843
  }
844
  OMP_THROW_EX();
845

Guolin Ke's avatar
Guolin Ke committed
846
  if (need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
847
    metadata_.Init(fullset->metadata_, used_indices, num_used_indices);
Guolin Ke's avatar
Guolin Ke committed
848
  }
Guolin Ke's avatar
Guolin Ke committed
849
  is_finish_load_ = true;
850
851
852
853
854
855
856
857
858
859
860
  numeric_feature_map_ = fullset->numeric_feature_map_;
  num_numeric_features_ = fullset->num_numeric_features_;
  if (has_raw_) {
    ResizeRaw(num_used_indices);
#pragma omp parallel for schedule(static)
    for (int i = 0; i < num_used_indices; ++i) {
      for (int j = 0; j < num_numeric_features_; ++j) {
        raw_data_[j][i] = fullset->raw_data_[j][used_indices[i]];
      }
    }
  }
861
862
863
864
865
866
867
868
869
870
871
872
873
  // update CUDA storage for column data and metadata
  device_type_ = fullset->device_type_;
  gpu_device_id_ = fullset->gpu_device_id_;

  #ifdef USE_CUDA_EXP
  if (device_type_ == std::string("cuda_exp")) {
    if (cuda_column_data_ == nullptr) {
      cuda_column_data_.reset(new CUDAColumnData(fullset->num_data(), gpu_device_id_));
      metadata_.CreateCUDAMetadata(gpu_device_id_);
    }
    cuda_column_data_->CopySubrow(fullset->cuda_column_data(), used_indices, num_used_indices);
  }
  #endif  // USE_CUDA_EXP
Guolin Ke's avatar
Guolin Ke committed
874
875
}

Guolin Ke's avatar
Guolin Ke committed
876
877
bool Dataset::SetFloatField(const char* field_name, const float* field_data,
                            data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
878
879
880
  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
881
#ifdef LABEL_T_USE_DOUBLE
882
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
883
#else
884
    metadata_.SetLabel(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
885
#endif
Guolin Ke's avatar
Guolin Ke committed
886
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
887
#ifdef LABEL_T_USE_DOUBLE
888
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
889
#else
890
    metadata_.SetWeights(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
891
#endif
Guolin Ke's avatar
Guolin Ke committed
892
893
894
895
896
897
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
898
899
bool Dataset::SetDoubleField(const char* field_name, const double* field_data,
                             data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
900
901
902
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
903
    metadata_.SetInitScore(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
904
  } else {
905
    return false;
Guolin Ke's avatar
Guolin Ke committed
906
  }
907
  return true;
Guolin Ke's avatar
Guolin Ke committed
908
909
}

Guolin Ke's avatar
Guolin Ke committed
910
911
bool Dataset::SetIntField(const char* field_name, const int* field_data,
                          data_size_t num_element) {
912
913
914
  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
915
    metadata_.SetQuery(field_data, num_element);
916
917
918
919
920
921
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
922
923
bool Dataset::GetFloatField(const char* field_name, data_size_t* out_len,
                            const float** out_ptr) {
924
925
926
  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
927
#ifdef LABEL_T_USE_DOUBLE
928
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
929
#else
930
931
    *out_ptr = metadata_.label();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
932
#endif
933
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
934
#ifdef LABEL_T_USE_DOUBLE
935
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
936
#else
937
938
    *out_ptr = metadata_.weights();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
939
#endif
Guolin Ke's avatar
Guolin Ke committed
940
941
942
943
944
945
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
946
947
bool Dataset::GetDoubleField(const char* field_name, data_size_t* out_len,
                             const double** out_ptr) {
Guolin Ke's avatar
Guolin Ke committed
948
949
950
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
951
    *out_ptr = metadata_.init_score();
Guolin Ke's avatar
Guolin Ke committed
952
    *out_len = static_cast<data_size_t>(metadata_.num_init_score());
953
  } else {
954
955
    return false;
  }
956
  return true;
957
958
}

Guolin Ke's avatar
Guolin Ke committed
959
960
bool Dataset::GetIntField(const char* field_name, data_size_t* out_len,
                          const int** out_ptr) {
961
962
963
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
964
    *out_ptr = metadata_.query_boundaries();
Guolin Ke's avatar
Guolin Ke committed
965
    *out_len = metadata_.num_queries() + 1;
Guolin Ke's avatar
Guolin Ke committed
966
967
968
  } else {
    return false;
  }
969
  return true;
970
971
}

Guolin Ke's avatar
Guolin Ke committed
972
void Dataset::SaveBinaryFile(const char* bin_filename) {
Guolin Ke's avatar
Guolin Ke committed
973
  if (bin_filename != nullptr && std::string(bin_filename) == data_filename_) {
974
    Log::Warning("Binary file %s already exists", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
975
976
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
977
  // if not pass a filename, just append ".bin" of original file
Guolin Ke's avatar
Guolin Ke committed
978
  std::string bin_filename_str(data_filename_);
Guolin Ke's avatar
Guolin Ke committed
979
980
981
982
  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
983
  bool is_file_existed = false;
984
985

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
986
    is_file_existed = true;
987
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
988
  }
Guolin Ke's avatar
Guolin Ke committed
989

Guolin Ke's avatar
Guolin Ke committed
990
  if (!is_file_existed) {
991
992
    auto writer = VirtualFileWriter::Make(bin_filename);
    if (!writer->Init()) {
Guolin Ke's avatar
Guolin Ke committed
993
      Log::Fatal("Cannot write binary data to %s ", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
994
    }
995
    Log::Info("Saving data to binary file %s", bin_filename);
996
    size_t size_of_token = std::strlen(binary_file_token);
997
    writer->AlignedWrite(binary_file_token, size_of_token);
Guolin Ke's avatar
Guolin Ke committed
998
    // get size of header
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
    size_t size_of_header =
        VirtualFileWriter::AlignedSize(sizeof(num_data_)) +
        VirtualFileWriter::AlignedSize(sizeof(num_features_)) +
        VirtualFileWriter::AlignedSize(sizeof(num_total_features_)) +
        VirtualFileWriter::AlignedSize(sizeof(int) * num_total_features_) +
        VirtualFileWriter::AlignedSize(sizeof(label_idx_)) +
        VirtualFileWriter::AlignedSize(sizeof(num_groups_)) +
        3 * VirtualFileWriter::AlignedSize(sizeof(int) * num_features_) +
        sizeof(uint64_t) * (num_groups_ + 1) +
        2 * VirtualFileWriter::AlignedSize(sizeof(int) * num_groups_) +
        VirtualFileWriter::AlignedSize(sizeof(int32_t) * num_total_features_) +
        VirtualFileWriter::AlignedSize(sizeof(int)) * 3 +
1011
        VirtualFileWriter::AlignedSize(sizeof(bool)) * 3;
1012
1013
    // size of feature names
    for (int i = 0; i < num_total_features_; ++i) {
1014
1015
1016
      size_of_header +=
          VirtualFileWriter::AlignedSize(feature_names_[i].size()) +
          VirtualFileWriter::AlignedSize(sizeof(int));
1017
    }
1018
1019
    // size of forced bins
    for (int i = 0; i < num_total_features_; ++i) {
1020
1021
      size_of_header += forced_bin_bounds_[i].size() * sizeof(double) +
                        VirtualFileWriter::AlignedSize(sizeof(int));
1022
    }
1023
    writer->Write(&size_of_header, sizeof(size_of_header));
Guolin Ke's avatar
Guolin Ke committed
1024
    // write header
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
    writer->AlignedWrite(&num_data_, sizeof(num_data_));
    writer->AlignedWrite(&num_features_, sizeof(num_features_));
    writer->AlignedWrite(&num_total_features_, sizeof(num_total_features_));
    writer->AlignedWrite(&label_idx_, sizeof(label_idx_));
    writer->AlignedWrite(&max_bin_, sizeof(max_bin_));
    writer->AlignedWrite(&bin_construct_sample_cnt_,
                         sizeof(bin_construct_sample_cnt_));
    writer->AlignedWrite(&min_data_in_bin_, sizeof(min_data_in_bin_));
    writer->AlignedWrite(&use_missing_, sizeof(use_missing_));
    writer->AlignedWrite(&zero_as_missing_, sizeof(zero_as_missing_));
1035
    writer->AlignedWrite(&has_raw_, sizeof(has_raw_));
1036
1037
1038
1039
1040
1041
1042
    writer->AlignedWrite(used_feature_map_.data(),
                         sizeof(int) * num_total_features_);
    writer->AlignedWrite(&num_groups_, sizeof(num_groups_));
    writer->AlignedWrite(real_feature_idx_.data(), sizeof(int) * num_features_);
    writer->AlignedWrite(feature2group_.data(), sizeof(int) * num_features_);
    writer->AlignedWrite(feature2subfeature_.data(),
                         sizeof(int) * num_features_);
Guolin Ke's avatar
Guolin Ke committed
1043
1044
    writer->Write(group_bin_boundaries_.data(),
                  sizeof(uint64_t) * (num_groups_ + 1));
1045
1046
1047
    writer->AlignedWrite(group_feature_start_.data(),
                         sizeof(int) * num_groups_);
    writer->AlignedWrite(group_feature_cnt_.data(), sizeof(int) * num_groups_);
Belinda Trotta's avatar
Belinda Trotta committed
1048
1049
1050
    if (max_bin_by_feature_.empty()) {
      ArrayArgs<int32_t>::Assign(&max_bin_by_feature_, -1, num_total_features_);
    }
1051
    writer->AlignedWrite(max_bin_by_feature_.data(),
Guolin Ke's avatar
Guolin Ke committed
1052
                  sizeof(int32_t) * num_total_features_);
Belinda Trotta's avatar
Belinda Trotta committed
1053
1054
1055
    if (ArrayArgs<int32_t>::CheckAll(max_bin_by_feature_, -1)) {
      max_bin_by_feature_.clear();
    }
1056
1057
1058
    // write feature names
    for (int i = 0; i < num_total_features_; ++i) {
      int str_len = static_cast<int>(feature_names_[i].size());
1059
      writer->AlignedWrite(&str_len, sizeof(int));
1060
      const char* c_str = feature_names_[i].c_str();
1061
      writer->AlignedWrite(c_str, sizeof(char) * str_len);
1062
    }
1063
1064
1065
    // write forced bins
    for (int i = 0; i < num_total_features_; ++i) {
      int num_bounds = static_cast<int>(forced_bin_bounds_[i].size());
1066
      writer->AlignedWrite(&num_bounds, sizeof(int));
1067

1068
1069
1070
1071
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
1072

Guolin Ke's avatar
Guolin Ke committed
1073
1074
    // get size of meta data
    size_t size_of_metadata = metadata_.SizesInByte();
1075
    writer->Write(&size_of_metadata, sizeof(size_of_metadata));
Guolin Ke's avatar
Guolin Ke committed
1076
    // write meta data
1077
    metadata_.SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
1078
1079

    // write feature data
Guolin Ke's avatar
Guolin Ke committed
1080
    for (int i = 0; i < num_groups_; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1081
      // get size of feature
Guolin Ke's avatar
Guolin Ke committed
1082
      size_t size_of_feature = feature_groups_[i]->SizesInByte();
1083
      writer->Write(&size_of_feature, sizeof(size_of_feature));
Guolin Ke's avatar
Guolin Ke committed
1084
      // write feature
1085
      feature_groups_[i]->SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
1086
    }
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098

    // write raw data; use row-major order so we can read row-by-row
    if (has_raw_) {
      for (int i = 0; i < num_data_; ++i) {
        for (int j = 0; j < num_features_; ++j) {
          int feat_ind = numeric_feature_map_[j];
          if (feat_ind > -1) {
            writer->Write(&raw_data_[feat_ind][i], sizeof(float));
          }
        }
      }
    }
Guolin Ke's avatar
Guolin Ke committed
1099
1100
1101
  }
}

1102
void Dataset::DumpTextFile(const char* text_filename) {
Guolin Ke's avatar
Guolin Ke committed
1103
1104
1105
1106
1107
1108
  FILE* file = NULL;
#if _MSC_VER
  fopen_s(&file, text_filename, "wt");
#else
  file = fopen(text_filename, "wt");
#endif
1109
1110
1111
1112
1113
  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: ");
1114
  for (auto n : feature_names_) {
1115
1116
    fprintf(file, "%s, ", n.c_str());
  }
Belinda Trotta's avatar
Belinda Trotta committed
1117
1118
1119
1120
  fprintf(file, "\nmax_bin_by_feature: ");
  for (auto i : max_bin_by_feature_) {
    fprintf(file, "%d, ", i);
  }
1121
  fprintf(file, "\n");
1122
  for (auto n : feature_names_) {
1123
1124
    fprintf(file, "%s, ", n.c_str());
  }
1125
1126
1127
1128
1129
1130
1131
  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]);
    }
  }
1132
1133
  std::vector<std::unique_ptr<BinIterator>> iterators;
  iterators.reserve(num_features_);
1134
  for (int j = 0; j < num_features_; ++j) {
1135
1136
    auto group_idx = feature2group_[j];
    auto sub_idx = feature2subfeature_[j];
Guolin Ke's avatar
Guolin Ke committed
1137
1138
    iterators.emplace_back(
        feature_groups_[group_idx]->SubFeatureIterator(sub_idx));
1139
  }
1140
  for (data_size_t i = 0; i < num_data_; ++i) {
1141
    fprintf(file, "\n");
1142
    for (int j = 0; j < num_total_features_; ++j) {
1143
      auto inner_feature_idx = used_feature_map_[j];
1144
1145
      if (inner_feature_idx < 0) {
        fprintf(file, "NA, ");
1146
      } else {
Guolin Ke's avatar
Guolin Ke committed
1147
        fprintf(file, "%d, ", iterators[inner_feature_idx]->Get(i));
1148
1149
1150
1151
1152
1153
      }
    }
  }
  fclose(file);
}

1154
void Dataset::InitTrain(const std::vector<int8_t>& is_feature_used,
1155
                        TrainingShareStates* share_state) const {
1156
  Common::FunctionTimer fun_time("Dataset::InitTrain", global_timer);
1157
1158
1159
  share_state->InitTrain(group_feature_start_,
        feature_groups_,
        is_feature_used);
1160
1161
}

Guolin Ke's avatar
Guolin Ke committed
1162
template <bool USE_INDICES, bool ORDERED>
1163
1164
1165
1166
1167
1168
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 {
1169
1170
  Common::FunctionTimer fun_time("Dataset::ConstructHistogramsMultiVal",
                                 global_timer);
1171
1172
  share_state->ConstructHistograms<USE_INDICES, ORDERED>(
      data_indices, num_data, gradients, hessians, hist_data);
1173
1174
}

Guolin Ke's avatar
Guolin Ke committed
1175
1176
template <bool USE_INDICES, bool USE_HESSIAN>
void Dataset::ConstructHistogramsInner(
1177
1178
1179
    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,
1180
    TrainingShareStates* share_state, hist_t* hist_data) const {
1181
  if (!share_state->is_col_wise) {
Guolin Ke's avatar
Guolin Ke committed
1182
1183
    return ConstructHistogramsMultiVal<USE_INDICES, false>(
        data_indices, num_data, gradients, hessians, share_state, hist_data);
1184
1185
1186
1187
  }
  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
1188
  for (int group = 0; group < num_groups_; ++group) {
Guolin Ke's avatar
Guolin Ke committed
1189
    const int f_start = group_feature_start_[group];
Guolin Ke's avatar
Guolin Ke committed
1190
    const int f_cnt = group_feature_cnt_[group];
1191
    bool is_group_used = false;
Guolin Ke's avatar
Guolin Ke committed
1192
    for (int j = 0; j < f_cnt; ++j) {
Guolin Ke's avatar
Guolin Ke committed
1193
      const int fidx = f_start + j;
Guolin Ke's avatar
Guolin Ke committed
1194
      if (is_feature_used[fidx]) {
1195
        is_group_used = true;
Guolin Ke's avatar
Guolin Ke committed
1196
1197
1198
        break;
      }
    }
1199
    if (is_group_used) {
1200
1201
1202
1203
      if (feature_groups_[group]->is_multi_val_) {
        multi_val_groud_id = group;
      } else {
        used_dense_group.push_back(group);
1204
      }
Guolin Ke's avatar
Guolin Ke committed
1205
    }
1206
1207
1208
  }
  int num_used_dense_group = static_cast<int>(used_dense_group.size());
  global_timer.Start("Dataset::dense_bin_histogram");
Guolin Ke's avatar
Guolin Ke committed
1209
1210
  auto ptr_ordered_grad = gradients;
  auto ptr_ordered_hess = hessians;
1211
  if (num_used_dense_group > 0) {
Guolin Ke's avatar
Guolin Ke committed
1212
1213
    if (USE_INDICES) {
      if (USE_HESSIAN) {
Guolin Ke's avatar
Guolin Ke committed
1214
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1215
1216
1217
1218
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
          ordered_hessians[i] = hessians[data_indices[i]];
        }
Guolin Ke's avatar
Guolin Ke committed
1219
1220
        ptr_ordered_grad = ordered_gradients;
        ptr_ordered_hess = ordered_hessians;
1221
      } else {
Guolin Ke's avatar
Guolin Ke committed
1222
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1223
1224
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
1225
        }
Guolin Ke's avatar
Guolin Ke committed
1226
        ptr_ordered_grad = ordered_gradients;
1227
      }
Guolin Ke's avatar
Guolin Ke committed
1228
1229
    }
    OMP_INIT_EX();
1230
#pragma omp parallel for schedule(static) num_threads(share_state->num_threads)
Guolin Ke's avatar
Guolin Ke committed
1231
1232
1233
1234
1235
1236
1237
1238
1239
    for (int gi = 0; gi < num_used_dense_group; ++gi) {
      OMP_LOOP_EX_BEGIN();
      int group = used_dense_group[gi];
      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,
                  num_bin * kHistEntrySize);
      if (USE_HESSIAN) {
        if (USE_INDICES) {
1240
          feature_groups_[group]->bin_data_->ConstructHistogram(
1241
1242
              data_indices, 0, num_data, ptr_ordered_grad, ptr_ordered_hess,
              data_ptr);
Guolin Ke's avatar
Guolin Ke committed
1243
        } else {
1244
          feature_groups_[group]->bin_data_->ConstructHistogram(
1245
              0, num_data, ptr_ordered_grad, ptr_ordered_hess, data_ptr);
1246
        }
1247
      } else {
Guolin Ke's avatar
Guolin Ke committed
1248
1249
1250
1251
        if (USE_INDICES) {
          feature_groups_[group]->bin_data_->ConstructHistogram(
              data_indices, 0, num_data, ptr_ordered_grad, data_ptr);
        } else {
1252
1253
          feature_groups_[group]->bin_data_->ConstructHistogram(
              0, num_data, ptr_ordered_grad, data_ptr);
1254
        }
Guolin Ke's avatar
Guolin Ke committed
1255
1256
1257
1258
        auto cnt_dst = reinterpret_cast<hist_cnt_t*>(data_ptr + 1);
        for (int i = 0; i < num_bin * 2; i += 2) {
          data_ptr[i + 1] = static_cast<double>(cnt_dst[i]) * hessians[0];
        }
1259
      }
Guolin Ke's avatar
Guolin Ke committed
1260
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
1261
    }
Guolin Ke's avatar
Guolin Ke committed
1262
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
1263
  }
1264
1265
  global_timer.Stop("Dataset::dense_bin_histogram");
  if (multi_val_groud_id >= 0) {
Guolin Ke's avatar
Guolin Ke committed
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
    if (num_used_dense_group > 0) {
      ConstructHistogramsMultiVal<USE_INDICES, true>(
          data_indices, num_data, ptr_ordered_grad, ptr_ordered_hess,
          share_state,
          hist_data + group_bin_boundaries_[multi_val_groud_id] * 2);
    } else {
      ConstructHistogramsMultiVal<USE_INDICES, false>(
          data_indices, num_data, gradients, hessians, share_state,
          hist_data + group_bin_boundaries_[multi_val_groud_id] * 2);
    }
1276
  }
Guolin Ke's avatar
Guolin Ke committed
1277
1278
}

James Lamb's avatar
James Lamb committed
1279
// explicitly initialize template methods, for cross module call
Guolin Ke's avatar
Guolin Ke committed
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
template void Dataset::ConstructHistogramsInner<true, true>(
    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,
    TrainingShareStates* share_state, hist_t* hist_data) const;

template void Dataset::ConstructHistogramsInner<true, false>(
    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,
    TrainingShareStates* share_state, hist_t* hist_data) const;

template void Dataset::ConstructHistogramsInner<false, true>(
    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,
    TrainingShareStates* share_state, hist_t* hist_data) const;

template void Dataset::ConstructHistogramsInner<false, false>(
    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,
    TrainingShareStates* share_state, hist_t* hist_data) const;

Guolin Ke's avatar
Guolin Ke committed
1304
1305
void Dataset::FixHistogram(int feature_idx, double sum_gradient,
                           double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1306
1307
  const int group = feature2group_[feature_idx];
  const int sub_feature = feature2subfeature_[feature_idx];
Guolin Ke's avatar
Guolin Ke committed
1308
1309
  const BinMapper* bin_mapper =
      feature_groups_[group]->bin_mappers_[sub_feature].get();
Guolin Ke's avatar
Guolin Ke committed
1310
1311
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1312
    const int num_bin = bin_mapper->num_bin();
1313
1314
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1315
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1316
      if (i != most_freq_bin) {
1317
1318
        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
1319
1320
1321
1322
1323
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
1324
template <typename T>
Guolin Ke's avatar
Guolin Ke committed
1325
1326
void PushVector(std::vector<T>* dest, const std::vector<T>& src) {
  dest->reserve(dest->size() + src.size());
1327
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1328
    dest->push_back(i);
1329
1330
1331
  }
}

Guolin Ke's avatar
Guolin Ke committed
1332
1333
1334
template <typename T>
void PushOffset(std::vector<T>* dest, const std::vector<T>& src,
                const T& offset) {
Guolin Ke's avatar
Guolin Ke committed
1335
  dest->reserve(dest->size() + src.size());
1336
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1337
    dest->push_back(i + offset);
1338
1339
1340
  }
}

Guolin Ke's avatar
Guolin Ke committed
1341
1342
1343
1344
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
1345
  if (!dest->empty() && !src.empty()) {
1346
    PushVector(dest, src);
Guolin Ke's avatar
Guolin Ke committed
1347
  } else if (!dest->empty() && src.empty()) {
1348
    for (size_t i = 0; i < src_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1349
      dest->push_back(deflt);
1350
    }
Guolin Ke's avatar
Guolin Ke committed
1351
  } else if (dest->empty() && !src.empty()) {
1352
    for (size_t i = 0; i < dest_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1353
      dest->push_back(deflt);
1354
1355
1356
1357
1358
    }
    PushVector(dest, src);
  }
}

1359
void Dataset::AddFeaturesFrom(Dataset* other) {
1360
  if (other->num_data_ != num_data_) {
1361
    Log::Fatal(
Guolin Ke's avatar
Guolin Ke committed
1362
1363
        "Cannot add features from other Dataset with a different number of "
        "rows");
1364
  }
1365
1366
1367
  if (other->has_raw_ != has_raw_) {
    Log::Fatal("Can only add features from other Dataset if both or neither have raw data.");
  }
Guolin Ke's avatar
Guolin Ke committed
1368
1369
1370
1371
1372
  int mv_gid = -1;
  int other_mv_gid = -1;
  for (int i = 0; i < num_groups_; ++i) {
    if (IsMultiGroup(i)) {
      mv_gid = i;
1373
1374
    }
  }
Guolin Ke's avatar
Guolin Ke committed
1375
1376
1377
1378
  for (int i = 0; i < other->num_groups_; ++i) {
    if (other->IsMultiGroup(i)) {
      other_mv_gid = i;
    }
1379
  }
Guolin Ke's avatar
Guolin Ke committed
1380
1381
1382
1383
1384
1385
  // Only one multi-val group, just simply merge
  if (mv_gid < 0 || other_mv_gid < 0) {
    PushVector(&feature2subfeature_, other->feature2subfeature_);
    PushVector(&group_feature_cnt_, other->group_feature_cnt_);
    feature_groups_.reserve(other->feature_groups_.size());
    for (auto& fg : other->feature_groups_) {
1386
1387
      const int cur_group_id = static_cast<int>(feature_groups_.size());
      feature_groups_.emplace_back(new FeatureGroup(*fg, true, cur_group_id));
Guolin Ke's avatar
Guolin Ke committed
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
    }
    for (auto feature_idx : other->used_feature_map_) {
      if (feature_idx >= 0) {
        used_feature_map_.push_back(feature_idx + num_features_);
      } else {
        used_feature_map_.push_back(-1);  // Unused feature.
      }
    }
    PushOffset(&real_feature_idx_, other->real_feature_idx_,
               num_total_features_);
    PushOffset(&feature2group_, other->feature2group_, num_groups_);
    auto bin_offset = group_bin_boundaries_.back();
    // Skip the leading 0 when copying group_bin_boundaries.
    for (auto i = other->group_bin_boundaries_.begin() + 1;
         i < other->group_bin_boundaries_.end(); ++i) {
      group_bin_boundaries_.push_back(*i + bin_offset);
    }
    PushOffset(&group_feature_start_, other->group_feature_start_,
               num_features_);
    num_groups_ += other->num_groups_;
    num_features_ += other->num_features_;
  } else {
    std::vector<std::vector<int>> features_in_group;
    for (int i = 0; i < num_groups_; ++i) {
      int f_start = group_feature_start_[i];
      int f_cnt = group_feature_cnt_[i];
      features_in_group.emplace_back();
      for (int j = 0; j < f_cnt; ++j) {
1416
1417
        const int real_fidx = real_feature_idx_[f_start + j];
        features_in_group.back().push_back(real_fidx);
Guolin Ke's avatar
Guolin Ke committed
1418
1419
1420
      }
    }
    feature_groups_[mv_gid]->AddFeaturesFrom(
1421
        other->feature_groups_[other_mv_gid].get(), mv_gid);
Guolin Ke's avatar
Guolin Ke committed
1422
1423
1424
1425
1426
    for (int i = 0; i < other->num_groups_; ++i) {
      int f_start = other->group_feature_start_[i];
      int f_cnt = other->group_feature_cnt_[i];
      if (i == other_mv_gid) {
        for (int j = 0; j < f_cnt; ++j) {
1427
1428
          const int real_fidx = other->real_feature_idx_[f_start + j] + num_total_features_;
          features_in_group[mv_gid].push_back(real_fidx);
Guolin Ke's avatar
Guolin Ke committed
1429
1430
1431
1432
        }
      } else {
        features_in_group.emplace_back();
        for (int j = 0; j < f_cnt; ++j) {
1433
1434
          const int real_fidx = other->real_feature_idx_[f_start + j] + num_total_features_;
          features_in_group.back().push_back(real_fidx);
Guolin Ke's avatar
Guolin Ke committed
1435
1436
        }
        feature_groups_.emplace_back(
1437
            new FeatureGroup(*other->feature_groups_[i], false, -1));
Guolin Ke's avatar
Guolin Ke committed
1438
1439
1440
1441
1442
1443
1444
      }
    }
    // regenerate other fields
    num_groups_ += other->num_groups_ - 1;
    CHECK(num_groups_ == static_cast<int>(features_in_group.size()));
    num_features_ += other->num_features_;
    int cur_fidx = 0;
1445
1446
    used_feature_map_ =
      std::vector<int>(num_total_features_ + other->num_total_features_, -1);
Guolin Ke's avatar
Guolin Ke committed
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
    real_feature_idx_.resize(num_features_);
    feature2group_.resize(num_features_);
    feature2subfeature_.resize(num_features_);
    group_feature_start_.resize(num_groups_);
    group_feature_cnt_.resize(num_groups_);

    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) {
      auto cur_features = features_in_group[i];
      int cur_cnt_features = static_cast<int>(cur_features.size());
      group_feature_start_[i] = cur_fidx;
      group_feature_cnt_[i] = cur_cnt_features;
      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;
        ++cur_fidx;
      }
      num_total_bin += feature_groups_[i]->num_total_bin_;
      group_bin_boundaries_.push_back(num_total_bin);
    }
  }
  std::unordered_set<std::string> feature_names_set;
  for (const auto& val : feature_names_) {
    feature_names_set.emplace(val);
  }
  for (const auto& val : other->feature_names_) {
    std::string new_name = val;
    int cnt = 2;
    while (feature_names_set.count(new_name)) {
      new_name = "D" + std::to_string(cnt) + "_" + val;
      ++cnt;
    }
    if (new_name != val) {
      Log::Warning(
        "Find the same feature name (%s) in Dataset::AddFeaturesFrom, change "
        "its name to (%s)",
        val.c_str(), new_name.c_str());
    }
    feature_names_set.emplace(new_name);
    feature_names_.push_back(new_name);
  }
  PushVector(&forced_bin_bounds_, other->forced_bin_bounds_);
  PushClearIfEmpty(&max_bin_by_feature_, num_total_features_,
                   other->max_bin_by_feature_, other->num_total_features_, -1);
1496
  num_total_features_ += other->num_total_features_;
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
  for (size_t i = 0; i < (other->numeric_feature_map_).size(); ++i) {
    int feat_ind = numeric_feature_map_[i];
    if (feat_ind > -1) {
      numeric_feature_map_.push_back(feat_ind + num_numeric_features_);
    } else {
      numeric_feature_map_.push_back(-1);
    }
  }
  num_numeric_features_ += other->num_numeric_features_;
  if (has_raw_) {
    for (int i = 0; i < other->num_numeric_features_; ++i) {
      raw_data_.push_back(other->raw_data_[i]);
    }
  }
1511
1512
1513
1514
1515
1516
1517
  #ifdef USE_CUDA_EXP
  if (device_type_ == std::string("cuda_exp")) {
    CreateCUDAColumnData();
  } else {
    cuda_column_data_ = nullptr;
  }
  #endif  // USE_CUDA_EXP
1518
1519
}

1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
const void* Dataset::GetColWiseData(
  const int feature_group_index,
  const int sub_feature_index,
  uint8_t* bit_type,
  bool* is_sparse,
  std::vector<BinIterator*>* bin_iterator,
  const int num_threads) const {
  return feature_groups_[feature_group_index]->GetColWiseData(sub_feature_index, bit_type, is_sparse, bin_iterator, num_threads);
}

const void* Dataset::GetColWiseData(
  const int feature_group_index,
  const int sub_feature_index,
  uint8_t* bit_type,
  bool* is_sparse,
  BinIterator** bin_iterator) const {
  return feature_groups_[feature_group_index]->GetColWiseData(sub_feature_index, bit_type, is_sparse, bin_iterator);
}

#ifdef USE_CUDA_EXP
void Dataset::CreateCUDAColumnData() {
  cuda_column_data_.reset(new CUDAColumnData(num_data_, gpu_device_id_));
  int num_columns = 0;
  std::vector<const void*> column_data;
  std::vector<BinIterator*> column_bin_iterator;
  std::vector<uint8_t> column_bit_type;
  int feature_index = 0;
  std::vector<int> feature_to_column(num_features_, -1);
  std::vector<uint32_t> feature_max_bins(num_features_, 0);
  std::vector<uint32_t> feature_min_bins(num_features_, 0);
  std::vector<uint32_t> feature_offsets(num_features_, 0);
  std::vector<uint32_t> feature_most_freq_bins(num_features_, 0);
  std::vector<uint32_t> feature_default_bin(num_features_, 0);
  std::vector<uint8_t> feature_missing_is_zero(num_features_, 0);
  std::vector<uint8_t> feature_missing_is_na(num_features_, 0);
  std::vector<uint8_t> feature_mfb_is_zero(num_features_, 0);
  std::vector<uint8_t> feature_mfb_is_na(num_features_, 0);
  for (int feature_group_index = 0; feature_group_index < num_groups_; ++feature_group_index) {
    if (feature_groups_[feature_group_index]->is_multi_val_) {
      for (int sub_feature_index = 0; sub_feature_index < feature_groups_[feature_group_index]->num_feature_; ++sub_feature_index) {
        uint8_t bit_type = 0;
        bool is_sparse = false;
        BinIterator* bin_iterator = nullptr;
        const void* one_column_data = GetColWiseData(feature_group_index,
                                                     sub_feature_index,
                                                     &bit_type,
                                                     &is_sparse,
                                                     &bin_iterator);
        column_data.emplace_back(one_column_data);
        column_bin_iterator.emplace_back(bin_iterator);
        column_bit_type.emplace_back(bit_type);
        feature_to_column[feature_index] = num_columns;
        ++num_columns;
        const BinMapper* feature_bin_mapper = FeatureBinMapper(feature_index);
        feature_max_bins[feature_index] = feature_max_bin(feature_index);
        feature_min_bins[feature_index] = feature_min_bin(feature_index);
        const uint32_t most_freq_bin = feature_bin_mapper->GetMostFreqBin();
        feature_offsets[feature_index] = static_cast<uint32_t>(most_freq_bin == 0);
        feature_most_freq_bins[feature_index] = most_freq_bin;
        feature_default_bin[feature_index] = feature_bin_mapper->GetDefaultBin();
        if (feature_bin_mapper->missing_type() == MissingType::Zero) {
          feature_missing_is_zero[feature_index] = 1;
          feature_missing_is_na[feature_index] = 0;
          if (feature_default_bin[feature_index] == feature_most_freq_bins[feature_index]) {
            feature_mfb_is_zero[feature_index] = 1;
          } else {
            feature_mfb_is_zero[feature_index] = 0;
          }
          feature_mfb_is_na[feature_index] = 0;
        } else if (feature_bin_mapper->missing_type() == MissingType::NaN) {
          feature_missing_is_zero[feature_index] = 0;
          feature_missing_is_na[feature_index] = 1;
          feature_mfb_is_zero[feature_index] = 0;
          if (feature_most_freq_bins[feature_index] + feature_min_bins[feature_index] == feature_max_bins[feature_index] &&
              feature_most_freq_bins[feature_index] > 0) {
            feature_mfb_is_na[feature_index] = 1;
          } else {
            feature_mfb_is_na[feature_index] = 0;
          }
        } else {
          feature_missing_is_zero[feature_index] = 0;
          feature_missing_is_na[feature_index] = 0;
          feature_mfb_is_zero[feature_index] = 0;
          feature_mfb_is_na[feature_index] = 0;
        }
        ++feature_index;
      }
    } else {
      uint8_t bit_type = 0;
      bool is_sparse = false;
      BinIterator* bin_iterator = nullptr;
      const void* one_column_data = GetColWiseData(feature_group_index,
                                                   -1,
                                                   &bit_type,
                                                   &is_sparse,
                                                   &bin_iterator);
      column_data.emplace_back(one_column_data);
      column_bin_iterator.emplace_back(bin_iterator);
      column_bit_type.emplace_back(bit_type);
      for (int sub_feature_index = 0; sub_feature_index < feature_groups_[feature_group_index]->num_feature_; ++sub_feature_index) {
        feature_to_column[feature_index] = num_columns;
        const BinMapper* feature_bin_mapper = FeatureBinMapper(feature_index);
        feature_max_bins[feature_index] = feature_max_bin(feature_index);
        feature_min_bins[feature_index] = feature_min_bin(feature_index);
        const uint32_t most_freq_bin = feature_bin_mapper->GetMostFreqBin();
        feature_offsets[feature_index] = static_cast<uint32_t>(most_freq_bin == 0);
        feature_most_freq_bins[feature_index] = most_freq_bin;
        feature_default_bin[feature_index] = feature_bin_mapper->GetDefaultBin();
        if (feature_bin_mapper->missing_type() == MissingType::Zero) {
          feature_missing_is_zero[feature_index] = 1;
          feature_missing_is_na[feature_index] = 0;
          if (feature_default_bin[feature_index] == feature_most_freq_bins[feature_index]) {
            feature_mfb_is_zero[feature_index] = 1;
          } else {
            feature_mfb_is_zero[feature_index] = 0;
          }
          feature_mfb_is_na[feature_index] = 0;
        } else if (feature_bin_mapper->missing_type() == MissingType::NaN) {
          feature_missing_is_zero[feature_index] = 0;
          feature_missing_is_na[feature_index] = 1;
          feature_mfb_is_zero[feature_index] = 0;
          if (feature_most_freq_bins[feature_index] + feature_min_bins[feature_index] == feature_max_bins[feature_index] &&
              feature_most_freq_bins[feature_index] > 0) {
            feature_mfb_is_na[feature_index] = 1;
          } else {
            feature_mfb_is_na[feature_index] = 0;
          }
        } else {
          feature_missing_is_zero[feature_index] = 0;
          feature_missing_is_na[feature_index] = 0;
          feature_mfb_is_zero[feature_index] = 0;
          feature_mfb_is_na[feature_index] = 0;
        }
        ++feature_index;
      }
      ++num_columns;
    }
  }
  cuda_column_data_->Init(num_columns,
                          column_data,
                          column_bin_iterator,
                          column_bit_type,
                          feature_max_bins,
                          feature_min_bins,
                          feature_offsets,
                          feature_most_freq_bins,
                          feature_default_bin,
                          feature_missing_is_zero,
                          feature_missing_is_na,
                          feature_mfb_is_zero,
                          feature_mfb_is_na,
                          feature_to_column);
}

#endif  // USE_CUDA_EXP

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