Search here, I have posted code and details before. If you can't find it or have troubles post again (with code would help) and I will try to assist.
Ensure you are handling the OnEraseBkgnd() and returning true.
Ensure you are only calling for a paint when required (minimum amout of InvalidateRect() calls).
Ensure you use InvalidateRect() with the minimum rectangle possible.
Follow each InvalidateRect() with an UpdateWindow() [this causes the paint msg to be posted directly to the window's callback, not to the OS msg queue, speeding up paint.]
Ensure your paint is not using the entire client rect and is using the rect / region returned in the PAINTSTRUCT or GetUpdateRect().
//this code is a rough guide, not working code
//it is a quick cut and paste from multiple methods
//I have a base class that does all the create and clean-up
//the individual drawing code is in the derived class
//I also prefer to return an error than throw / ASSERT()
//you will need to tailor this code to your needs.
#define WHITE RGB(255,255,255)
CBitmap *m_ScrOrBmp; //this si the original 1x1 black and white BMP we get in a created DC, we save it till we need to delete the DC
CBitmap m_ScrBmp; //this is our created BMP with size equal to the client area and colour depth of the main screen
CDC m_ScrDC; //this is the DC to hold our created BMP. We use this DC to do all the drawing, and then call for a paint to copy this DC to the screen
if(!Rect.Width() || !Rect.Height())//window not yet sized
//create a memory DC and bitmap
//catch the returned BMP so we can return the DC to the original state before we delete it
//fill the client area with a solid white colour
CPaintDC dc(this); // device context for painting
// test to ensure we do not try to release a NULL DC
//put the original BMP back
//now the created BMP is not selected into a DC we can delete it
//now the created DC is back to its original state we can delete it
//make sure our test is valid by setting the HDC member to NULL
//add methods to draw to m_ScrDC and then call a paint msg
//add a method to handle size changes, delete the current BMP and DC and create a new set the required size