A hidden performance cost of regional windows

Date:June 11, 2004 / year-entry #231
Tags:code
Orig Link:https://blogs.msdn.microsoft.com/oldnewthing/20040611-00/?p=38923
Comments:    22
Summary:Regional windows are neat, but they come at a cost. Most of the cost you can see directly. For example, constantly changing the region clearly generates a cost since you have to sit there and generate new regions all the time. One question that came up on an internal performance alias highlights one of the...

Regional windows are neat, but they come at a cost. Most of the cost you can see directly. For example, constantly changing the region clearly generates a cost since you have to sit there and generate new regions all the time.

One question that came up on an internal performance alias highlights one of the hidden costs of regional windows: The putative window rectangle.

Suppose you have a large window but set a small window region. How much worse is this than haveing a small window with a small window region?

Quite a bit, actually.

Hit-testing is one of the most common operations performed by a window manager. Given a point on the screen, find the window that it corresponds to. To speed this up, the window rectangle is used to rule out windows quickly. For example, if a window's rectangle is (0,0)-(100,100) then the point (200,10) is clearly not within the window since it doesn't fit in the rectangle. Rectangle tests are fast.

If the window is regional, then the rectangle test is not good enough, because the point may exist within the rectangle but outside the region. In that case, the point must be tested against the window region itself.

But Windows uses the window rectangle as a "quick test" to see if the region is worth checking. If the point lies outside the rectangle, then the window manager doesn't even bother checking the region, which is good because region testing is comparatively slow.

In other word, the pseudocode for hit-testing goes something like this:

if (point is outside window rectangle)
  return no-hit;
else if (window has no region)
  return hit;
else if (point is inside region)
  return hit;
else
  return no-hit;

So if you create a huge window with a tiny region, the window manager can't rule out the hit-test based on the first (fast) rectangle test. It has to go to the third (slower) region test.

Moral of the story: When using regional windows, try to keep the window rectangle reasonably close to the bounding box of the region itself. It helps the window manager decide more quickly which window a point belongs to.


Comments (22)
  1. asdf says:

    Is the speed hit here going to kernel mode to test the kernel REGION object (how about an article or blurb why it’s stored in kernel mode in the first place)? REGION does contain the bounding rectangle in it so I’d imagine the PtInRegion function tests against that first.

  2. Aarrgghh says:

    I’d think the complexity of the region would be a big consideration, too. Is the array of rectangles in RGNDATAHEADER the actual internal representation of the region?

  3. Reuben Harris says:

    I’ve done a bit of graphics driver work and IIRC window regions are internally CLIPOBJs (http://msdn.microsoft.com/library/default.asp?url=/library/en-us/graphics/hh/graphics/grstrcts_77zb.asp) … It’s a DDI-defined structure that usually boils down to a variable-length array of RECTs.

    A complex region such as a circle shape is implemented as one RECT per scanline, top-down.

  4. asdf says:

    Regions aren’t CLIPOBJs, that’s just an abstraction for the device driver just like the RGNDATAHEADER is for user mode programs. From what I remember in the win95, nt, or dx7 ddks (I don’t remember which one), the raw region data looked something like:

    struct Pair { long left, right; };

    struct ScanLine {

    long top, bottom;

    size_t count;

    Pair pairs[count];

    };

  5. Serge Wautier says:

    asdf, Reuben,

    > A complex region such as a circle shape is implemented as one RECT per scanline, top-down

    I’m totally unfamiliar with regions so I might be off-based here but this would mean that you can’t have a region that looks like a… hmm… "lying C" because it woud require 2 pairs per horizontal scan line.

    +–+ +–+

    + + + +

    + +—–+ +

    + +

    +———–+ (How does this show in proportional font ? :-( )

  6. Serge Wautier says:

    How does this show in proportional font ? :-(

    Very badly :-(

  7. Centaur says:

    Another moral would be to weigh all the pros and cons before making your windows nonrectangular. They slow down your application, they are hard to arrange with other windows, they need a custom non-client painting procedure and a custom non-client hit testing (so that the user can at least move your window), and, lastly, they are hard to make resizable.

    Luna windows are implemented using regions, right?

  8. mschaef says:

    "Luna windows are implemented using regions, right? "

    Yes (plus some other stuff, of course).

    A year or so ago, I was implementing a drawer-style window I wanted to be rectangular. In addition to doing my own non-client painting, I had to call SetWindowRgn (IIRC) to clear out the region and allow me to draw into the whole window rectangle. I don’t remember how SetWindowTheme affects this, but I’m pretty sure I ended up switching to using it to clear out the Luna theming on a per-window basis. One day, I want to explore using the visual styles API to draw the border too…

  9. Jack Mathews says:

    Raymond:

    Given the structure of the region data, wouldn’t an alpha blended layered window be much faster for hit testing than a region window? It should be, because it’s just a one pixel lookup into a bitmap. But I was curious if this was the case, and if maybe Microsoft may start evangelizing these in the future.

  10. Raymond Chen says:

    On the other hand, you can’t clip a DC to a bitmap.

  11. Jack Mathews says:

    Raymond: Yeah, but if you didn’t need that clipping to happen that way, would it be faster?

    Something off the top of my head would be something like the OSX dock. It would be simple to not worry about the DC clipping for an object such as this, and fast hit testing would be nice. I’m talking about an application designed around this alpha blending, not trying to hook onto others and change their window regions or anything.

  12. Raymond Chen says:

    I don’t know. That layering stuff is all newfangled.

  13. Raymond Chen says:

    asdf: Why is the region kept in kernel mode? Well, where would *you* keep the region data then?

  14. asdf says:

    Serge: anything you can draw in a black and white paint program can be represented as a region. The pair of rects thing is the winapi trying optimize regions while keeping them sorted top to bottom, left to right. This is a very good optimization compared to Mac regions (http://groups.google.com/groups?selm=1991Sep30.141944.5043%40waikato.ac.nz) because Windows draws windows from child to parent to reduce overdraw (and flicker because it doesn’t draw to an offscreen surface until longhorn) and the most common operations here are subtracting rectangular donut holes (until XP came along with its oversized round titlebars on by default).

    Raymond: how about in the user mode memory space of the process that created the region? It’s not that strange of a thing to do, DIBSECTIONs are stored there.

  15. Raymond Chen says:

    Think about it.

    If you kept the region data in user-space, then each time the mouse moves and USER needs to do a hit-test to decide which window should receive the message, it would have to context-switch to every process that has a regional window in order to do the region hit-test.

  16. js says:

    <i>If you kept the region data in user-space, then each time the mouse moves and USER needs to do a hit-test to decide which window should receive the message, it would have to context-switch to every process that has a regional window in order to do the region hit-test.</i>

    I’m not convinced every process would need to be visited if the region data were in shared memory.

  17. Raymond Chen says:

    Well if the memory is shared with kernel mode, then it’s in kernel mode again isn’t it?

  18. js says:

    I was thinking of shared with other processes, rather than shared with the kernel. In an architecture where it’s the job of kernel-space code to route events to processes, that kernel-space code does need access to data structures describing the windows and their shapes. But that activity could also be performed outside the kernel in a user-space process that used shared memory to coordinate window descriptions with application processes.

  19. Dan Maas says:

    Couldn’t the window manager process handle hit testing?

  20. Raymond Chen says:

    js/Dan: Yes, the window manager could be a user-mode process instead of hanging out in kernel mode. In fact, that’s how it was in Windows NT 3.1, but for performance reasons the window manager moved into kernel mode not long afterwards.

  21. asdf says:

    To keep beating a dead horse, there is a context switch from kernel to the window’s thread to handle the WM_NCHITTEST message anyway. But now that I really think about it, I wouldn’t want it in the process’ address space because then you can have the app take down the whole system.

    But then I look here in Feng Yuan and it says Windows does an optimization where if the region is just a single rect created with CreateRectRgn, it is stored in the process’ address space along with the pid.

  22. Raymond Chen says:

    WM_NCHITTEST doesn’t happen inside the hardware interrupt handler. That’s much later in the input-handling process.

Comments are closed.


*DISCLAIMER: I DO NOT OWN THIS CONTENT. If you are the owner and would like it removed, please contact me. The content herein is an archived reproduction of entries from Raymond Chen's "Old New Thing" Blog (most recent link is here). It may have slight formatting modifications for consistency and to improve readability.

WHY DID I DUPLICATE THIS CONTENT HERE? Let me first say this site has never had anything to sell and has never shown ads of any kind. I have nothing monetarily to gain by duplicating content here. Because I had made my own local copy of this content throughout the years, for ease of using tools like grep, I decided to put it online after I discovered some of the original content previously and publicly available, had disappeared approximately early to mid 2019. At the same time, I present the content in an easily accessible theme-agnostic way.

The information provided by Raymond's blog is, for all practical purposes, more authoritative on Windows Development than Microsoft's own MSDN documentation and should be considered supplemental reading to that documentation. The wealth of missing details provided by this blog that Microsoft could not or did not document about Windows over the years is vital enough, many would agree an online "backup" of these details is a necessary endeavor. Specifics include:

<-- Back to Old New Thing Archive Index