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, and can waste more engineering time than the slowness itself.

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.

INPUT SCALE
Currently 500k rows, expected to reach 2-3M rows within the next two quarters.

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, and check that hypothesis against Currently 500k rows, expected to reach 2-3M rows within the next two quarters. — a fix that only helps at 10x the current scale is a different priority than one needed right now.
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, and should be presented first even if it's more work to implement.
4. For any fix that trades memory for speed, or changes behavior under concurrency, say so explicitly, and check it against Must stay single-threaded (runs inside a Celery worker with its own concurrency model already)..
5. Record a concrete before number from Takes 40+ seconds on 500k rows; was fine at 10k rows a few months ago. as the baseline — not a vague "it's slow," an actual wall-clock time or throughput figure — so the fix has something specific to beat rather than a moving target.
6. Note where the profiling tool itself might distort the result: cProfile's per-call instrumentation overhead can make a function relatively look slower than it actually is in production if it's called an extreme number of times, so say explicitly if that risk applies here and whether py-spy's sampling approach (near-zero overhead) would give a more trustworthy picture instead.
7. State how to verify the fix actually helped: re-run the same profiling step and compare numbers against the baseline from step 5, not "this should be faster" — a fix that isn't measured against a real before number isn't confirmed, it's assumed.

OUTPUT FORMAT
Bottleneck hypothesis, then the profiling command to confirm it, then the baseline number, then a ranked fix list, then the verification step with the after number compared against the baseline.