dataset.cpp 64.5 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_;
Guolin Ke's avatar
Guolin Ke committed
743
744
745
746
747
748
}

void Dataset::CreateValid(const Dataset* dataset) {
  feature_groups_.clear();
  num_features_ = dataset->num_features_;
  num_groups_ = num_features_;
749
750
751
752
753
  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
754
755
  feature2group_.clear();
  feature2subfeature_.clear();
756
757
758
759
  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
760
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
761
762
763
764
765
  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
766
767
768
  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
769
770
    if (bin_mappers.back()->GetDefaultBin() !=
        bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
771
772
      feature_need_push_zeros_.push_back(i);
    }
773
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
774
775
    feature2group_.push_back(i);
    feature2subfeature_.push_back(0);
Guolin Ke's avatar
Guolin Ke committed
776
777
778
779
    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
780
781
782
783
784
785
786
787
  }

  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_;
788
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
789
790
  device_type_ = dataset->device_type_;
  gpu_device_id_ = dataset->gpu_device_id_;
Guolin Ke's avatar
Guolin Ke committed
791
792
}

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

807
void Dataset::CopySubrow(const Dataset* fullset,
Guolin Ke's avatar
Guolin Ke committed
808
809
                         const data_size_t* used_indices,
                         data_size_t num_used_indices, bool need_meta_data) {
Nikita Titov's avatar
Nikita Titov committed
810
  CHECK_EQ(num_used_indices, num_data_);
811
812
813
814

  std::vector<int> group_ids, subfeature_ids;
  group_ids.reserve(num_features_);
  subfeature_ids.reserve(num_features_);
Guolin Ke's avatar
Guolin Ke committed
815
  for (int group = 0; group < num_groups_; ++group) {
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
    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) {
832
    OMP_LOOP_EX_BEGIN();
833
834
835
836
    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);
837
    OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
838
  }
839
  OMP_THROW_EX();
840

Guolin Ke's avatar
Guolin Ke committed
841
  if (need_meta_data) {
Guolin Ke's avatar
Guolin Ke committed
842
    metadata_.Init(fullset->metadata_, used_indices, num_used_indices);
Guolin Ke's avatar
Guolin Ke committed
843
  }
Guolin Ke's avatar
Guolin Ke committed
844
  is_finish_load_ = true;
845
846
847
848
849
850
851
852
853
854
855
  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]];
      }
    }
  }
856
857
858
859
860
861
862
863
864
865
866
867
868
  // 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
869
870
}

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

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

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

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

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

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

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

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
981
    is_file_existed = true;
982
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
983
  }
Guolin Ke's avatar
Guolin Ke committed
984

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

1063
1064
1065
1066
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
1067

Guolin Ke's avatar
Guolin Ke committed
1068
1069
    // get size of meta data
    size_t size_of_metadata = metadata_.SizesInByte();
1070
    writer->Write(&size_of_metadata, sizeof(size_of_metadata));
Guolin Ke's avatar
Guolin Ke committed
1071
    // write meta data
1072
    metadata_.SaveBinaryToFile(writer.get());
Guolin Ke's avatar
Guolin Ke committed
1073
1074

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

    // 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
1094
1095
1096
  }
}

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

1149
void Dataset::InitTrain(const std::vector<int8_t>& is_feature_used,
1150
                        TrainingShareStates* share_state) const {
1151
  Common::FunctionTimer fun_time("Dataset::InitTrain", global_timer);
1152
1153
1154
  share_state->InitTrain(group_feature_start_,
        feature_groups_,
        is_feature_used);
1155
1156
}

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

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

James Lamb's avatar
James Lamb committed
1274
// explicitly initialize template methods, for cross module call
Guolin Ke's avatar
Guolin Ke committed
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
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
1299
1300
void Dataset::FixHistogram(int feature_idx, double sum_gradient,
                           double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1301
1302
  const int group = feature2group_[feature_idx];
  const int sub_feature = feature2subfeature_[feature_idx];
Guolin Ke's avatar
Guolin Ke committed
1303
1304
  const BinMapper* bin_mapper =
      feature_groups_[group]->bin_mappers_[sub_feature].get();
Guolin Ke's avatar
Guolin Ke committed
1305
1306
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1307
    const int num_bin = bin_mapper->num_bin();
1308
1309
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1310
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1311
      if (i != most_freq_bin) {
1312
1313
        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
1314
1315
1316
1317
1318
      }
    }
  }
}

Guolin Ke's avatar
Guolin Ke committed
1319
template <typename T>
Guolin Ke's avatar
Guolin Ke committed
1320
1321
void PushVector(std::vector<T>* dest, const std::vector<T>& src) {
  dest->reserve(dest->size() + src.size());
1322
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1323
    dest->push_back(i);
1324
1325
1326
  }
}

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

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

1354
void Dataset::AddFeaturesFrom(Dataset* other) {
1355
  if (other->num_data_ != num_data_) {
1356
    Log::Fatal(
Guolin Ke's avatar
Guolin Ke committed
1357
1358
        "Cannot add features from other Dataset with a different number of "
        "rows");
1359
  }
1360
1361
1362
  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
1363
1364
1365
1366
1367
  int mv_gid = -1;
  int other_mv_gid = -1;
  for (int i = 0; i < num_groups_; ++i) {
    if (IsMultiGroup(i)) {
      mv_gid = i;
1368
1369
    }
  }
Guolin Ke's avatar
Guolin Ke committed
1370
1371
1372
1373
  for (int i = 0; i < other->num_groups_; ++i) {
    if (other->IsMultiGroup(i)) {
      other_mv_gid = i;
    }
1374
  }
Guolin Ke's avatar
Guolin Ke committed
1375
1376
1377
1378
1379
1380
  // 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_) {
1381
1382
      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
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
    }
    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) {
1411
1412
        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
1413
1414
1415
      }
    }
    feature_groups_[mv_gid]->AddFeaturesFrom(
1416
        other->feature_groups_[other_mv_gid].get(), mv_gid);
Guolin Ke's avatar
Guolin Ke committed
1417
1418
1419
1420
1421
    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) {
1422
1423
          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
1424
1425
1426
1427
        }
      } else {
        features_in_group.emplace_back();
        for (int j = 0; j < f_cnt; ++j) {
1428
1429
          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
1430
1431
        }
        feature_groups_.emplace_back(
1432
            new FeatureGroup(*other->feature_groups_[i], false, -1));
Guolin Ke's avatar
Guolin Ke committed
1433
1434
1435
1436
1437
1438
1439
      }
    }
    // 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;
1440
1441
    used_feature_map_ =
      std::vector<int>(num_total_features_ + other->num_total_features_, -1);
Guolin Ke's avatar
Guolin Ke committed
1442
1443
1444
1445
1446
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
    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);
1491
  num_total_features_ += other->num_total_features_;
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
  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]);
    }
  }
1506
1507
1508
1509
1510
1511
1512
  #ifdef USE_CUDA_EXP
  if (device_type_ == std::string("cuda_exp")) {
    CreateCUDAColumnData();
  } else {
    cuda_column_data_ = nullptr;
  }
  #endif  // USE_CUDA_EXP
1513
1514
}

1515
1516
1517
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
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
1671
}  // namespace LightGBM