BUG: assert_frame_equal can be very slow
- [x] I have checked that this issue has not already been reported.

- [x] I have confirmed this bug exists on the latest version of pandas.

- [ ] (optional) I have confirmed this bug exists on the master branch of pandas.

---

**Note**: Please read [this guide](https://matthewrocklin.com/blog/work/2018/02/28/minimal-bug-reports) detailing how to provide the necessary information for us to reproduce your bug.

#### Code Sample, a copy-pastable example

Comparisons which can take less than a second, take 50 seconds when they are combined:

```python
import pandas as pd
import numpy as np
from string import ascii_letters

idx = np.random.choice(np.array(list(ascii_letters)), size=10000).astype(object)
a = np.random.random_integers(0, 100, (10000, 1000))

# This is fine
%time pd.testing.assert_frame_equal(pd.DataFrame(a), pd.DataFrame(a.copy()))
# CPU times: user 409 ms, sys: 20.8 ms, total: 429 ms
# Wall time: 429 ms

# As is this
%time pd.testing.assert_index_equal(pd.Index(idx), pd.Index(idx.copy()))
# CPU times: user 1.06 ms, sys: 26 µs, total: 1.08 ms
# Wall time: 1.08 ms

# This is weird:
%time pd.testing.assert_frame_equal(pd.DataFrame(a, index=idx), pd.DataFrame(b, index=idx))
# CPU times: user 50.5 s, sys: 62.6 ms, total: 50.6 s
# Wall time: 50.6 s
```

#### Problem description

It seems weird that the whole process slows down when the index has strings in it. It's especially weird since comparing the index itself is fairly fast. This may be a regression, since I've never noticed this before, and this seem very noticeable.

This might have something to do with  #38091

#### Output of ``pd.show_versions()``

<details>

```
INSTALLED VERSIONS
------------------
commit           : 67a3d4241ab84419856b84fc3ebc9abcbe66c6b3
python           : 3.8.5.final.0
python-bits      : 64
OS               : Darwin
OS-release       : 19.6.0
Version          : Darwin Kernel Version 19.6.0: Thu Oct 29 22:56:45 PDT 2020; root:xnu-6153.141.2.2~1/RELEASE_X86_64
machine          : x86_64
processor        : i386
byteorder        : little
LC_ALL           : None
LANG             : en_US.UTF-8
LOCALE           : en_US.UTF-8

pandas           : 1.1.4
numpy            : 1.19.4
pytz             : 2020.1
dateutil         : 2.8.1
pip              : 20.2.4
setuptools       : 50.3.2
Cython           : 0.29.21
pytest           : 6.1.2
hypothesis       : None
sphinx           : 3.3.1
blosc            : None
feather          : None
xlsxwriter       : None
lxml.etree       : None
html5lib         : None
pymysql          : None
psycopg2         : None
jinja2           : 2.11.2
IPython          : 7.19.0
pandas_datareader: None
bs4              : None
bottleneck       : None
fsspec           : 0.8.4
fastparquet      : 0.4.1
gcsfs            : None
matplotlib       : 3.3.3
numexpr          : 2.7.1
odfpy            : None
openpyxl         : None
pandas_gbq       : None
pyarrow          : 2.0.0
pytables         : None
pyxlsb           : None
s3fs             : 0.4.2
scipy            : 1.5.4
sqlalchemy       : 1.3.18
tables           : 3.6.1
tabulate         : 0.8.7
xarray           : 0.16.1
xlrd             : 1.2.0
xlwt             : None
numba            : 0.51.2
```


</details>
