Sp suddenly taking WAAAY too long

Take a look at the estimated execution plan, try to find any types of scans. In Management studio you can use shortcut key CTRL + L

You should also beware of this:

• a procedure with 4000 lines of code is not very efficient. The query optimizer may have issues when the procedure is compliled. Try to break the procedure into smaller parts.
• Cursors are not very efficient in SQL server. Try to use a SET based approach.
• Statistics that is out of date may cause an incorrect execution plan
• Indexes that are fragmented may cause even worse performance issues.
• Indexes that are missing or incorrect causes scans (table or index scans)

Incorrect indexes may be caused by:

• Index not selective enough (more data added)
• query doesn't include a filter on the first column in the index. (make sure you are using filter on columns that is specified in the index, from left to right. If you don't use a filter on the last column in an index may be okey, but not the first column)
• The index used is not covering and SQL need to use a key lookup to get the rest of the data from clustered index.

involves an inner and outer cursor

That says it all, pretty much.

Ok, so it's started to take a lot longer - so that's going to be something related to your recent changes. However, it's pretty likely that you will be able to get that procedure running much much much quicker if it was written in a set based way.

I accept that you're probably not going to re-write a 4000 line proc, so other things you can try:

• Review the changes to make sure it wasn't something silly
• Have a look at the estimated execution plan to check nothing shows up
• Check that the statistics on the referenced tables are up to date
• Check that the indexing on the referenced tables is appropriate

4000 lines & Cursors! That sounds like your problem.

But to get you started: You say the sproc has recently been modified, this is the first place to start. What has changed? Have you changed table structure? Added lots of code to the sproc? Added lots more data to the underlying tables? Added any triggers to tables that are now slowing things down?

The best way to go is to take the sproc apart, step by step and see what is going on (look at the execution plans for each part separately). If you can remove the cursors that will help - SQL Server was not designed for cursors and can do most things without them.

What is your sproc doing in those 4000 lines, if you don't mind me asking?

Was there additional logging added to the SPROC? Any additional I/O is exponentially bothersome within cursors.

Has blocking increased?

Are there multiple transactions in the SPROC or is it all wrapped up as one big one?

Consider using some diagnostic DMVs.

Glenn Berry has some here for SQL 2008, and I am sure there are more on his site for 2005.