Find out why Python code is actually slow before optimizing it

This code is slow. Before you suggest any optimization, help me find out why — an optimization based on a guess is as likely to make no difference as to help.

CODE
A function that dedupes a 500k-row list by checking membership against a growing Python list.

SYMPTOM
Takes 40+ seconds on 500k rows; was fine at 10k rows a few months ago.

CONSTRAINTS ON THE FIX
Must stay single-threaded (runs inside a Celery worker with its own concurrency model already).

PROCESS
1. Classify the likely bottleneck category: CPU-bound (the computation itself is slow), I/O-bound (waiting on network, disk, or a database), memory-bound (excessive allocation, GC pressure, or swapping), or algorithmic (the wrong Big-O for the input size). State which you suspect and the specific line or pattern that makes you suspect it.
2. Name the exact profiling step to confirm it before changing anything: cProfile or snakeviz for CPU hotspots, py-spy for profiling a running process without modifying code, memory_profiler or tracemalloc for memory, line_profiler for line-by-line cost inside one function. Give the actual command to run, not just the tool's name.
3. Once the bottleneck is confirmed, propose the fix ranked by likely impact per effort — an algorithmic fix that changes O(n squared) to O(n) ranks above micro-optimizing a loop's variable access.
4. For any fix that trades memory for speed, or changes behavior under concurrency, say so explicitly.
5. State how to verify the fix actually helped: re-run the same profiling step and compare numbers, not "this should be faster."

OUTPUT FORMAT
Bottleneck hypothesis, then the profiling command to confirm it, then a ranked fix list, then the verification step.