SetPixel slows down over time

Question

I love to SetPixel on the DesktopWindow but sometimes it behaves strangely.

for(i=0;i<10000;i++)
    SetPixel(DC,100+100*sin((float)i/100),100+100*cos((float)i/100),0);

The code above should print 10,000 pixels drawing a Circle on the top-left corner of your screen. But if I use it many times, it becomes slower and slower. The code below should provide an example of this:

#include<windows.h>
int main(){
    Sleep(4000);//waiting you to be ready
    int i,j,k,l;
    HDC DC=GetDC(GetDesktopWindow());
    j=GetTickCount();//base time
    for(l=0;l<10;l++)
    {
        for(i=0;i<10000;i++)
            SetPixel(DC,rand()%1000,rand()%1000,0);//print 10000 random x,y pixel
        printf("%d\n",(k=GetTickCount())-j);//time duration from the last count
        for(i=0;i<10000;i++)
            SetPixel(DC,rand()%1000,rand()%1000,0);
        printf("%d\n",(j=GetTickCount())-k);
    }
    return 0;
}

Why would this operation slow down over time?

Answer 1

First, a bit of cleanup of your test code:

#include<windows.h>

// number of pixels written in each run
#define NUM_PIXELS 50000

// range of pixel coordinates
#define MIN_RANGE 100
#define MAX_RANGE 1000
#define RANGE_MULT 10

// pause after each run to allow DWM to do its things
#define DWM_PAUSE 20 // seconds

HDC DC;

void bench(int range, int pause)
{
    int i, start;

    // let DWM digest previous pixels
    Sleep(pause*1000);

    // feed more pixels into the system
    start = GetTickCount();
    for (i = 0; i != NUM_PIXELS; i++)
    {
        SetPixel(DC, rand()%range, rand()%range, 0);
    }
    printf ("pause %d range %d duration %d\n", pause, range, GetTickCount()-start);
}

int main (void)
{
    DC=GetDC(GetDesktopWindow());

    int range;
    for (range = MIN_RANGE; range <= MAX_RANGE; range *= RANGE_MULT) bench(range, 0);
    for (range = MAX_RANGE; range >= MIN_RANGE; range /= RANGE_MULT) bench(range, 0);
    for (range = MIN_RANGE; range <= MAX_RANGE; range *= RANGE_MULT) bench(range, DWM_PAUSE);
    for (range = MAX_RANGE; range >= MIN_RANGE; range /= RANGE_MULT) bench(range, DWM_PAUSE);
    return 0;
}

Running this program on Win7 with Aero desktop enabled produced this:

c:\Dev\PHP\_StackOverflow\C++\SlowSetPixel\Release>SlowSetPixel.exe
pause 0 range 100 duration 1404
pause 0 range 1000 duration 5273
pause 0 range 1000 duration 8377
pause 0 range 100 duration 3713
pause 20 range 100 duration 3089
pause 20 range 1000 duration 6942
pause 20 range 1000 duration 8455
pause 20 range 100 duration 3151

Same program running with Aero disabled:

c:\Dev\PHP\_StackOverflow\C++\SlowSetPixel\Release>SlowSetPixel.exe
pause 0 range 100 duration 47
pause 0 range 1000 duration 31
pause 0 range 1000 duration 31
pause 0 range 100 duration 31
pause 20 range 100 duration 63
pause 20 range 1000 duration 47
pause 20 range 1000 duration 47
pause 20 range 100 duration 62

Did somebody steal my CPU?

Yessir, and I caught the culprit in the act.

These tests are best used with a task manager open to watch the dreadful dwm.exe Desktop Window (Inept) Manager at work.

During the first execution, dwm.exe was stuck at 100% CPU (using one of the 4 cores of my PC) and its memory consumption rose to ludicrous amounts (it went from about 28 Mb to 112 Mb).

Even with a 20 seconds pause, the bloody DWM was not even finished digesting the pixels. That is why the second part of the test shows slightly longer execution times.

Without Aero, the SetPixel function basically does nothing. The DC is not invalid, but SetPixel does not carry out any (visible) modification.

What the heck?

The probable reason why all this happens is that with the flashy "new" (since Vista) desktop interface, composition of the final desktop bitmap is done by this dwm.exe process. Each window has its own graphic buffer, and dwm.exe gets notified of any changes and recomputes the final aspect of each pixel in the background.

Writing pixels directly into the desktop window basically screws up that little scheme, since an external program accesses what is supposedly the private playground of dwm.exe.

I don't know how the Microsoft guys handled that case, but obviously they did not do it in anything like an efficient way.
It looks like multiple copies of the desktop are loaded into memory, probably to allow one to be modified while the others are integrated in the composition chain.

The amount of memory gobbled by dwm.exe is roughly 25 times the size of a 1000*1000 RGBA bitmap.
The test shows this amount varies with the surface of the modified area.

I suspect the silly process samples the screen 20 or 30 times per second and creates a new copy of the modified portion of the screen when it sees something strange (like a SetPixel call) has happened.

With such a crappy result, I wonder why they allowed to access the desktop DC in the first place, except to allow people to smudge the screen with 10 lines of code.

Efficient screen access now requires the use of DirectX to bypass the awful crappy layer of backward-compatibility you must go through to manipulate bitmaps with the antiquated Win32 GDI.

Answer 2

Well, Kuroi neko has tried to explain it to some extent but I think the exact cause is not being answered.

Why it slows down over the time?

==> because in the end it turns out to be of order nlogn.

How ==>

1. Lets start by How setpixel works(might be working, but i'll talk as if its the way it works). First and most important task will be parameter validation. Google for cost of parameters validation(or stackexchange). It would also include mapping screen data to device context and then testing passed coordinates against it. Simply put, it takes time which should be considered.
2. Pixel has some properties; so it then would have to fill in some structure kinda thing, it would then have to create the palette and then fill in the color bits acc. to the structure, then it would need to map this palette to the device context. Next, it would need to clean up the mess for THIS pixel, and almost similar(may be little less) work is in the store for next pixel
3. Now comes the real meat: SetPixel() is function in gdi32.dll, and BOOM, graphics subsystem resides in kernel mode!!. So FOR EACH AND EVERY pixel there is an overhead of Usermode -> KernelMode -> Usermode, and that is why point 1 and 2 are rather of more importance than usual cases. And its easy to guess now why does it slow down over the time.

Has MS tried to solve this issue?

1. Yes, Yes and in fact this is the problem caused because of solution to some other problem. Simply, graphics subsystem was not part of kernel mode in the initial design, but Increase the Performance they moved it to kernel mode.
2. They tried GetEnhMetaFile which is definitely CALLED inside SetPixel()

And more important --> YOU should know when to use SetPixel(). If you are using it for the thing that can be done using other less time consuming mechanism, its YOUR mistake and not of MS. You should use it for the purposes like handwriting analysis or similar, where value of a single or very less pixels ARE making the difference

You can definitely google what does it mean by switching the mode some 100000 times continuously.