Performance considerations throwing exceptions (best way to refactor this pattern)

I'm not sure if i need to ask this question here or on https://softwareengineering.stackexchange.com/, but lets start with what i have at the moment.

---

Current situation

I'm maintaining a data converter that is converting record by record and a lot of them (30M+). I receive an id from the old database and after inserting i have the new primary key. These keys will be stored inside an Dictionary of some kind so when i need to find the new id i can find it. This is done by the following code (simplified example code, not the real one)

public class PersonConverter : Converter
{
    public bool Convert(int oldPersonId /*some more parameters*/)
    {
        int newPersonId;

        try
        {
            newPersonId = GetNewPersonIdForPerson(oldPersonId);
        }
        catch (SourceKeyNotFoundException)
        {
            SomeLogging("Log message");
            return true;
        }

        //lots of more thing are happening here!
        return true;
    }
}

public class Converter
{
    private Dictionary<int,int> _convPersonId;

    protected int GetNewPersonIdForPerson(int oldPersonId)
    {
        int key = oldPersonId;
        if (_convPersonId.TryGetValue(key, out int newPersonId))
            return newPersonId;
        throw new SourceKeyNotFoundException(key.ToString());
    }

    protected void SomeLogging(string message)
    {
        //Implement logging etc...
    }
}

Here in the PersonConverter we have a single call to GetNewPersonIdForPerson(oldPersonId) but in the real code there are lots of these calls to different dictionaries. My predecessor was fond of throwing exeptions as you can see. Performance wise this is not ideal, and according to Microsoft's website about Exceptions & Performance they suggest using the Tester-Doer Pattern or the Try-Parse pattern

The solution

solution 1

The solution i came up with is have the GetNewPersonIdForPerson(oldPersonId) return a int.MinValue or some other deterministic value and instead of the try/catch block use an if/else block checking for that value.

Take a loot at the new method GetNewPersonIdForPerson2(int oldPersonId)

protected int GetNewPersonIdForPerson2(int oldPersonId)
{
    int key = oldPersonId;
    if (_convPersonId.TryGetValue(key, out int newPersonId))
        return newPersonId;
    return int.MinValue;
}

and the way i call this instead of the try/catch block inside the Convert method of PersonConverter

if(GetNewPersonIdForPerson2(oldPersonId) != int.MinValue)
{
    newPersonId = GetNewPersonIdForPerson(oldPersonId); 
}
else
{
    SomeLogging("Log message");
    return true;
}

This solution has some problems because i need to call GetNewPersonIdForPerson2 twice event though i think performance wise this is quicker than throwing the exceptions.

solution 2

Another solution will be having an out variable on the GetNewPersonIdForPerson method like the following

protected bool GetNewPersonIdForPerson3(int oldPersonId, out int returnPersonId)
{
    int key = oldPersonId;
    if (_convPersonId.TryGetValue(key, out returnPersonId))
        return true;
    return false;
}

And do the following inside the Convert method of PersonConverter

if (!GetNewPersonIdForPerson3(oldPersonId, out newPersonId))
{
    SomeLogging("Log message");
    return true;
}

I haven't done anything jet to refactor this because I want some input on what is the best solution. I prefer Solution 1 because this is easier to refactor but this has 2 lookups in the same dictionary. I can't exactly tell how much of these Try/Catch blocks I have but there are lots of them. and the GetNewPersonIdForPerson method is not the only one i have (20+) don't know exaclty.

The question

Can anyone tell me what a good pattern is to fix this problem or is one the the two solutions i came up with the best one.

PS: With large conversions, 7.5M+ execeptions are throw according to the performance counter # of Exceps Thrown
PS 2: This is only some sample code and the dictionaries live forever unlike this example.