• The Old New Thing

    How to insert a large number of items into a treeview efficiently

    • 18 Comments

    Just a quick tip today.

    If you need to insert a large number of items into a treeview, like tens of thousands, then it's much more efficient to insert them "backwards". (I'm ignoring for now the usability question of having a treeview that large in the first place.) In other words, instead of

    for (i = 0; i < array.Count(); i++) {
     TVINSERTSTRUCT tvis;
     tvis.hParent = hParentNode;
     tvis.hInsertAfter = TVIF_LAST;
     tvis.item.mask = TVIF_TEXT;
     item.item.pszText = array[i].Text();
     TreeView_InsertItem(hwndTreeView, &tvis);
    }
    
    do it this way:
    for (i = array.Count() - 1; i >= 0; i--) {
     TVINSERTSTRUCT tvis;
     tvis.hParent = hParentNode;
     tvis.hInsertAfter = TVIF_FIRST;
     tvis.item.mask = TVIF_TEXT;
     item.item.pszText = array[i].Text();
     TreeView_InsertItem(hwndTreeView, &tvis);
    }
    

    Why is backwards-insertion faster?

    It has to do with the annoying hInsert­After parameter. To validate that the hInsert­After parameter is valid, the treeview needs to verify that the hInsert­After is a valid child of the hParent, and this is done by walking the parent's children looking for a match. The sooner you find the match, the faster the validation completes. (And if you pass TVI_LAST, then the treeview needs to walk to the end of the child list.)

    You'd think that you could verify the parent/child relationship by just doing a Tree­View_Get­Parent(hInsert­After), but that turns out not to be strict enough, because hInsert­After might itself not be a valid parameter. If hInsert­After is a bogus value, then you may crash when you try to read its Parent property. That's if you're lucky. If you're not lucky, then the random memory that hInsert­After points to might look just enough like a valid HTREEITEM that you end up inserting the new node after a completely bogus node, and now the treeview has become corrupted.

    Sure, you got the same problem if you passed a garbage HTREEITEM to Tree­View_Get­Parent, but in that case, it's just garbage in garbage out. Nothing gets corrupted; the application just gets a garbage result. But in the case of Tree­View_Insert­Item, the treeview is going to update its internal data structures based on the garbage you passed in, and that means that the treeview winds up corrupted.

    To ensure that the value passed in is valid, the treeview checks it against the list of valid values for hInsert­After. And therefore, you get better performance if the valid value you pass is the one that it checks first.

    (As it happens, a lot of programs pass garbage for hInsert­After, so this defensive validation step is absolutely necessary.)

    You might say that the treeview could have a one-off optimization for the special TVI_LAST value by remembering the last child so it can be located quickly. The question is whether the complexity of adding that optimization is worth the cost: Any tree rearranging function would have to update the cached value, and if you miss a spot, then the treeview ends up corrupted. That's a pretty high-risk optimization you're suggesting there.

    And think about it this way: You're worrying about a tree where a single node has tens of thousands of children, something which (I am no longer ignoring) is a horrible user interface. That's like a list box with tens of thousands of items, or a dialog box with tens of thousands of checkboxes. You'll probably want to consider a better way of presenting the information than in a tree view that goes on for hundreds of screens. The treeview isn't optimized for this case because you don't optimize for the case where somebody is mis-using your system.

  • The Old New Thing

    Book review: Advanced Windows Debugging (Mario Hewardt and Daniel Pravat)

    • 19 Comments

    Ever so often, somebody sends me a book, and most of the time I glance through it and say, "Eh."

    But not this time.

    Advanced Windows Debugging will make you the envy of your friends (if your friends are computer nerds). Even the section with the "Oh come on every moron knows this already" title Basic Debugger Tasks has stuff that I didn't know. Fortunately, you don't have to slog through the stuff you already do know in order to find it, because the nifty new debugger commands are set off in the snippets of debugger conversation. (And by debugger conversation, I mean output of a debugger based on the Windows debug engine, debuggers like ntsd, kd and windbg.)

    Once you get past the "basics", you still have loads more ahead of you. The book covers debugging scenarios like a corrupted heap, a deadlock, or 100% CPU usage, as well as debugging tasks, like following the trail of an LPC request from the client to the server, peeking at the token count of a semaphore, and reconstructing a partially-corrupted stack—and illustrates each investigation with both discussion and annotated debugger output. All the things that seasoned developers take for granted (because they have become instinctual after years of experience) are spelled out for you. Learn more from the book's web site, not unsurprisingly named advancedwindowsdebugging.com.

    I'm keeping this book on my shelf. You can borrow it, but I'm going to insist that you return it when you're done.

  • The Old New Thing

    If you need anything other than natural alignment, you have to ask for it

    • 27 Comments

    If you need variables to be aligned a particular way, you need to ask for it.

    Let's say I have the following code:

    void fn() 
    { 
     int a; 
     char b; 
     long c; 
     char d[10];
    } 
    

    What would the alignment of the starting adresses of a,b,c and d be?

    What would the alignment be if the memory were allocated on heap?

    If this alignment varies for different data types within the same translation unit, is there a way to force uniform alignment for all types?

    If you need a particular alignment, you have to ask for it. By default, all you can count on is that variables are aligned according to their natural requirements.

    First, of course, there is no guarantee that local variables even reside on the stack. The optimizer may very well decide that particular local variables can reside in registers, in which case it has no alignment at all!

    There are a few ways to force a particular alignment. The one that fits the C language standard is to use a union:

    union char_with_int_alignment {
     char ch;
     int Alignment;
    } u;
    

    Given this union, you can say u.ch to obtain a character whose alignment is suitable for an integer.

    The Visual C++ compiler supports a declaration specifier to override the default alignment of a variable.

    typedef struct __declspec(align(16)) _M128 {
        unsigned __int64 Low;
        __int64 High;
    } M128, *PM128;
    

    This structure consists of two eight-byte members. Without the __declspec(align(#)) directive, the alignment of this structure would be 8-byte, since that is the alignment of the members with the most restrictive alignment. (Both unsigned __int64 and __int64 are naturally 8-byte-aligned.) But with the directive, the aligment is expanded to 16 bytes, which is more restrictive than what the structure normally would be. This particular structure is declared with more restrictive alignment because it is intended to be use to hold 128-bit values that will be used by the 128-bit XMM registers.

    A third way to force alignment with the Visual C++ compiler is to use the #pragma pack(#) directive. (There is also a "push" variation of this pragma which remembers the previous ambient alignment, which can be restored by a "pop" directive. And the /Zp# directive allows you to specify this pragma from the compiler command line.) This directive specifies that members can be placed at alignments suitable for #-byte objects rather than their natural alignment requirements, if the natural alignment is more restrictive. For example, if you set the pack alignment to 2, then all objects that are bigger than two bytes will be aligned as if they were two-byte objects. This can cause 32-bit values and 64-bit values to become mis-aligned; it is assumed that you know what you're doing any can compensate accordingly.

    For example, consider this structure whose natural alignment has been altered:

    #pragma pack(1)
    struct misaligned_members {
     WORD w;
     DWORD dw;
     BYTE b;
    };
    

    Given this structure, you cannot pass the address of the dw member to a function that expects a pointer to a DWORD, since the ground rules for programming specify that all pointers must be aligned unless unaligned pointers are explicitly permitted.

    void ExpectsAlignedPointer(DWORD *pdw);
    void UnalignedPointerOkay(UNALIGNED DWORD *pdw);
    
    misaligned_members s;
    ExpectsAlignedPointer(&s.dw); // wrong
    UnalignedPointerOkay(&s.dw);  // okay
    

    What about the member w? Is it aligned or not? Well, it depends.

    If you allocate a single structure on the heap, then the w member is aligned, since heap allocations are always aligned in a manner suitable for any fundamental data type. (I vaguely recall some possible weirdness with 10-byte floating point values, but that's not relevant to the topic at hand.)

    misaligned_members *p = (misaligned_members)
        HeapAllocate(hheap, 0, sizeof(misaligned_members));
    

    Given this code fragment, the member p->w is aligned since the entire structure is suitably aligned, and therefore so too is w. If you allocated an array, however, things are different.

    misaligned_members *p = (misaligned_members)
        HeapAllocate(hheap, 0, 2*sizeof(misaligned_members));
    

    In this code fragment, p[1].w is not aligned because the entire misaligned_members structure is 2+4+1=7 bytes in size since the packing is set to 1. Therefore, the second structure begins at an unaligned offset relative to the start of the array.

    One final issue is the expectations for alignment when using header files provided by an outside component. If you are writing a header file that will be consumed by others, and you require special alignment, you need to say so explicitly in your header file, because you don't control the code that will be including your header file. Furthermore, if your header file changes any compiler settings, you need to restore them before your header file is complete. If you don't follow this rule, then you create the situation where a program stops working if a program changes the order in which it includes seemingly-unrelated header files.

    // this code works
    #include <foo.h>
    #include <bar.h>
    
    // this code doesn't
    #include <bar.h>
    #include <foo.h>
    

    The problem was that bar.h changed the default structure alignment and failed to return it to the original value before it was over. As a result, in the second case, the structure alignment for the foo.h header file got "infected" and no longer matched the structure alignment used by the foo library.

    You can imagine an analogous scenario where deleting a header file can cause a program to stop working.

    Therefore, if you're writing a header file that will be used by others, and you require nonstandard alignment for your structures, you should use this pattern to change the default alignment:

    #include <pshpack1.h> // change alignment to 1
    ... stuff that assumes byte packing ...
    #include <poppack.h>  // return to original alignment
    

    In this way, you "leave things the way you found them" and avoid the mysterious infection scenarios described above.

  • The Old New Thing

    Which windows appear in the Alt+Tab list?

    • 16 Comments

    Commenter Phil Quirk wants to know what the rules are for determining which windows appear in the Alt+Tab list. It's actually pretty simple although hardly anything you'd be able to guess on your own. Note: The details of this algorithm are an implementation detail. It can change at any time, so don't rely on it. In fact, it already changed with Flip and Flip3D; I'm just talking about the Classic Alt+Tab window here.

    For each visible window, walk up its owner chain until you find the root owner. Then walk back down the visible last active popup chain until you find a visible window. If you're back to where you're started, then put the window in the Alt+Tab list. In pseudo-code:

    BOOL IsAltTabWindow(HWND hwnd)
    {
     // Start at the root owner
     HWND hwndWalk = GetAncestor(hwnd, GA_ROOTOWNER);
    
     // See if we are the last active visible popup
     HWND hwndTry;
     while ((hwndTry = GetLastActivePopup(hwndWalk)) != hwndTry) {
      if (IsWindowVisible(hwndTry)) break;
      hwndWalk = hwndTry;
     }
     return hwndWalk == hwnd;
    }
    

    The purpose of this algorithm is to assign the most meaningful representative winow from each cluster of windows related by ownership. (Notice that the algorithm doesn't care whether the owned window is modal or non-modal.)

    At least that's the simple rule if you're not playing crazy window style games. The WS_EX_TOOLWINDOW and WS_EX_APPWINDOW extended styles were created so people can play games and put their window in the Alt+Tab list or take it out even if the simple rule would normally have decided otherwise. This is one of those "Okay, if you think you're smarter than Windows, here's your chance to prove it" options. Personally, I would avoid them since it makes your window behave differently from the rest of the windows in the system.

    A window with the WS_EX_TOOLWINDOW extended style is treated as if it weren't visible, even if it is. A window with the WS_EX_APPWINDOW extended style is treated as if it has no owner, even if it does.

    Once you start adding these extended styles, you enter the world of "I'm trying to work around the rules" and the result is typically even worse confusion than what you had without them.

    I'm not sure what the original commenter is getting at. The window hierarchy described in the suggestion (which doesn't make it so much a suggestion as it is a request for me to debug their problem) says that window C is modal on both windows A and B, which doesn't make sense to me, since a window has only one owner.

    The algorithm for choosing the Alt+Tab representative from each cluster of windows may not be the best, but it's what we have. I wouldn't be surprised if the details are tweaked from time to time. No, wait, let me rephrase that. I know that the details are tweaked from time to time. The spirit of the operation is preserved (to show the windows the user can switch to, using the most "natural" candidate for each cluster of windows), but the specific details may be fined-tuned as the concept of "naturalness" is refined.

  • The Old New Thing

    The magical healing properties of safe mode - bonus content

    • 35 Comments

    Okay, so you already read The healing properties of safe mode in TechNet Magazine. Here's the bonus content that was cut for space.

    First, the original title was "The Magical Healing Powers of Safe Mode," but it got trimmed for space reasons. (Ich bin mit der deutschen Übersetzung des ersten Satzes ein bisschen enttäuscht. Die eingeklammerte Phrase bittet um einen von den berühmten nur auf Deutsch gesehenen unverständlich langen adjektivischen Ausdrücken. Anstatt dessen hat der Übersetzer aufgegeben und die Phrase einfach weggelassen. Anderseits benutzt die deutsche Version den ursprünglichen Titel, so vielleicht ist es ja nicht so schlecht.)

    Useless Windows history: The feature now known as safe mode went through many other names before the final name was settled upon.

    • Fail-safe boot
    • FailSafe boot
    • Fail-safe mode
    • Safe mode
  • The Old New Thing

    Why was Pinball removed from Windows Vista?

    • 115 Comments

    Windows XP was the last client version of Windows to include the Pinball game that had been part of Windows since Windows 95. There is apparently speculation that this was done for legal reasons.

    No, that's not why.

    One of the things I did in Windows XP was port several millions of lines of code from 32-bit to 64-bit Windows so that we could ship Windows XP 64-bit Edition. But one of the programs that ran into trouble was Pinball. The 64-bit version of Pinball had a pretty nasty bug where the ball would simply pass through other objects like a ghost. In particular, when you started the game, the ball would be delivered to the launcher, and then it would slowly fall towards the bottom of the screen, through the plunger, and out the bottom of the table.

    Games tended to be really short.

    Two of us tried to debug the program to figure out what was going on, but given that this was code written several years earlier by an outside company, and that nobody at Microsoft ever understood how the code worked (much less still understood it), and that most of the code was completely uncommented, we simply couldn't figure out why the collision detector was not working. Heck, we couldn't even find the collision detector!

    We had several million lines of code still to port, so we couldn't afford to spend days studying the code trying to figure out what obscure floating point rounding error was causing collision detection to fail. We just made the executive decision right there to drop Pinball from the product.

    If it makes you feel better, I am saddened by this as much as you are. I really enjoyed playing that game. It was the location of the one Windows XP feature I am most proud of.

    Update: Hey everybody asking that the source code be released: The source code was licensed from another company. If you want the source code, you have to go ask them.

  • The Old New Thing

    If you say that you don't care about something, you shouldn't be upset that it contains garbage

    • 32 Comments

    There are many situations where you pass a structure to a function, and the function fills in the structure with information you request. In some cases, the function always fills in the entire structure (example: GlobalMemoryStatus). In other cases, you tell the function which bits of information you care about, to save the function the effort of computing something you weren't interested in anyway (example: TreeView_GetItem).

    In the latter case, if you say that you aren't interested in certain parts of the structure, and then you change your mind and start paying attention to them, don't be surprised if you find that there's nothing interesting there. After all, you said you didn't care.

    For example, if you call TreeView_GetItem and set the mask to TVIF_IMAGE | TVIF_PARAM, this means that you want the function to set the iImage and lParam members of the TVITEM structure and that you don't care about the rest. After the call returns, the values of those two members are defined, since you said that's what you wanted, and the remainder of the output fields are undefined. They might contain useful information, they might contain garbage, you're not supposed to care since you said that you didn't.

    Why might fields you said you didn't care about still contain information (correct or incorrect)? It might be that the value is so easy to compute that checking whether the value should be set takes more work than actually setting it! In such a case, the function might choose to set the value even if you didn't say that you needed it.

    On the other hand, the value might be an artifact of a translation layer: You pass a structure saying, "I'm interested in two out of the four members." The function in turn calls a lower lever function with a different structure, saying, "I'm interested in two out of the five members of this different structure." After the call returns, the middle-man function converts the lower-level structure to the higher-level structure. Sure, it may also "convert" stuff that was never asked for, but you said you weren't interested, so they just get garbage. In other words, the function you're calling might be defined like this:

    // The pinfo parameter points to this structure
    struct FOOINFO {
     DWORD dwInUse;
     DWORD dwAvailable;
     DWORD dwRequested;
     DWORD dwDenied;
    };
    
    // The dwMask parameter can be a combination of these values
    #define FOOINFO_INUSE     0x0001
    #define FOOINFO_AVAILABLE 0x0002
    #define FOOINFO_REQUESTED 0x0004
    #define FOOINFO_DENIED    0x0008
    
    BOOL GetFooInfo(FOOINFO *pinfo, DWORD dwMask);
    

    Now, the GetFooInfo function might just be a middle man that talks to another component to do the real work.

    // lowlevel.h
    
    struct LOWLEVELSTATS {
     DWORD dwUnitSize;
     DWORD dwUnitsInUse;
     DWORD dwUnitsAvailable;
     DWORD dwUnitsRequested;
     DWORD dwUnitsGranted;
     DWORD dwTotalRequests;
    };
    
    // The dwMask parameter can be a combination of these values
    #define LLSTATS_UNITSIZE  0x0001
    #define LLSTATS_INUSE     0x0002
    #define LLSTATS_AVAILABLE 0x0004
    #define LLSTATS_REQUESTED 0x0008
    #define LLSTATS_GRANTED   0x0020
    #define LLSTATS_REQUESTS  0x0040
    
    BOOL GetLowLevelStatistics(LOWLEVELSTATS *pstats, DWORD dwMask);
    

    The resulting GetFooInfo function merely translates the call from the application into a call to the GetLowLevelStatistics function:

    BOOL GetFooInfo(FOOINFO *pinfo, DWORD dwMask)
    {
     LOWLEVELSTATS stats;
     DWORD dwLowLevelMask = LLINFO_UNITSIZE;
    
     if (dwMask & FOOINFO_INUSE)
      dwLowLevelMask |= LLSTATS_INUSE;
     if (dwMask & FOOINFO_AVAILABLE)
      dwLowLevelMask |= LLSTATS_AVAILABLE;
     if (dwMask & FOOINFO_REQUESTED)
      dwLowLevelMask |= LLSTATS_REQUESTED;
     if (dwMask & FOOINFO_DENIED)
      dwLowLevelMask |= LLSTATS_REQUESTED | LLSTATS_GRANTED;
    
     if (!GetLowLevelStats(&info;stats, dwLowLevelMask))
      return FALSE;
    
     // Convert the LOWLEVELSTATS into a FOOINFO
     pinfo->dwInUse = stats.dwUnitSize * stats.dwUnitsInUse;
     pinfo->dwAvailable = stats.dwUnitSize * stats.dwUnitsAvailable;
     pinfo->dwRequested = stats.dwUnitSize * stats.dwUnitsRequested;
     pinfo->dwDenied = stats.dwUnitSize *
                       (stats.dwUnitsRequested - stats.dwUnitsGranted);
    
     return TRUE;
    }
    

    Notice that if you ask for just FOOINFO_DENIED, you still get the dwRequested as a side effect, since computing the number of requests that were denied entails obtaining the total number of requests. On the other hand, you also get garbage for dwInUse since the call to GetLowLevelStats didn't ask for LLSTATS_INUSE, but the code that converts the LOWLEVELSTATS to a FOOINFO doesn't know that and converts the uninitialized garbage. But since you said that you didn't care about the dwInUse member, you shouldn't be upset that it contains garbage.

    You now know enough to answer this person's question.

    (Note of course that I'm assuming we are not returning uninitialized garbage across a security boundary.)

  • The Old New Thing

    You just have to accept that the file system can change

    • 31 Comments

    A customer who is writing some sort of code library wants to know how they should implement a function that determines whether a file exists. The usual way of doing this is by calling GetFileAttributes, but what they've found is that sometimes GetFileAttributes will report that a file exists, but when they get around to accessing the file, they get the error ERROR_DELETE_PENDING.

    The lesser question is what ERROR_DELETE_PENDING means. It means that somebody opened the file with FILE_SHARE_DELETE sharing, meaning that they don't mind if somebody deletes the file while they have it open. If the file is indeed deleted, then it goes into "delete pending" mode, at which point the file deletion physically occurs when the last handle is closed. But while it's in the "delete pending" state, you can't do much with it. The file is in limbo.

    You just have to be prepared for this sort of thing to happen. In a pre-emptively multi-tasking operating system, the file system can change at any time. If you want to prevent something from changing in the file system, you have to open a handle that denies whatever operation you want to prevent from happening. (For example, you can prevent a file from being deleted by opening it and not specifying FILE_SHARE_DELETE in your sharing mode.)

    The customer wanted to know how their "Does the file exist?" library function should behave. Should it try to open the file to see if it is in delete-pending state? If so, what should the function return? Should it say that the file exists? That it doesn't exist? Should they have their function return one of three values (Exists, Doesn't Exist, and Is In Funky Delete State) instead of a boolean?

    The answer is that any work you do to try to protect users from this weird state is not going to solve the problem because the file system can change at any time. If a program calls "Does the file exist?" and the file does exist, you will return true, and then during the execution of your return statement, your thread gets pre-empted and somebody else comes in and puts the file into the delete-pending state. Now what? Your library didn't protect the program from anything. It can still get the delete-pending error.

    Trying to do something to avoid the delete-pending state doesn't accomplish anything since the file can get into that state after you returned to the caller saying "It's all clear." In one of my messages, I wrote that it's like fixing a race condition by writing

    // check several times to try to avoid race condition where
    // g_fReady is set before g_Value is set
    if (g_fReady && g_fReady && g_fReady && g_fReady && g_fReady &&
        g_fReady && g_fReady && g_fReady && g_fReady && g_fReady &&
        g_fReady && g_fReady && g_fReady) { return g_Value; }
    

    The compiler folks saw this message and got a good chuckle out of it. One of them facetiously suggested that they add code to the compiler to detect this coding style and not optimize it away.

  • The Old New Thing

    How do I get the reference count of a CLR object?

    • 41 Comments

    A customer asked the rather enigmatic question (with no context):

    Is there a way to get the reference count of an object in .Net?

    Thanks,
    Bob Smith
    Senior Developer
    Contoso

    The CLR does not maintain reference counts, so there is no reference count to "get". The garbage collector only cares about whether an object has zero references or at least one reference. It doesn't care if there is one, two, twelve, or five hundred—from the point of view of the garbage collector, one is as good as five hundred.

    The customer replied,

    I am aware of that, yet the mechanism is somehow implemented by the GC...

    What I want to know is whether at a certain point there is more then one variable pointing to the same object.

    As already noted, the GC does not implement the "count the number of references to this object" algorithm. It only implements the "Is it definitely safe to reclaim the memory for his object?" algorithm. A null garbage collector always answers "No." A tracing collector looks for references, but it only cares whether it found one, not how many it found.

    The discussion of "variables pointing to the same objects" is somewhat confused, because you can have references to an object from things other than variables. Parameters to a method contain references, the implicit this is also a reference, and partially-evaluated expressions also contain references. (During execution of the line string s = o.ToString();, at the point immediately after o.ToString() returns and before the result is assigned to s, the string has an active reference but it isn't stored in any variable.) And as we saw earlier, merely storing a reference in a variable doesn't prevent the object from being collected.

    It's clear that this person solved half of his problem, and just needs help with the other half, the half that doesn't make any sense. (I like how he immediately weakened his request from "I want the exact reference count" to "I want to know if it is greater than one." Because as we all know, the best way to solve a problem is to reduce it to an even harder problem.)

    Another person used some psychic powers to figure out what the real problem is:

    If I am reading properly into what you mean, you may want to check out the Weak­Reference class. This lets you determine whether an object has been collected. Note that you don't get access to a reference count; it's a zero/nonzero thing. If the Weak­Reference is empty, it means the object has been collected. You don't get a chance to act upon it (as you would if you were the last one holding a reference to it).

    The customer explained that he tried Weak­Reference, but it didn't work. (By withholding this information, the customer made the mistake of not saying what he already tried and why it didn't work.)

    Well this is exactly the problem: I instantiate an object and then create a Weak­Reference to it (global variable).

    Then at some point the object is released (set to null, disposed, erased from the face of the earth, you name it) yet if I check the Is­Alive property it still returns true.

    Only if I explicitly call to GC.Collect(0) or greater before the check it is disposed.

    The customer still hasn't let go of the concept of reference counting, since he says that the object is "released". In a garbage-collected system, object are not released; rather, you simply stop referencing them. And disposing of an object still maintains a reference; disposing just invokes the IDisposable.Dispose method.

    FileStream fs = new FileStream(fileName);
    using (fs) {
     ...
    }
    

    At the end of this code fragment, the File­Stream has been disposed, but there is still a reference to it in the fs variable. Mind you, that reference isn't very useful, since there isn't much you can do with a disposed object, Even if you rewrite the fragment as

    using (FileStream fs = new FileStream(fileName)) {
     ...
    }
    

    the variable fs still exists after the close-brace; it simply has gone out of scope (i.e., you can't access it any more). Scope is not the same as lifetime. Of course, the optimizer can step in and make the object eligible for collection once the value becomes inaccessible, but there is no requirement that this optimization be done.

    The fact that the Is­Alive property says true even after all known references have been destroyed is also no surprise. The environment does not check whether an object's last reference has been made inaccessible every time a reference changes. One of the major performance benefits of garbage collected systems comes from the de-amortization of object lifetime determination. Instead of maintaining lifetime information about an object continuously (spending a penny each time a reference is created or destroyed), it saves up those pennies and splurges on a few dollars every so often. The calculated risk (which usually pays off) is that the rate of penny-saving makes up for the occasional splurges.

    It does mean that between the splurges, the garbage collector does not know whether an object has outstanding references or not. It doesn't find out until it does a collection.

    The null garbage collector takes this approach to an extreme by simply hoarding pennies and never spending them. It saves a lot of money but consumes a lot of memory. The other extreme (common in unmanaged environments) is to spend the pennies as soon as possible. It spends a lot of money but reduces memory usage to the absolute minimum. The designers of a garbage collector work to find the right balance between these two extremes, saving money overall while still keeping memory usage at a reasonable level.

    The customer appears to have misinterpreted what the Is­Alive property means. The property doesn't say whether there are any references to the object. It says whether the object has been garbage collected. Since the garbage collector can run at any time, there is nothing meaningful you can conclude if Is­Alive returns true, since it can transition from alive to dead while you're talking about it. On the other hand, once it's dead, it stays dead; it is valid to take action when Is­Alive is false. (Note that there are two types of Weak­Reference; the difference is when they issue the death certificate.)

    The name Is­Alive for the property could be viewed as misleading if you just look at the property name without reading the accompanying documentation. Perhaps a more accurate (but much clumsier) name would have been Has­Not­Been­Collected. The theory is, presumably, that if you're using an advanced class like Weak­Reference, which works "at the GC level", you need to understand the GC.

    The behavior the customer is seeing is correct. The odds that the garbage collector has run between annihilating the last live reference and checking the Is­Alive property is pretty low, so when you ask whether the object has been collected, the answer will be No. Of course, forcing a collection will cause the garbage collector to run, and that's what does the collection and sets Is­Alive to false. Mind you, forcing the collection to take place messes up the careful penny-pinching the garbage collector has been performing. You forced it to pay for a collection before it had finished saving up for it, putting the garbage collector in debt. (Is there a garbage collector debt collector?) And the effect of a garbage collector going into debt is that your program runs slower than it would have if you had let the collector spend its money on its own terms.

    Note also that forcing a generation-zero collection does not guarantee that the object in question will be collected: It may have been promoted into a higher generation. (Generational garbage collection takes advantage of typical real-world object lifetime profiles by spending only fifty cents on a partial collection rather than a whole dollar on a full collection. As a rough guide, the cost of a collection is proportional to the number of live object scanned, so the most efficient collections are those which find mostly dead objects.) Forcing an early generation-zero collection messes up the careful balance between cheap-but-partial collections and expensive-and-thorough collections, causing objects to get promoted into higher generations before they really deserve it.

    Okay, that was a long discussion of a short email thread. Maybe tomorrow I'll do a better job of keeping things short.

    Bonus chatter: In addition to the Weak­Reference class, there is also the GC­Handle structure.

    Bonus reading: Maoni's WebLog goes into lots of detail on the internals of the CLR garbage collector. Doug Stewart created this handy index.

  • The Old New Thing

    If you're going to reformat source code, please don't do anything else at the same time

    • 36 Comments

    I spend a good amount of my time doing source code archaeology, and one thing that really muddles the historical record is people who start with a small source code change which turns into large-scale source code reformatting.

    I don't care how you format your source code. It's your source code. And your team might decide to change styles at some point. For example, your original style guide may have been designed for the classic version of the C language, and you want to switch to a style guide designed for C++ and its new // single-line comments. Your new style guide may choose to use spaces instead of tabs for indentation, or it may dictate that opening braces go on the next line rather than hanging out at the end of the previous line, or you may have a new convention for names of member variables. Maybe your XML style guidelines changed from using

    <element attribute1="value1" attribute2="value2" />
    
    to
    <element
             attribute1="value1"
             attribute2="value2"
    />
    

    Whatever your changes are, go nuts. All I ask is that you restrict them to "layout-only" check-ins. In other words, if you want to do some source code reformatting and change some code, please split it up into two check-ins, one that does the reformatting and the other that changes the code.

    Otherwise, I end up staring at a diff of 1500 changed lines of source code, 1498 of which are just reformatting, and 2 of which actually changed something. Finding those two lines is not fun.

    And the next time somebody is asked to do some code archaeology, say to determine exactly when a particular change in behavior occurred, or to give an assessment of how risky it would be to port a change, the person who is invited to undertake the investigation may not be me. It may very well be you.

Page 5 of 438 (4,377 items) «34567»