PERF: hash_pandas_object performance regression between 2.1.0 and 2.1.1

[snazzer]

Pandas version checks

• I have checked that this issue has not already been reported.

• I have confirmed this issue exists on the latest version of pandas.

• I have confirmed this issue exists on the main branch of pandas.

Reproducible Example

Given the following example:

from hashlib import sha256
import numpy as np
import pandas as pd

import time

size = int(1e4)
while size <= int(3e5):
    df = pd.DataFrame(np.random.normal(size=(size, 50)))
    df_t = df.T
    start = time.process_time()
    hashed_rows = pd.util.hash_pandas_object(df_t.reset_index()).values
    t = (size, time.process_time() - start)
    print(f'{t[0}, {t[1]}')
    size = size + 10000

The runtimes between version 2.1.0 and 2.1.1 are drastically different, with 2.1.1 showing polynomial/exponential runtime.

Installed Versions

For 2.1.0

INSTALLED VERSIONS
------------------
commit              : ba1cccd19da778f0c3a7d6a885685da16a072870
python              : 3.9.18.final.0
python-bits         : 64
OS                  : Linux
OS-release          : 5.15.49-linuxkit-pr
Version             : #1 SMP PREEMPT Thu May 25 07:27:39 UTC 2023
machine             : aarch64
processor           : 
byteorder           : little
LC_ALL              : None
LANG                : C.UTF-8
LOCALE              : en_US.UTF-8

pandas              : 2.1.0
numpy               : 1.26.0
pytz                : 2023.3.post1
dateutil            : 2.8.2
setuptools          : 67.8.0
pip                 : 23.2.1
Cython              : 3.0.2
pytest              : None
hypothesis          : None
sphinx              : None
blosc               : None
feather             : None
xlsxwriter          : None
lxml.etree          : None
html5lib            : None
pymysql             : None
psycopg2            : None
jinja2              : 3.1.2
IPython             : None
pandas_datareader   : None
bs4                 : None
bottleneck          : None
dataframe-api-compat: None
fastparquet         : None
fsspec              : 2023.9.1
gcsfs               : None
matplotlib          : 3.8.0
numba               : None
numexpr             : None
odfpy               : None
openpyxl            : None
pandas_gbq          : None
pyarrow             : 13.0.0
pyreadstat          : None
pyxlsb              : None
s3fs                : None
scipy               : 1.11.2
sqlalchemy          : None
tables              : None
tabulate            : None
xarray              : None
xlrd                : None
zstandard           : None
tzdata              : 2023.3
qtpy                : None
pyqt5               : None

For 2.1.1

INSTALLED VERSIONS
------------------
commit              : e86ed377639948c64c429059127bcf5b359ab6be
python              : 3.9.18.final.0
python-bits         : 64
OS                  : Linux
OS-release          : 5.15.49-linuxkit-pr
Version             : #1 SMP PREEMPT Thu May 25 07:27:39 UTC 2023
machine             : aarch64
processor           : 
byteorder           : little
LC_ALL              : None
LANG                : C.UTF-8
LOCALE              : en_US.UTF-8

pandas              : 2.1.1
numpy               : 1.26.0
pytz                : 2023.3.post1
dateutil            : 2.8.2
setuptools          : 67.8.0
pip                 : 23.2.1
Cython              : 3.0.2
pytest              : None
hypothesis          : None
sphinx              : None
blosc               : None
feather             : None
xlsxwriter          : None
lxml.etree          : None
html5lib            : None
pymysql             : None
psycopg2            : None
jinja2              : 3.1.2
IPython             : None
pandas_datareader   : None
bs4                 : None
bottleneck          : None
dataframe-api-compat: None
fastparquet         : None
fsspec              : 2023.9.1
gcsfs               : None
matplotlib          : 3.8.0
numba               : None
numexpr             : None
odfpy               : None
openpyxl            : None
pandas_gbq          : None
pyarrow             : 13.0.0
pyreadstat          : None
pyxlsb              : None
s3fs                : None
scipy               : 1.11.2
sqlalchemy          : None
tables              : None
tabulate            : None
xarray              : None
xlrd                : None
zstandard           : None
tzdata              : 2023.3
qtpy                : None
pyqt5               : None

Prior Performance

Same example as above. 2.1.0 is fine. 2.1.1 is not.

[jbrockmendel]

@jorisvandenbossche i think you and i are the only ones to mess with this code recently, but IIRC only EAs would have been affected?

[gupta-paras]

I have verified and can confirm, this issue exists on main branch as well.

Shall I take this issue?

[jorisvandenbossche]

@snazzer thanks for the report!
I can also reproduce the issue. Smaller code sample:

size = 10_000
df = pd.DataFrame(np.random.normal(size=(50, size)))
%timeit pd.util.hash_pandas_object(df.reset_index())

But, from a quick profile, it seems it is not related to the actual hashing code itself, but from getting each row: hash_pandas_object calls DataFrame.items() to iterate over the columns (and that eventually calls BlockManager.iget), and it is this part that has become slower.

And it also seems it is related to some caching issue. With the reset_index() included, we see the slowdown:

In [44]: %timeit pd.util.hash_pandas_object(df.reset_index())
1.87 s ± 42.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

But when removing that part of the reproducer, we only see the slowdown the first time when called, and so when timing multiple times, we don't see it anymore:

In [45]: %timeit pd.util.hash_pandas_object(df)
168 ms ± 2.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

@gupta-paras certainly welcome to help, but so it might require some more investigation first

[jorisvandenbossche]

So this is another manifestation of #55008 (comment), I think

[gupta-paras]

@jorisvandenbossche, I have dome some initial investigation, and found that below section is slow in particular. This is affecting the iget:
https://github.com/pandas-dev/pandas/blob/main/pandas/core/internals/managers.py#L1014

nb = NumpyBlock / Block(
                values, placement=bp, ndim=1, refs=block.refs if track_ref else None
            )

[jorisvandenbossche]

Indeed, see #55008 (comment) for the context (that's the PR that caused this). There is already a PR open to address this in the meantime -> #55518

[gupta-paras]

Exactly, disabling "_clear_dead_references" made program run faster. Thanks @jorisvandenbossche