Exceptions are meant to represent exceptional states.

The data is always expected to be valid and there is no recovery? .Parse

The data may be invalid and the implementation can handle it? .TryParse

This is a very common pattern and adopted for reasons besides the cost of exceptions. Though in this case it is Uri.TryCreate instead.

The allocation is plenty cheap, but creating the stack trace is expensive in pretty much all structured exception systems, and it is noticeable in loops, not necessarily even really tight ones.

So yeah if you’re parsing thousands of url candidates and expect many will not parse, don’t use exceptions to communicate the expected errors. Otherwise don’t worry about it.