Int64Index.get_loc() is very slow on unsorted, non-unique index

[toobaz]

Code Sample, a copy-pastable example if possible

In [2]: idx = pd.Int64Index(np.random.randint(2000, size=10000))

In [3]: %timeit idx.get_loc(1000)
316 µs ± 1.73 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [4]: %timeit np.where((idx == 1000))
26.6 µs ± 268 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [5]: (idx.get_loc(1000) == (idx == 1000)).all()
Out[5]: True

Problem description

In [4]: does the same thing that In [3]: does, taking ~11 times less.

Might be related to #9466 .

Output of pd.show_versions()

INSTALLED VERSIONS

commit: None
python: 3.5.3.final.0
python-bits: 64
OS: Linux
OS-release: 4.9.0-5-amd64
machine: x86_64
processor:
byteorder: little
LC_ALL: None
LANG: it_IT.UTF-8
LOCALE: it_IT.UTF-8

pandas: 0.23.0.dev0+187.g4618a0918.dirty
pytest: 3.2.3
pip: 9.0.1
setuptools: 36.7.0
Cython: 0.25.2
numpy: 1.12.1
scipy: 0.19.0
pyarrow: None
xarray: None
IPython: 6.2.1
sphinx: 1.5.6
patsy: 0.4.1
dateutil: 2.6.1
pytz: 2017.2
blosc: None
bottleneck: 1.2.0dev
tables: 3.3.0
numexpr: 2.6.1
feather: 0.3.1
matplotlib: 2.0.0
openpyxl: 2.3.0
xlrd: 1.0.0
xlwt: 1.3.0
xlsxwriter: 0.9.6
lxml: 4.1.1
bs4: 4.5.3
html5lib: 0.999999999
sqlalchemy: 1.0.15
pymysql: None
psycopg2: None
jinja2: 2.10
s3fs: None
fastparquet: None
pandas_gbq: None
pandas_datareader: 0.2.1

[jreback]

maybe a manifestation of #17754