Along those lines, in C++, a vector very often performs better than a theoretically better data structure. I learned C++ fairly well from a very experienced guy in the company, and he said that you should always benchmark against a vector. I suspect if I was in his team and he were reviewing my code, he wouldn't let the code pass unless I had benchmarks that show whatever data set I picked is faster than a vector.
He wasn't against other data structures - he just wanted proof they would perform better. In quite a few cases, they didn't.
In this particular case I'd expect the change to be motivated by profiling of the real production instances. And that makes it pretty obvious how the change should be evaluated. "We're spending more time than is reasonable in linear scans, so the worst case inputs must be worse than expected. Switch to a data structure more suited to large inputs, and see if CPU use improves in the next rollout."
No one here is agreeing with that.