Repository navigation
Slow dataset creation #4037
Description
import datatable as dt
import numpy as np
rows=200
cols=800000
table = dt.Frame(np.random.rand(rows, cols))
table.names = ["name_" + str(x) for x in range(table.shape[1])]
target = "name_0"
y = table[:, target].to_numpy().ravel()
del table[target]
import lightgbm as lgb
model = lgb.LGBMRegressor()
model.fit(table, y)
3.1.1.99
Using datatable or numpy, same result. Gets "stuck" here using 1 core for 10-20 minutes:
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/basic.py", line 1204 in __init_from_np2d
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/basic.py", line 1158 in _lazy_init
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/basic.py", line 1356 in construct
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/basic.py", line 2096 in __init__
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/engine.py", line 230 in train
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/sklearn.py", line 637 in fit
File "/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/sklearn.py", line 794 in fit
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(_ZN8LightGBM10FindGroupsERKSt6vectorISt10unique_ptrINS_9BinMapperESt14default_deleteIS2_EESaIS5_EERKS0_IiSaIiEEPPiPKiiiibbPS0_IaSaIaEE+0x1f4)[0x7fc824bb1404]
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(_ZN8LightGBM19FastFeatureBundlingERKSt6vectorISt10unique_ptrINS_9BinMapperESt14default_deleteIS2_EESaIS5_EEPPiPPdPKiiiRKS0_IiSaIiEEibbPS0_IaSaIaEE+0xbc2)[0x7fc824bb44e2]
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(_ZN8LightGBM7Dataset9ConstructEPSt6vectorISt10unique_ptrINS_9BinMapperESt14default_deleteIS3_EESaIS6_EEiRKS1_IS1_IdSaIdEESaISB_EEPPiPPdPKiimRKNS_6ConfigE+0x278)[0x7fc824bb50b8]
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(_ZN8LightGBM13DatasetLoader31ConstructBinMappersFromTextDataEiiRKSt6vectorISsSaISsEEPKNS_6ParserEPNS_7DatasetE+0x1a29)[0x7fc824bcf179]
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(_ZN8LightGBM13DatasetLoader12LoadFromFileEPKcii+0x1bb)[0x7fc824bd2b7b]
/home/jon/minicondadai/lib/python3.6/site-packages/lightgbm_gpu/lib_lightgbm.so(LGBM_DatasetCreateFromFile+0x17b)[0x7fc824df36eb]
After the 10-20 minutes, I get system OOM even though I have 64GB.
I read: #1081
which is also quite wide. But in general, what recommendations are there for many columns and speeding things up while using not too much memory.
I'm trying various things, but seems like how lgb uses 1 core for 20 minutes can be improved. E.g. in xgboost I/we used openmp for data ingestion, which despite alot of the operations being memory bandwidth limited does speed things up. That makes sense since the lgb dataset construction operation is about 100x slower than making the data itself, which is bad.
So, it must be possible to parallelize the dataset construction since features are independent. E.g. even fork many jobs that take portion of data and create Dataset objects, then use add_features_from to column bind the features? Why isn't that done internally using openmp?
Activity
pseudotensor commentedon Mar 1, 2021
Using csv is still very slow and single threaded
pseudotensor commentedon Mar 1, 2021
Setting max_bin = 4 doesn't help, still same time. Is there possibly an O(N^2) operation in the dataset creation process?
pseudotensor commentedon Mar 1, 2021
Repeated samples of where in gdb shows always stuck in the
FindGroupsfunction using theBinMapperhttps://github.com/microsoft/LightGBM/blob/master/src/io/dataset.cpp#L120-L187
Potential fix for lightgbm-org#4037
pseudotensor commentedon Mar 2, 2021
https://github.com/microsoft/LightGBM/blob/master/src/io/dataset.cpp#L125-L134
Basically this inner features_in_group loop has a size that grows directly and same size as fidx (the outer loop). So even if by fidx=100000 the time is only 100us per fidx value, but by fidx=800000 the time is 1000us per fidx value.
I already moved the bin_mapper stuff out of the loop:
h2oai@e498551
but that didn't help this slowness or the O(N^2) behavior.
guolinke commentedon Mar 2, 2021
ping @shiyu1994
pseudotensor commentedon Mar 2, 2021
I tried to use the rand.Sample() to sample features_in_group, but turns out rand.Sample() is just as bad. The way it is designed it scales with the size to sample from, not the size of sample. That's also quite bad.
So such an attempt still keeps things at O(N^2).
Example of random without replacement that is O(N): https://stackoverflow.com/questions/28287138/c-randomly-sample-k-numbers-from-range-0n-1-n-k-without-replacement
shiyu1994 commentedon Mar 5, 2021
@pseudotensor Thanks for using LightGBM.
The synthesized dataset is dense. So I think https://github.com/microsoft/LightGBM/blob/37e987828d3141aded1a6e356fdcc7954a6f2f5c/src/io/dataset.cpp#L125-L134
won't find any available groups. Each feature will end up in a separate group.
This is a very extreme case. A possible solution would be to limit the maximum number of trials (iterations) in line 125.
StrikerRUS commentedon Jun 9, 2021
@shiyu1994
Do you have plans implementing this? Or we can write this into our feature requests?
shiyu1994 commentedon Jul 6, 2021
@StrikerRUS We can have this in feature requests. A quick fix would be to randomly sample from feature groups in line 125. How to sample the groups when the total number of groups is large is an open question.
We have a plan to separate the dataset construction. I think we may leave it to that part.
StrikerRUS commentedon Jul 24, 2024
Closed in favor of being in #2302. We decided to keep all feature requests in one place.
Welcome to contribute this feature! Please re-open this issue (or post a comment if you are not a topic starter) if you are actively working on implementing this feature.