How to deal with: Apex CPU time limit exceeded

In my recent project on SFDC-SAP integration, there is one interface called "Customer Master Data and Hierarchy". SFDC has exposed this service thru SOAP APIs. The web service class is so huge and complex (more than 2000 LoC) that I have to keep the code optimization and performance in mind. During bulk data load testing in UAT, SFDC thows "Apex CPU time limit exceeded" limit exception during run time.

Wayout: Optimize your code by using maps and sets. Use less or avoid using nested For loops as the more is the iterations, the more time it takes for the logic when there are bulk load (thousands and thousands of records).

In my case,

1. there were two nested For loops which was causing the error: Replaced with only one For loop and used maps and sets for compensating this change.
2. the packet size from SAP:  When it was set to 999, SFDC was skipping some intermidiate batch of data. When it is set to 200. everything is perfect.