[BUG] cudf pivot extremely slow compared to pandas

[drabastomek]

Describe the bug
With a semi-large dataframe, the pivot method is super slow, especially compared to running it in pandas.

Steps/Code to reproduce bug

import cudf
import cupy

user_id  = cupy.array(cupy.random.uniform(0, 200000, 30000000)).astype('int')
movie_id = cupy.array(cupy.random.uniform(0,   4000, 30000000)).astype('int')

df = cudf.DataFrame({
    'user': user_id,
    'movie': movie_id
}).drop_duplicates()

df['rating'] = cupy.array(cupy.random.uniform(0, 10, df.shape[0])).astype('int') / 2
df.head()

The structure of the table looks as follows

user	movie	rating
143416	3101	1.0
180375	1766	4.5
6071	1750	4.0
179403	209	1.5
76224	3324	1.0

Executing the following code takes ~ 3 min 45 seconds on a single A6000
df_cudf_pivot = df.pivot(index='user', columns='movie', values='rating').fillna(-1)

Doing the same in pandas -- ~15 seconds.
df_cudf_pivot = df.to_pandas().pivot(index='user', columns='movie', values='rating').fillna(-1)

Expected behavior
I would expect that the cudf version to be significantly faster than pandas.

Environment overview (please complete the following information)

• Environment location: Docker
• Method of cuDF install: Docker
  • If method of install is [Docker], provide docker pull & docker run commands used

docker run --gpus all --pull always --rm -it     --shm-size=1g --ulimit memlock=-1 --ulimit stack=67108864     -p 8888:8888 -p 8787:8787 -p 8786:8786 -v /home/tom/work/data:/data  -v /home/tom/work/codes:/home/rapids/notebooks/codes   nvcr.io/nvidia/rapidsai/notebooks:24.10-cuda12.5-py3.12

Environment details

Click here to see environment details

 **git***
 commit cd3e352be06795b825828156da10ba83e1e8939f (HEAD -> branch-25.02, origin/branch-25.02, origin/HEAD)
 Author: Matthew Murray <[email protected]>
 Date:   Wed Dec 4 14:38:35 2024 -0500
 
 Migrate `cudf::io::merge_row_group_metadata` to pylibcudf (#17491)
 
 Apart of #15162
 
 Authors:
 - Matthew Murray (https://github.com/Matt711)
 
 Approvers:
 - Matthew Roeschke (https://github.com/mroeschke)
 
 URL: https://github.com/rapidsai/cudf/pull/17491
 **git submodules***
 
 ***OS Information***
 DISTRIB_ID=Ubuntu
 DISTRIB_RELEASE=24.04
 DISTRIB_CODENAME=noble
 DISTRIB_DESCRIPTION="Ubuntu 24.04.1 LTS"
 PRETTY_NAME="Ubuntu 24.04.1 LTS"
 NAME="Ubuntu"
 VERSION_ID="24.04"
 VERSION="24.04.1 LTS (Noble Numbat)"
 VERSION_CODENAME=noble
 ID=ubuntu
 ID_LIKE=debian
 HOME_URL="https://www.ubuntu.com/"
 SUPPORT_URL="https://help.ubuntu.com/"
 BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
 PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
 UBUNTU_CODENAME=noble
 LOGO=ubuntu-logo
 Linux atlantis 6.8.0-48-generic #48-Ubuntu SMP PREEMPT_DYNAMIC Fri Sep 27 14:04:52 UTC 2024 x86_64 x86_64 x86_64 GNU/Linux
 
 ***GPU Information***
 Wed Dec  4 20:37:10 2024
 +-----------------------------------------------------------------------------------------+
 | NVIDIA-SMI 560.35.03              Driver Version: 560.35.03      CUDA Version: 12.6     |
 |-----------------------------------------+------------------------+----------------------+
 | GPU  Name                 Persistence-M | Bus-Id          Disp.A | Volatile Uncorr. ECC |
 | Fan  Temp   Perf          Pwr:Usage/Cap |           Memory-Usage | GPU-Util  Compute M. |
 |                                         |                        |               MIG M. |
 |=========================================+========================+======================|
 |   0  NVIDIA RTX 6000 Ada Gene...    Off |   00000000:01:00.0 Off |                  Off |
 | 30%   44C    P8             23W /  300W |   28481MiB /  49140MiB |      0%      Default |
 |                                         |                        |                  N/A |
 +-----------------------------------------+------------------------+----------------------+
 |   1  NVIDIA RTX 6000 Ada Gene...    Off |   00000000:C1:00.0 Off |                  Off |
 | 30%   36C    P8             17W /  300W |       4MiB /  49140MiB |      0%      Default |
 |                                         |                        |                  N/A |
 +-----------------------------------------+------------------------+----------------------+
 
 +-----------------------------------------------------------------------------------------+
 | Processes:                                                                              |
 |  GPU   GI   CI        PID   Type   Process name                              GPU Memory |
 |        ID   ID                                                               Usage      |
 |=========================================================================================|
 |    0   N/A  N/A     55233      C   /opt/conda/bin/python                       28472MiB |
 +-----------------------------------------------------------------------------------------+
 
 ***CPU***
 Architecture:                         x86_64
 CPU op-mode(s):                       32-bit, 64-bit
 Address sizes:                        52 bits physical, 57 bits virtual
 Byte Order:                           Little Endian
 CPU(s):                               64
 On-line CPU(s) list:                  0-63
 Vendor ID:                            AuthenticAMD
 Model name:                           AMD Ryzen Threadripper PRO 7975WX 32-Cores
 CPU family:                           25
 Model:                                24
 Thread(s) per core:                   2
 Core(s) per socket:                   32
 Socket(s):                            1
 Stepping:                             1
 CPU(s) scaling MHz:                   15%
 CPU max MHz:                          7775.0000
 CPU min MHz:                          545.0000
 BogoMIPS:                             7987.72
 Flags:                                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_good amd_lbr_v2 nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 pcid sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pstate ssbd mba perfmon_v2 ibrs ibpb stibp ibrs_enhanced vmmcall fsgsbase bmi1 avx2 smep bmi2 erms invpcid cqm rdt_a avx512f avx512dq rdseed adx smap avx512ifma clflushopt clwb avx512cd sha_ni avx512bw avx512vl xsaveopt xsavec xgetbv1 xsaves cqm_llc cqm_occup_llc cqm_mbm_total cqm_mbm_local user_shstk avx512_bf16 clzero irperf xsaveerptr rdpru wbnoinvd amd_ppin cppc arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold avic v_vmsave_vmload vgif x2avic v_spec_ctrl vnmi avx512vbmi umip pku ospke avx512_vbmi2 gfni vaes vpclmulqdq avx512_vnni avx512_bitalg avx512_vpopcntdq la57 rdpid overflow_recov succor smca fsrm flush_l1d debug_swap
 Virtualization:                       AMD-V
 L1d cache:                            1 MiB (32 instances)
 L1i cache:                            1 MiB (32 instances)
 L2 cache:                             32 MiB (32 instances)
 L3 cache:                             128 MiB (4 instances)
 NUMA node(s):                         1
 NUMA node0 CPU(s):                    0-63
 Vulnerability Gather data sampling:   Not affected
 Vulnerability Itlb multihit:          Not affected
 Vulnerability L1tf:                   Not affected
 Vulnerability Mds:                    Not affected
 Vulnerability Meltdown:               Not affected
 Vulnerability Mmio stale data:        Not affected
 Vulnerability Reg file data sampling: Not affected
 Vulnerability Retbleed:               Not affected
 Vulnerability Spec rstack overflow:   Mitigation; Safe RET
 Vulnerability Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
 Vulnerability Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
 Vulnerability Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; STIBP always-on; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
 Vulnerability Srbds:                  Not affected
 Vulnerability Tsx async abort:        Not affected
 
 ***CMake***
 
 ***g++***
 /usr/bin/g++
 g++ (Ubuntu 13.2.0-23ubuntu4) 13.2.0
 Copyright (C) 2023 Free Software Foundation, Inc.
 This is free software; see the source for copying conditions.  There is NO
 warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
 
 
 ***nvcc***
 
 ***Python***
 
 ***Environment Variables***
 PATH                            : /usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games:/snap/bin
 LD_LIBRARY_PATH                 :
 NUMBAPRO_NVVM                   :
 NUMBAPRO_LIBDEVICE              :
 CONDA_PREFIX                    :
 PYTHON_PATH                     :
 
 conda not found
 pip not found

Additional context
Add any other context about the problem here.

[mroeschke]

Thanks for the report.

I don't have a solution off the top of my head, but I believe the hot spot is in this line.

cudf/python/cudf/cudf/core/reshape.py

Line 1005 in 1b82963

names, target._split(range(nrows, new_size, nrows))

target is a "flattened" (1D) version of each pivoted column= label, and this for loop copies out each column from the flattened version to create the resulting DataFrame

[drabastomek]

Ah, I see -- it basically create a humongous dictionary of ~4400 elements and 200k items, mostly N/As...

Side note...

I do this so I can train a KNN model and it requires a user by movie rating table that would by definition be extremely sparse. Perhaps a better solution (memory and speed wise) would be to adjust the .fit method of the NearestNeighbors to accept a sparse version of the table, like CSR or CSC. Just a thought.

[drabastomek]

I just realized that I can use CuPy to convert my table to CSR sparse matrix to fit the KNN so that point is moot.

Still, the slowness of the pivot remains.