dataset.cpp 60.3 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;
Guolin Ke's avatar
Guolin Ke committed
29
30
}

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

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

Guolin Ke's avatar
Guolin Ke committed
42
std::vector<std::vector<int>> NoGroup(const std::vector<int>& used_features) {
Guolin Ke's avatar
Guolin Ke committed
43
44
45
46
47
48
49
50
  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
51
int GetConflictCount(const std::vector<bool>& mark, const int* indices,
Guolin Ke's avatar
Guolin Ke committed
52
                     int num_indices, data_size_t max_cnt) {
Guolin Ke's avatar
Guolin Ke committed
53
54
55
56
  int ret = 0;
  for (int i = 0; i < num_indices; ++i) {
    if (mark[indices[i]]) {
      ++ret;
57
58
59
    }
    if (ret > max_cnt) {
      return -1;
Guolin Ke's avatar
Guolin Ke committed
60
61
62
63
    }
  }
  return ret;
}
64

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

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

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

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

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

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

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

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

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

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

  auto is_sparse = io_config.is_enable_sparse;
  if (io_config.device_type == std::string("cuda")) {
      LGBM_config_::current_device = lgbm_device_cuda;
      if (is_sparse) {
        Log::Warning("Using sparse features with CUDA is currently not supported.");
      }
      is_sparse = false;
  }

348
  std::vector<int8_t> group_is_multi_val(used_features.size(), 0);
349
  if (io_config.enable_bundle && !used_features.empty()) {
350
    bool lgbm_is_gpu_used = io_config.device_type == std::string("gpu") || io_config.device_type == std::string("cuda");
Guolin Ke's avatar
Guolin Ke committed
351
352
353
    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),
354
355
        used_features, num_data_, lgbm_is_gpu_used,
        is_sparse, &group_is_multi_val);
Guolin Ke's avatar
Guolin Ke committed
356
357
  }

Guolin Ke's avatar
Guolin Ke committed
358
359
360
361
362
363
364
365
366
367
  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
368
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
369
370
371
372
373
  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
374
375
376
  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
377
378
    group_feature_start_[i] = cur_fidx;
    group_feature_cnt_[i] = cur_cnt_features;
Guolin Ke's avatar
Guolin Ke committed
379
380
381
382
383
384
385
386
    // 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
387
      cur_bin_mappers.emplace_back(ref_bin_mappers[real_fidx].release());
Guolin Ke's avatar
Guolin Ke committed
388
389
      if (cur_bin_mappers.back()->GetDefaultBin() !=
          cur_bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
390
391
        feature_need_push_zeros_.push_back(cur_fidx);
      }
Guolin Ke's avatar
Guolin Ke committed
392
393
      ++cur_fidx;
    }
Guolin Ke's avatar
Guolin Ke committed
394
395
    feature_groups_.emplace_back(std::unique_ptr<FeatureGroup>(
      new FeatureGroup(cur_cnt_features, group_is_multi_val[i], &cur_bin_mappers, num_data_)));
Guolin Ke's avatar
Guolin Ke committed
396
397
398
    num_total_bin += feature_groups_[i]->num_total_bin_;
    group_bin_boundaries_.push_back(num_total_bin);
  }
Belinda Trotta's avatar
Belinda Trotta committed
399
  if (!io_config.max_bin_by_feature.empty()) {
400
401
402
403
    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
404
    max_bin_by_feature_.resize(num_total_features_);
Guolin Ke's avatar
Guolin Ke committed
405
406
    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
407
  }
408
  forced_bin_bounds_ = forced_bins;
409
410
411
412
413
414
415
  max_bin_ = io_config.max_bin;
  min_data_in_bin_ = io_config.min_data_in_bin;
  bin_construct_sample_cnt_ = io_config.bin_construct_sample_cnt;
  use_missing_ = io_config.use_missing;
  zero_as_missing_ = io_config.zero_as_missing;
}

Guolin Ke's avatar
Guolin Ke committed
416
void Dataset::FinishLoad() {
Guolin Ke's avatar
Guolin Ke committed
417
418
419
  if (is_finish_load_) {
    return;
  }
420
421
  if (num_groups_ > 0) {
    for (int i = 0; i < num_groups_; ++i) {
422
      feature_groups_[i]->FinishLoad();
423
    }
Guolin Ke's avatar
Guolin Ke committed
424
  }
Guolin Ke's avatar
Guolin Ke committed
425
  is_finish_load_ = true;
Guolin Ke's avatar
Guolin Ke committed
426
}
Guolin Ke's avatar
Guolin Ke committed
427

428
void PushDataToMultiValBin(
Guolin Ke's avatar
Guolin Ke committed
429
    data_size_t num_data, const std::vector<uint32_t> most_freq_bins,
430
    const std::vector<uint32_t> offsets,
Guolin Ke's avatar
Guolin Ke committed
431
    std::vector<std::vector<std::unique_ptr<BinIterator>>>* iters,
432
433
434
    MultiValBin* ret) {
  Common::FunctionTimer fun_time("Dataset::PushDataToMultiValBin",
                                 global_timer);
435
  if (ret->IsSparse()) {
Guolin Ke's avatar
Guolin Ke committed
436
437
438
439
440
    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
441
            (*iters)[tid][j]->Reset(start);
442
          }
Guolin Ke's avatar
Guolin Ke committed
443
444
445
          for (data_size_t i = start; i < end; ++i) {
            cur_data.clear();
            for (size_t j = 0; j < most_freq_bins.size(); ++j) {
Guolin Ke's avatar
Guolin Ke committed
446
              auto cur_bin = (*iters)[tid][j]->Get(i);
Guolin Ke's avatar
Guolin Ke committed
447
448
449
450
451
452
453
454
455
456
              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);
457
          }
Guolin Ke's avatar
Guolin Ke committed
458
        });
459
  } else {
Guolin Ke's avatar
Guolin Ke committed
460
461
462
463
    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
464
            (*iters)[tid][j]->Reset(start);
Guolin Ke's avatar
Guolin Ke committed
465
466
467
          }
          for (data_size_t i = start; i < end; ++i) {
            for (size_t j = 0; j < most_freq_bins.size(); ++j) {
Guolin Ke's avatar
Guolin Ke committed
468
              auto cur_bin = (*iters)[tid][j]->Get(i);
Guolin Ke's avatar
Guolin Ke committed
469
470
471
472
473
474
475
476
477
              if (cur_bin == most_freq_bins[j]) {
                cur_bin = 0;
              } else {
                cur_bin += offsets[j];
                if (most_freq_bins[j] == 0) {
                  cur_bin -= 1;
                }
              }
              cur_data[j] = cur_bin;
478
            }
Guolin Ke's avatar
Guolin Ke committed
479
            ret->PushOneRow(tid, i, cur_data);
480
          }
Guolin Ke's avatar
Guolin Ke committed
481
        });
482
483
484
485
  }
}

MultiValBin* Dataset::GetMultiBinFromSparseFeatures() const {
486
487
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromSparseFeatures",
                                 global_timer);
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
  int multi_group_id = -1;
  for (int i = 0; i < num_groups_; ++i) {
    if (feature_groups_[i]->is_multi_val_) {
      if (multi_group_id < 0) {
        multi_group_id = i;
      } else {
        Log::Fatal("Bug. There should be only one multi-val group.");
      }
    }
  }
  if (multi_group_id < 0) {
    return nullptr;
  }
  const auto& offsets = feature_groups_[multi_group_id]->bin_offsets_;
  const int num_feature = feature_groups_[multi_group_id]->num_feature_;
503
  int num_threads = OMP_NUM_THREADS();
504
505
506
507
508

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

MultiValBin* Dataset::GetMultiBinFromAllFeatures() const {
531
532
  Common::FunctionTimer fun_time("Dataset::GetMultiBinFromAllFeatures",
                                 global_timer);
533
  int num_threads = OMP_NUM_THREADS();
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
  double sum_dense_ratio = 0;

  std::unique_ptr<MultiValBin> ret;
  std::vector<std::vector<std::unique_ptr<BinIterator>>> iters(num_threads);
  std::vector<uint32_t> most_freq_bins;
  std::vector<uint32_t> offsets;
  int num_total_bin = 1;
  offsets.push_back(num_total_bin);
  for (int gid = 0; gid < num_groups_; ++gid) {
    if (feature_groups_[gid]->is_multi_val_) {
      for (int fid = 0; fid < feature_groups_[gid]->num_feature_; ++fid) {
        const auto& bin_mapper = feature_groups_[gid]->bin_mappers_[fid];
        sum_dense_ratio += 1.0f - bin_mapper->sparse_rate();
        most_freq_bins.push_back(bin_mapper->GetMostFreqBin());
        num_total_bin += bin_mapper->num_bin();
        if (most_freq_bins.back() == 0) {
          num_total_bin -= 1;
        }
        offsets.push_back(num_total_bin);
553
#pragma omp parallel for schedule(static, 1)
554
        for (int tid = 0; tid < num_threads; ++tid) {
555
556
          iters[tid].emplace_back(
              feature_groups_[gid]->SubFeatureIterator(fid));
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
        }
      }
    } else {
      most_freq_bins.push_back(0);
      num_total_bin += feature_groups_[gid]->bin_offsets_.back() - 1;
      for (int tid = 0; tid < num_threads; ++tid) {
        iters[tid].emplace_back(feature_groups_[gid]->FeatureGroupIterator());
      }
      offsets.push_back(num_total_bin);
      for (int fid = 0; fid < feature_groups_[gid]->num_feature_; ++fid) {
        const auto& bin_mapper = feature_groups_[gid]->bin_mappers_[fid];
        sum_dense_ratio += 1.0f - bin_mapper->sparse_rate();
      }
    }
  }
  sum_dense_ratio /= static_cast<double>(most_freq_bins.size());
573
574
575
576
577
  Log::Debug("Dataset::GetMultiBinFromAllFeatures: sparse rate %f",
             1.0 - sum_dense_ratio);
  ret.reset(MultiValBin::CreateMultiValBin(
      num_data_, num_total_bin, static_cast<int>(most_freq_bins.size()),
      1.0 - sum_dense_ratio));
Guolin Ke's avatar
Guolin Ke committed
578
  PushDataToMultiValBin(num_data_, most_freq_bins, offsets, &iters, ret.get());
579
580
581
582
  ret->FinishLoad();
  return ret.release();
}

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

    std::chrono::duration<double, std::milli> col_wise_init_time,
        row_wise_init_time;
622
    auto start_time = std::chrono::steady_clock::now();
623
    colwise_state->SetMultiValBin(GetMultiBinFromSparseFeatures());
624
    col_wise_init_time = std::chrono::steady_clock::now() - start_time;
625

626
    start_time = std::chrono::steady_clock::now();
627
628
629
630
    rowwise_state->SetMultiValBin(GetMultiBinFromAllFeatures());
    std::vector<hist_t, Common::AlignmentAllocator<hist_t, kAlignedSize>>
        hist_data(NumTotalBin() * 2);

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

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

void Dataset::CreateValid(const Dataset* dataset) {
  feature_groups_.clear();
  num_features_ = dataset->num_features_;
  num_groups_ = num_features_;
  feature2group_.clear();
  feature2subfeature_.clear();
Guolin Ke's avatar
Guolin Ke committed
710

Guolin Ke's avatar
Guolin Ke committed
711
  feature_need_push_zeros_.clear();
Guolin Ke's avatar
Guolin Ke committed
712
713
714
715
716
  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
717
718
719
  for (int i = 0; i < num_features_; ++i) {
    std::vector<std::unique_ptr<BinMapper>> bin_mappers;
    bin_mappers.emplace_back(new BinMapper(*(dataset->FeatureBinMapper(i))));
Guolin Ke's avatar
Guolin Ke committed
720
721
    if (bin_mappers.back()->GetDefaultBin() !=
        bin_mappers.back()->GetMostFreqBin()) {
Guolin Ke's avatar
Guolin Ke committed
722
723
      feature_need_push_zeros_.push_back(i);
    }
724
    feature_groups_.emplace_back(new FeatureGroup(&bin_mappers, num_data_));
Guolin Ke's avatar
Guolin Ke committed
725
726
    feature2group_.push_back(i);
    feature2subfeature_.push_back(0);
Guolin Ke's avatar
Guolin Ke committed
727
728
729
730
    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
731
732
733
734
735
736
737
738
  }

  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_;
739
  forced_bin_bounds_ = dataset->forced_bin_bounds_;
Guolin Ke's avatar
Guolin Ke committed
740
741
}

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

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

Guolin Ke's avatar
Guolin Ke committed
775
776
bool Dataset::SetFloatField(const char* field_name, const float* field_data,
                            data_size_t num_element) {
Guolin Ke's avatar
Guolin Ke committed
777
778
779
  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
780
#ifdef LABEL_T_USE_DOUBLE
781
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
782
#else
783
    metadata_.SetLabel(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
784
#endif
Guolin Ke's avatar
Guolin Ke committed
785
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
786
#ifdef LABEL_T_USE_DOUBLE
787
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
788
#else
789
    metadata_.SetWeights(field_data, num_element);
Guolin Ke's avatar
Guolin Ke committed
790
#endif
Guolin Ke's avatar
Guolin Ke committed
791
792
793
794
795
796
  } else {
    return false;
  }
  return true;
}

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

Guolin Ke's avatar
Guolin Ke committed
809
810
bool Dataset::SetIntField(const char* field_name, const int* field_data,
                          data_size_t num_element) {
811
812
813
  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
814
    metadata_.SetQuery(field_data, num_element);
815
816
817
818
819
820
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
821
822
bool Dataset::GetFloatField(const char* field_name, data_size_t* out_len,
                            const float** out_ptr) {
823
824
825
  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
826
#ifdef LABEL_T_USE_DOUBLE
827
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
828
#else
829
830
    *out_ptr = metadata_.label();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
831
#endif
832
  } else if (name == std::string("weight") || name == std::string("weights")) {
Guolin Ke's avatar
Guolin Ke committed
833
#ifdef LABEL_T_USE_DOUBLE
834
    Log::Fatal("Don't support LABEL_T_USE_DOUBLE");
Guolin Ke's avatar
Guolin Ke committed
835
#else
836
837
    *out_ptr = metadata_.weights();
    *out_len = num_data_;
Guolin Ke's avatar
Guolin Ke committed
838
#endif
Guolin Ke's avatar
Guolin Ke committed
839
840
841
842
843
844
  } else {
    return false;
  }
  return true;
}

Guolin Ke's avatar
Guolin Ke committed
845
846
bool Dataset::GetDoubleField(const char* field_name, data_size_t* out_len,
                             const double** out_ptr) {
Guolin Ke's avatar
Guolin Ke committed
847
848
849
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("init_score")) {
850
    *out_ptr = metadata_.init_score();
Guolin Ke's avatar
Guolin Ke committed
851
    *out_len = static_cast<data_size_t>(metadata_.num_init_score());
852
  } else {
853
854
    return false;
  }
855
  return true;
856
857
}

Guolin Ke's avatar
Guolin Ke committed
858
859
bool Dataset::GetIntField(const char* field_name, data_size_t* out_len,
                          const int** out_ptr) {
860
861
862
  std::string name(field_name);
  name = Common::Trim(name);
  if (name == std::string("query") || name == std::string("group")) {
863
    *out_ptr = metadata_.query_boundaries();
Guolin Ke's avatar
Guolin Ke committed
864
    *out_len = metadata_.num_queries() + 1;
Guolin Ke's avatar
Guolin Ke committed
865
866
867
  } else {
    return false;
  }
868
  return true;
869
870
}

Guolin Ke's avatar
Guolin Ke committed
871
void Dataset::SaveBinaryFile(const char* bin_filename) {
Guolin Ke's avatar
Guolin Ke committed
872
  if (bin_filename != nullptr && std::string(bin_filename) == data_filename_) {
873
    Log::Warning("Bianry file %s already exists", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
874
875
    return;
  }
Guolin Ke's avatar
Guolin Ke committed
876
  // if not pass a filename, just append ".bin" of original file
Guolin Ke's avatar
Guolin Ke committed
877
  std::string bin_filename_str(data_filename_);
Guolin Ke's avatar
Guolin Ke committed
878
879
880
881
  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
882
  bool is_file_existed = false;
883
884

  if (VirtualFileWriter::Exists(bin_filename)) {
Guolin Ke's avatar
Guolin Ke committed
885
    is_file_existed = true;
886
    Log::Warning("File %s exists, cannot save binary to it", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
887
  }
Guolin Ke's avatar
Guolin Ke committed
888

Guolin Ke's avatar
Guolin Ke committed
889
  if (!is_file_existed) {
890
891
    auto writer = VirtualFileWriter::Make(bin_filename);
    if (!writer->Init()) {
Guolin Ke's avatar
Guolin Ke committed
892
      Log::Fatal("Cannot write binary data to %s ", bin_filename);
Guolin Ke's avatar
Guolin Ke committed
893
    }
894
    Log::Info("Saving data to binary file %s", bin_filename);
895
    size_t size_of_token = std::strlen(binary_file_token);
896
    writer->AlignedWrite(binary_file_token, size_of_token);
Guolin Ke's avatar
Guolin Ke committed
897
    // get size of header
898
899
900
901
902
903
904
905
906
907
908
909
910
    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 +
        VirtualFileWriter::AlignedSize(sizeof(bool)) * 2;
Guolin Ke's avatar
Guolin Ke committed
911

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

967
968
969
970
      for (size_t j = 0; j < forced_bin_bounds_[i].size(); ++j) {
        writer->Write(&forced_bin_bounds_[i][j], sizeof(double));
      }
    }
971

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

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

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

1041
void Dataset::InitTrain(const std::vector<int8_t>& is_feature_used,
1042
                        TrainingShareStates* share_state) const {
1043
  Common::FunctionTimer fun_time("Dataset::InitTrain", global_timer);
1044
1045
  share_state->is_use_subcol = false;
  if (share_state->multi_val_bin == nullptr) {
1046
1047
    return;
  }
1048
  const auto multi_val_bin = share_state->multi_val_bin.get();
1049
1050
1051
1052
1053
1054
1055
  double sum_used_dense_ratio = 0.0;
  double sum_dense_ratio = 0.0;
  int num_used = 0;
  int total = 0;
  std::vector<int> used_feature_index;
  for (int i = 0; i < num_groups_; ++i) {
    int f_start = group_feature_start_[i];
Nikita Titov's avatar
Nikita Titov committed
1056
    if (feature_groups_[i]->is_multi_val_) {
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        const auto dense_rate =
            1.0 - feature_groups_[i]->bin_mappers_[j]->sparse_rate();
        if (is_feature_used[f_start + j]) {
          ++num_used;
          used_feature_index.push_back(total);
          sum_used_dense_ratio += dense_rate;
        }
        sum_dense_ratio += dense_rate;
        ++total;
      }
1068
    } else if (!share_state->is_colwise) {
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
      bool is_group_used = false;
      double dense_rate = 0;
      for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
        if (is_feature_used[f_start + j]) {
          is_group_used = true;
        }
        dense_rate += 1.0 - feature_groups_[i]->bin_mappers_[j]->sparse_rate();
      }
      if (is_group_used) {
        ++num_used;
        used_feature_index.push_back(total);
        sum_used_dense_ratio += dense_rate;
      }
      sum_dense_ratio += dense_rate;
      ++total;
    }
  }
  const double k_subfeature_threshold = 0.6;
  if (sum_used_dense_ratio >= sum_dense_ratio * k_subfeature_threshold) {
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
    // only need to copy subset
    if (share_state->is_use_subrow && !share_state->is_subrow_copied) {
      if (share_state->multi_val_bin_subset == nullptr) {
        share_state->multi_val_bin_subset.reset(multi_val_bin->CreateLike(
            share_state->bagging_indices_cnt, multi_val_bin->num_bin(), total,
            multi_val_bin->num_element_per_row()));
      } else {
        share_state->multi_val_bin_subset->ReSize(
            share_state->bagging_indices_cnt, multi_val_bin->num_bin(), total,
            multi_val_bin->num_element_per_row());
      }
      share_state->multi_val_bin_subset->CopySubrow(
          multi_val_bin, share_state->bagging_use_indices,
          share_state->bagging_indices_cnt);
      // avoid to copy subset many times
      share_state->is_subrow_copied = true;
    }
  } else {
    share_state->is_use_subcol = true;
    std::vector<uint32_t> upper_bound;
    std::vector<uint32_t> lower_bound;
    std::vector<uint32_t> delta;
    share_state->hist_move_src.clear();
    share_state->hist_move_dest.clear();
    share_state->hist_move_size.clear();
1113

1114
1115
    int num_total_bin = 1;
    int new_num_total_bin = 1;
1116

1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
    for (int i = 0; i < num_groups_; ++i) {
      int f_start = group_feature_start_[i];
      if (feature_groups_[i]->is_multi_val_) {
        for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
          const auto& bin_mapper = feature_groups_[i]->bin_mappers_[j];
          int cur_num_bin = bin_mapper->num_bin();
          if (bin_mapper->GetMostFreqBin() == 0) {
            cur_num_bin -= 1;
          }
          num_total_bin += cur_num_bin;
          if (is_feature_used[f_start + j]) {
            new_num_total_bin += cur_num_bin;

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

            share_state->hist_move_src.push_back(
                (new_num_total_bin - cur_num_bin) * 2);
            share_state->hist_move_dest.push_back((num_total_bin - cur_num_bin) *
                                                 2);
            share_state->hist_move_size.push_back(cur_num_bin * 2);
            delta.push_back(num_total_bin - new_num_total_bin);
          }
        }
      } else if (!share_state->is_colwise) {
        bool is_group_used = false;
        for (int j = 0; j < feature_groups_[i]->num_feature_; ++j) {
          if (is_feature_used[f_start + j]) {
            is_group_used = true;
            break;
          }
1148
        }
1149
        int cur_num_bin = feature_groups_[i]->bin_offsets_.back() - 1;
1150
        num_total_bin += cur_num_bin;
1151
        if (is_group_used) {
1152
1153
1154
1155
          new_num_total_bin += cur_num_bin;

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

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

Guolin Ke's avatar
Guolin Ke committed
1192
template <bool USE_INDICES, bool ORDERED>
1193
1194
1195
1196
1197
1198
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 {
1199
1200
  Common::FunctionTimer fun_time("Dataset::ConstructHistogramsMultiVal",
                                 global_timer);
1201
1202
1203
1204
  const auto multi_val_bin =
      (share_state->is_use_subcol || share_state->is_use_subrow)
          ? share_state->multi_val_bin_subset.get()
          : share_state->multi_val_bin.get();
1205
1206
1207
  if (multi_val_bin == nullptr) {
    return;
  }
1208
1209
  global_timer.Start("Dataset::sparse_bin_histogram");
  const int num_bin = multi_val_bin->num_bin();
1210
1211
  const int num_bin_aligned =
      (num_bin + kAlignedSize - 1) / kAlignedSize * kAlignedSize;
Guolin Ke's avatar
Guolin Ke committed
1212
1213
  int n_data_block = 1;
  int data_block_size = num_data;
1214
  Threading::BlockInfo<data_size_t>(share_state->num_threads, num_data, 1024,
Guolin Ke's avatar
Guolin Ke committed
1215
                                    &n_data_block, &data_block_size);
1216
1217
  const size_t buf_size =
      static_cast<size_t>(n_data_block - 1) * num_bin_aligned * 2;
1218
1219
  if (share_state->hist_buf.size() < buf_size) {
    share_state->hist_buf.resize(buf_size);
1220
  }
1221
  auto origin_hist_data = hist_data;
1222
1223
  if (share_state->is_use_subcol) {
    hist_data = share_state->TempBuf();
1224
  }
Guolin Ke's avatar
Guolin Ke committed
1225
  OMP_INIT_EX();
1226
#pragma omp parallel for schedule(static, 1) num_threads(share_state->num_threads)
1227
  for (int tid = 0; tid < n_data_block; ++tid) {
Guolin Ke's avatar
Guolin Ke committed
1228
    OMP_LOOP_EX_BEGIN();
1229
1230
1231
1232
    data_size_t start = tid * data_block_size;
    data_size_t end = std::min(start + data_block_size, num_data);
    auto data_ptr = hist_data;
    if (tid > 0) {
1233
      data_ptr = share_state->hist_buf.data() +
1234
                 static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
1235
    }
1236
    std::memset(reinterpret_cast<void*>(data_ptr), 0, num_bin * kHistEntrySize);
Guolin Ke's avatar
Guolin Ke committed
1237
1238
1239
1240
    if (USE_INDICES) {
      if (ORDERED) {
        multi_val_bin->ConstructHistogramOrdered(data_indices, start, end,
                                                 gradients, hessians, data_ptr);
1241
      } else {
1242
        multi_val_bin->ConstructHistogram(data_indices, start, end, gradients,
Guolin Ke's avatar
Guolin Ke committed
1243
                                          hessians, data_ptr);
1244
1245
      }
    } else {
Guolin Ke's avatar
Guolin Ke committed
1246
1247
      multi_val_bin->ConstructHistogram(start, end, gradients, hessians,
                                        data_ptr);
1248
    }
Guolin Ke's avatar
Guolin Ke committed
1249
    OMP_LOOP_EX_END();
1250
  }
Guolin Ke's avatar
Guolin Ke committed
1251
  OMP_THROW_EX();
1252
1253
1254
  global_timer.Stop("Dataset::sparse_bin_histogram");

  global_timer.Start("Dataset::sparse_bin_histogram_merge");
Guolin Ke's avatar
Guolin Ke committed
1255
1256
  int n_bin_block = 1;
  int bin_block_size = num_bin;
1257
  Threading::BlockInfo<data_size_t>(share_state->num_threads, num_bin, 512, &n_bin_block,
Guolin Ke's avatar
Guolin Ke committed
1258
                                    &bin_block_size);
1259
#pragma omp parallel for schedule(static, 1) num_threads(share_state->num_threads)
Guolin Ke's avatar
Guolin Ke committed
1260
1261
1262
1263
1264
1265
1266
1267
  for (int t = 0; t < n_bin_block; ++t) {
    const int start = t * bin_block_size;
    const int end = std::min(start + bin_block_size, num_bin);
    for (int tid = 1; tid < n_data_block; ++tid) {
      auto src_ptr = share_state->hist_buf.data() +
                     static_cast<size_t>(num_bin_aligned) * 2 * (tid - 1);
      for (int i = start * 2; i < end * 2; ++i) {
        hist_data[i] += src_ptr[i];
1268
1269
1270
1271
      }
    }
  }
  global_timer.Stop("Dataset::sparse_bin_histogram_merge");
1272
  global_timer.Start("Dataset::sparse_bin_histogram_move");
1273
  share_state->HistMove(hist_data, origin_hist_data);
1274
  global_timer.Stop("Dataset::sparse_bin_histogram_move");
1275
1276
}

Guolin Ke's avatar
Guolin Ke committed
1277
1278
template <bool USE_INDICES, bool USE_HESSIAN>
void Dataset::ConstructHistogramsInner(
1279
1280
1281
    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,
1282
1283
    TrainingShareStates* share_state, hist_t* hist_data) const {
  if (!share_state->is_colwise) {
Guolin Ke's avatar
Guolin Ke committed
1284
1285
    return ConstructHistogramsMultiVal<USE_INDICES, false>(
        data_indices, num_data, gradients, hessians, share_state, hist_data);
1286
1287
1288
1289
  }
  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
1290
  for (int group = 0; group < num_groups_; ++group) {
Guolin Ke's avatar
Guolin Ke committed
1291
    const int f_start = group_feature_start_[group];
Guolin Ke's avatar
Guolin Ke committed
1292
    const int f_cnt = group_feature_cnt_[group];
1293
    bool is_group_used = false;
Guolin Ke's avatar
Guolin Ke committed
1294
    for (int j = 0; j < f_cnt; ++j) {
Guolin Ke's avatar
Guolin Ke committed
1295
      const int fidx = f_start + j;
Guolin Ke's avatar
Guolin Ke committed
1296
      if (is_feature_used[fidx]) {
1297
        is_group_used = true;
Guolin Ke's avatar
Guolin Ke committed
1298
1299
1300
        break;
      }
    }
1301
    if (is_group_used) {
1302
1303
1304
1305
      if (feature_groups_[group]->is_multi_val_) {
        multi_val_groud_id = group;
      } else {
        used_dense_group.push_back(group);
1306
      }
Guolin Ke's avatar
Guolin Ke committed
1307
    }
1308
1309
1310
  }
  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
1311
1312
  auto ptr_ordered_grad = gradients;
  auto ptr_ordered_hess = hessians;
1313
  if (num_used_dense_group > 0) {
Guolin Ke's avatar
Guolin Ke committed
1314
1315
    if (USE_INDICES) {
      if (USE_HESSIAN) {
Guolin Ke's avatar
Guolin Ke committed
1316
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1317
1318
1319
1320
        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
1321
1322
        ptr_ordered_grad = ordered_gradients;
        ptr_ordered_hess = ordered_hessians;
1323
      } else {
Guolin Ke's avatar
Guolin Ke committed
1324
#pragma omp parallel for schedule(static, 512) if (num_data >= 1024)
1325
1326
        for (data_size_t i = 0; i < num_data; ++i) {
          ordered_gradients[i] = gradients[data_indices[i]];
1327
        }
Guolin Ke's avatar
Guolin Ke committed
1328
        ptr_ordered_grad = ordered_gradients;
1329
      }
Guolin Ke's avatar
Guolin Ke committed
1330
1331
    }
    OMP_INIT_EX();
1332
#pragma omp parallel for schedule(static) num_threads(share_state->num_threads)
Guolin Ke's avatar
Guolin Ke committed
1333
1334
1335
1336
1337
1338
1339
1340
1341
    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) {
1342
          feature_groups_[group]->bin_data_->ConstructHistogram(
1343
1344
              data_indices, 0, num_data, ptr_ordered_grad, ptr_ordered_hess,
              data_ptr);
Guolin Ke's avatar
Guolin Ke committed
1345
        } else {
1346
          feature_groups_[group]->bin_data_->ConstructHistogram(
1347
              0, num_data, ptr_ordered_grad, ptr_ordered_hess, data_ptr);
1348
        }
1349
      } else {
Guolin Ke's avatar
Guolin Ke committed
1350
1351
1352
1353
        if (USE_INDICES) {
          feature_groups_[group]->bin_data_->ConstructHistogram(
              data_indices, 0, num_data, ptr_ordered_grad, data_ptr);
        } else {
1354
1355
          feature_groups_[group]->bin_data_->ConstructHistogram(
              0, num_data, ptr_ordered_grad, data_ptr);
1356
        }
Guolin Ke's avatar
Guolin Ke committed
1357
1358
1359
1360
        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];
        }
1361
      }
Guolin Ke's avatar
Guolin Ke committed
1362
      OMP_LOOP_EX_END();
Guolin Ke's avatar
Guolin Ke committed
1363
    }
Guolin Ke's avatar
Guolin Ke committed
1364
    OMP_THROW_EX();
Guolin Ke's avatar
Guolin Ke committed
1365
  }
1366
1367
  global_timer.Stop("Dataset::dense_bin_histogram");
  if (multi_val_groud_id >= 0) {
Guolin Ke's avatar
Guolin Ke committed
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
    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);
    }
1378
  }
Guolin Ke's avatar
Guolin Ke committed
1379
1380
}

Guolin Ke's avatar
Guolin Ke committed
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
// explicitly initilize template methods, for cross module call
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
1406
1407
void Dataset::FixHistogram(int feature_idx, double sum_gradient,
                           double sum_hessian, hist_t* data) const {
Guolin Ke's avatar
Guolin Ke committed
1408
1409
  const int group = feature2group_[feature_idx];
  const int sub_feature = feature2subfeature_[feature_idx];
Guolin Ke's avatar
Guolin Ke committed
1410
1411
  const BinMapper* bin_mapper =
      feature_groups_[group]->bin_mappers_[sub_feature].get();
Guolin Ke's avatar
Guolin Ke committed
1412
1413
  const int most_freq_bin = bin_mapper->GetMostFreqBin();
  if (most_freq_bin > 0) {
Guolin Ke's avatar
Guolin Ke committed
1414
    const int num_bin = bin_mapper->num_bin();
1415
1416
    GET_GRAD(data, most_freq_bin) = sum_gradient;
    GET_HESS(data, most_freq_bin) = sum_hessian;
Guolin Ke's avatar
Guolin Ke committed
1417
    for (int i = 0; i < num_bin; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1418
      if (i != most_freq_bin) {
1419
1420
        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
1421
1422
1423
1424
1425
      }
    }
  }
}

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

Guolin Ke's avatar
Guolin Ke committed
1434
1435
1436
template <typename T>
void PushOffset(std::vector<T>* dest, const std::vector<T>& src,
                const T& offset) {
Guolin Ke's avatar
Guolin Ke committed
1437
  dest->reserve(dest->size() + src.size());
1438
  for (auto i : src) {
Guolin Ke's avatar
Guolin Ke committed
1439
    dest->push_back(i + offset);
1440
1441
1442
  }
}

Guolin Ke's avatar
Guolin Ke committed
1443
1444
1445
1446
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
1447
  if (!dest->empty() && !src.empty()) {
1448
    PushVector(dest, src);
Guolin Ke's avatar
Guolin Ke committed
1449
  } else if (!dest->empty() && src.empty()) {
1450
    for (size_t i = 0; i < src_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1451
      dest->push_back(deflt);
1452
    }
Guolin Ke's avatar
Guolin Ke committed
1453
  } else if (dest->empty() && !src.empty()) {
1454
    for (size_t i = 0; i < dest_len; ++i) {
Guolin Ke's avatar
Guolin Ke committed
1455
      dest->push_back(deflt);
1456
1457
1458
1459
1460
    }
    PushVector(dest, src);
  }
}

1461
void Dataset::AddFeaturesFrom(Dataset* other) {
1462
  if (other->num_data_ != num_data_) {
1463
    Log::Fatal(
Guolin Ke's avatar
Guolin Ke committed
1464
1465
        "Cannot add features from other Dataset with a different number of "
        "rows");
1466
  }
Guolin Ke's avatar
Guolin Ke committed
1467
1468
1469
1470
1471
  int mv_gid = -1;
  int other_mv_gid = -1;
  for (int i = 0; i < num_groups_; ++i) {
    if (IsMultiGroup(i)) {
      mv_gid = i;
1472
1473
    }
  }
Guolin Ke's avatar
Guolin Ke committed
1474
1475
1476
1477
  for (int i = 0; i < other->num_groups_; ++i) {
    if (other->IsMultiGroup(i)) {
      other_mv_gid = i;
    }
1478
  }
Guolin Ke's avatar
Guolin Ke committed
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
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
  // 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_) {
      feature_groups_.emplace_back(new FeatureGroup(*fg));
    }
    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) {
        features_in_group.back().push_back(f_start + j);
      }
    }
    feature_groups_[mv_gid]->AddFeaturesFrom(
        other->feature_groups_[other_mv_gid].get());
    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) {
          features_in_group[mv_gid].push_back(f_start + j);
        }
      } else {
        features_in_group.emplace_back();
        for (int j = 0; j < f_cnt; ++j) {
          features_in_group.back().push_back(f_start + j);
        }
        feature_groups_.emplace_back(
            new FeatureGroup(*other->feature_groups_[i]));
      }
    }
    // 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;
    used_feature_map_ = std::vector<int>(num_total_features_, -1);
    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);
1591
1592
1593
  num_total_features_ += other->num_total_features_;
}

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