The appropriate time is after you've done some profiling. Only when you have identified a (separable) routine or part of your program that takes up a big chunk of the runtime (and isn't just slow because of I/O) is it worth thinking about using C.

If a hash could be done faster in C then the perl interpreter would already do that. Don't try to make perls data structures faster, think about making parts of your code faster.

If you think about speeding up data structures you also have to think about whether you still have anything left from the speedup after the data was translated from perl to C and back again.

Lets say, you find a subroutine in your code that uses up 20% of your runtime. And you speed that up a hundred times faster, which would be a phenomenal "get out the champagne" success. But your overall speed up would still only be less than 20%. That is 8 minutes instead of 10.

You see, you really need to find something that takes up a major part of your runtime or you will be just wasting your own time